Entwicklung und Evaluierung eines parallelen

Transcrição

Entwicklung und Evaluierung
eines parallelen
Tableau-Reasoners für
Beschreibungslogiken
Felix Müller
DIPLOMARBEIT
eingereicht im
Studiengang
Informatik Diplom
an der Universität Ulm
im Juni 2007
Betreuer/Gutachter:
Prof. Dr. F. von Henke, Institut für künstliche Intelligenz
Dr. T. Liebig, Institut für künstliche Intelligenz
c Copyright 2007 Felix Müller
Alle Rechte vorbehalten
ii
Erklärung
Hiermit erkläre ich an Eides statt, dass ich die vorliegende Arbeit selbstständig und
ohne fremde Hilfe verfasst, andere als die angegebenen Quellen und Hilfsmittel nicht
benutzt und die aus anderen Quellen entnommenen Stellen als solche gekennzeichnet
habe. Die Arbeit wurde bisher noch keiner Prüfungsbehörde in gleicher oder ähnlicher
Form vorgelegt.
Ulm, am 17. Juni 2007
Felix Müller
iii
iv
ERKLÄRUNG
Zusammenfassung
Beschreibungslogiken finden immer mehr Anwendungen und werden auch als Grundlage einer semantischen Erweiterung des Internets (des sog. Semantic Webs) verwendet.
Schlussfolgern mit ausdrucksmächtigen Beschreibungslogiken ist dabei ein im komplexitätstheoretischen Sinn sehr schwieriges Problem. Die Tableaumethode bietet zwar
einen korrekten und vollständigen Algorithmus. Durch Quellen für inhärente Komplexität (zum Beispiel Disjunktionen) arbeiten naive Tableau-Algorithmen allerdings oft
ineffizient. Daher ist es von Interesse, nach Möglichkeiten für eine schnellere Verarbeitung zu suchen.
Parallelverarbeitung ist eine bisher wenig betrachtete Möglichkeit zur Beschleunigung des Tableau-Algorithmus’. In dieser Diplomarbeit werden daher Ansätze zur Parallelverarbeitung in Tableau-Algorithmen untersucht. Tableau-Algorithmen bieten dabei mehrere Ansatzpunkte für Parallelverarbeitung. Zum einen lässt sich entstehender
Nichtdeterminismus intuitiv auf eine parallele Verarbeitungsweise abbilden. Zum anderen lassen sich aber auch in deterministischen Konstrukten wie Konjunktionen einzelne
Teile gleichzeitig bearbeiten.
Parallelität in einem ansonsten naiven Tableau-Algorithmus jedoch ist wenig vielversprechend. Daher wurde besonderes Augenmerk auf Wechselwirkungen zwischen herkömmlichen Optimierungen und Parallelverarbeitung gelegt. Eine Reihe wichtiger Optimierungen wurde ausgewählt und auf ihre Realisierbarkeit in einem parallelen Reasoner
hin untersucht. Als Beschreibungslogik wurde hier ALCN Hr+ unter Berücksichtigung
von GCI-Axiomen und ABox-Wissen verwendet.
Basierend auf den angestellten Überlegungen wurde eine prototypische Implementierung erstellt. Dafür wurde die Architektur eines Parallelrechners mit gemeinsamem Speicher gewählt, auf deren Basis der Tableau-Algorithmus mittels des Workpool-Modells
realisiert wurde. Die Implementierung unterstützt ebenfalls ALCN Hr+ , GCI-Axiome
und ABox-Wissen. Um aussagekräftige Ergebnisse über den Erfolg einer parallelen Implementierung zu erhalten, wurde bei deren Entwicklung auf möglichst hohe Effizienz
wert gelegt. Aufgrund der technischen Ausrichtung dieser Arbeit wird die Implementierung detailliert beschrieben.
Die prototypische Implementierung konnte zeigen, dass sich durch die parallele Implementierung durchaus beachtliche Performancegewinne erzielen lassen. Anhand von
einigen Beispielen wird das Verhalten der Implementierung auf mehreren parallelen
Systemen gezeigt und mit anderen verfügbaren beschreibungslogischen Systemen verglichen. Es wird ein Überblick über andere Projekte gegeben, die Parallelverarbeitung
im Zusammenhang mit logischem Schlussfolgern einsetzen. Mehrere Möglichkeiten und
v
vi
ZUSAMMENFASSUNG
Ideen zur Verbesserung des Ansatzes werden aufgezeigt. Diese zielen auf eine bessere
Ausnutzung des vorhandenen Rechenkraftpotentials, Anwendung weiterer Optimierungen und die Erweiterung auf ausdrucksmächtigere Beschreibungslogiken ab.
Inhaltsverzeichnis
Erklärung
iii
Zusammenfassung
v
1 Einleitung
1.1 Einsatzgebiete von Beschreibungslogiken . . . . . . . . . . . . . . . . . .
1.2 Parallelverarbeitung und Beschreibungslogiken . . . . . . . . . . . . . . .
1.3 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
2
2
2 Grundlagen
2.1 Beschreibungslogiken . . . . . . . . . . . . . . . . .
2.1.1 Einführung . . . . . . . . . . . . . . . . . .
2.1.2 Beschreibungslogik in dieser Arbeit . . . . .
2.1.3 Inferenzdienste . . . . . . . . . . . . . . . .
2.1.4 Bestehende Inferenzsysteme . . . . . . . . .
2.2 Parallelverarbeitung . . . . . . . . . . . . . . . . .
2.2.1 Motivation . . . . . . . . . . . . . . . . . . .
2.2.2 Parallele Rechnerarchitekturen . . . . . . . .
2.2.3 Programmiermodelle . . . . . . . . . . . . .
2.2.4 Maße zur Beurteilung paralleler Programme
2.2.5 Grenzen paralleler Programme . . . . . . . .
3 Tableau-basiertes Schlussfolgern
3.1 Der Tableau-Algorithmus . . . . . . . . . . . .
3.2 Standardoptimierungen sequentieller Reasoner
3.2.1 Lexical Normalization . . . . . . . . .
3.2.2 Semantic Branching . . . . . . . . . .
3.2.3 Simplification . . . . . . . . . . . . . .
3.2.4 Dependency Directed Backtracking . .
3.2.5 Heuristic Guided Search . . . . . . . .
3.2.6 Caching . . . . . . . . . . . . . . . . .
3.2.7 GCI Absorption . . . . . . . . . . . . .
vii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
5
5
6
7
9
9
9
10
11
15
15
.
.
.
.
.
.
.
.
.
19
19
22
23
23
24
25
26
26
26
viii
INHALTSVERZEICHNIS
4 Parallelisierung
4.1 Designentscheidungen . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Ansatzpunkte für eine Parallelisierung . . . . . . . . .
4.1.2 Abwägungen bei der Entscheidung für ein oder mehrere
4.1.3 Entscheidung für ein Programmiermodell . . . . . . . .
4.2 Der resultierende Prototyp . . . . . . . . . . . . . . . . . . . .
4.2.1 Klassendesign . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Kontrollierbare Parallelität . . . . . . . . . . . . . . . .
4.3 Realisierung der Optimierungen . . . . . . . . . . . . . . . . .
4.3.1 Implementierte Optimierungen . . . . . . . . . . . . .
4.3.2 Nicht implementierte Optimierungen . . . . . . . . . .
. . . . .
. . . . .
Ansätze
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
29
29
29
31
31
32
32
35
40
41
43
5 Implementierung
5.1 Systembeschreibung . . . . . . . . . . .
5.2 Verwendete Bibliotheken . . . . . . . .
5.2.1 Xerces-c . . . . . . . . . . . . .
5.2.2 Boost.Threads . . . . . . . . . .
5.2.3 Speichermanager . . . . . . . .
5.3 Implementierung der Datenstrukturen .
5.3.1 Darstellung von TBoxen . . . .
5.3.2 Darstellung von ABoxen . . . .
5.3.3 Implementierung des Workpools
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
45
45
46
46
47
47
48
48
49
51
.
.
.
.
.
.
.
.
53
53
54
55
55
56
56
59
59
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Evaluierung
6.1 Verwendete Testbeispiele . . . . . . . . . . . . . . .
6.2 Verwendete Testumgebungen . . . . . . . . . . . . .
6.2.1 Verfügbarkeit benötigter Bibliotheken . . . .
6.3 Testmodi . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Einfluss der Anzahl der Worker-Threads . .
6.3.2 Vergleich mit anderen verfügbaren Systemen
6.3.3 Einfluss des Speichermanagers . . . . . . . .
6.4 Interpretation der Ergebnisse . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Verwandte Arbeiten
63
7.1 Parallele Verarbeitung von Beschreibungslogiken . . . . . . . . . . . . . . 63
7.2 Parallele Verarbeitung in anderen Logiken . . . . . . . . . . . . . . . . . 63
8 Bewertung und Ausblick
8.1 Kritik . . . . . . . . . . . . . . . . . . . . . . .
8.2 Weiterführende Arbeiten . . . . . . . . . . . . .
8.2.1 Verbesserungen der Architektur . . . . .
8.2.2 Implementierung weiterer Optimierungen
8.2.3 Erweiterungen des Sprachumfangs . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
65
65
66
67
68
70
INHALTSVERZEICHNIS
ix
A Testbeispiele
71
A.1 Testfall 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
A.2 Testfall 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
A.3 Testfall 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
B DIG-Unterstützung
75
C Inhalt der beigefügten CD
C.1 Ausarbeitung . . . . . .
C.2 UUPR . . . . . . . . . .
C.3 Testdaten . . . . . . . .
C.4 DIG 2.0 . . . . . . . . .
77
77
77
77
77
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
INHALTSVERZEICHNIS
Kapitel 1
Einleitung
Beschreibungslogiken sind Fragmente der Prädikatenlogik erster Ordnung mit einer formal definierten Semantik. Mit ihnen kann man konzeptuelles Wissen so ausdrücken, dass
Computer in der Lage sind, den Wahrheitsgehalt von mit ihnen formulierten Aussagen
zu überprüfen und implizites Wissen daraus abzuleiten.
1.1
Einsatzgebiete von Beschreibungslogiken
Zur Zeit werden Einsatzgebiete für Beschreibungslogiken im Internet erforscht. Das sogenannte Semantic Web soll das heute bestehende Internet um beschreibungslogische
Informationen erweitern, so das Inhalte für Computer nicht nur lesbar, sondern bis zu
einem gewissen Grad interpretierbar werden. So könnte es in Zukunft beispielsweise
Suchmaschinen ermöglicht werden, das Internet nicht auf Basis von Schlüsselwörtern,
sondern anhand von Begriffen mit formal definierter Semantik zu durchsuchen. Die
einfachste Anwendung der zusätzlichen Information wäre die Auflösung von Doppeldeutigkeiten aufgrund von Homonymen1 . Falls die im Internet oder im Intranet eines
Unternehmens vorhandene Information effizient durch Computer interpretiert werden
kann, sind dort noch weit komplexere Anwendungen möglich. Die anfallenden Beweise
könnten dabei in Zukunft sowohl zentrale Server als auch Heimcomputer führen.
Diese Art Anwendung liegt allerdings noch in weiter Ferne. Auf dem Weg dorthin müssen leistungsstarke Schlussfolgerungssysteme entwickelt werden, die in der Lage
sind, beschreibungslogische Probleme schnell zu lösen. Heutige Systeme arbeiten bereits
mit hochoptimierten Tableau-Algorithmen2 . Um noch Geschwindigkeitsgewinne gegenüber diesen Systemen erzielen zu können bietet sich der Einsatz von Parallelverarbeitung
an.
1
Das Wort Kiefer ist beispielsweise ein Homonym, da es sowohl einen Baum als auch einen Teil des
Schädels bezeichnet.
2
Tableau-Algorithmen werden in Kapitel 3 näher erläutert.
1
2
KAPITEL 1. EINLEITUNG
1.2
Parallelverarbeitung und Beschreibungslogiken
Parallelität ist in vielen Bereichen der Informationsverarbeitung von wachsender Bedeutung. Auch in derzeitigen Heimcomputern sind oft bereits Prozessoren mit bis zu vier
Prozessorkernen im Einsatz3 . In naher Zukunft könnte die Anzahl der Threads, die ein
Prozessor gleichzeitig bearbeiten kann, bei acht oder mehr liegen. Aus diesem Grund
ist Parallelverarbeitung nicht mehr nur für teure Supercomputer interessant, sondern
kann auch bei Heimcomputern angewandt werden.
Obwohl es bereits mehrfach Voraussagen gegeben hat, dass Parallelverarbeitung im
Zusammenhang mit der Verarbeitung von Beschreibungslogiken von Bedeutung werden
kann (siehe dazu etwa Abschnitt 8.4 in [Hor97] und [Vor03]), wurden bisher wenig Anstrengungen in dieser Richtung unternommen. Diese Arbeit untersucht daher, wie sich
die durch die Anwesenheit mehrerer Prozessoren gewonnene Rechenkraft dazu verwenden lässt, beschreibungslogisches Schlussfolgern zu beschleunigen.
1.3
Überblick
Diese Arbeit untergliedert sich wie folgt.
• In Kapitel 2 wird zuerst der logische Formalismus der Beschreibungslogiken definiert und erklärt. Es werden typische Inferenzdienste und bestehende Systeme
beschrieben. Danach wird eine Einführung in die Begriffe und Methoden der parallelen Verarbeitung gegeben. Dabei werden verschiedene Paradigmen und Programmiermethoden erklärt. Außerdem werden die Grenzen paralleler Programme
diskutiert und Maße zu ihrer Bewertung vorgestellt.
• Der eigentliche Tableau-Algorithmus für die Beschreibungslogik ALCN Hr+ wird
in Kapitel 3 beschrieben. Dieser Algorithmus bildet die Grundlage dieser Arbeit.
Es werden Vorgehen und Terminierungskriterien erläutert. Insbesondere werden
dabei einige wichtige gängige Optimierungen des Tableau-Algorithmus’ beschrieben. Die Optimierungen werden jeweils durch ein Beispiel motiviert, dass eine
Ineffizienz des naiven Algorithmus’ offenlegt. Anschließend wird eine Methode
vorgestellt, die die Effizienz in diesem Fall erhöht.
• Kapitel 4 beschreibt, wie die Idee der Parallelverarbeitung in einem Beschreibungslogikreasoner umgesetzt werden kann. Es werden verschiedene Ansatzpunkte
für Parallelverarbeitung erklärt und untersucht. Nach einer Entscheidung für einen
Ansatzpunkt wird das Design eines parallelen Reasoners entworfen. Dabei werden
Möglichkeiten zur Integration der in Kapitel 3 vorgestellten Optimierungen erörtert und erläutert, welche Optimierungen in die prototypische Implementierung
aufgenommen wurden.
• In Kapitel 5 wird die Umsetzung des Designs in die konkrete Implementierung
skizziert. Es werden verwendete Bibliotheken genannt und die Benutzung des
3
Der Prozessor ’Intel Quad Core Xeon E5310’ ist beispielsweise ein solcher Prozessor.
1.3. ÜBERBLICK
3
Prototyps erklärt. Bei der Beschreibung des Systems wird auf die verwendeten
Techniken zur Erreichung einer möglichst hohen Effizienz eingegangen.
• Kapitel 6 widmet sich der im Rahmen dieser Arbeit gewonnenen Testergebnisse.
Es werden die verwendeten Testkonfigurationen und -beispiele genannt. Anschließend folgt eine Interpretation der Ergebnisse.
• Auf mit dieser Arbeit verwandte Arbeiten wird in Kapitel 7 verwiesen.
• Schließlich zieht Kapitel 8 ein Fazit und verweist auf weiterführende Arbeiten, die
in dieser Arbeit nicht mehr berücksichtigt werden konnten. Dort finden Erweiterungen dieses Ansatzes auf andere Beschreibungslogiken ebenso Erwähnung wie
die Integration weiterer Optimierungen.
4
KAPITEL 1. EINLEITUNG
Kapitel 2
Grundlagen
Für den in dieser Arbeit entwickelten Ansatz werden einerseits Formalismen und Algorithmen der künstlichen Intelligenz und andererseits Algorithmen und Methoden der
Parallelverarbeitung verwendet. Dieses Kapitel teilt sich deshalb in zwei Teile. Der erste Teil widmet sich Syntax und Semantik der Familie der Beschreibungslogiken. Im
zweiten Teil werden die Grundlagen paralleler Verarbeitung vorgestellt.
2.1
2.1.1
Einführung
Die Familie der Beschreibungslogiken (engl. Description Logics, abgekürzt DL) umfasst
eine Reihe miteinander verwandter Sprachformalismen zur Repräsentation konzeptuellen Wissens. Beschreibungslogiken sind unterschiedlich große, typischerweise entscheidbare Teilmengen der Prädikatenlogik erster Ordnung. Jede Beschreibungslogik basiert
auf unären Prädikaten (sogenannten Konzepten) und binären Prädikaten (sogenannten Relationen oder Rollen). Außerdem können Konzepte zu Individuen instantiiert
werden, Beziehungen zwischen Individuen entsprechen Instantiierungen von Rollen. In
dieser Diplomarbeit gelten für die Benennung von Konzepten, Rollen und Individuen
folgende Konventionen und Notationen:
• A, B bezeichnen atomare Konzepte, d.h. Konzepte ohne komplexe Definition,
• C, D bezeichnen komplexe Konzeptausdrücke,
• r, s, t bezeichnen Rollen und
• a, b bezeichnen Individuen.
Eine Beschreibungslogik ist durch die Menge ihrer erlaubten Konstruktoren definiert, welche die Definition von komplexen Konzepten und Rollen erlauben. Die erlaubten Konstruktoren bestimmen auch die Komplexität der auf einer Beschreibungslogik
5
6
KAPITEL 2. GRUNDLAGEN
arbeitenden Schlussfolgerungsalgorithmen: je größer die Anzahl der Konstruktoren, desto höher der Sprachumfang und desto größer in der Regel die Komplexität. Zur Unterscheidung der Beschreibungslogiken hat sich ein (nicht konsistentes) Namensschema
etabliert, in dem Konstruktoren Buchstaben zugeordnet werden.
Ein großer Schritt in der Entwicklung von Beschreibungslogiken war die in [SSS91]
vorgestellte Beschreibungslogik ALC, mit der sich bereits relativ komplexe Sachverhalte
beschreiben lassen. Sie erlaubt die Definition von Konzepten aus atomaren Konzepten,
die mittels Konjunktion (geschrieben C u D), Disjunktion (C t D), existentieller Quantifikation (∃r.C), universeller Quantifikation (∀r.C) und Negation (¬C) miteinander
verknüpft werden. Außerdem ist in dieser Beschreibungslogik die Definition von atomaren Rollen erlaubt. Mithilfe der Axiome C v D (Konzeptinklusion) und C ≡ D
(Konzeptäquivalenz) lassen sich Zusammenhänge zwischen komplexen Konzepten herstellen. Ein solches Axiom nennt man auch General Concept Inclusion-Axiom oder kurz
GCI.
Eine Zusammenfassung zusammengehöriger Axiome wird Terminologie oder TBox
T genannt. Eine Sammlung von auf Basis einer TBox T erstellten Individuen heißt
ABox A. Das Paar (T , A) wird Ontologie genannt. Die Semantik der Konstrukte in
einer Ontologie ist durch eine Interpretation I = (∆I , ·I ) definiert, welche Konzepte C
auf Teilmengen des Objektuniversums ∆I , Relationen auf Teilmengen von ∆I ×∆I und
Individuen auf Elemente von ∆I abbildet. Eine Interpretation wird genau dann Modell
für T genannt, wenn C I ⊆ DI für alle Axiome C v D in T gilt (analog für C ≡ D).
2.1.2
Beschreibungslogik in dieser Arbeit
Der in dieser Diplomarbeit beschriebene Ansatz baut auf der ausdrucksmächtigeren
Beschreibungslogik ALCN Hr+ 1 auf, welche in [HM00] beschrieben wird. ALCN Hr+
erweitert ALC um weitere Konstruktoren. N erlaubt nichtqualifizierte Kardinalitätseinschränkungen, also ≥ n r und ≤ n r. Desweiteren werden einige Konstruktoren zur
näheren Beschreibung von Rollen eingeführt. H erlaubt die Definition von Rollenhierarchien mittels des Konstruktors r v s, durch r+ lassen sich Rollen mit r ∈ r+ als
transitive Rollen markieren. Es ist allerdings aufgrund der unklaren Semantik nicht erlaubt, Kardinalitäteinschränkungen auf transitiven Rollen zu fordern. Tabelle 2.1 fasst
Syntax und Semantik der Sprachmittel von ALCN Hr+ zusammen.
Weitere wichtige Begriffe im Umgang mit Beschreibungslogiken sind die Unique Name Assumption (UNA) und die Open World Assumption (OWA) [Lie07] [BCM+ 03].
Die Unique Name Assumption fordert, dass alle in einer ABox zur Benennung von Individuen verwendeten Bezeichner jeweils verschiedene Objekte referenzieren. Während
diese Annahme klassischerweise meistens getroffen wird, da sie das Schlußfolgern vereinfacht, so ist sie mit der zunehmenden Verbreitung von Beschreibungssprachen im stark
heterogenen Umfeld des Internets oft hinderlich. Hier kann es gewünscht sein, Wissen
aus verschiedenen Quellen in Einklang zu bringen. In dieser Arbeit jedoch wird von der
UNA ausgegangen.
1
Für die Beschreibungslogik ALC r+ hat sich auch der Buchstabe S eingebürgert [BCM+ 03], weshalb
man ALCN Hr+ auch als SHN bezeichnen könnte.
2.1. BESCHREIBUNGSLOGIKEN
Syntax
Konzepte allgemeinstes Konzept
>
speziellstes Konzept
⊥
atomares Konzept
A
Negation
¬C
Konjunktion
C uD
Disjunktion
C tD
existentielle Quantifikation ∃r.C
universelle Quantifikation
∀r.C
unqualifizierte Minimum≥nr
kardinalitätseinschränkung
unqualifizierte Maximum- ≤ n r
kardinalitätseinschränkung
Konzeptinklusion
CvD
Konzeptäquivalenz
C≡D
Rollen
atomare Rolle
r
Rolleninklusion
rvs
transitive Rolle
r ∈ r+
ABox
Konzeptinstantiierung
a:C
Rolleninstantiierung
(a, b) : r
7
Semantik
∆I
∅
AI ⊆ ∆I
∆I \ C I
C I ∩ DI
C I ∪ DI
{d|∃e.((d, e) ∈ rI ∧ e ∈ C I )}
{d|∀e.((d, e) ∈ rI ⇒ e ∈ C I )}
{d||{e|(d, e) ∈ rI }| ≥ n}
{d||{e|(d, e) ∈ rI }| ≤ n}
C I ⊆ DI
C I = DI
rI ⊆ ∆I × ∆I
r I ⊆ sI
rI = (rI )+
aI ∈ C I
(aI , bI ) ∈ rI
Tabelle 2.1: Konstruktoren der ALCN Hr+ -Beschreibungslogik
Die Open World Assumption lässt sich am besten durch ihr Gegenstück, die Closed
World Assumption, beschreiben. Die Closed World Assumption geht davon aus, dass
alle nicht explizit als wahr definierten Fakten falsch sind. Für die Aussage P eter ist
der Vater von Klara könnte man unter der Closed World Assumption folgern, dass
P eter genau ein Kind hat. Unter der Open World Assumption ist der Wahrheitswert
von nicht getroffenen Aussagen undefiniert. Es könnte also nur noch gesagt werden, dass
P eter mindestens ein Kind hat. Es gibt Beispiele, bei denen man nur unter Annahme
der Open World Assumption zu einem korrekten Ergebnis kommt, deshalb wird sie im
Kontext von Beschreibungslogiken meistens angewendet, so auch in dieser Arbeit.
Weiterführende und genaue Informationen über Beschreibungslogiken im Allgemeinen finden sich auch in [BCM+ 03].
2.1.3
Inferenzdienste
Zur Beantwortung beschreibungslogischer Fragestellungen müssen DL-Systeme Anfrageschnittstellen bereitstellen. Diese werden Inferenz- oder Schlussfolgerungsdienste genannt. Im folgenden werden einige wichtige Inferenzdienste vorgestellt. Diese sind miteinander verwandt, daher wird beschrieben, wie sich Anfragen an einen Inferenzdienst
auf Anfragen an andere Inferenzdienste zurückführen lassen.
8
(Un-)Erfüllbarkeit
Oft ist es interessant zu wissen, ob ein Konzept bereits in sich widersprüchlich ist,
oder ob ein Modell dafür existiert. Zur Überprüfung eines Konzeptes übergibt man
dem Inferenzdienst die Konzeptdefinition. Dieser antwortet dann mit wahr, falls das
Konzept erfüllbar ist, andernfalls mit falsch.
Subsumtion
Mit Subsumtion bezeichnet man die Allgemeinheitshierarchie zweier oder mehrerer Konzepte. Ein Konzept C wird von einem Konzept D subsumiert, falls für alle denkbaren
Interpretationen I = (∆I , ·I ) gilt, dass C I ⊆ DI ist. Man schreibt C v D, D heißt
hierbei der Subsumer, C der Subsumee. Subsumtionstests lassen sich anhand der Äquivalenz C v D ⇐⇒ C u ¬D ist unerfüllbar in Erfüllbarkeitstests umformen. Um einen
Unerfüllbarkeitstest in einen Subsumtionstest umzuwandeln stellt man eine Subsumtionsanfrage mit D v ⊥.
Instanztest
Die Schlussfolgerungsdienste Erfüllbarkeit und Subsumtion sind auf die TBox einer
Wissensbasis beschränkt. In einem DL-System, das auch die Verarbeitung von ABoxWissen erlaubt, sind auch Fragestellungen bezüglich der Individuen von Interesse. Mit
dem Instanztest lässt sich bezüglich einer ABox A feststellen, ob ein Individuum a
Instanz eines Konzepts C ist, also ob a : C konsistent ist. Mit Instanztests lassen
sich auch Subsumtionstests und Erfüllbarkeitstests realisieren, da gilt: C ist erfüllbar
⇐⇒ a : C ist konsistent, wobei a ein in A neu gewählter Individuenname ist.
ABox-Konsistenz
Für die Überprüfung einer ABox auf Konsistenz müssen die in der ABox vorgegebenen
Informationen über Individuen und ihre Beziehungen untereinander vervollständigt werden. Dabei wird versucht, alle geforderten Individuen und Beziehungen widerspruchsfrei
zu instantiieren. Ist dies möglich, so heißt die ABox konsistent. Durch die Erstellung
und Überprüfung einer ABox, die nur eine Zusicherung der Form a : C enthält, lässt sich
auch hiermit die Erfüllbarkeit von Konzepten überprüfen. Um bei konsistenter ABox
A zu erfahren, ob ein Individuum b ∈ A Instanz eines Konzepts C ist, kann folgende
Äquivalenz verwendet werden: {b : ¬C} ∪ A ist inkonsistent ⇐⇒ b : C ist konsistent.
Weitere Inferenzdienste
Es existieren viele weitere Inferenzdienste, wie zum Beispiel Disjunktheit und Äquivalenz zweier Konzepte oder Erstellung einer Konzept-Taxonomie. Da diese sich aber
durch oben beschriebene Inferenzdienste realisieren lassen werden sie hier nicht weiter
vorgestellt.
2.2. PARALLELVERARBEITUNG
2.1.4
9
Bestehende Inferenzsysteme
Bisherige Systeme, die genannte Inferenzdienste implementieren sind zum Beispiel Racer [HM03], FaCT++ [TH06] oder Pellet [SPG+ 06]. Alle diese Systeme setzen die
Tableau-Methode2 ein, die es erlaubt, korrekt und vollständig über ausdrucksstarke
Beschreibungslogiken zu schlussfolgern. Der Unterschied zwischen einem naiv implementierten Tableau-Algorithmus und diesen Systemen ist dabei sehr groß: Viele Probleme, für deren Lösung ein moderner Tableau-Reasoner nicht viel Zeit braucht, wären aufgrund der hohen Laufzeit einer naiven Implementierung praktisch nicht lösbar.
Moderne Systeme erreichen eine hohe Performance durch den Einsatz von ausgefeilten Optimierungsmethoden. Unterschiede zwischen diesen Systemen gibt es allerdings
dennoch. FaCT++, das in C++ implementiert ist, zeichnet sich dabei durch eine effiziente Implementierung der internen Konzeptdarstellung und geschickte syntaktische
Optimierungen aus. Racer ist in Lisp implementiert und verwendet viele semantische
Optimierungen, um überflüssige Arbeit zu vermeiden. In [Lie06] konnten Racer, im Gegensatz zu FaCT++ und Pellet, keine falschen Ergebnisse nachgewiesen werden. Pellet
ist ein stark forschungsorientierter Prototyp, an dem viele experimentelle Erweiterungen
getestet werden. Pellet ist in Java implementiert. Ein Vergleich dieser drei und anderer
Systeme bezüglich Leistung, Sprachumfang und Korrektheit findet sich in [Lie06]. Die
wichtigsten Optimierungen des Tableau-Algorithmus werden in 3.2 vorgestellt.
2.2
2.2.1
Parallelverarbeitung
Motivation
Parallelverarbeitung erlaubt es, den bei einem Programm anfallenden Rechenaufwand
auf mehrere Recheneinheiten zu verteilen. Auf diese Art und Weise lässt sich die Ausführungszeit von rechenintensiven Programmen reduzieren. Analog lässt sich Parallelverarbeitung auch dazu verwenden in der selben Zeit größere Probleme zu lösen als es
mit einem sequentiellen Programm möglich wäre.
Im Folgenden werden kurz einige Konzepte und Begriffe der parallelen Programmierung vorgestellt. Zuerst werden ausgewählte Rechnerarchitekturen beschrieben, die
sich für Parallelverarbeitung eignen, anschließend werden von der konkreten Rechnerarchitektur abstrahierende Programmiermodelle vorgestellt. Außerdem werden die zur
Erstellung paralleler Programme benötigten Sprachmittel sowie Maße für die Bewertung paralleler Programme angegeben. Für ein tieferes Verständnis dieser Thematik sei
der interessierte Leser auf [GGK03] verwiesen. Die Beschreibungen der vorgestellten
parallelen Programmiermodelle baut auf der Darstellung in [Str05] auf.
2
Der Tableau-Algorithmus für ALCN Hr+ wird in Kapitel 3 beschrieben.
10
2.2.2
Parallele Rechnerarchitekturen
Parallelrechner mit gemeinsamem Speicher
Parallelrechner mit gemeinsamem Speicher werden symmetrische Multiprozessoren (engl.
Symmetric Multi Processor, kurz SMP ) genannt. In einem SMP ist jeder Prozessor per
Bus an den gesamten Hauptspeicher angebunden, es gibt einen globalen Addressraum
für mehrere Prozesse oder Threads. Jeder Thread oder Prozess verfügt über ein eigenes
Stacksegment, kann aber auf den gemeinsamen Speicher zugreifen. Die Kommunikation
untereinander findet über gemeinsame Variablen statt, auf die der Zugriff dann über
atomare Operationen (realisiert zum Beispiel mit Semaphoren oder Monitoren) synchronisiert werden muss. Bei symmetrischen Multiprozessoren ist die Zugriffszeit aller
Prozessoren auf alle Speichermodule (nahezu) identisch, daher wird diese Architektur
auch manchmal als UMA (Uniform Memory Access) bezeichnet. Das größte Problem
bei SMPs ist die Erreichung der Cache-Kohärenz, da sich Kopien einer Speicherstelle in
den lokalen Caches mehrerer Prozessoren befinden können. Wenn dann die tatsächliche
Speicherstelle überschrieben wird, führt dies zu unkorrekten Cacheinhalten.
Parallelrechner mit verteiltem Speicher
Parallele Systeme mit verteiltem Speicher heißen DMC (engl. Distributed Memory Computer ). Bei diesen Systemen kann jeder Prozessor nur auf seinen eigenen lokalen Addressraum zugreifen. Die Kopplung der Prozessoren findet dann nicht über gemeinsamen
Speicher, sondern über Eingabe-/Ausgabeschnittstellen und ein Verbindungsnetzwerk
statt. Prozessoren können untereinander durch den Austausch von Nachrichten (message passing) kommunizieren. Der Vorteil dieser Architektur gegenüber der eines SMPs ist
die bessere Skalierbarkeit bezüglich Kosten und Leistung: Um die Leistungsfähigkeit zu
erhöhen, muss lediglich eine weitere Prozessor-/Hauptspeichereinheit in das Netzwerk
eingebunden werden.
Konvergenz dieser Architekturen
Die Unterschiede beider Ansätze lassen sich durch Simulation einer anderen Umgebung überbrücken. Auf einem SMP lässt sich Nachrichtenaustausch durch Übergabe
von Zeigern auf Speicherbereiche simulieren. Auf DMCs kann man aufbauend auf der
tatsächlichen Architektur einen logischen globalen Addressraum bilden. Die Zugriffszeiten auf den Speicher anderer Knoten sind dabei natürlich höher als auf lokalen Speicher.
Cache-Kohärenz muss auch hier durch ein spezielles Netzwerkprotokoll gewährleistet
werden. Bei einer solchen Architektur spricht man von ccNUMA (für cache coherent
Non-Uniform Memory Access). Bei heutigen Systemen werden die Unterschiede zwischen SMPs und DMCs bezüglich Latenzzeiten und Bandbreite immer geringer.
Parallelität in modernen Prozessoren
Auch innerhalb von modernen Prozessoren ist auf verschiedene Art und Weise Parallelität realisiert. Moderne Prozessoren haben zumeist SIMD-Einheiten (Single Instructi-
11
on Multiple Data), die es erlauben, eine Instruktion auf mehreren Werten gleichzeitig
auszuführen. Sie sind in der Lage, durch Pipelining und mehrfach vorhandene Funktionseinheiten mehrere Instruktionen parallel auszuführen.
In diesem Kontext besonders interessant sind Multikern-Prozessoren, in denen auf
einem Chip mehrere Prozessorkerne untergebracht sind. Zusätzlich können in jedem
Prozessorkern noch die Registersätze repliziert werden, so dass dort mehrere Threads
quasi gleichzeitig laufen können, da für den Threadwechsel nur auf die Verwendung eines
anderen Registersatzes gewechselt werden muss. Ein so aufgebauter Prozessor verhält
sich wie ein SMP.
Vektorrechner
Mit Vektorrechner bezeichnet man eine Architektur, die es erlaubt, auf großen Datenfeldern parallel Operationen durchzuführen. Diese Architektur ist besonders für Anwendungen geeignet, bei denen eher einfache Operationen auf große Datenmengen angewendet werden müssen, wie zum Beispiel Wettersimulationen oder die Anwendung eines
Filters auf Bilddaten. Da dies bei beschreibungslogischen Beweisen allerdings nicht der
Fall ist und sich diese Architektur somit für die betrachtete Anwendung nicht anbietet,
sei sie hier nur der Vollständigkeit halber erwähnt.
2.2.3
Programmiermodelle
Um von der konkreten Architektur eines parallelen Systems abstrahieren zu können,
definiert man sich eine Sicht auf eine abstrakte parallele Maschine, das sogenannte Programmiermodell. Es enthält neben einer Beschreibung der parallelen Maschine Sprachprimitive, mit denen man Parallelität in einem Programm modellieren kann. Dies erlaubt die Beschreibung von Programmabläufen, ohne sich auf eine konkrete Programmiersprache oder eine Bibliothek zur Parallelverarbeitung festlegen zu müssen. Die Entscheidung für ein Modell ist dabei dem Designer des Programms überlassen und richtet
sich nach seinen Erwartungen, auf welcher/welchen Plattform/-en das Programm zum
Einsatz kommt.
Gemeinsamer Speicher
Auf einer abstrakten parallelen Maschine mit gemeinsamem Speicher teilen sich mehrere
Prozesse oder Threads einen Addressraum. Dadurch wird eine explizite Synchronisation
beim Zugriff auf gemeinsame Variablen erforderlich. Die folgenden Sprachkonstrukte
erlauben sowohl die Beschreibung von Nebenläufigkeit als auch der dadurch notwendigen
Synchronisation:
• Das con-Konstrukt drückt Nebenläufigkeit von Instruktionen aus. Es gibt zwei
Varianten des con-Konstrukts. Die erste führt unterschiedliche Anweisungen (d.h.
Einzelanweisungen, Anweisungsblöcke oder Funktionsaufrufe) aus:
con {
S1;
12
S2;
S3;
}
Das zweite ähnelt einer parallel ausgeführten for-Schleife, tatsächlich wird jede
Anweisung S(i) mit i indiziert:
con (i = 0; i < P; i++) {
S(i);
}
Beide Varianten terminieren erst, wenn alle enthaltenen Anweisungen abgearbeitet
sind. Mit diesem Konstrukt lässt sich zum Beispiel eine parallele Matrixmultiplikation zweier Matrizen A und B zu C folgendermaßen ausdrücken:
con (i = 0; i < n; i++) {
con (j = 0; j < n; j++) {
C[i][j] = 0;
for (k = 0; k < n; k++)
C[i][j] += A[i][k] * B[k][j];
}
}
• Um Zugriffskonflikte auf eine gemeinsame Variable a zu vermeiden muss sichergestellt sein, dass nur ein Thread gleichzeitig eine bestimmte Anweisungsfolge (zum
Beispiel a = a + 5;) ausführt. Andernfalls könnte es in diesem Beispiel sein, dass
zwei Threads gleichzeitig den Wert der Variable a lesen, ihn um 5 inkrementieren
und jeweils diese Summe als Ergebnis zurückschreiben. Dies hätte zur Folge, dass
a nicht, wie intendiert, um insgesamt 10, sondern nur um 5 erhöht wird. Eine
solche Anweisungsfolge nennt man auch kritischen Abschnitt. Um korrekt ausgeführt zu werden darf ein kritischer Abschnitt nur unter gegenseitigem Ausschluss
(engl. mutual exclusion) als atomare Operation ausgeführt werden. Um das zu
gewährleisten gibt es das Primitiv atomic:
atomic {
S1;
S2;
S3;
}
Die Anweisungen S1 bis S3 werden so als eine Einheit von einem Thread ausgeführt
und kein anderer Thread kann in diesen Abschnitt eintreten bevor der aktuell
ausführende Thread ihn nicht verlassen hat. Ein nicht-synchronisierter Zugriff
auf eine gemeinsame Variable kann zu schwer zurückzuverfolgenden und nicht
reproduzierbaren Programmfehlern führen. Einen solchen Fehler nennt man auch
race condition.
13
• Oft muss ein Thread auf eine bestimmte Bedingung warten, zum Beispiel bis
benötigte Daten von einem anderen Thread bereitgestellt wurden. Dafür gibt es
das await-Konstrukt, wovon zwei Varianten existieren. In der ersten Variante
wartet der Thread, der auf die Anweisung trifft, bis die angegebene Bedingung
erfüllt ist und fährt dann mit der Verarbeitung fort:
await (Bedingung);
Manchmal ist es notwendig, direkt nachdem die Bedingung wahr geworden ist einige Anweisungen auszuführen, um sicher zu gehen, dass die Bedingung nicht durch
Interaktion eines anderen Threads bereits wieder falsch geworden ist. Hierfür gibt
es die zweite Variante von await:
await (Bedingung) {
S1;
S2;
S3;
}
Bei dieser Variante wird auf die Erfüllung der Bedingung Bedingung gewartet und
danach werden atomar (wie bei atomic) die Anweisungen S1 bis S3 ausgeführt.
Bei der Verwendung beider Varianten muss man darauf achten, dass es zur Laufzeit nicht zu Situationen kommt, in denen zwei oder mehr Threads wechselseitig
aufeinander warten. In diesem Fall kann das Programm nicht mehr terminieren,
man spricht von einem deadlock.
Mithilfe der vorgestellten Primitive lässt sich zum Beispiel das Erzeuger-VerbraucherProblem folgendermaßen lösen:
main() {
con {
erzeuger();
verbraucher();
}
}
erzeuger() {
while (true) {
x = erzeugeElement();
await (p < puffer.size()) {
puffer[p] = x;
p = p + 1;
}
}
}
14
verbraucher() {
while (true) {
await (p > 0) {
y = puffer[p];
p = p - 1;
}
verbraucheElement(y);
}
}
Nachrichtenaustausch
Bei einer abstrakten parallelen Maschine, bei der Prozesse keinen gemeinsamen Speicher
haben, müssen diese explizites message passing zur Kommunikation verwenden. Dieser
Nachrichtenaustausch findet über Primitive zum Senden und Empfangen von Nachrichten statt. Um unterscheiden zu können, welche Sende- und Empfangsbefehle in den
unterschiedlichen Prozessen zusammengehören, gibt es Kanäle, über die die Nachrichten geschickt werden. Folgende Sprachmittel werden für den Nachrichtenaustausch über
Kanäle also benötigt:
• Für die Deklaration eines Kanals wird die Anweisung channel ch(tag, type)
verwendet. Sie deklariert einen Kanal ch, über den Objekte des Typs type versendet werden können. Der Parameter tag (beispielsweise eine Ganzzahl) erlaubt
die Identifikation von zusammengehörigen Kanälen in verschiedenen Prozessen.
Für die Kommunikation zwischen zwei Prozessen muss dann in beiden Prozessen
ein Kanal mit dem selben tag deklariert sein.
• Mittels des Befehls send(ch, x) kann ein Objekt x über den Kanal ch verschickt
werden. Dieser Befehl blockiert nicht. Daten werden, falls nötig, im System zwischengespeichert.
• Empfangen werden Daten mittels receive(ch, y). Diese Anweisung blockiert
solange keine Daten über den Kanal verfügbar sind. Die Verarbeitung wird erst
fortgesetzt, wenn das Objekt y verfügbar ist. Auch hier muss darauf geachtet
werden, dass keine deadlocks entstehen.
Obiges Erzeuger-Verbraucher-Problem lässt sich hier also mit zwei Prozessen, die ein
unterschiedliches Programm ausführen, so bearbeiten:
• Erzeuger:
channel ch(ERZEUGER_VERBRAUCHER, T);
while (true) {
T x = erzeugeElement();
send(ch, x);
}
15
• Verbraucher:
channel ch(ERZEUGER_VERBRAUCHER, T);
T y;
while (true) {
receive(ch, y);
verbraucheElement(y);
}
2.2.4
Maße zur Beurteilung paralleler Programme
Um die Leistung paralleler Programme beurteilen zu können ist es wichtig, geeignete Bewertungsmaße für die Leistung zu definieren. Dazu sei hier die Anzahl der verwendeten
Prozessoren mit p, die Problemgröße mit n und die Programmlaufzeit mit t bezeichnet. Zwei Maße sind besonders von Interesse: Das erste ist der sogenannte speed-up
Sp , mit dem man den Geschwindigkeitsgewinn einer parallelen Implementierung auf p
Prozessoren gegenüber einer sequentiellen Referenzimplementierung misst:
Sp (n) =
t1 (n)
≤p
tp (n)
Dieses Maß ist geeignet um den absoluten Performancegewinn einer parallelen Implementierung zu ermitteln, allerdings trägt es der Anzahl der eingesetzten Prozessoren
keine Rechnung. Hierzu gibt es das Maß der Effizienz Ep ,
Ep (n) =
Sp (n)
t1 (n)
=
≤ 1,
p
p · tp (n)
das den Grad der Ausnutzung der zusätzlichen Rechenkraft angibt.
Für diese Bewertungmaße gelten jedoch einige Einschränkungen. Oft ist es schwierig
eine gute sequentielle Referenzimplementierung zu finden. Selbst wenn eine solche Referenzimplementierung zur Verfügung steht, kann die Aussagekraft der Maße dadurch
eingeschränkt sein, dass sich der sequentielle Algorithmus stark vom parallelen Algorithmus unterscheidet. Die Werte von Sp und Ep sind außerdem oft stark abhängig von
n und vom Verhältnis von n zu p [Str05].
2.2.5
Grenzen paralleler Programme
Bei der Performance parallelisierter Programme sind oft nicht die erhofften Ergebnisse
zu beobachten: Die parallelen Programme sind nicht oder nur wenig schneller als ihr
sequentielles Gegenstück. Das kann mehrere Gründe haben, wovon einige hier beschrieben werden. Soll ein Programm erfolgreich parallelisiert werden, so gilt es, diese Quellen
der Ineffizienz zu kennen und sie wenn möglich zu umgehen.
16
Granularität der Parallelisierung
Eine Gefahr bei der Erstellung paralleler Programme liegt darin, zu übersehen, dass
auch die Erreichung von Parallelität in einem Programm Rechenzeit benötigt. Es ist
also mit einem gewissen Overhead verbunden, ein Programm zu parallelisieren, weshalb
genau bedacht werden muss, welche Programmteile parallel bearbeitet werden sollen
und welche nicht. Man spricht von der Granularität der Parallelisierung: Je feiner die
Granularität, desto höher der mögliche Parallelitätsgrad, desto höher allerdings auch
der Overhead, gemessen an der Gesamtlaufzeit des Programms. Als Beispiel sei hier
ein paralleler Sortieralgorithmus angeführt: Wenn dieser so stark parallelisiert wird,
dass jeder Vergleich zwischen zwei Zahlen von einem eigenen Thread (oder Prozess)
ausgeführt wird, so steht der Aufwand für die Verwaltung der Threads in einem sehr
ungünstigen Verhältnis zum Aufwand der Berechnung, die ein Thread ausführt.
Eine grobe Granularität steht allerdings leider oft im Widerspruch zu einer anderen
wünschenswerten Eigenschaft paralleler Programme, der gleichmäßigen Auslastung aller
vorhandenen Prozessoren. Das Bestreben, eine möglichst gleichmäßige Auslastung zu
erreichen nennt man load balancing. Wird ein Programm in viele Teile unterteilt, können
diese besser so auf die Prozessoren verteilt werden, dass diese ständig ausgelastet sind.
Es gilt also einen Kompromiss zwischen beiden Zielen zu erreichen. Das Idealziel
ist dabei die gröbste Granularität, bei der alle Prozessoren über die ganze Laufzeit des
Programms ausgelastet sind. Dann wird so wenig Zeit wie möglich auf Synchronisation verwendet, während gleichzeitig keine Prozessorleistung ungenutzt bleibt. Dieses
Idealziel ist in der Praxis schwer zu erreichen.
Pseudoparallelität
Durch fehlerhaftes Design kann es dazu kommen, dass ein Programm zwar die Primitive zur parallelen Verarbeitung verwendet, tatsächlich aber immer nur ein Thread
rechnet, während die anderen auf diesen warten. Ein solches Programm ist im entsprechenden Programmabschnitt unweigerlich langsamer als ein sequentielles Programm,
da die eigentliche Berechnung sequentiell ausgeführt wird, der Overhead durch die Parallelisierung aber dennoch anfällt. Problematisch wird diese Art der Ineffizienz dann,
wenn sie nur manchmal oder in bestimmten Programmteilen auftritt und dadurch nicht
entdeckt wird.
Performancelimitierende Faktoren
Bei manchen Programmen schränken bereits ohne eine parallele Implementierung andere Faktoren die Geschwindigkeit ein. Es ist zum Beispiel wenig sinnvoll ein Programm
parallel zu implementieren, dass Bilddaten eines Scanners in einen Puffer schreibt, wenn
die Geschwindigkeit des Scanners bereits bei einer sequentiellen Implementierung der
limitierende Faktor ist. Es kann auch weniger offensichtliche Gründe geben, die die
Programmperformance mindern. In modernen Rechnern ist der Zugriff auf den Hauptspeicher oft um Größenordnungen langsamer als der auf Register oder Caches. Ein
Programm, das starken Gebrauch des Hauptspeichers macht, kann so eventuell bei ei-
17
ner Implementierung auf einer parallelen Maschine mit gemeinsamem Speicher nicht
von der zusätzlichen Rechenkraft profitieren.
18
Kapitel 3
Tableau-basiertes Schlussfolgern mit
Wie in Abschnitt 2.1.2 bereits erwähnt, bildet die ALCN Hr+ -Beschreibungslogik die
Grundlage für diese Arbeit. In diesem Kapitel wird nun das Tableauverfahren für diese
Beschreibungslogik erläutert. Da der Beweiser auch mit ABox-Wissen umgehen können soll, wird bei der Beschreibung davon ausgegangen, dass der Inferenzdienst ABoxKonsistenz implementiert werden soll. Nach einem kleinen Beispiel werden zuerst einige
wichtige Begriffe und Annahmen eingeführt, danach folgt ein prägnante Darstellung des
eigentlichen Algorithmus’. Eine detaillierte Beschreibung dieses Algorithmus’ einschließlich eines Beweises seiner Vollständigkeit und Korrektheit ist in [HM00] nachzulesen.
Anschließend werden gängige Optimierungen des naiven Algorithmus vorgestellt,
indem auf auftretende Ineffizienzen und Lösungsmöglichkeiten eingegangen wird.
3.1
Der Tableau-Algorithmus
Ein Tableau ist ein gerichteter, azyklischer Graph, bei dem die Knoten mit Individuennamen und ihren Konzepten und die Kanten mit Rollenbezeichnern beschriftet sind.
Abbildung 3.1 zeigt ein vollständiges Tableau für den Ausdruck A u ∃r.C u ∃r.D u ∀r.E,
der durch das Individuum a instantiiert wird. Der Tableau-Algorithmus versucht durch
Anwendung von Erweiterungsregeln aus dem initialen Ausdruck A u ∃r.C u ∃r.D u ∀r.E
a : A ⊓ ∃r.C ⊓ ∃r.D ⊓ ∀r.E
r
r
b:C ⊓E
c:D⊓E
Abbildung 3.1: Ein Beispiel für ein Tableau
19
20
KAPITEL 3. TABLEAU-BASIERTES SCHLUSSFOLGERN
das Tableau zu vervollständigen. Ein Tableau heißt vollständig, wenn keine Erweiterungsregeln mehr anwendbar sind. Falls nach einer Regelanwendung ein Widerspruch
gefunden wird, ist der Ausdruck unerfüllbar. Falls der Algorithmus an einen Punkt gelangt, an dem keine Regeln mehr anwendbar sind (wie in diesem Beispiel der Fall), ohne
dass ein Widerspruch gefunden wurde, so ist der Ausdruck erfüllbar, da ein vollständiges
Tableau ein Modell darstellt.
Um die Beschreibung des Tableau-Algorithmus’ zu vereinfachen und zu verkürzen
wird im folgenden davon ausgegangen, dass alle vorkommenden Konzepte in Negationsnormalform (NNF) vorliegen. Die Negationsnormalform zeichnet sich dadurch aus,
dass Negationen nur vor atomaren Konzepten stehen dürfen. Jedes Konzept lässt sich
(mit in der Länge der Eingabe linearem Aufwand) durch entsprechende Anwendung
folgender Äquivalenzen in NNF überführen:
• ¬> ≡ ⊥
• ¬⊥ ≡ >
• ¬(C u D) ≡ ¬C t ¬D
• ¬(C t D) ≡ ¬C u ¬D
• ¬∀r.C ≡ ∃r.¬C
• ¬∃r.C ≡ ∀r.¬C
• ¬ ≤ n r ≡≥ (n + 1) r
• ¬ ≥ n r ≡≤ (n − 1) r
Der Verarbeitungsprozess wird mit den Individuen begonnen, die bereits vor dem
Start des Beweises in A enthalten waren. Diese Menge wird mit Oo bezeichnet. Für
den Umgang mit diesen Individuen gelten im Vergleich zu den während des Beweises
generierten Individuen On leicht abgeänderte Regeln. Maßgebend dafür, welche Regeln
auf ein Individuum angewendet werden können, sind alle Konzepte, die ein Individuum instantiiert. Die Menge aller instantiierten Konzepte heißt auch concept set eines
Individuums. Das concept set eines Individuums a in einer ABox A ist also definiert als
.
σ(A, a) = {>} ∪ {C|a : C ∈ A}.
Das Tableau wird nun unter Anwendung der Tableauregeln aufgebaut, welche in Tabelle 3.1 zusammengefasst sind. Die Regeln werden dabei nicht in beliebiger Reihenfolge
angewendet. Um Regeln möglichst selten anwenden zu müssen und die Vollständigkeit
und Korrektheit garantieren zu können gilt eine strikte Reihenfolge. Diese bezieht sich
sowohl darauf, welche Individuen zuerst bearbeitet werden, als auch auf die Reihenfolge
der Anwendung innerhalb der Bearbeitung eines Individuums:
• Individuen werden in der Reihenfolge ihrer Erzeugung bearbeitet. Individuen aus
Oo werden dabei als untereinander gleichwertig behandelt. Damit wird sichergestellt, dass das concept set eines neu erzeugten Individuums vollständig aufgebaut ist, bevor es bearbeitet wird. Mit Ausnahme der Individuen in Oo wird ein
3.1. DER TABLEAU-ALGORITHMUS
Regel
Die Konjunktionsregel
Die Disjunktionsregel (nichtdeterministisch)
Die Rollenfüllerrestriktionsregel
Die transitive
Rollenfüllerrestriktionsregel
Die globale
Konzeptrestriktionsregel
Die Rollenfüllerexistenzregel
(generierend)
Die Minimumkardinalitätsregel
(generierend)
Die Maximumkardinalitätsregel
(nichtdeterministisch)
Bedingung(en)
1. a : C u D ∈ A, und
2. {a : C, a : D} 6⊆ A
1. a : C t D ∈ A, und
2. {a : C, a : D} ∩ A = ∅
1. a : ∀r.C ∈ A, und
2. ∃b ∈ O, s ∈ r↓ :
(a, b) : s ∈ A, und
3. b : C 6∈ A
1. a : ∀r.C ∈ A, und
2. ∃b ∈ O, t ∈ r↓ , t ∈ r+ ,
s ∈ t↓ : (a, b) : s ∈ A, und
3. b : ∀t.C 6∈ A
1. ∀x.x : C ∈ A, und
2. ∃a ∈ O : a : C 6∈ A
1. a : ∃r.C ∈ A, und
2. 6 ∃ blockierendes Individuum
c ∈ On für a, und
3. 6 ∃b ∈ O, s ∈ r↓ :
{(a, b) : s, b : C} ⊆ A
1. a : ∃ ≥ n r ∈ A
2. 6 ∃ blockierendes Individuum
c ∈ On für a, und
3. 6 ∃b1 , . . . , bn ∈ O, s1 , . . . , sn ∈ r↓ :
{(ak , bk ) : sk |k = 1..n}
.
∪{bi =
6 bj |i, j = 1..n, i 6= j} ⊆ A
1. a : ∃ ≤ n r ∈ A
2. ∃b1 , . . . , bm ∈ O, s1 , . . . , sm ∈ r↓ :
{(a, b1 ) : s1 , . . . , (a, bm ) : sm } ⊆ A,
mit m > n, und
3. ∃bi , bj ∈ {b1 , . . . , bm } :
.
i 6= j, bi =
6 bj 6∈ A
21
Behandlung
A0 = A ∪ {a : C, a : D}
A0 = A ∪ {a : C} oder
A0 = A ∪ {a : D}
A0 = A ∪ {b : C}
A0 = A ∪ {b : ∀t.C}
A0 = A ∪ {a : C}
A0 = A ∪ {(a, b) : r, b : C},
wobei b 6∈ A
A0 = A
∪{(a, bk ) : r|k = 1..n}
.
∪{bi =
6 bj |i, j = 1..n, i 6= j},
wobei b1 , . . . , bn 6∈ A
A0 = A[bi /bj ], d.h.
jedes Vorkommen von bi
in A durch bj ersetzen
Tabelle 3.1: Tableauregeln für die ALCN Hr+ Beschreibungslogik
22
Individuum immer zuerst vollständig bearbeitet, bevor das nächste Individuum
betrachtet wird.
• Innerhalb eines Individuums werden zuerst alle nichtgenerierenden Regeln angewendet (siehe dazu Tabelle 3.1). Danach wird eine generierende Regel angewendet
bevor wiederum alle nichtgenerierenden Regel neu angewendet werden. Da Individuen in Oo gleichwertig behandelt werden, werden hier zuerst alle nichtgenerierenden Regeln auf alle Individuen aus Oo angewendet bevor eine generierende
Regel angewendet wird.
Um alle benötigten Informationen korrekt bearbeiten zu können wird eine ABox
vor dem Start des eigentlichen Beweises leicht modifiziert. GCIs der zugrundeliegenden
TBox werden in die ABox mit aufgenommen, indem man für jedes GCI-Axiom der
Form C v D die Zusicherung ∀x.x : (¬C t D) (lies: für alle Individuen x gilt entweder ¬C oder D). Für alle Individuen in der ursprünglichen ABox gilt außerdem die
Unique Name Assumption, das heißt ihre Verschiedenheit wird vorausgesetzt. Um dies
repräsentieren zu können werden Verschiedenheitszusicherungen eingeführt und zu A
.
hinzugefügt: A0 = A ∪ {ai =
6 aj |ai , aj ∈ Oo , i, j ∈ 1..n, i 6= j}.
Die Bearbeitung wird gestoppt, falls durch die Anwendung einer Regel ein primitiver
Widerspruch (oder clash) entsteht. Ein clash tritt dann auf, falls für ein Individuum a
entweder
• ⊥ ∈ σ(A, a),
• {C, ¬C} ⊆ σ(A, a), für ein beliebiges Konzept C, oder
• {∃ ≥ n r, ∃ ≤ m r} ⊆ σ(A, a) für n > m
gilt.
Um die Terminierung des Algorithmus’ auch für zyklische Definitionen, zum Beispiel M ensch v ∃hatElternteil.M ensch, zu garantieren, muss eine Technik namens
blocking zum Einsatz kommen. Blocking bezeichnet den Abbruch der Bearbeitung eines
Individuums für bestimmte Fälle. Für die hier verwendete Beschreibungslogik genügt
diese einfache Form von blocking: Die Anwendung einer generierenden Regel auf ein
Individuum b wird dann geblockt, falls in A bereits ein Individuum a existiert, dessen
concept set eine Obermenge des concept sets von b ist, also σ(A, a) ⊇ σ(A, b) gilt. a
heißt dann das blocking individual. Für ausdruckmächtigere Beschreibungslogiken muss
jedoch auf eine kompliziertere Form von blocking zurückgegriffen werden.
3.2
Standardoptimierungen sequentieller Reasoner
Zwar ist der im vorigen Abschnitt beschriebene Algorithmus korrekt und vollständig,
er arbeitet jedoch in vielen Fällen ineffizient. In diesem Abschnitt sind in Kürze einige
Optimierungen für Tableau-basierte Reasoner beschrieben, die in verfügbaren beschreibungslogischen Systemen wie zum Beispiel FaCT [Hor97] und DLP [PS98] implemen-
3.2. STANDARDOPTIMIERUNGEN SEQUENTIELLER REASONER
23
tiert sind1 . Diese Optimierungen machen oft den Unterschied zwischen der Lösung eines
Problems in Sekundenbruchteilen und einer Dauer von mehreren Minuten aus.
Es wird jeweils ein Szenario beschrieben, in dem der Tableau-Algorithmus ineffizient arbeitet, und eine Methode, die diese Ineffizienz beseitigt oder verringert. Für eine
detailliertere Beschreibung sowieso Messungen zur Effektivität der einzelnen Optimierungen wird der interessierte Leser auf [HT00] für Absorption bzw. [HPS99] für die
anderen Optimierungen verwiesen.
3.2.1
Lexical Normalization
Für die Beschreibung obigen Tableau-Algorithmus’ wurde unterstellt, dass die bearbeiteten Konzepte in Negationsnormalform vorliegen. Das vereinfacht die Beschreibung
des Algorithmus’, erschwert jedoch die frühe Erkennung von clashes. Man betrachte
folgenden widersprüchlichen Ausdruck:
∃r.(C u D) u ∀r.¬C
Zur Evaluierung generiert der Algorithmus einen r-Nachfolger. Falls C ein atomares
Konzept ist, enthält der r-Nachfolger sowohl C als auch ¬C und der Widerspruch wird
erkannt. Falls C ein zusammengesetzter Ausdruck ist, liegt ¬C in Negationsnormalform
vor. Alle Negationen, die letztlich zur Erkennung eines Widerspruchs führen, stehen
dann direkt vor atomaren Konzepten. Daher wird der Widerspruch nicht sofort erkannt
und die Evaluierung benötigt bei großem C unnötig Rechenzeit.
Um diese Ineffizienz zu beseitigen werden rekursiv alle komplexen Ausdrücke in eine
lexikalische Normalform gebracht, die nur atomare Konzepte, Konjunktionen, Allquantifizierungen und ihre Negationen erlaubt. Zusätzlich werden Konjunktionen wie Mengen
behandelt, so dass die Reihenfolge der Konjunkte keine Rolle bei der Erkennung von
Äquivalenzen spielt. Man verwendet dabei die Notation u{C, D} für C u D. Die Normalform obigen Beispiels wäre also u{¬∀r.¬(u{C, D}), ∀r.¬C}. Das Konzept C liegt
dabei ebenfalls in Normalform vor, weshalb die Widersprüchlichkeit des r-Nachfolgers
im Beweis schnell erkannt werden kann. Tabelle 3.2 zeigt die Normalisierungsregeln.
Weiterhin helfen die in Tabelle 3.3 beschriebenen Vereinfachungsregeln offensichtliche (Un-)Erfüllbarkeit oder Redundanzen zu erkennen.
3.2.2
Semantic Branching
In herkömmlichen Tableau-Algorithmen wird zur Überprüfung der Erfüllbarkeit von
disjunktiv verknüpften Konzepten eine einfache syntaktische Methode verwendet. Um
u{(C tD1 ), (C tD2 )} zu evaluieren wird zuerst die Alternative u{C, (C tD2 )} und dann
u{D1 , (C t D2 )} überprüft. Sei nun C ein unerfüllbares Konzept. Die erste Alternative
führt bei der Überprüfung von C zum Widerspruch, weshalb die zweite Alternative betrachtet wird. Hierbei wird u{D1 , (C t D2 )} zu u{D1 , C} und u{D1 , D2 } aufgefaltet,
was zur Folge hat, dass C wiederum auf Erfüllbarkeit überprüft werden muss. Falls die
1
Eine Ausnahme ist hier GCI Absorption, da diese Optimierung erst nach FaCT und DLP entwickelt
wurde.
24
Ausdruck
⊥
C tD
∃r.C
¬¬C
C uD
u{u{C1 , . . . , Cn }, . . . }
u{C}
Normalform
¬>
¬(¬C u ¬D)
¬(∀r.¬C)
C
u{C, D}
u{C1 , . . . , Cn , . . . }
C
Tabelle 3.2: Normalisierungsregeln
Ausdruck
∀r.>
u{>, C, . . . }
u{¬>, . . . }
u{C, ¬C, . . . }
Vereinfachung
>
u{C, . . . }
¬>
¬>
Tabelle 3.3: Vereinfachungsregeln
Erfüllbarkeit von C ein komplexes Unterproblem ist, führt dies zu erheblichen Performanceeinbußen.
Durch eine semantic branching genannte Technik, die zuerst in der Verarbeitung
der Aussagenlogik angewendet wurde, kann diese Ineffizienz verringert werden. Anstatt
eine Disjunktion u{C1 , . . . , Cn } auszuwählen und n Alternativen zu überprüfen, wird
ein Disjunktionsglied Ci , i ∈ {1, . . . , n} ausgewählt. Anschließend werden 2 Alternativen
durch Hinzufügen von Ci bzw. ¬Ci erzeugt und überprüft. Diese beiden Alternativen
sind disjunkt, daher ist eine Ineffizienz wie in oben genanntem Beispiel ausgeschlossen.
Falls Ci ein großes Konzept ist könnte die Negation ¬Ci einen großen Suchraum zur
Folge haben, in der Praxis jedoch scheint dieses Problem selten aufzutreten.
3.2.3
Simplification
Durch Vereinfachung von Konzeptausdrücken lässt sich die Anzahl der nichtdeterministischen Verzweigungen verringern. Mithilfe der als BCP (Boolean constraint propagation) bekannten Vereinfachungsregel
¬C1 , . . . , ¬Cn , C1 t · · · t Cn t D
D
werden Ausdrücke wie beispielsweise
u{(C t (D1 u D2 )), (¬D1 t ¬D2 ), ¬C}
25
schrittweise vereinfacht. Da der Ausdruck ¬C enthält und C in einer Disjunktion vorkommt führt die erste Anwendung der Regel auf
u{D1 , D2 , (¬D1 t ¬D2 )}.
Ein weiterer Anwendungsschritt führt zu
u{D2 , ¬D2 }
und fördert dadurch ohne nichtdeterministische Verzweigung die Widersprüchlichkeit
des Ausdrucks zutage.
3.2.4
Dependency Directed Backtracking
Es gibt noch weitere Möglichkeiten, die Anzahl unnötiger nichtdeterministischer Verzweigungen zu reduzieren. Gegeben sei dazu folgender - wiederum widersprüchliche Ausdruck:
u{(C1 t D1 ), . . . , (Cn t Dn ), ∃r.(C u D), ∀r.¬C}.
Wenn blocking eingesetzt wird um die Terminierung zu gewährleisten werden generierende Regeln (in diesem Fall auf ∃r.(C u D) ) erst angewendet, wenn keine anderen
Regeln mehr anwendbar sind. Das heißt, dass in diesem Beispiel nach n Verzweigungsschritten ein Knoten entsteht, der {∃r.(C u D), ∀r.¬C} und keine Disjunktionen mehr
enthält. Der dann erzeugte r-Nachfolger enthält sowohl C als auch ¬C und damit einen
Widerspruch. Durch backtracking werden überflüssigerweise nach und nach alle insgesamt 2n Alternativen, die ebenfalls auf den selben Widerspruch führen, getestet.
Dieses Problem lässt sich durch intelligenteres backtracking beheben. Dabei wird
mit jedem Konzeptausdruck eine Menge von Verzweigungspunkten assoziiert, von denen
er abhängt. Ein Ausdruck C hängt von einem Verzweigungspunkt ab, wenn entweder
C durch den Verzweigungspunkt hinzugefügt wurde oder C durch z.B. eine Vereinfachungsregel aus D hervorging und D von dem Verzweigungspunkt abhängt. Bei einem
clash werden dann die Abhängigkeitsmengen der am clash beteiligten Konzepte vereinigt, im Beispiel also die Abhängigkeitsmengen der Ausdrücke C und ¬C.
Mithilfe dieser Menge wird dann das backtracking gesteuert. Jeder dabei getroffene
Verzweigungspunkt wird darauf überprüft, ob er in der Abhängigkeitsmenge enthalten
ist, falls nicht, kann die entsprechende andere Alternative ohne weiteres verworfen werden: Da die den Widerspruch erzeugenden Ausdrücke in ihr ebenfalls enthalten sind,
kann sie nur zum gleichen Widerspruch führen. In obigem Beispiel hängen C bzw. ¬C
von keinem der n Verzweigungspunkte ab, das heißt, der Algorithmus kann direkt nachdem der Widerspruch durch u{C, ¬C} das erste Mal erkannt wird unerfüllbar zurückgeben. In diesem Fall wird durch dependency directed backtracking also die überflüssige
Evaluierung von 2n − 1 r-Nachfolgern verhindert.
26
3.2.5
Heuristic Guided Search
Durch heuristische Methoden kann die Größe des Suchbaums weiter verkleinert werden. Eine Möglichkeit stellt die in Kombination mit semantic branching in Algorithmen
für aussagenlogische Beweise oft verwendete MOMS-Heuristik (maximum occurences,
minimum size) dar. Dabei wird bei der nichtdeterministischen Verzweigung ein Disjunktionsglied ausgewählt, das in möglichst vielen Disjunktionen vorkommt, die möglichst
wenig andere Disjunktionsglieder enthalten. Auf diese Weise wird versucht, den Effekt
der BCP-Regel zu maximieren. Leider ist in beschreibungslogischen Problemen im Gegensatz zu aussagenlogischen Problemen die Anzahl der unterschiedlichen Konzeptausdrücke groß im Vergleich zur Anzahl der Disjunktionen, so dass die MOMS-Heuristik für
beschreibungslogische Ausdrücke meist keine befriedigend starke Aussage hinsichtlich
einer guten Verzweigungsreihenfolge trifft.
Eine andere Auswahlstrategie versucht den Effekt von dependency directed backtracking zu maximieren. Hierzu wird bei der Verzweigung versucht, eine Disjunktion
auszuwählen, in deren Abhängigkeitsmenge keiner der letzten Verzweigungspunkte vorkommen. Dieselbe Technik kann auch bei der Bestimmung der Expansionsreihenfolge
für Rollennachfolger eingesetzt werden.
3.2.6
Caching
Bei Erfüllbarkeitschecks werden unter Umständen viele ähnliche Knoten erzeugt. Zum
Beispiel enthalten alle durch den Ausdruck ∀r.C erzeugten r-Nachfolger das Konzept
C. Dadurch kann es sein, dass viel Rechenzeit darauf verwendet wird, Nachfolger zu
evaluieren, deren Konzeptmengen eigentlich identisch sind. Der Aufwand pro Nachfolger
kann sehr groß sein, wenn zum Beispiel in den Nachfolgern wiederum Nachfolger erzeugt
werden.
Dieser Rechenaufwand kann vermindert werden, wenn einmal evaluierte Knoten
(bzw. die durch sie beschriebenen Konzepte) und ihr Erfüllbarkeitsstatus in einer Tabelle gespeichert werden. Ein Problem des cachings ist allerdings der nicht unerhebliche
zusätzliche Speicheraufwand.
3.2.7
GCI Absorption
Die Verwendung von GCIs erhöht die Komplexität des Schlussfolgerns dramatisch. GCIAxiome stellen für alle Individuen geltende Einschränkungen dar. Jedes GCI-Axiom
C v D fügt deshalb die Disjunktion D t ¬C zu jedem Individuum dazu. Das resultiert
also beispielsweise bei 10 GCI-Axiomen und 10 Individuen darin, dass 2100 Möglichkeiten
betrachtet werden müssen. Es ist in manchen Fällen allerdings möglich, GCI-Axiome in
primitive Konzeptdefinitionen umzuwandeln, nämlich wenn atomare Konzepte in einem
GCI-Axiom enthalten sind. Sei A ein atomares Konzept. Dann kann zum Beispiel das
Axiom A u C v D äquivalent in die einfache Konzeptdefinition A v D u ¬C umgeformt
werden. Dieses Verfahren nennt man Absorption. Das neue Axiom ist kein GCI-Axiom
mehr und muss daher nicht mehr bei der Bearbeitung eines jeden Individuums beachtet
werden.
27
Unter Anwesenheit mehrerer zusammenhängender GCIs gibt es oft mehrere Möglichkeiten, GCI-Axiome zu absorbieren. Die verschiedenen Möglichkeiten können sich
sehr stark in ihrer Qualität (d.h. in ihrem Effekt auf die Beweiskomplexität) unterscheiden. GCI Absorption kann bereits in einem Vorverarbeitungsschritt erledigt werden.
Wie in [HT00] dargestellt, lässt sich Reasoning unter Anwesenheit von GCIs durch die
Verwendung von Absorption sehr stark vereinfachen.
28
Kapitel 4
Parallelisierung des
Schlussfolgerungsprozesses
Dieses Kapitel widmet sich der Anwendung der in Abschnitt 2.2 vorgestellten Grundlagen der Parallelverarbeitung auf ein tableaubasiertes beschreibungslogisches Beweissystem. Das System soll den in Kapitel 3 beschriebenen Sprachumfang ALCN Hr+ unterstützen. Insbesondere soll es auch Möglichkeiten zu ABox-Reasoning und zur von
Verwendung GCIs bieten. Die Implementierung des Inferenzdienstes ABox-Konsistenz
genügt dabei laut Abschnitt 2.1.3, um auch Inferenzdienste wie Subsumtion oder (Un-)
Erfüllbarkeit abzudecken.
Es werden Designentscheidungen erläutert und alternative Ansätze diskutiert. Besonderes Augenmerk wird auf die in Abschnitt 3.2 beschriebenen Optimierungen des
Tableau-Algorithmus’ gelegt: Es ist anzunehmen, dass der Geschwindigkeitsvorsprung
einer parallelen Implementierung ohne diese Optimierungen gegenüber einer optimierten sequentiellen Implementierung stark zusammenschmilzt, in vielen Fällen wäre die
sequentielle Implementierung vermutlich sogar schneller.
4.1
Designentscheidungen
In diesem Abschnitt werden die Designentscheidungen motiviert, die beim Entwurf eines
parallelen Reasoners anfallen. Es werden Punkte im Reasoning-Prozess identifiziert,
die sich für eine Parallelisierung potentiell eignen. Anschließend wird ein passendes
Programmiermodell ausgewählt.
4.1.1
Ansatzpunkte für eine Parallelisierung
Im Verlauf eines Tableaubeweises gibt es viele Stellen, an denen mehrere Alternativen betrachtet werden müssen, oder verschiedene, in sich abgeschlossene Teilbeweise
geführt werden müssen, die dann zu einem Ergebnis zusammengefasst werden. Diese Alternativen und Teilbeweise lassen sich unabhängig voneinander und daher auch
parallel bearbeiten. Da der Verlauf des Tableaubeweises durch die in Individuen auftretenden Konzepte bestimmt ist, lassen sich Stellen, an denen Parallelität möglich ist,
29
30
KAPITEL 4. PARALLELISIERUNG
durch deren Konstruktoren identifizieren. Im Folgenden wird für einige Konstruktoren
beschrieben, wie ihre Abarbeitung parallel vonstatten gehen kann.
Disjunktion
Man betrachte folgendes Individuum: a : C1 tC2 . Um feststellen zu können, ob a Instanz
von C1 t C2 ist, muss überprüft werden, ob a : C1 oder a : C2 gilt. Angenommen beide
Teilbeweise sind sehr aufwendig und führen zum Ergebnis, dass a : Ci inkonsistent ist.
Ein paralleler Beweiser könnte dann die Teilbeweise parallel führen und damit schneller
zum Ergebnis kommen. Mehr noch: Sei C2 ein erfüllbares Konzept, dessen Erfüllbarkeit
leicht nachzuweisen ist. Damit wäre auch a : C1 t C2 konsistent. Bei einer sequentiellen
Bearbeitung könnte es nun sein, dass für den Beweis für a : C1 viel Zeit investiert wird,
obwohl durch eine Betrachtung von a : C2 die Erfüllbarkeit schnell zutage gefördert
werden könnte. Eine Implementierung, die die Teilbeweise gleichzeitig führt, könnte
in diesem Fall den noch laufenden anderen Teilbeweis abbrechen, da sein Ergebnis
ohnehin irrelevant für das Gesamtergebnis ist. Bei semantic branching wird nur a : C2
durch a : ¬C1 ersetzt, die Argumentation funktioniert aber ebenfalls. Insbesondere
bei Wissensbasen, die GCIs enthalten, können Beweise durch immer wiederkehrendes
Auftauchen von Disjunktionen hochgradig parallel werden.
Konjunktion
Mit Einschränkungen lässt sich eine analoge Betrachtung auch für die Konjunktion
anstellen. Für ein Individuum b : D1 u D2 müssen bei der Bearbeitung der Konjunktion zwei Konzepte evaluiert werden. Diese könnten prinzipiell gleichzeitig bearbeitet
werden. Komplementär zur Bearbeitung der Disjunktion kann auch hier der Beweiser,
falls einer der Teilbeweise auf einen Widerspruch führt, die Bearbeitung des anderen
Konzepts abbrechen. Ein Problem bei der parallelen Verarbeitung von Konjunktionen
sind mögliche Abhängigkeiten der parallel zu verarbeitenden Konzepte. Sei D1 ≡ ∃r.E
und D2 ≡ ∀r.¬E, so dass b als b : ∃r.E u ∀r.¬E definiert ist. Hier muss in jedem Fall
zuerst der durch ∃r.E geforderte Rollennachfolger erzeugt werden, da sonst der durch
∀r.¬E entstehende Widerspruch nicht erkannt werden kann. Das heißt die Bearbeitung
dieser Konzepte kann nicht parallel, sondern nur nacheinander stattfinden. Hier muss
ein paralleler Beweiser erkennen, dass eine Abhängigkeit vorliegt, und die Konzepte
entsprechend sequentiell bearbeiten.
Kardinalitätsrestriktion
Seien in einer ABox folgende Zusicherungen enthalten: (a, b1 ) : r, (a, b2 ) : r, (a, b3 ) : r
und a :≤ 2 r. Da für a höchstens zwei r-Nachfolger erlaubt sind, müssen b1 , b2 und b3 zu
zwei Individuen zusammengefasst werden. Dabei gibt es drei Möglichkeiten: {b12 , b3 },
{b13 , b2 } und {b1 , b23 }. Wie bei einer Disjunktion lässt sich auch hier der Nichtdeterminismus dazu verwenden, die drei Alternativen parallel zu verarbeiten. Es kann auch
genauso die Verarbeitung dann beendet werden, wenn für eine der drei Alternativen die
Erfüllbarkeit nachgewiesen werden konnte.
4.1. DESIGNENTSCHEIDUNGEN
31
Weitere Ansätze
Um auf ganz andere Art und Weise Nutzen aus einer parallelen Verarbeitung zu ziehen,
könnte ein Ansatz auch sein, nicht den Reasoning-Prozess an sich zu parallelisieren, sondern für jede Anfrage an einen Reasoner parallel einen Beweis zu starten. Ein einzelner
Beweis würde in sich dann sequentiell ablaufen. Diese Methode könnte man zum Beispiel verwenden um die Berechnung einer Taxonomie zu beschleunigen. Auch bei einer
Wissensbasis, an die viele Anfragen gestellt werden, könnte dieser Ansatz vielversprechend sein (etwa bei einer Wissensbasis, die bei einem Webdienst eines Unternehmens
Verwendung findet, aber als Betriebsgeheimnis nicht an die Öffentlichkeit gelangen soll).
Da es dieser Ansatz allerdings nicht erlaubt, einzelne, schwierige Beweise schneller
zu führen, wird er in dieser Diplomarbeit nicht weiter verfolgt.
4.1.2
Abwägungen bei der Entscheidung für ein oder mehrere
Ansätze
Die hier vorgestellten Ansatzpunkte zur Parallelisierung lassen sich potentiell alle miteinander kombinieren. Wie allerdings in Abschnitt 2.2.5 beschrieben, muss sorgfältig
abgewogen werden, bei welchen Ansatzpunkten tatsächlich eine verteilte Abarbeitung
stattfinden soll, um eine zu feine Granularität zu vermeiden. Die Entscheidung für
einen oder mehrere Ansatzpunkte ist bei einem Tableau-Reasoner nicht trivial: Da der
mögliche und tatsächliche Parallelitätsgrad stark von der Eingabe (bzw. den darin verwendeten Konstruktoren) abhängt, kann nicht für alle möglichen Eingaben sowohl ein
befriedigender Mindestparallelitätsgrad als auch ein minimaler Overhead erreicht werden.
Aufgrund der Verwandtschaft von Disjunktion und Maximalkardinalitätseinschränkungen lassen sich diese beiden Ansatzpunkte zur Parallelisierung gut kombinieren:
Beide fußen auf Nichtdeterminismus und erlauben den Abbruch der Verarbeitung, sobald für eine Alternative die Erfüllbarkeit gezeigt werden konnte. Bei Verwendung von
GCIs kommen Disjunktionen außerdem oft im Tableau-Beweis vor. Deshalb wurden in
dieser Diplomarbeit diese beiden Punkte für eine Parallelisierung ausgewählt. Würde
man zusätzlich noch Konjunktionen parallel verarbeiten zöge das nach sich, dass sehr
viele im Tableaubeweis anfallenden Operationen eine parallele Verarbeitung anstoßen.
Dies hätte also eine sehr feine Granularität zur Folge. Außerdem müssten die bei Konjunktionen auftretenden Abhängigkeiten beachtet werden. Aus diesen Gründen wurde
von einer parallelen Verarbeitung von Konjunktionen abgesehen.
4.1.3
Entscheidung für ein Programmiermodell
Nach der Entscheidung für die Art, auf die Parallelität entstehen soll, steht die Entscheidung für ein Programmiermodell an. Grundsätzlich lassen sich sowohl das Modell
eines Rechners mit gemeinsamem Speicher als auch das Modell eines Rechners mit verteiltem Speicher verwenden um einen verteilten Beweiser zu realisieren. Für das Modell
mit verteiltem Speicher spricht, dass es sich natürlich auf DMCs abbilden lässt, welche
sich durch eine gute Skalierbarkeit bezüglich ihrer Leistung auszeichnen.
32
Das Modell mit gemeinsamem Speicher hingegen lässt sich gut auf Rechner abbilden,
bei denen sich mehrere Recheneinheiten ein und den selben Speicher teilen. Aus diesem
Grund lässt sich ein mit diesem Modell entwickelter Reasoner nicht nur auf SMPs,
sondern auch auf Systemen mit Mehrkernprozessoren ohne Umweg implementieren.
Desweiteren spricht für das Modell mit gemeinsamem Speicher, dass für Optimierung
wie caching und dependency directed backtracking1 Daten gespeichert werden müssen,
die in allen Threads benötigt werden, was bei einem message passing-Ansatz einen
hohen Kommunikationsaufwand bedeuten würde. Diese kleinen Vorteile gaben letztlich
den Ausschlag für das Modell mit gemeinsamem Speicher.
4.2
Der resultierende Prototyp
Auf der Basis der Entscheidungen der vorigen Abschnitte wird hier nun ein objektorientiertes paralleles beschreibungslogisches Beweissystem entwickelt. Um einen handlichen
Begriff für dieses System zu haben wird es in dieser Arbeit auch UUPR (für Uni Ulm
Parallel Reasoner ) genannt. Es wird die Abbildung der beschreibungslogischen Begriffe
auf Klassen ebenso beschrieben wie die praktische Realisierung der Parallelität. Dabei
wird insbesondere darauf eingegangen wie die in Abschnitt 2.2.5 beschriebenen Ineffizienzen - soweit bereits im Design absehbar - vermieden werden können.
4.2.1
Klassendesign
Zuerst muss die zentrale Komponente von UUPR beschrieben werden. Ihre Aufgabe
ist es, Beweise zu starten und Resultate zurückzugeben. Da sich das Konzeptwissen
über den gesamten Beweis nicht verändert und für alle (noch zu entwerfenden) parallel
arbeitenden Einheiten gleich ist, kann es zentral in diesem Objekt gespeichert werden.
Die Klasse, die dieses Objekt realisiert, heißt im folgenden Reasoner.
Da der in Kapitel 3 beschriebene Reasoner einen ABox-Erfüllbarkeitsdienst implementiert, muss eine Klasse für die Repräsentation von ABox-Wissen entworfen werden.
Die in der Klasse ABox enthaltenen Daten sind im wesentlichen entsprechend aus der
Beschreibung des Beweises in Kapitel 3 übernommen. Für die Individuen einer ABox
wird also jeweils die Menge von Konzepten, die einem Individuum zugeordnet sind, und
Informationen darüber, welche Individuen auf jeden Fall verschieden sind, gespeichert.
Informationen über Rollenbeziehungen unter den Individuen werden ebenfalls dort abgelegt.
Die Klasse ABox beherbergt auch die Realisierung des eigentlichen Tableaubeweises. In ihr ist die Methode definiert, die die ABox auf ihre Erfüllbarkeit überprüft.
Sie wendet die Tableauregeln auf die in ihr enthaltenen Individuen an. Der Entwurf
entscheidet sich bis zu dieser Stelle nicht von einem sequentiell arbeitenden Reasoner.
Alle Tableauregeln, die nicht zu einer parallelen Verarbeitung führen sollen, können
genauso wie in einem sequentiellen System umgesetzt werden. Auch gängige Implemen1
Parallele Realisierungen dieser Optimierungen werden in Abschnitt 4.3 beschrieben.
4.2. DER RESULTIERENDE PROTOTYP
33
tierungstechniken wie lazy unfolding 2 und tagging 3 können übernommen werden. Der
große Unterschied besteht nun in der Art und Weise, wie die Disjunktions- und Maximumkardinalitätsregeln angewendet werden. In einer sequentiellen Implementierung
würde man aus Effizienz- und Speicherplatzgründen vermutlich ein Design anstreben,
das es erlaubt, in einer ABox alle möglichen Alternativen zusammenzufassen. Da die
Alternativen nacheinander abgearbeitet werden, können durch den unterschiedlichen
jeweiligen Fortgang des Beweises auch keine Probleme entstehen: nach der abgeschlossenen Bearbeitung einer Alternative kann die ABox wieder in den Zustand von vor der
Anwendung dieser Alternative zurückversetzt werden. In UUPR muss es jedoch möglich sein, mehrere einander ausschließende Alternativen gleichzeitig zu bearbeiten. Aus
diesem Grund wird die Konstruktion von Alternativen hier anders realisiert. Für jede
Alternative wird eine neue ABox erzeugt, in der diese Alternative als wahr angenommen
wird. Diese ABoxen können ohne Konflikte gleichzeitig bearbeitet werden.
Wenn man einmal einen auf Basis dieser Klassen arbeitenden sequentiellen Reasoner
unterstellt, so könnte die rekursive Implementierung des Erfüllbarkeitstests einer ABox
(in Pseudocode) so aussehen:
class ABox {
boolean isSatisfiable() {
// sind noch Regeln anwendbar?
while (hasMoreRulesToApply()) {
// ’Rule’ beinhaltet hier Individuum und Konstruktor
Rule x = getNextRule();
// erzeugt diese Regel alternative ABoxen?
if (x.isDisjunction() || x.isMaximumCardinalityRestriction()) {
// generiere alternative ABoxen
ABox[] y = generateAlternatives(x);
for (int i = 0; i < y.size(); i++) {
// sobald eine erfuellbare Alternative gefunden wurde
// kann die Verarbeitung abgebrochen werden.
if (y[i].isSatisfiable()) return true;
}
// war keine der Alternativen erfuellbar?
// -> diese ABox ist ebenfalls unerfuellbar
return false;
} else {
// andere Regeln werden ganz normal angewendet.
this.applyDeterministicRule(x);
// anschliessend wird ueberprueft, ob dadurch ein
// primitiver clash entstanden ist.
if (hasPrimitiveClash()) return false;
}
}
2
3
Auffalten benamter Konzepte nach Bedarf, siehe [BHN+ 92].
rekursives Benennen von Unterkonzepten, siehe [HPS99].
34
// keine Regeln mehr anwendbar und kein clash gefunden?
// -> ABox ist erfuellbar.
return true;
}
...
}
In Reasoner kann der ABox-Erfüllbarkeitsdienst nun implementiert werden, indem an
der gewünschten ABox die Methode isSatisfiable() aufgerufen wird.
Um nun auf eine einfache Art und Weise Parallelität in diesen Algorithmus einzubauen, kann man die in 2.2 vorgestellten Primitive des Programmiermodells mit gemeinsamem Speicher verwenden. Dazu ersetzt man die Zeilen
for (int i = 0; i < y.size(); i++) {
// sobald eine erfuellbare Alternative gefunden wurde
// kann die Verarbeitung abgebrochen werden.
if (y[i].isSatisfiable()) return true;
}
return false;
durch folgenden Code, der das con-Konstrukt verwendet:
boolean[] results;
// parallele Abarbeitung der Alternativen, es wird
// gewartet, bis alle Ergebnisse vorliegen
con (int i = 0; i < y.size(); i++) {
results[i] = y[i].isSatisfiable();
}
// sobald eine erfuellbare Alternative gefunden wurde kann
// true zurueckgegeben werden.
for (int i = 0; i < results.size(); i++) {
if (results[i]) return true;
}
return false;
In einer praktischen Implementierung hat diese Variante jedoch zwei Nachteile. Zum
einen müssen alle Alternativen vollständig bearbeitet werden, bevor eine Auswertung
stattfinden kann, was in überflüssiger Arbeit resultiert, falls eine der Alternativen schnell
35
zu einem Ergebnis führen würde. Zum anderen ist der Parallelitätsgrad bei dieser Variante sehr schwer zu kontrollieren. Der Parallelitätsgrad hängt hier allein von der Eingabe
ab - es gibt keine Möglichkeit, innerhalb des Programms Einfluß darauf zu nehmen.
Während der erste Nachteil noch durch eine geschicktere Implementierung abgefangen werden kann (der Nachteil kommt unter anderem durch das Fehlen eines Primitivs zum Abbruch anderer Verarbeitungsstränge im Programmiermodell zustande),
so ist der zweite Nachteil schwerer zu beheben. Für eine Anfrage, die viele Disjunktionen (oder Maximumkardinalitätseinschränkungen) enthält, wird pro Alternative ein
Thread erzeugt und nach seiner Beendigung wieder zerstört. Je nach Anzahl ineinander
geschachtelter Disjunktion entsteht dadurch ein sehr hoher Aufwand für die Threadverwaltung, ähnlich wie durch eine zu feine Granularität. Falls die erzeugten Threads auf
echte Betriebssystemsthreads abgebildet werden, kann die Anzahl der Threads auch
schnell die Anzahl der zur Verfügung stehenden Prozessoren übersteigen. Wenn dies
der Fall ist, so bleibt das Thread-Scheduling vollständig dem Betriebssystem überlassen. Die Abarbeitungsreihenfolge entzieht sich also der Kontrolle des Programmierers,
wodurch an dieser Stelle auch keinerlei Optimierungen mehr möglich sind. Deshalb ist
bei dieser einfachen Umsetzung von Parallelität kein großer Geschwindigkeitsgewinn zu
erwarten. Ein geschickteres Design muss also in der Lage sein, den Overhead durch die
ständige Erzeugung und Zerstörung von Threads zu vermeiden und gleichzeitig eine
gewisse Kontrolle über den Programmablauf ermöglichen.
4.2.2
Kontrollierbare Parallelität
Eine Möglichkeit hierfür ist eine Unterscheidung zwischen dem Betriebssystembegriff
Thread und seiner Aufgabe. Die Aufgabe oder Arbeitseinheit heißt im folgenden auch
Job. Dazu wird eine Klasse Executor eingeführt. Ein Executor verwaltet intern eine
feste Anzahl von n Threads (Worker ) und einen zentralen Pool aus noch zu bearbeitenden Jobs. Er nimmt Jobs entgegen, bearbeitet sie und gibt fertige Jobs (ein Job besitzt
in erster Linie eine Methode zu seiner Ausführung, run()) zurück. Jeder der n Worker
holt sich, sobald er frei ist, einen oder mehrere Jobs aus dem Pool, bearbeitet diese
und kann im Anschluß neue Jobs in den Pool legen. Unter Zuhilfenahme der Primitive
des Programmiermodells mit gemeinsamem Speicher kann Executor folgendermaßen
implementiert werden:
class Executor {
Pool jobs;
// nimmt einen Job aus dem Pool und gibt ihn zurueck
Job getJobFromPool() {
await(!jobs.empty()) {
return jobs.remove();
}
}
// legt neue Jobs in den Pool
36
void submitJobsToPool(Job[] newJobs) {
atomic {
jobs.add(newJobs);
}
}
// weitere Methoden
// testet, ob der Executor noch fertige oder zu bearbeitende
// Jobs hat
boolean hasMoreJobs();
// gibt eine Liste der seit dem letzten Aufruf dieser Methode
// fertiggestellten Jobs zurueck
Job[] getFinishedJobs();
// bricht alle Verarbeitung ab und leert den Pool
void cancelComputation();
...
}
Die Worker führen folgende Funktion aus:
void workerFunction() {
while (!stopWorking()) {
Job next = executor.getJobFromPool();
Job[] followUpJobs = next.run();
executor.submitJobsToPool(followUpJobs);
}
}
Der Zugriff auf den Pool muss dabei synchronisiert werden. Dieses Entwurfsmuster
paralleler Programmierung heißt auch Workpool-Modell [Str05]. Es hat einige große
Vorteile:
• Mithilfe dieses Entwurfsmusters lässt sich eine gleichmäßige Auslastung aller n
Threads erreichen. Nach Beendigung eines Jobs kann ein Worker sofort den nächsten Job aus dem Pool holen und weiterarbeiten, ohne auf die Fertigstellung anderer Jobs warten zu müssen.
• Aufwand für die Erzeugung und Zerstörung von Threads fällt nur bei Erzeugung
bzw. Zerstörung des Executors am Beginn bzw. Ende des Programms an.
• Der maximale Parallelitätsgrad ist n und kann gut an die Anzahl der tatsächlich
vorhandenen Prozessoren angepasst werden.
• Die Implementierung der Pool-Datenstruktur kann so angepasst werden, dass sie
eine priorisierte Abarbeitung der Jobs ermöglicht. Dies würde es erlauben, vielversprechende Jobs bevorzugt zu verarbeiten und damit schneller zum Ergebnis
zu kommen.
37
• Durch dieses Entwurfsmuster entsteht ebenfalls Overhead bei der Parallelisierung,
der aber geringer ausfällt als bei der naiven Parallelisierung.
Der zentrale Pool kann jedoch auch zum Nachteil werden, da für große n und/oder sehr
einfache Jobs die Synchronisierung des Pools zu einem Flaschenhals für die Gesamtperformance werden kann.
Um das Workpool-Modell auf den beschriebenen Reasoner anzuwenden muss die
Klasse ABox angepasst werden. Da Jobs nur parallel ausgeführt werden, wenn sie dem
Executor übergeben werden, kann die Methode isSatisfiable() nicht auf die Ergebnisse der von ihr erzeugten alternativen ABoxen warten. Sie würde ansonsten nicht
terminieren und den sie bearbeitenden Worker nicht freigeben. Dies verhindert auch,
dass isSatisfiable() das vollständige Ergebnis (sprich die Erfüllbarkeit der ABox)
zurückgeben kann. Die Bestimmung des Endergebnisses muss also anders stattfinden.
Dazu kann man folgende Betrachtung anstellen: Gegeben sei eine ABox A, die zwei
Alternativen generiert: A1 und A2 . A ist erfüllbar falls A1 oder A2 erfüllbar ist. Jede der
Ai erzeuge nun wiederum zwei Alternativen Ai1 und Ai2 . Sei die Erfüllbarkeit von Aij
mit aij bezeichnet. Die Erfüllbarkeit von A ist damit bestimmt durch a ⇐⇒ (a11 ∨a12 )∨
(a21 ∨ a22 ) ⇐⇒ a11 ∨ a12 ∨ a21 ∨ a22 . Man kann also alle Alternativen unabhängig von der
Disjunktion, aus der sie entstanden sind, betrachten. Anders ausgedrückt, sobald eine
ABox gefunden wird, auf die keine Regel mehr anwendbar ist und die keinen Widerspruch
enthält, war die ursprüngliche ABox erfüllbar. Gelingt es nicht, eine solche ABox zu
erzeugen, so war die ursprüngliche ABox unerfüllbar. Das bedeutet, dass sich die Klasse
ABox gut auf den Begriff Job aus dem Workpool-Modell abbilden lässt, da man für die
Erfüllbarkeit einer ABox nur so lange immer neue ABoxen (d.h. neue Jobs) erzeugen und
bearbeiten muss, bis eine erfüllbare ABox gefunden wird.
Bei einem Ansatz, der (nur) Konjunktionen parallel bearbeitet, kann eine ähnliche Betrachtung angestellt werden. Hier sind die Ergebnisse konjunktiv verknüpft und
die Bearbeitung kann abgebrochen werden, sobald eine nicht erfüllbare ABox gefunden
wird. Falls allerdings sowohl Konjunktionen als auch Disjunktionen parallel verarbeitet werden sollen, ist die Ermittlung des Endergebnisses nicht so einfach. Hier müsste
die Zuordnung der ABoxen zu den Disjunktionen bzw. Konjunktionen, aus denen sie
entstanden sind, erhalten bleiben, um das korrekte Ergebnis ermitteln zu können.
Um die Überlegung auf den disjunktiven Ansatz von UUPR zu übertragen muss die
Klasse ABox dahingehend verändert werden, dass die Methode isSatisfiable() durch
die Methode run() ersetzt wird, die kein Ergebnis in Form eines booleschen Wertes
zurück gibt, sondern nur neue Alternativen (sprich: Jobs) erzeugt. Diese stellen dann die
Erweiterung der ABox dar und sollen statt ihr weiterbearbeitet werden. Weiterhin erhält
die Klasse ABox eine Objektvariable namens result, die den Wert true annimmt, falls
auf die ABox keine Regeln mehr anwendbar sind und sie keinen Widerspruch enthält.
Ansonsten ist der Wert von result false. Vor der Beendigung von run() wird result
entsprechend gesetzt:
class ABox extends Job {
boolean result;
38
Job[] run() {
// sind noch Regeln anwendbar?
while (hasMoreRulesToApply()) {
// ’Rule’ beinhaltet hier Individuum und Konstruktor
Rule x = getNextRule();
// erzeugt diese Regel alternative ABoxen?
// statt dieser ABox werden jetzt die Alternativen
// ueberprueft, diese ABox wird verworfen (der Einfachheit
// halber, eine Optimierung waere leicht zu erreichen)
this.result = false;
return y;
} else {
// andere Regeln werden ganz normal angewendet.
this.applyDeterministicRule(x);
// anschliessend wird ueberprueft, ob dadurch ein
// primitiver clash entstanden ist.
if (hasPrimitiveClash()) {
return null;
}
}
}
// keine Regeln mehr anwendbar und kein clash gefunden?
// -> ABox ist erfuellbar.
this.result = true;
return null;
}
...
}
Auch der Reasoner muss angepasst werden. Er wird von einem eigenen Thread ausgeführt und startet den Erfüllbarkeitstest für eine ABox nicht mehr über die Methode
isSatisfiable(), sondern übergibt die ABox dem Executor und testet alle fertiggestellten ABoxen darauf, ob result auf true gesetzt ist. Falls eine ABox gefunden wird,
deren result true ist, so kann die Anfrage mit true beantwortet werden:
class Reasoner {
Executor ex;
boolean testABoxSatisfiability(ABox toTest) {
Job[] jobArray = new Job[1];
Job[0] = toTest;
ex.submitJobsToPool(jobArray);
39
while (ex.hasMoreJobs()) {
ABox[] finishedABoxes = (ABox[]) ex.getFinishedJobs();
for (int i = 0; i < finishedABoxes.size(); i++) {
if (finishedABoxes[i].result == true) {
// erfuellbare ABox gefunden, Abbruch und
// Rueckgabe true
ex.cancelComputation();
return true;
}
}
}
// keine erfuellbare ABox gefunden -> toTest war nicht
// erfuellbar
return false;
}
...
}
Abbildung 4.1 veranschaulicht die wichtigsten Kommunikationswege des vorgestellten
Designs.
Um die genannten Vorteile dieses Designs nutzen zu können, muss man bei der
Wahl der Datenstruktur für den Pool Sorgfalt walten lassen. Die gängige Implementierung des Pools als Schlange jedenfalls ist hier kontraproduktiv: Damit entspräche die
Verarbeitungsreihenfolge der ABoxen der einer Breitensuche im Baum der Alternativen.
Dies hätte nicht nur einen hohen Speicherplatzbedarf, sondern auch eine sehr schlechte
Performance zur Folge, da ABoxen, auf die weniger Disjunktions- oder Maximumkardinalitätsregeln angewendet wurden, bevorzugt würden. Somit würde die Entdeckung von
erfüllbaren, vollständig aufgefalteten ABoxen (d.h. Lösungen) gezielt verzögert. Die Verwendung eines Stapels verbessert das beschriebene schlechte Verhalten, allerdings lässt
sich von der Möglichkeit im Workpool-Modell, Jobs priorisiert zu verarbeiten, auch Gebrauch machen, um die Performance noch weiter zu erhöhen. Eine einfache Methode
ist es, ABoxen folgendermaßen eine Priorität zuzuweisen:
• Die ursprüngliche ABox erhält die Priorität 0.
• Wird auf eine ABox mit Priorität n eine Disjunktions- oder Maximumkardinalitätsregel angewendet, so haben die daraus entstehenden ABoxen die Priorität
n + 1.
Damit werden ABoxen, auf die mehr Disjunktions- und Maximumkardinalitätsregeln
angewendet wurden, bevorzugt. Die Verarbeitungsreihenfolge ähnelt eher der anderer
Reasoner, nämlich einer Tiefensuche im Baum der Alternativen. Dies genügt bereits, um
signifikant weniger ABoxen zur Findung eines Ergebnisses überprüfen zu müssen. Weitere
Optimierungen an der Verarbeitungsreihenfolge sind denkbar, siehe dazu Kapitel 8.
40
.
Reasoner
testABoxSatisfiability(ABox toTest)
Original-ABox
bearbeitete ABoxen
Executor
getJobFromPool()
submitJobsToPool(Job[] newJobs)
zu bearbeitende Jobs
Folgejobs
zu bearbeitende Jobs
Worker
.
workerFunction()
Folgejobs
Folgejobs
Worker
workerFunction()
···
Folgejobs
Aufruf
ABox
run()
.
Aufruf
ABox
···
run()
.
Abbildung 4.1: Kommunikationswege der Klassen in UUPR
4.3
Realisierung der Optimierungen
In der bisherigen Beschreibung von UUPR wurden außer der internen Konzeptdarstellung und lazy unfolding noch keine der in heutigen Systemen gängigen Optimierungen
erwähnt. Reasoner ohne diese Optimierungen sind allerdings in vielen Fällen nicht in
der Lage, beschreibungslogische Probleme in akzeptabler Zeit zu lösen. Um bewerten zu
können, wie sinnvoll eine parallele Implementierung im Hinblick auf eine Verbesserung
der Leistungsfähigkeit von Beschreibungslogikreasonern tatsächlich ist, müssen gängige
Optimierungen mitbetrachtet werden. Ein zentraler Punkt in dieser Arbeit ist es daher zu untersuchen, inwieweit sich diese Optimierungen mit einem parallelen Ansatz
kombinieren lassen. Hier werden nun die in Abschnitt 3.2 beschriebenen Optimierungen auf ihre Realisierbarkeit und ihren Nutzen in einer parallelen Implementierung
hin analysiert. Aufbauend auf diesen Einschätzungen wurde über die Aufnahme einer
Optimierung in die prototypische Implementierung entschieden. Das Ziel ist es, die Optimierungen so zu implementieren, dass sie für Testzwecke an- und wieder ausgeschaltet
werden können.
4.3. REALISIERUNG DER OPTIMIERUNGEN
4.3.1
41
Implementierte Optimierungen
Lexical Normalization
Lexical normalization setzt bereits vor dem eigentlichen Beweis an: Alle Konzeptausdrücke werden beim Einlesen in lexikale Normalform gebracht. Da sich die Semantik der
Konzepte in lexikaler Normalform nicht ändert, beziehen sich die nötigen Änderungen
bei der Regelanwendung nur auf die Darstellung der jeweiligen Konstruktoren. Lexical
normalization beeinflusst den Reasoning-Prozess also nur dadurch, dass aufgrund der
Darstellung clashes schneller als solche erkannt werden.
Wechselwirkungen zwischen paralleler Verarbeitung und lexical normalization sind
nicht zu erwarten, die Effektivität dieser Optimierung sollte bei paralleler und bei sequentieller Verarbeitung in etwa gleich sein.
Semantic Branching
Da semantic branching direkt die Generierung von Alternativen verändert, muss hier
genauer betrachtet werden, ob sich diese Optimierung und Parallelverarbeitung gegenseitig beeinflussen. Die Eigenschaft von semantic branching, dass die unnötige Mehrfachevaluierung von Teilproblemen vermieden wird, geht jedoch beim Einsatz des beschriebenen parallelen Algorithmus’ nicht verloren. Eine unnötige Mehrfachevaluierung
würde auch den parallelen Algorithmus verlangsamen, so dass sich der Einsatz von
semantic branching genauso auszahlt wie in einer sequentiellen Implementierung.
Unter Implementierungsaspekten verändert sich durch semantic branching nur die
Art der Entstehung von Alternativen. Da sonst keine weiteren Änderungen nötig sind,
verkompliziert diese Optimierung die parallele Implementierung nicht.
Simplification
Simplification versucht, die Anzahl der nichtdeterministischen Verzweigungen bei der
Expansion eines Individuums zu verringern. Dies mag in einer auf Nichtdeterminismus
aufbauenden Parallelisierung auf den ersten Blick kontraproduktiv aussehen. Tatsächlich verringert die Anwendung dieser Optimierung jedoch den durch Parallelverarbeitung entstehenden Overhead. Dazu betrachte man den Ausdruck (C t D) u ¬C. Würde
ohne Simplification einer Alternative (egal ob mit oder ohne semantic branching) C
hinzugefügt, so entstünde eine Alternative mit dem Ausdruck (C t D) u ¬C u C, welche sofort als widersprüchlich verworfen würde4 . Bei einer Alternative, in der so wenig
Arbeit anfällt, hat eine parallele Verarbeitung keinen Geschwindigkeitsvorteil. Simplification verringert also den Anteil des Parallelisierungsoverheads an der Gesamtrechenzeit. Da bei sequentieller Bearbeitung kein Overhead für die Parallelisierung anfällt
ist diese Optimierung in einem parallelen Beweiser wahrscheinlich sogar effektiver als
in einem sequentiellen Beweiser. Die Integration dieser Optimierung in UUPR kann
genau wie in sequentiellen Reasoner stattfinden, indem sie vor der Betrachtung von
nicht-deterministischen Regeln angewendet wird: Das Code-Stück
4
Durch die lexikale Normalform wird C u ¬C sofort als clash erkannt.
42
// ueberprueft, diese ABox wird verworfen
return y;
} ...
muss also nur durch
// Vereinfachung anwenden
this.simplify(x);
// Branching wird dann nur ausgef"uhrt, falls noch notwendig
if (this.branchingStillNeeded(x)) {
// ueberprueft, diese ABox wird verworfen
return y;
}
} ...
ersetzt werden.
Caching
Caching erlaubt den Abbruch der Verarbeitung für den Fall, dass für einen Ausdruck
der Erfüllbarkeitsstatus bereits bekannt ist. Um dies in einer parallelen Implementierung sinnvoll umzusetzen, müssen alle Threads Zugriff auf den Erfüllbarkeitsstatus aller
bereits bearbeiteten Ausdrücke haben. Das heißt, der Cache für diese Ausdrücke muss
zentral verwaltet und der Zugriff darauf synchronisiert werden. Wenn viele Threads parallel arbeiten, kann der Zugriff auf den gemeinsamen Cache zu einem Flaschenhals für
die Performance werden. Ein weiteres Problem entsteht durch die Art und Weise auf die
Parallelität realisiert wird. Die Alternativen einer Disjunktion werden asynchron und
unabhängig von einander bearbeitet, innerhalb einer Alternative hat man keinen Zugriff
auf die ”Geschwister”-Alternativen. Dadurch ist es sehr schwierig Buch darüber zu führen, wann und mit welchem Ergebnis die Verarbeitung der Alternativen abgeschlossen
wird.
Aus diesem Grund wurde nur eine einfache caching-Variante implementiert. Im Objekt Reasoner wird ein Cache verwaltet, der auf Ausdruckssebene arbeitet. Für jeden
vollständig aufgefalteten Tableau-Knoten wird vor seiner Verarbeitung5 mittels des auf5
Genauer: Der Verarbeitung seiner Rollennachfolger.
4.3. REALISIERUNG DER OPTIMIERUNGEN
43
a : A ⊔ ∃r.B
a:A
⊔
a : ∃r.B
r
b:B
Abbildung 4.2: Caching in UUPR
gefalteten Ausdrucks eine Cache-Anfrage gestellt. Wenn die Bearbeitung eines TableauKnotens abgeschlossen ist, wird, falls nötig, ein entsprechender Eintrag erstellt.
Für Ausdrücke, bei deren Verarbeitung Nichtdeterminismus auftritt, wird kein CacheEintrag erstellt. Hierfür wäre die Kenntnis der Ergebnisse aller Alternativen nötig, was
aus oben genanntem Grund nicht trivial ist. Eine Veranschaulichung, für welche Ausdrücke ein Cache-Eintrag erstellt wird, bietet Abbildung 4.26 : Die Erfüllbarkeit der
Ausdrücke A, ∃r.B und B wird jeweils im Cache abgelegt. Da die beiden Alternativen
a : A und a : ∃r.B parallel und ohne Bezug zueinander bearbeitet werden, wird für
A t ∃r.B kein Cache-Eintrag erstellt.
Tagging und Lazy Unfolding
Der Vollständigkeit halber seien hier noch die bereits genannten Methoden tagging und
lazy unfolding erwähnt. Diese Techniken beschleunigen zwar den Beweisprozess, sie
sind aber so grundlegend, dass für die erfolgreiche Realisierung eines Tableaubeweisers
vorausgesetzt wurden. Diese Techniken sind tief in UUPR integriert, so dass sie nicht
abgeschaltet werden können.
4.3.2
Nicht implementierte Optimierungen
Dependency Directed Backtracking
Das Ziel bei dependency directed backtracking ist es, die Evaluierung von Alternativen,
die bekanntermaßen alle denselben Widerspruch enthalten, zu verhindern. Bei einer
normalen Implementierung liegen alle Informationen über diese Alternativen vor, etwa
auf dem Funktionsaufrufsstack bei einer rekursiven Implementierung. Auf diese Weise
ist es möglich, zu dem Punkt im Beweis zurückzukehren, an dem dieser Widerspruch
hinzugefügt wurde. Da bei einer parallelen Implementierung die vollständig instantiierten Alternativen von einem Pool verwaltet werden gibt es einen solchen Punkt nicht.
Würde in einer Alternative festgestellt, dass sie einen Widerspruch enthält, der auf
einen bestimmten Verzweigungspunkt zurückgeht, so müsste die parallele Implementierung in der Lage sein, alle entsprechenden verwandten Alternativen zu identifizieren
6
Aus Übersichtlichkeitsgründen verwendet diese Darstellung kein semantic branching.
44
und ihre Verarbeitung zu verhindern beziehungsweise abzubrechen. Verwandte Alternativen sind in diesem Fall alle ABoxen, die die selben Konzepte enthalten, die in der
als widersprüchlich identifizierten ABox zum clash geführt haben. Eine solche Implementierung müsste also über eine entsprechende Datenstruktur zur Verwaltung dieser
Informationen verfügen.
Die Entwicklung einer solchen Datenstruktur und die korrekte Implementierung des
Abbruchmechanismus’ sprengen den Rahmen dieser Arbeit. Deshalb wurde auf eine
Adaption dieser Optimierung in UUPR verzichtet.
In sequentiellen Implementierungen wird versucht, durch Heuristiken eine gute Verarbeitungsreihenfolge zu erreichen, um insgesamt weniger Alternativen betrachten zu
müssen und schneller zum Ergebnis zu kommen. In UUPR werden alle Alternativen
gleichzeitig generiert und in den Pool gelegt. Da die im Pool vorhandenen ABoxen priorisiert verarbeitet werden, macht dies die Verwendung von Heuristiken zwar nicht unmöglich, verändert sie aber. Die Reihenfolge kann nun nicht mehr explizit angegeben
werden. Die Kombination mit dem in UUPR verwendeten Prioritätssystem (das ABoxen
aufgrund der Anzahl der auf sie angewendeten Disjunktionen bewertet) ist jedoch prinzipiell nicht schwierig. Bei der Erzeugung einer ABox wird ihr eine Priorität zugewiesen.
Die Bewertung der Heuristik muss an dieser Stelle mit in die Priorität einfließen, die
weitere Verarbeitung findet dann anhand der Priorität statt.
Mit welchen Gewichtungen die Berechnungen in der Priorität kombiniert werden sollen und welche der zahlreichen entwickelten Heuristiken sich gut eignen ist im Rahmen
dieser Diplomarbeit schwer zu ermitteln. Da der Einsatz von Heuristiken erst durch
Erfahrungswerte und lange Testreihen sinnvoll wird, wurde also von einer Implementierung in UUPR abgesehen.
GCI Absorption
Absorption ist ein vorverarbeitender Schritt, der auf eine Ontologie angewendet werden kann, die GCI-Axiome enthält. Durch den vorverarbeitenden Charakter kann die
Optimierung problemlos mit einem parallel arbeitenden Reasoner kombiniert werden.
Absorption verringert durch den Wegfall von GCI-Axiomen, ähnlich wie Simplification, die Anzahl der nichtdeterministischen Verzweigungen in einem Knoten. Wiederum
lässt sich hier argumentieren, dass eine Verringerung der Anzahl von Verzweigungen
auch und gerade in einer parallelen Implementierung vorteilhaft ist, falls dadurch nicht
sämtlicher Nichtdeterminismus verschwindet.
Es liegt allerdings einige Schwierigkeit darin, bei der GCI-Absorption eine gute Auswahl der tatsächlich durchzuführenden Absorptionen zu treffen [HT00]. Aus diesem
Grunde wurde beschlossen, Absorption im Rahmen dieser Arbeit nicht zu betrachten.
Kapitel 5
Implementierung
Dieses Kapitel widmet sich der im Rahmen der Diplomarbeit entstandenen prototypischen Implementierung des parallel arbeitenden beschreibungslogischen Beweissystems
UUPR. Als Programmiersprache wurde C++ gewählt, da diese Sprache sowohl mächtige Sprachmittel bietet als auch eine effiziente Implementierung ermöglicht. Die verwendete Entwicklungsumgebung ist Eclipse1 unter Linux zusammen mit dem C/C++Development-Toolkit CDT2 .
Zuerst wird ein Überblick über die verwendeten Bibliotheken und die Benutzung von
UUPR gegeben. Dabei wird insbesondere auf die Bedeutung der Wahl einer geeigneten
Speicherverwaltung eingegangen. Danach werden die Implementierungen der in Kapitel
4 vorgestellten Klassen näher erläutert. Bei der Umsetzung von UUPR wurde, soweit im
Rahmen dieser Arbeit möglich, auf eine effiziente Implementierung der einzelnen Komponenten geachtet, um für eine Bewertung des Erfolgs einer parallelen Implementierung
aussagekräftige Ergebnisse erhalten zu können.
5.1
Systembeschreibung
UUPR ist eine prototypische Implementierung eines parallelen ABox-Reasoners. Es verarbeitet ALCN Hr+ -Ontologien im DIG 2.0-Format3 . Aufgrund des prototypischen Charakters von UUPR wird nur ein Teil der in DIG 2.0 vorgesehenen Tags unterstützt. Eine
genau Auflistung dieser Tags findet sich in Anhang B. Der Start erfolgt mittels Kommandozeilenaufruf:
./uupr <Ontologiedatei> <Querydatei> <Anzahl der Worker-Threads>
oder
./uupr <Ontologie- und Querydatei> <Anzahl der Worker-Threads>
1
http://www.eclispe.org/
http://www.eclipse.org/cdt/
3
Zum Zeitpunkt der Abgabe dieser Diplomarbeit ist DIG 2.0 noch kein standardisiertes Format,
seine Entwicklung ist noch nicht abgeschlossen. Siehe daher Anhang C für die dieser Arbeit zugrundeliegende Version.
2
45
46
KAPITEL 5. IMPLEMENTIERUNG
Da immer ein Master-Thread für das Einlesen von Dateien und Verwalten von Beweisen gestartet wird beträgt die Gesamtzahl der Threads Anzahl der Worker-Threads
+ 1. UUPR arbeitet dabei in einer Art Batch-Modus: Alle in <Querydatei> gefundenen
Anfragen werden nacheinander abgearbeitet. Um die Queries untereinander unterscheiden zu können wurde ein vom DIG 2.0 Format nicht vorgesehenes Attribut namens id
eingeführt, das den Anfragetags hinzugefügt werden muss. Um die Erfüllbarkeit eines
Konzeptes C zu erfahren lautet die entsprechende Query zum Beispiel:
<dig:IsClassSatisfiable id="Erfuellbarkeit von C">
<owl:OWLClass owl:URI="C"/>
</dig:IsClassSatisfiable>
Die dazugehörige Ausgabe von UUPR ist dann
Answering query Erfuellbarkeit von C...
Query with id=’Erfuellbarkeit von C’ finished, result: true.
Um später die Effektivität der implementierten Optimierungen messen zu können,
gibt es in UUPR die Möglichkeit, Optimierungen zur Compilezeit an- und auszuschalten. Dazu gibt es in der Quelldatei Const.h mehrere #defines. Zu jeder Optimierung gibt es eine Zeile #define OPTIMIZATION_x, wobei x LEXICAL_NORMALISATION,
SIMPLIFICATION, SEMANTIC_BRANCHING oder CACHING ist. Das Auskommentieren einer
Zeile bewirkt das Abschalten der entsprechenden Optimierung. Aus implementierungstechnischen Gründen ist es allerdings nicht möglich OPTIMIZATION_SIMPLIFICATION
bei aktivierter Optimierung OPTIMIZATION_SEMANTIC_BRANCHING auszuschalten. Damit Änderungen an den verwendeten Optimierungen angewendet werden, muss UUPR
mit dem Befehl make neu übersetzt werden. Dies erhöht zwar den Zeitaufwand bei der
Änderung der aktivierten Optimierungen. Da die Wahl zwischen optimiertem und nicht
optimiertem Code aber nicht zur Laufzeit getroffen werden muss, kann so eine bessere
Performance erreicht werden.
5.2
Verwendete Bibliotheken
Bei der Entwicklung von UUPR kamen verschiedene Bibliotheken zum Einsatz, über
die dieser Abschnitt einen kurzen Überblick gibt.
5.2.1
Xerces-c
Die xerces-c Bibliothek4 ist eine C++-Adaption der für Java entwickelten xerces-Bibliothek und stellt diverse Tools für die Verarbeitung von XML-Dokumenten bereit.
Sie wird für den Umgang mit dem XML-basierten DIG 2.0-Format benötigt. Zum Einlesen der Eingabe wird der in xerces-c enthaltene DOM-Parser verwendet. Er erlaubt
das komfortable Traversieren der DIG 2.0-Dateien als Baum. Durch die vorhandenen
Möglichkeiten Attribute auszulesen und Knoten auszufiltern, wird die Erstellung der
internen Repräsentation aus den DIG-Daten vereinfacht.
4
http://xml.apache.org/xerces-c/
5.2. VERWENDETE BIBLIOTHEKEN
5.2.2
47
Boost.Threads
Boost5 ist ein großes Projekt, das sich zum Ziel gesetzt hat, die äußerst heterogene C++Welt durch standardisierte Bibliotheken zu vereinheitlichen. Die Thread-Bibliothek des
Boost-Projektes realisiert eine portable und objektorientierte Möglichkeit zur Verwendung von Threads in C++-Programmen. Sie stellt die wichtigsten Hilfsmittel zur Verwaltung von Threads bereit. Boost.Threads enthält Methoden zur Synchronisierung, für
den gegenseitigen Ausschluss und das bedingte Warten von Threads. Boost.Threads arbeitet als ein gemeinsames Frontend von verschiedenen anderen Threading-Bibliotheken,
zum Beispiel pthread oder Windows Threads.
Um möglichst unabhängig von der zugrundeliegenden Implementierung der Threads
zu sein, basiert die Parallelisierung von UUPR auf dieser Bibliothek.
5.2.3
Speichermanager
UUPR macht starken Gebrauch der verschiedenen Containerklassen der Standard Template Library (STL) von C++. Diese Containerklassen erlauben es, ihre Speicherverwaltung mittels sogenannter allocator-Klassen zu konfigurieren. Wenn nicht näher
spezifiziert, wird eine Standardimplementierung verwendet, der std::allocator. Bei
der Implementierung von UUPR stellte sich heraus, dass die Klasse std::allocator für
parallele Programme, die intensiven Gebrauch des Hauptspeichers machen, nicht geeignet ist. Frühe Tests unter Verwendung des std::allocator zeigten eine enttäuschende
Performance: Es konnte kein Geschwindigkeitsgewinn festgestellt werden.
Um Abhilfe zu schaffen wurden verschiedene, speziell für die Verwendung in parallelen Programmen optimierte Speicherverwaltungen getestet. Einige der alternativen
Implementierungen ersetzen lediglich die Speicherverwaltungsmethoden malloc() und
free() durch eigene. Durch die Verwendung dieser Methoden in einer selbst geschriebenen Klasse MallocAllocator wurde ihr Einsatz in den STL-Containern möglich. Drei
Speichermanager wurde dabei getestet:
• Der Hoard memory manager6 ersetzt malloc() und free() sowie die Operatoren
new und delete durch eigene Implementierungen. Die Vorgehensweise von Hoard
wird in [BMBW00] beschrieben. Hoard wird beim Linkvorgang mittels einer Bibliothek eingebunden. Für nichtkommerzielle Zwecke existiert eine kostenlose Version.
• Nedmalloc7 ist frei erhältlich und auch in kommerzieller Software einsetzbar. Für
die Verwendung von nedmalloc müssen lediglich ein paar weitere Quelldateien
mitübersetzt werden.
• In dem Paket Intel Thread Building Blocks (TBB)8 ist neben anderer Klassen für
die Entwicklung paralleler Software auch ein Speichermanager (scalable_allocator)
5
http://www.boost.org/
http://www.hoard.org/
7
http://www.nedprod.com/programs/portable/nedmalloc/index.html
8
http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm
6
48
enthalten. Dieser wird über eine Bibliothek im Programm eingebunden. Wiederum
existiert eine für nichtkommerzielle Zwecke kostenfreie Version.
Um den Austausch der verschiedenen Speicherverwaltungen so einfach wie möglich zu
machen, kann der verwendete Speichermanager, ähnlich wie die zu verwendenden Optimierungen, in Const.h ausgewählt werden: Const.h definiert struct Allocators<T>,
welches den inneren Typ Type enthält. Allocators<T>::Type wird von allen Containern in UUPR als Speichermanager verwendet. Leider konnte dies nicht wie bei der
Auswahl der aktivierten Optimierungen implementiert werden. Alle drei Speichermanager gleichzeitig in UUPR zu integrieren würde zu Konflikten aufgrund der unterschiedlichen Neudefinitionen von malloc() und free() führen. Daher muss bei einer
Änderung neben der Angabe des entsprechenden allocators noch die Einbindung der
dazugehörigen Bibliotheken im Makefile sichergestellt werden.
5.3
Implementierung der Datenstrukturen
Dieser Abschnitt präzisiert die in Abschnitt 4.2 gezeigte skelettartige Beschreibung der
zur Implementierung von UUPR verwendeten Klassen. Da ein Großteil dieser Arbeit
die technische Umsetzung der Parallelität betrifft wurde bei der Konzeptrepräsentation
und der Implementierung der benötigten Klassen Wert auf möglichst hohe Effizienz
gelegt. Obwohl folgende Überlegungen also nicht essentiell wichtig für eine parallele
Implementierung sind, so helfen sie doch, die parallele Implementierung so effizient wie
möglich zu gestalten.
5.3.1
Darstellung von TBoxen
Aus einem Praktikum, bei dem das Ziel war, einen kompakten Beschreibungslogikreasoner für den Einsatz auf einem Handheld oder Mobiltelefon zu entwickeln, stammt
die Idee für die interne Konzeptrepräsentation. Grundsätzlich wird dabei jedem Konzept eine Ganzzahl (int) zugeordnet. Diese platzsparende Darstellung war in einem
speichersparenden Reasoner ein wichtiges Kriterium. Die Zuordnung von Konzepten
zu ints beschränkt sich nicht auf benamte Konzepte, Unterkonzepte werden ebenfalls
rekursiv indiziert. Die Klasse DIG20Parser, die diese Repräsentation aufbaut, geht beispielsweise bei einem Konzept C ≡ (A1 t A2 ) u B so vor: Zuerst werden den Konzepten
A1 , A2 und B auf eindeutige Weise Zahlen zugeordnet. Die Disjunktion A1 t A2 erhält
dann eine eigene Zahl, welche in der Darstellung von C anstatt der Disjunktion selbst
verwendet wird. Für die Darstellung der Konstruktoren wird dabei ebenfalls eine Zahl
r verwendet, so dass sich ein Konzept als int-array darstellen lässt. Die gesamte TBox
ist dann ein array aus int-arrays. Auf diese Weise wird in UUPR Tagging [HPS99]
realisiert.
Für die Umsetzung dieser Darstellung gelten weitere Regeln: Die Verwendung von
Ganzahlen erlaubt intuitiv die Realisierung der Konzeptnegation als numerische Negation (”-”). Desweiteren ist die Zahl 1 im TBox-array für das allgemeinste Konzept >
reserviert, woraus auch folgt, dass −1 das speziellste Konzept ⊥ darstellt. Die genannte
5.3. IMPLEMENTIERUNG DER DATENSTRUKTUREN
49
Index array-Inhalt
0x06 000 000
0
1
0x06 000 000
2
0x04 000 000 -4 5
3
0x06 000 000
4
0x03 000 000 3
5
0x00 001 001 1
Abbildung 5.1: Die interne Darstellung einer Beispiel-TBox
Zahl r erhält in der array-Darstellung eines Konzeptes immer den Index 0. Diese Zahl
enthält außer dem Konstruktor für das Konzept noch andere Daten:
• Für existentielle und universelle Quantifikationen wird die betroffene Rolle mit
einkodiert. Rollen werden dabei in der Reihenfolge ihres ersten Auftauchens in
der Ontologie durchnummeriert, beginnend bei 0.
• Für Kardinalitätsrestriktionen werden Rolle und Kardinalität einkodiert.
Der Datentyp int hat auf den unterstützten Systemen eine Länge von 32 Bit. Die
genannten Informationen werden im Verhältnis AABBBCCC (hexadezimale Darstellung)
auf die 32 Bit aufgeteilt. Dies hat natürlich zur Folge, dass die maximal darstellbaren
Kardinalitäten und die maximale Anzahl möglicher Rollen eingeschränkt ist:
• 8 Bit entfallen auf die Darstellung des Konstruktors (AA). Damit lassen sich theoretisch 32 verschiedene Konstruktoren darstellen.
• 12 Bit entfallen auf die Darstellung der Kardinalität (BBB), was hierbei einem
Maximalwert von 4096 entspricht.
• Die Anzahl der möglichen darstellbaren Rollen beträgt ebenfalls 4096 (CCC).
Diese Einschränkungen sind für heutige Anwendungen ein akzeptabler Wert. Im Gegenzug ermöglicht diese Darstellung einen effizienten Umgang mit Konzepten. Abbildung
5.1 zeigt beispielhaft die interne Darstellung einer TBox, die lediglich die Definition
C ≡ ¬∀r.A u (≥ 1 s) enthält9 .
5.3.2
Darstellung von ABoxen
Eine ABox enthält nach Kapitel 3 Individuen, Rollenverknüpfungen und Informationen darüber, welche Individuen garantiert verschieden sind. Für diese drei Kategorien existiert jeweils ein array dynamischer Größe (vector), da zum Beispiel jederzeit
9
Das Konzept C erhält hierbei der Index 2, 3 repräsentiert A. Die Rollen r und s erhalten die
Nummern 0 bzw. 1. Die Konstruktoren sind 6 für atomare Konzepte, 4 für Konjunktionen, 3 für
Allquantifikation und 0 für die Minimumkardinalitätseinschränkung.
50
Individuen
a1
r
Rollenbeziehungen a1
a2
a3
a4 .
r
a1
Abbildung 5.2: Eine einfache ABox
neue Individuen dazukommen können. Individuen (Individual) und Rollenbeziehungen (RoleLink) sind als eigene Klassen realisiert. Ein Individual hat dabei mehrere
RoleLinks. Jeder RoleLink fasst dabei alle Nachfolger, die zu einer Rolle gehören zusammen. Abbildung 5.2 zeigt eine einfache ABox, in der vier Individuen a1 , a2 , a3 und
a4 über (a1 , a2 ) : r, (a1 , a3 ) : r und (a3 , a4 ) : r miteinander in Beziehung stehen.
Für die Verknüpfung der Individuen untereinander mittels Rollenbeziehungen würden in einer normalen Anwendung pointer verwendet. Dies vereinfacht beim Programmieren den Umgang mit den Beziehungen. Bei der Erstellung einer Kopie einer ABox
würden jedoch nur die Werte dieser pointer kopiert, das heißt die entsprechenden Verknüpfungen in der Kopie verwiesen weiterhin auf das Original. Eine manuelle Ermittlung
der korrekten Individuen wäre aber zu komplex und zeitaufwändig, da in UUPR sehr
oft Kopien von ABoxen angelegt werden. Um diese Vermischung von Original und Kopie
effizienter zu umgehen werden in UUPR keine echten pointer verwendet, um Verweise
zu realisieren. Anstelle eines pointers enthält eine Rollenverknüpfung einen int-Wert,
der den Index eines Individuums im entsprechenden array angibt. Der Index bezieht sich
immer auf die dazugehörige ABox, ein Bezug zum Original besteht damit nicht mehr.
Analog dazu wird bei der Darstellung der Informationen über nicht verschmelzbare Individuen verfahren. Die Datenstrukturen der Klassen ABox, Individual und RoleLink
gestalten sich also folgendermaßen:
class ABox {
// Individuen
vector<Individual> individuals;
// Rollenbeziehungen
vector<RoleLink> links;
// Informationen ueber Merging: Das Individuum
// individuals[i] und die Individuen mit den Indices
// in distinctnessInformation[i] duerfen nicht
// verschmolzen werden.
vector<vector<int> > distinctnessInformation;
}
class Individual {
// Durch dieses Individuum instantiierte Konzepte,
5.3. IMPLEMENTIERUNG DER DATENSTRUKTUREN
51
// dargestellt durch ihre int-Repraesentation
vector<int> conceptSet;
// Rollennachfolger
// erste Zahl: Rolle
// zweite Zahl: Index des RoleLink-Objektes in
// ABox.links
map<int, int> roleLinks;
}
class RoleLink {
// Indices der Individuen in ABox.individuals
vector<int> individuals;
}
Für die Erstellung einer eigenständigen ABox-Kopie genügt es damit, den vom Compiler
automatisch generierten Kopierkonstruktor zu verwenden.
Die Implementierung der Methode run() stützt sich auf das in Kapitel 4 gezeigte
Design. Alle Tableauregeln werden dabei in der in Kapitel 3 erläuterten Reihenfolge
angewendet. Um zu verhindern, dass Konzepte mehrfach betrachtet werden, wird eine
Datenstruktur (in der obigen Darstellung der Klasse ABox aus Übersichtlichkeitsgründen nicht dargestellt) verwaltet, auf der alle noch nicht betrachteten Konzepte abgelegt
sind. Um Speicherplatz zu sparen sind in dieser Datenstruktur nur die Konzepte des
aktuell bearbeiteten Individuums abgelegt. Wenn die Datenstruktur leer ist und das
nächste Individuum bearbeitet werden soll, werden dessen Konzepte in die Datenstruktur eingefügt. Eine Ausnahme sind hierbei die Individuen, die bereits in der Ontologie
(d.h. der Eingabe) enthalten waren. Ihre Konzepte werden bei der Erstellung der ABox
alle zusammen in die Datenstruktur gelegt, um die in Kapitel 3 beschriebene Verarbeitungsreihenfolge zu gewährleisten. Ein Unterschied zum in Kapitel 4 gezeigten Skelett
von run() besteht darin, dass eine ABox, die Alternativen generiert, selbst auch zur
Bearbeitung einer Alternative weiterverwendet wird. Das heißt, dass beispielsweise für
eine Disjunktion mit drei Disjunkten nur zwei neue ABoxen erzeugt werden.
5.3.3
Implementierung des Workpools
In Abschnitt 4.2 wurde die Notwendigkeit zur prioritätsgesteuerten Verarbeitung der
ABoxen diskutiert. Die Findung einer geeigneten Datenstruktur für diese Aufgabe erfordert eine Abwägung zwischen den Vor- und Nachteilen der verschiedenen Möglichkeiten.
Die naheliegendste ist die Verwendung einer priority queue, die auf Basis eines heaps
arbeitet. Hier entstehen bei jeder Einfüge- und Löschoperation Kosten in Höhe von
O(log n), wobei n die Anzahl der Elemente im heap ist. Der zusätzlich benötigte Speicherplatz ist gering. Zwar ist die theoretische Komplexität eines heaps klein, es müssen
jedoch viele Elementaroperationen für die Aufrechterhaltung der heap-Eigenschaft ausgeführt werden.
Die andere getestete Alternative approximiert das Verhalten einer priority queue
lediglich. Dabei werden Jobs in kleinen Gruppen mit ähnlicher Priorität zusammen-
52
gefasst. Eine Löschoperation nimmt dann immer einen Job aus der Gruppe, die die
Jobs mit der höchsten Priorität zusammenfasst. Die Gruppen selbst werden in einem
dynamischen array verwaltet, sortiert nach den zugehörigen Prioritäten. Dies ähnelt im
Vorgehen dem Sortieralgorithmus bucket sort. Durch die Verwendung eines dynamischen
arrays kann die Anzahl der Gruppen leicht der maximalen tatsächlich vorkommenden
Priorität angepasst werden. Damit lässt sich erreichen, dass bei einer Löschoperation
schnell ein Element mit hoher Priorität gefunden wird. Der Nachteil dieser Lösung ist,
dass der zusätzlich genötigte Speicherplatz linear in der Höhe der höchsten vorkommenden Priorität ist10 . Dafür werden für Einfüge- und Löschoperationen nur sehr wenige
Elementaroperationen benötigt.
Obwohl mit der zweiten Alternative bessere Performance-Ergebnisse erzielt werden
konnten, fiel die Wahl letztendlich auf die priority queue. Erstens bewegte sich der
Laufzeitunterschied im unteren einstelligen Prozentbereich und zweitens ist die priority
queue unabhängiger von den tatsächlich vorkommenden Prioritätswerten. Dies erlaubt
eine größere Flexibilität im Falle einer Verwendung von Heuristiken für die Prioritäten
von ABoxen (siehe Kapitel 8).
10
Das heißt, der benötigte Speicherplatz ist exponentiell in der Länge dieser Zahl.
Kapitel 6
Evaluierung
Um den Erfolg des Ansatzes einer parallelen Implementierung des Tableau-Algorithmus
bewerten zu können, wurde UUPR auf verschiedene Arten getestet. Das Ziel war dabei,
innerhalb des begrenzten Zeitrahmens einer Diplomarbeit aussagekräftige Resultate zu
erhalten. Die dabei verwendeten Testplattformen, Testkonfigurationen und beschreibungslogischen Probleme sind im folgenden aufgelistet. Alle gelisteten Laufzeiten sind
mittels des Programms time gemessen und über drei Läufe gemittelt.
6.1
Verwendete Testbeispiele
Es wurde versucht eine kleine Anzahl von aussagekräftigen Testfällen auszuwählen,
anhand derer die Performancetests durchgeführt werden können. Drei Testfälle wurden
betrachtet1 :
• Der erste Testfall ist der aus [Lie06] übernommene Testfall 10a. Dieser Testfall definiert ein Konzept, bei dem viele Rollennachfolger erzeugt werden, die aufgrund
einer Maximumkardinalitätseinschränkung zusammengefasst werden müssen. Bei
der Überprüfung dieses Konzeptes auf Erfüllbarkeit entsteht also eine große Menge
an Nichtdeterminismus. Die entstehenden Rollennachfolger sind dabei so qualifiziert, dass das Zusammenfassen auf jeden Fall zu einem Widerspruch führt. Für
die hier gemachten Tests wurde er gegenüber [Lie06] leicht vereinfacht, indem die
Anzahl der existentiellen Quantifikationen reduziert wurde.
Bei diesem Testfall müssen sehr viele einfache Teilprobleme gelöst (bzw. ABoxen
bearbeitet) werden. Er eignet sich also zur Beurteilung der Auswirkungen des
durch Synchronisation entstehenden Overheads. Im folgenden wird dieser Fall als
Testfall 1 bezeichnet.
• Um den maximal möglichen Geschwindigkeitsgewinn von UUPR zu demonstrieren
wird eine Variante des Testfalls 28 aus [Lie06] eingesetzt. Das im Originaltestfall
definierte Konzept enthält keinen Nichtdeterminismus. Seine Komplexität beruht
1
Darstellungen in abstrakter Syntax finden sich in Anhang A, für DIG-Realisierung der Eingaben
siehe Anhang C.
53
54
KAPITEL 6. EVALUIERUNG
darauf, dass aufgrund seiner Konstruktion beim Beweis sehr viele Individuen erstellt werden müssen.
Da UUPR nur auf Nichtdeterminismus basierende Komplexität parallel verarbeiten kann wurde der Testfall erweitert: Es wird eine Disjunktion von acht dem
Original ähnlichen Konzepten untersucht. Jede einzelne Disjunkte modifiziert das
Original auf zwei Arten. Erstens wurde durch die Einfügung eines Widerspruchs
sichergestellt, dass überhaupt alle Disjunkten betrachtet werden müssen (das Gesamtkonzept wird dadurch auch unerfüllbar). Um zu vermeiden, dass die Bearbeitung durch gecachete Informationen ungewollt vereinfacht wird, wurden zweitens
die verwendeten atomaren Konzepte jeder Disjunkte anders benannt. Diese Konstruktion hat die Folge, dass acht relativ schwierige Teilprobleme auf mehrere
Threads verteilt werden. Die einzelnen Threads rechnen dann ohne Wechselwirkungen parallel. Damit wird der Parallelisierungsoverhead so gering wie möglich
gehalten und das volle Potential der parallelen Verarbeitung kann ausgeschöpft
werden. Dieser Testfall trägt die Nummer 2.
Da die Optimierung semantic branching den Umgang mit Disjunktionen dahingehend verändert, dass nicht mehr jeder Thread eine Disjunkte bearbeitet, wurde
sie für diesen Testfall ausgeschaltet.
• Die in [HM00] beschriebene Beispiel-Ontologie reizt den in UUPR implementierten Sprachumfang ALCN Hr+ gut aus. Sie verwendet Kardinalitätsrestriktionen,
eine kleine Rollenhierarchie, GCIs und definiert eine kleine ABox. Diese Ontologie
wurde daher eingesetzt um die Performance in einer möglichst realistischen Anwendung zu simulieren. Die ABox an sich ist dabei erfüllbar. Um zu zeigen, dass
das Individuum betty eine Instanz des Konzepts mother having only sisters ist,
wird mittels der zusätzlichen Aussage betty : ¬mother having only sisters ein
Instanztest simuliert. Die dann unerfüllbare ABox wird als Testfall 3 verwendet.
6.2
Verwendete Testumgebungen
Um eine Beeinflussung der Testresultate durch einzelne Testplattformen auszuschließen, wurden verschiedene Parallelrechner für die Tests verwendet. Um die prinzipielle
Leistungsfähigkeit des Ansatzes zu untersuchen, wurden zwei an der Universität Ulm
vorhandene Parallelrechner verwendet. Ein mit einem Doppelkernprozessor ausgestatteter Rechner wurde eingesetzt, um die Eignung für moderne Einzelplatzsysteme zu
testen. Als Referenz für die Messungen diente ein normaler Einprozessorrechner. Folgende Systeme wurden also verwendet:
• Das Rechenzentrum der Universität Ulm verfügt über vier leistungsstarke Parallelrechner der Firma Sun. Jeder dieser SMP-Rechner hat 12 UltraSPARC IV+
Dual Core-Prozessoren, die jeweils mit 1,8 GHz getaktet sind. Der Hauptspeicher
eines solchen Rechners ist 96 GB groß. Theoretisch ist der maximale speed-up
auf diesen Rechnern also 24. Leider sind alle vier Rechner oft stark ausgelastet,
so dass es zu Verfälschungen der Ergebnisse kommen kann. Daher wird bei auf
6.3. TESTMODI
55
diesem Parallelrechner gewonnenen Ergebnissen immer zusätzlich die Auslastung
zum Zeitpunkt der Messung mit angegeben.
• Das Institut für künstliche Intelligenz besitzt einen Compute-Server, welcher ebenfalls über geteilten Speicher nach dem SMP-Modell verfügt. Der Compute-Server
beherbergt zwei Dual Core Opteron-Prozessoren der Firma AMD. Jeder dieser 64
Bit-Prozessoren ist mit 2,2 GHz getaktet, die Größe des Hauptspeichers beträgt
16 GB. Auf diesem Rechner war es möglich, nicht durch andere laufende Prozesse
verfälschte Testergebnisse zu erhalten.
• Um den Nutzen auf modernen Mehrkernprozessorplattformen zu testen wurde ein
Rechner mit einem Dual Core-Prozessor von AMD getestet, dessen Kerne mit je
1 GHz getaktet sind. Dieser Rechner verfügt über 1 GB Arbeitsspeicher.
• Um einen Bezugspunkt für die Performance von UUPR zu erhalten wurden die
Testläufe noch auf einer normalen Einprozessormaschine wiederholt. Diese verfügt
über einen mit 3 GHz getakteten Intel Pentium 4 Prozessor und 1 GB Hauptspeicher.
Das Betriebssystem des Sun Parallelrechners ist Solaris 10, alle anderen Systeme arbeiten unter Linux (Kernel Version 2.6).
6.2.1
Verfügbarkeit benötigter Bibliotheken
In C++ implementierte Programme sind nicht per se plattformunabhängig. Insbesondere sind nicht alle der in UUPR verwendeten Bibliotheken auf allen Plattformen verfügbar. Zwar konnten mit xerces-c (Version 2.7) und Boost.Threads (Version 1.33.1) die
für die Lauffähigkeit von UUPR unbedingt notwendigen Bibliotheken auf allen Plattformen eingesetzt werden. Einige der unterschiedlichen Speichermanager allerdings sind
nur auf einem Teil der Plattformen einsetzbar. So gelang es nicht, die Hoard-Bibliothek
auf dem Compute-Server des Instituts für künstliche Intelligenz zu übersetzen. Versionen von Intel TBB existieren wiederum nur für Intel-kompatible Prozessoren, weshalb
es nicht auf dem UltraSPARC-Rechner eingesetzt werden konnte.
Für die Tests auf dem Compute-Server des Instituts für KI, dem Dual-Core-Rechner
und dem Einzelprozessorrechner wurde Intel TBB in der Version 1.1 verwendet. Tests
auf dem UltraSPARC-Computer wurden mit Hoard 3.6.2 durchgeführt. Zur Übersetzung wurde auf der UltraSPARC-Plattform der Sun C++ Compiler in der Version 5.8
verwendet, auf allen anderen Plattformen kam der GNU C++ Compiler in der Version 4.1 zum Einsatz. UUPR wurde jeweils mit der höchstmöglichen Optimierungsstufe
übersetzt.
6.3
Testmodi
Bei den Tests wurden verschiedene Aspekte der Geschwindigkeit von UUPR untersucht.
Im folgenden werden die gemachten Tests vorgestellt.
56
Plattform
Testfall 1
Testfall 2
Testfall 3
Sun Server, 1 Worker
181.931s
60.519s
53.764s
Sun Server, bester Wert (Anzahl d. Worker) 56.834s (8) 8.152s (8) 13.122s (8)
KI Server, 1 Worker
37.837s
17.556s
13.111s
KI Server, bester Wert (Anzahl d. Worker)
13.702s (8) 4.546s (4) 3.965s (7)
Dualcore, 1 Worker
38.219s
16.505s
11.431s
Dualcore, bester Wert (Anzahl d. Worker)
20.927 (12) 8.784s (8) 6.725s (12)
Singlecore, 1 Worker
70.262s
26.138s
20.543s
Singlecore, bester Wert (Anzahl d. Worker) 56.917s (8) 26.138s (1) 20.543s (1)
Tabelle 6.1: Absolute Laufzeiten
6.3.1
Einfluss der Anzahl der Worker-Threads
Um das Verhalten der Performance von UUPR in Abhängigkeit der Anzahl der WorkerThreads zu ermitteln wurde jedes Testbeispiel auf den verfügbaren Plattformen getestet.
Die Auslastung des verwendeten Sun Parallelrechners betrug dabei zwischen 25% und
55%, so dass Testläufe mit bis zu 12 Threads ohne signifikante Geschwindigkeitseinbußen
durchgeführt werden konnten. Die gezeigten Diagramme kommen dabei folgendermaßen
zustande: Um eine anschauliche Darstellung zu erhalten, wurden die gemessenen Werte jeweils mit der Performance unter Verwendung eines Worker-Threads in Beziehung
gesetzt. Die gezeigten Werte repräsentieren also den speed-up zur Basis eines WorkerThreads2 . Die Abbildung 6.1 zeigt die Ergebnisse für Testfall 1, die Abbildungen 6.2
bzw. 6.3 entsprechend die Ergebnisse für die Testfälle 2 und 3.
Da nicht nur die relativen Werte interessant sind, zeigt Tabelle 6.1 absolute Laufzeiten für jede Plattform. Es ist für jeden Testfall jeweils die Laufzeit für einen WorkerThread und die schnellste gemessene Laufzeit angegeben.
6.3.2
Vergleich mit anderen verfügbaren Systemen
Wie effizient UUPR tatsächlich arbeitet kann erst im Vergleich mit anderen Systemen
bewertet werden. Dazu wurden die Systeme Pellet3 [SPG+ 06] in den Versionen 1.3 und
1.4 und KAON24 verwendet. Weder das bereits in Kapitel 2 beschriebene Pellet noch
KAON2 arbeiten parallel. KAON2 verwendet auch keinen Tableau-Algorithmus, sondern formuliert eine gegebene Ontologie in disjunctive datalog um [HMS04]. Sowohl
Pellet in beiden Versionen als auch KAON2 sind in Java implementiert. KAON2 unterstützt die Beschreibungslogik SHIQ(D), was gegenüber UUPR einer Erweiterung
der Sprachmächtigkeit um Möglichkeiten zur Definition von inversen Rollen (I), qualifizierten Kardinalitätseinschränkungen (Q) und konkreten Wertebereichen (D) darstellt.
2
In Ermangelung einer sequentiellen Referenzimplementierung zur korrekten Berechnung des speedups wird hier der speed-up zur Basis eines Worker-Threads verwendet.
3
http://pellet.owldl.com/
4
http://kaon2.semanticweb.org/
6.3. TESTMODI
57
Abbildung 6.1: speed-ups für Testfall 1
Die Sprachmächtigkeit von Pellet 1.3 und 1.4 umfasst SHOIQ(D), was SHIQ(D) um
Möglichkeiten zur Definition von Klassen als Menge von Individuen (O) erweitert.
Die Vergleichstests wurden auf der UltraSPARC-Plattform ausgeführt. Für KAON2
und Pellet wurde der Java Virtual Machine mittels der Option -Xmx1000m 1000 MB
Speicher zugesichert. UUPR arbeitete mit 8 Worker-Threads. Um gleichzeitig den Einfluss der in UUPR implementierten Optimierungen auf die Performance zu ermitteln
wurden die Tests für UUPR mit deaktivierten Optimierungen wiederholt. Laufzeiten
von 5 Minuten und länger sind in der Tabelle nur als timeout angegeben. Falls ein Reasoner mangels Speicher abstürzte, ist dies mit memout gekennzeichnet. UUPR stürzte
während der Tests mit deaktivierten Optimierungen bei Testfall 3 nach ca. einer Minute
Laufzeit mit einem Speicherzugriffsfehler ab. Die Ursache konnte nicht geklärt werden.
Eine Wiederholung dieses Tests auf dem Compute Server des Instituts für KI ergab
keinen Speicherzugriffsfehler, allerdings wurde dieser Test nach ca. 20 Minuten Laufzeit
abgebrochen. Tabelle 6.2 zeigt die gemessenen Werte.
58
System
Testfall 1 Testfall 2
Testfall 3
KAON2
memout
timeout
2.490s
Pellet 1.3
2.016s 182.571s
2.022s
Pellet 1.4
timeout 144.921s
2.375s
UUPR mit Optimierungen
56.834s
8.152s
13.122s
UUPR ohne Optimierungen
60.401s
8.794s Speicherzugriffsfehler
Tabelle 6.2: Vergleich mit anderen Systemen
6.4. INTERPRETATION DER ERGEBNISSE
59
6.3.3
Einfluss des Speichermanagers
Um die Bedeutung der Verwendung eines geeignetes Speichermanagers zu demonstrieren ist hier exemplarisch für den Testfall 2 ein Vergleich zwischen der Verwendung des
std::allocators und Hoard angegeben. Abbildung 6.4 zeigt die auf dem Sun Parallelrechner gemessenen Laufzeiten.
6.4
Interpretation der Ergebnisse
Die Bedeutung der Verwendung eines geeigneten Speichermanagers wird in Abbildung
6.4 klar deutlich. Unter Verwendung des std:allocators konnte durch eine Erhöhung
der Anzahl der Worker-Threads keine Verbesserung der Laufzeit erreicht werden, im
Gegenteil: UUPR war hier unter Verwendung eines Worker-Threads mit Abstand am
schnellsten.
In den Abbildungen 6.4 und 6.2 wird auch deutlich, dass die Speicherallokation mit
einem geeigneten Speichermanager keinen Flaschenhals darstellt. Betrachtet man in
60
Abbildung 6.4: Einfluss des Speichermanagers
Abbildung 6.2 die Werte für einen, zwei, vier und acht Threads auf dem Sun Parallelrechner, so kann man auf einen in der Anzahl der Worker-Threads linearen Verlauf der
Laufzeit schließen.
Einbrüche im speed-up für drei, fünf, sechs und sieben Worker-Threads erklären sich
aus der Verteilung des Aufwands auf die Worker-Threads: Bei Testfall 2 müssen acht
Disjunkte, die sich in auf acht gleich aufwändige Jobs bzw. ABoxen aufteilen, auf die
vorhandenen Worker-Threads verteilt werden. Das heißt, dass es zum Beispiel im Fall
von sieben Worker-Threads sechs Worker-Threads gibt, die eine ABox bearbeiten müssen, und einen Worker-Thread, der zwei ABoxen bearbeiten muss. Da auf das Ergebnis
aller ABoxen gewartet werden muss, unterscheidet sich die Gesamtlaufzeit bei sieben
Worker-Threads nicht wesentlich von der Gesamtlaufzeit unter Verwendung von vier
Worker-Threads (wo jeder Worker-Thread genau zwei ABoxen bearbeiten muss). Die
Abbildungen 6.5 und 6.6 illustrieren diesen Sachverhalt. Die acht ABoxen sind dabei
von a1 bis a8 durchnummeriert. Ein höherer speed-up als acht ist in diesem Beispiel
nicht möglich, da lediglich acht Jobs erzeugt werden.
Die Testfälle 1 und 3, die jeweils viele kleine Einzelprobleme erzeugen, belasten die
6.4. INTERPRETATION DER ERGEBNISSE
Worker 1 a1
61
a8 .
Worker 2 a2
Worker 3 a3
Worker 4 a4
Worker 5 a5
Worker 6 a6
Worker 7 a7
.
Abbildung 6.5: Verteilung des Aufwands für Testfall 2 bei sieben Worker-Threads
Worker 1 a1
a5 .
Worker 2 a2
a6
Worker 3 a3
a7
Worker 4 a4
a8
.
Abbildung 6.6: Verteilung des Aufwands für Testfall 2 bei vier Worker-Threads
entworfene Architektur stärker. Hier ist zu verzeichnen, dass der speed-up schon ab der
relativ kleinen Anzahl von drei bis fünf Worker-Threads abflacht. Da mit Testfall 2 die
Speicherverwendung als Flaschenhals ausgeschlossen werden konnte, muss hier eine andere Ursache vorliegen. Offenbar verhindert der synchronisierte Zugriff auf gemeinsame
Datenstrukturen wie Cache und Workpool eine höhere Performance. Insgesamt aber
lässt sich bei allen drei Testfällen eine deutliche Geschwindigkeitserhöhung beobachten.
Die Performance der Vergleichssysteme ist sehr durchwachsen. Dies macht es schwierig, hier eine Aussage zu treffen. Obwohl Pellet 1.4 eine gegebene Ontologie vor dem
Beweisprozess analysiert, entsprechend der ermittelten Sprachmächtigkeit eine Strategie auswählt und für SHN eigens eine Strategie existiert, konnte es für Testfall 2 in der
gegebenen Zeit kein Ergebnis präsentieren. Der Vorgängerversion Pellet 1.3 bereitete
dieser Testfall keine Probleme. KAON2 kam mit den Testfällen 1 und 2 nur schlecht
zurecht.
UUPR ist für Testfall 2 deutlich schneller als die Vergleichssysteme. Selbst wenn
man miteinbezieht, dass UUPR hier mit 8 Worker-Threads ausgeführt wurde, liegt die
summierte Laufzeit aller Threads immer noch weit unter der mit den anderen Systemen gemessenen Laufzeit. Dieser Effekt könnte einerseits durch den Einsatz effizienter
Datenstrukturen und die im Gegensatz zu Java-Programmen native Übersetzung des
Programmcodes zustande kommen. Andererseits könnte dies auf die höhere Sprach-
62
mächtigkeit der Vergleichssysteme zurückzuführen sein.
Für den Testfall 3, der den Umgang mit einer möglichst realistischen Ontologie
simulieren soll, sind die etablierten Systeme allerdings im Vorteil. Hier macht sich bei
UUPR offenbar das Fehlen der nicht implementierten Optimierungen bemerkbar.
Die Deaktivierung der Optimierungen hatte für die Testfälle 1 und 2 nur geringen
Einfluss. Keine der in UUPR implementierten Optimierungen kann die Komplexität
dieser Probleme entscheidend verringern. UUPR ohne Optimierungen produzierte für
Testfall 3 einen Absturz, so dass hier kein Vergleichswert vorliegt. Der gleiche Test auf
dem Compute Server des Instituts für KI wiederholt ergab keinen Absturz, aber eine sehr
hohe Laufzeit. Für die erfolgreiche Bearbeitung dieses Testfalls sind die implementierten
Optimierungen also offenbar unverzichtbar.
Kapitel 7
Verwandte Arbeiten
Bei der Suche nach zu dieser Diplomarbeit verwandten Arbeiten fiel auf, dass es offenbar
in neuerer Zeit keine Bestrebungen gab, die Möglichkeiten zur Parallelität in der Verarbeitung von Beschreibungslogiken systematisch auszunutzen. Aktuelle beschreibungslogische Systeme wie Racer [HM03], Pellet [SPG+ 06] oder FaCT++ [TH06] arbeiten rein
sequentiell. Um einen etwas weiter gefassten Überblick zu erlauben wurden daher auch
Arbeiten über Parallelverarbeitung in Beweissystemen für andere Logiken betrachtet.
7.1
Parallele Verarbeitung von Beschreibungslogiken
Ideen zur Parallelverarbeitung in Beschreibungslogiken finden sich in [BQ95]. Dort werden zwei Ansätze zur Parallelisierung Systems FLEX beschrieben. Der erste Ansatz,
genannt Farm-Parallelität, ähnelt dem Ansatz in UUPR dahingehend, dass dabei ein
Master-Prozess mit mehreren Worker-Prozessen kommuniziert. Mit diesem Ansatz wurden dort allerdings keine guten Ergebnisse erzielt, wie die Autoren selbst schreiben.
Eine Implementierung des zweiten Ansatzes, der auf verteilten Objekten basiert, erbrachte bessere Resultate. Allerdings wurde nur anhand eines Beispiels getestet. Da
FLEX allerdings keinen Tableau-Algorithmus verwendet, lässt es sich seine parallele
Implementierung schwer mit UUPR vergleichen.
7.2
Parallele Verarbeitung in anderen Logiken
In [Pon96] werden Möglichkeiten zur Parallelverarbeitung in Prolog-Programmen betrachtet. Es wird beschrieben, wie sich die Semantik von Prolog-Programmen bei einer
parallelen Verarbeitung erhalten lässt. Dazu muss aufgrund der nicht-logischen Zusätze
in Prolog (insbesondere die Bedeutung der Klauselreihenfolge) zwischen unabhängiger,
beschränkter und abhängiger Parallelität unterschieden werden. Betrachtungen werden
sowohl für UND- als auch für ODER-Parallelität angestellt. Das Paper nennt allerdings weder Performanceergebnisse noch eine konkrete Implementierung eines parallelen
Prolog-Systems.
63
64
KAPITEL 7. VERWANDTE ARBEITEN
Die Ausdrucksmächtigkeiten von Prolog-Programmen und Beschreibungslogiken unterscheiden sich stark [GHVD03]. Die Ausdrucksmächtigkeit der Prädikatenlogik erster
Ordnung (First Order Logic, FOL) hingegen ist eine echte Obermenge der Ausdrucksmächtigkeit von Beschreibungslogiken. Ein paralleler Beweiser für FOL kann also auch
beschreibungslogische Probleme, insbesondere in ALCN Hr+ formulierte Probleme, parallel bearbeiten.
Das erste tableaubasierte, auf ODER-Parallelität aufbauende Beweissystem war Parthenon, ein FOL-Beweiser [BCLM89]. Dieses System wurde bald zu PARTHEO [SL90]
weiterentwickelt, welches ebenfalls einen ODER-parallelen Tableau-Ansatz verwendet
und mittels Nachrichtenaustausch implementiert ist. Mit PARTHEO konnte bei einigen Problemen eine signifikant geringere Laufzeit erreicht werden.
Ein anderer Ansatz für einen parallelen Beweiser wird in [Sch96] beschrieben. SiCoTHEO ist ebenfalls ein paralleles System für die Prädikatenlogik erster Ordnung. Der
darin verfolgte Ansatz entspricht dem einer Parallelität durch Konkurrenz. Dazu werden mehrere Instanzen eines sequentiell arbeitenden Beweisers auf einem Parallelrechner ausgeführt. In jeder Instanz sind dabei Parameter, die das Verhalten des Beweisers
beeinflussen, variiert. Sobald eine Instanz ein Ergebnis berechnet hat, wird die Verarbeitung abgebrochen. Ein offensichtlicher Nachteil dieses Ansatzes ist, dass Ineffizienzen
des zugrundeliegenden Beweisers, die nicht durch Parameter beeinflussbar sind, in allen
parallel arbeitenden Instanzen vorhanden sind. Falls ein gegebenes Problem nicht durch
einen Parameter in einer Instanz zum Trivialfall wird ist außerdem kein großer speed-up
zu erwarten.
Eine Verfeinerung des Ansatzes von [Sch96] wird im System p-SETHEO realisiert
[Wol98]. Dort wird versucht, die einzelnen Instanzen so miteinander zu verknüpfen, dass
bereits von einer Instanz besuchte Teile des Suchraums nicht von anderen durchsucht
werden. Dieser Ansatz wird dort als Strategie-Parallelität bezeichnet. Probleme hierbei
sind eine geeignete Auswahl der Strategien sowie die Skalierbarkeit mit der Anzahl der
Prozessoren, da die Anzahl der hinreichend verschiedenen Strategien im wesentlichen
die Anzahl sinnvoll einsetzbarer Prozessoren bestimmt.
Für eine Klassifizierung der möglichen Parallelisierungsansätze für FOL sei der interessierte Leser auf [Bon00] verwiesen. Dort werden verschiedene Ansätze kurz diskutiert
und in einer Hierarchie miteinander in Beziehung gesetzt.
Kapitel 8
Bewertung und Ausblick
8.1
Kritik
Diese Arbeit hat gezeigt, dass der Einsatz von Parallelität beschreibungslogische Tableaubeweise stark beschleunigen kann. Die in Kapitel 6 gezeigten Ergebnisse demonstrieren, dass sich das Tableauverfahren trotz seiner Komplexität für eine Parallelverarbeitung eignet. Bei allen verwendeten Testbeispielen konnte durch die Erhöhung der
Anzahl der arbeitenden Threads eine deutliche Geschwindigkeitserhöhung festgestellt
werden. Es hat sich gezeigt, dass im Ansatz der Parallelverarbeitung in beschreibungslogischen Systemen viel Potential steckt, in einigen Bereichen aber noch Arbeit investiert
werden muss.
Um eine parallele Verarbeitung zu ermöglichen musste eine Entscheidung für einen
Ansatzpunkt getroffen werden. Die Parallelisierung anhand von nichtdeterministischen
Tableauregeln hat sich dabei bewährt. Mit der Entscheidung, konjunktive Regeln nicht
zu parallelisieren, ließ sich die Findung eines Beweisergebnisses vereinfachen und die
Granularität erhöhen. Diese Entscheidung impliziert, dass sich beschreibungslogische
Probleme, die keinen Nichtdeterminismus enthalten, mit UUPR nicht parallel verarbeiten lassen. In praktischen Anwendungen ist dieser Fall allerdings unwahrscheinlich.
Insbesondere unter Anwesenheit von GCIs enthalten realistische Anwendungen genug
Nichtdeterminismus, dass durch parallele Verarbeitung ein Geschwindigkeitsgewinn erzielt werden kann. Damit wird mit diesem Ansatz ein große Klasse von Problemen
abgedeckt.
Die Verwendung eines Modells mit gemeinsamem Speicher machte den Einsatz von
speziell entwickelten Speichermanagern nötig, da in UUPR sehr oft kleine Mengen an
Speicher von den verschiedenen arbeitenden Threads angefordert werden. Durch die
Verwendung dieser Speichermanager ließ sich der Flaschenhals weitestgehend beseitigen, wie die Ergebnisse in Kapitel 6 zeigen, da sich bei einigen Problemen eine lineare
Skalierung des speed-ups beobachten ließ.
Selbst bei beschreibungslogischen Problemen, die die entworfene Architektur durch
die stark parallele Verarbeitung einfacher Probleme ungünstig beanspruchen, lässt sich
noch eine deutliche Erhöhung der Geschwindigkeit beobachten. Allerdings wurde bei
dieser Art Problem der Workpool und/oder der Cache schnell zu einem Flaschenhals.
65
66
KAPITEL 8. BEWERTUNG UND AUSBLICK
Es hat sich gezeigt, dass sich für diese Problemklasse bis zu einer Anzahl von drei
bis vier Worker-Threads eine gute Effizienz erreichen lässt. Damit ist die Architektur
in ihrer derzeitigen Form für einen massiv parallel arbeitenden Rechner zwar nicht
uneingeschränkt geeignet. Für eine Verwendung auf Heimcomputern der kommenden
Generation, die mit zwei oder gar vier Prozessoren arbeiten, ist sie aber gut geeignet.
Es besteht auch Anlass zur Hoffnung, dass mit der Integration weiterer Optimierungen,
die die Granularität der Parallelisierung verbessern und damit den Workpool entlasten
(siehe Abschnitt 8.2), eine bessere Skalierung mit der Anzahl der Prozessoren erreicht
werden kann.
Tests mit deaktivierten Optimierungen zeigen, dass durch Parallelverarbeitung alleine kein Geschwindigkeitsvorteil gegenüber herkömmlichen Reasonern zu erreichen ist.
Der durch manche Optimierungen entstehende Overhead muss daher in Kauf genommen
werden um die Performance anderer Reasoner zu erreichen und zu übertreffen. Durch
Parallelverarbeitung entsteht auch erhöhter Speicherplatzbedarf. Wo in einer sequentiellen Implementierung nur von einem Thread Speicher angefordert wird, arbeiten in
einer parallelen Implementierung viele Threads, die Speicher benötigen, nebeneinander
her. Parallelverarbeitung kann auch, im Gegensatz zu manchen anderen Optimierungen, nie einzelne Probleme trivialisieren, das heißt, ihre Bearbeitungsgeschwindigkeit
um Größenordnungen verbessern. Im Gegenzug funktioniert sie bei einer sehr großen
Klasse von Problemen und stellt daher eine zuverlässige Methode dar, Reasoning zu
beschleunigen.
Die prototypische Implementierung beinhaltet einige Einschränkungen. Sie verwendet beispielsweise die UNA, die in Anwendungen im Semantic Web hinderlich ist. Das
implementierte caching ist lediglich eine vereinfachte Version, eine mögliche vollständige
Realisierung ist in Abschnitt 8.2 beschrieben. Durch die unterschiedliche Verfügbarkeit
der benötigten Bibliotheken ist eine wirkliche Plattformunabhängigkeit schwer zu erreichen. Eine automatische Wahl einer geeigneten Anzahl von Worker-Threads ist ebenfalls
nicht möglich, der Benutzer muss diesen Parameter selbst ermitteln. Auch gängige Dienste wie die Berechnung einer Taxonomie wurden in der prototypischen Implementierung
ausgeklammert.
Insgesamt überwiegen die Vorteile der Parallelverarbeitung die Nachteile deutlich.
Der Ansatz ist allgemein genug, um damit für einen Großteil der beschreibungslogischen Probleme eine Geschwindigkeitsverbesserung zu erzielen. Durch die Flexibilität
der Workpool-Architektur lässt sich der Parallelitätsgrad steuern und eine gleichmäßige
Auslastung der vorhandenen Prozessorleistung erreichen.
8.2
Weiterführende Arbeiten
Viele weiterführende Ideen konnten im Rahmen dieser Arbeit nicht mehr betrachtet
werden. Im Folgenden werden mögliche Weiterentwicklungen aufgezeigt, untergliedert
in denkbare Verbesserungen des parallelen Designs, Integration weiterer bekannter Optimierungen des Tableau-Algorithmus’ und Erweiterungen des Ansatzes auf ausdrucksmächtigere Beschreibungslogiken.
8.2. WEITERFÜHRENDE ARBEITEN
8.2.1
67
Verbesserungen der Architektur
Viel Feinarbeit kann sowohl in die Darstellung als auch in die Verarbeitung der ABoxen
gesteckt werden. In UUPR wird bei der Erstellung von Alternativen ein vollständige Kopie der zugrundeliegenden ABox erzeugt. Falls diese eine große ABox mit vielen, bereits
fertig bearbeiteten Individuen ist, wird dabei viel Speicherplatz durch die redundante Speicherung dieser Individuen verschwendet. Eine mögliche Lösung dieses Problems
besteht darin, dass bei der Erzeugung von alternativen ABoxen Individuen, die in allen
Alternativen gleich sind, nicht kopiert werden. Stattdessen werden diese Individuen nur
einmal gespeichert, jede ABox verwaltet dann lediglich einen Zeiger auf die gemeinsamen
Individuen. Eine effiziente Implementierung von zwischen Alternativen geteilten Individuen ist eine Herausforderung, insbesondere, wenn der unterstützte Sprachumfang um
inverse Rollen erweitert wird (siehe Abschnitt 8.2.3).
Es ist auch eine Optimierung denkbar, bei der kleine1 beschreibungslogische Probleme mit einem sequentiellen Beweiser bearbeitet werden. Dazu wäre eine Heuristik
nötig, die in der Lage ist, die Problemgröße eines beschreibungslogischen Teilsproblems
einzuschätzen. Eine solche Vorgehensweise wirkt sich auf zwei Arten positiv auf die
Performance aus: Erstens kommen sequentielle Implementierungen ohne den mit einer
Parallelisierung verbundenen Overhead aus und haben damit bei einfachen Problemen
einen Geschwindigkeitsvorteil. ABoxen, die einfache Probleme repräsentieren, könnten
dadurch schneller bearbeitet werden. Zweitens werden diese einfachen Probleme dann
unter Umgehung des Workpools bearbeitet, womit die Bedeutung des Workpools als
möglicher Flaschenhals für die Gesamtperformance gemindert wird. Die sequentielle
Verarbeitung kleiner Probleme entspricht einer Optimierung der Granularität der Parallelisierung.
Falls bei einer Verwendung des Designs von UUPR mit vielen parallel rechnenden
Einheiten die Verwendung des Workpools zum Flaschenhals wird, gibt es weitere Möglichkeiten, dieses Problem zu entschärfen. Der zentrale Workpool könnte etwa durch
eine hierarchische Anordnung mehrerer Pools ersetzt werden. Die parallelen Recheneinheiten wären dann in Gruppen organisiert, die sich jeweils einen Pool teilen. Falls in
einem Pool keine Jobs mehr verfügbar sind, müssten die vorhandenen Jobs entsprechend
umverteilt werden.
Es gibt auch eine einfachere Möglichkeit, den Pool zu entlasten: Anstatt einem Job
nimmt ein Worker immer gleich mehrere Jobs zur Bearbeitung aus dem Pool. Die Anzahl
der Jobs, die auf einmal aus dem Pool entnommen werden ist allerdings ein sehr schwer
zu justierender Parameter. Durch eine zu große Wahl dieses Parameters kann es zu
einer ungünstigen Verteilung von Jobs auf Worker kommen, so dass keine gleichmäßige
Auslastung mehr zustande kommt. Hier würde sich wiederum der Einsatz einer Heuristik
zur Bestimmung einer guten Anzahl anbieten.
1
Klein bedeutet hier hinreichend einfach.
68
8.2.2
Implementierung weiterer Optimierungen
In dieser Arbeit fast ganz ausgeklammert wurde die Verwendung von Heuristiken, da
die Entwicklung von Heuristiken lange Testreihen und Erfahrungswerte voraussetzt, die
den Rahmen dieser Arbeit gesprengt hätten. In sequentiellen Implementierungen werden
Heuristiken beispielsweise dazu verwendet, lokal Entscheidungen bezüglich der Verarbeitungsreihenfolge in Disjunktionen zu treffen (Heuristische Suche, siehe Abschnitte
3.2 und 4.3). In einer parallelisierten Implementierung ist die Entsprechung der heuristischen Suche die Bewertung von zu bearbeitenden ABoxen mit einer Priorität. Im
Gegensatz zu sequentiellen Implementierungen, bei denen meist nur lokal Entscheidungen mithilfe von Heuristiken gefällt werden, erlaubt die Verwendung eines ABox-Pools
in UUPR eine globalere Sicht: Die Priorität einer ABox setzt sich dann aus der bisher auf die ABox verwendete Arbeit und einer heuristischen Bewertung, die angibt, wie
vielversprechend die Evaluierung dieser ABox ist, zusammen. Auf diese Weise kann der
Suchraum der zu evaluierenden ABoxen wie mit einem A∗ -Algorithmus bearbeitet werden. Wenn es gelingt eine gute solche Heuristik zu entwickeln, ist dieser Ansatz sehr
vielversprechend.
Dependeny Directed Backtracking
Wie in Abschnitt 4.3 bereits erwähnt, ist die geeignete Adaption von dependency directed backtracking eine Herausforderung in der Weiterentwicklung von UUPR. Diese
Optimierung ist in sequentiellen Implementierungen von großer Bedeutung [HPS99]. Sie
erlaubt in vielen Fällen eine deutliche Verkleinerung des Suchraums und damit einen
hohen Performancegewinn. Die Idee hinter dependency directed backtracking ist die
Vermeidung der Betrachtung von Alternativen. Wenn aufgrund von beim Beweis gewonnenen Erkenntnissen bekannt ist, dass sie nicht zum Erfolg führen können, werden
sie übersprungen. Sequentielle Implementierungen realisieren dies beim Auftreten eines
Widerspruchs durch vorzeitiges Zurückspringen an den Verzweigungspunkt, an dem die
am Widerspruch beteiligten Konzepte hinzugefügt wurden. Anders ausgedrückt, alle
Alternativen, die die am Widerspruch beteiligten Konzepte ebenfalls enthalten, werden
nicht betrachtet. In UUPR werden bei einer Verzweigung alle Alternativen (in Form von
ABoxen, die in den Pool gelegt werden) auf einmal erzeugt. Das Äquivalent zum Zurückspringen wäre hier die Herausnahme der entsprechenden ”Geschwister”-Alternativen
und der aus ihnen entstandenen Alternativen aus dem Pool, also dependency directed
cancellation. Dazu müsste eine Methode entwickelt werden, die es erlaubt, alle zu einem
Verzweigungspunkt gehörigen Alternativen zu identifizieren. Sie sollte in der Lage sein,
schnell alle betroffenen Alternativen zu identifizieren und aus dem Pool zu löschen. Insbesondere müssen auch bereits durch einen Worker in Bearbeitung befindliche betroffene
Alternativen bei der Löschung so behandelt werden, dass durch sie erzeugte Alternativen nicht in den Pool gelangen. Eine Herausforderung dabei ist es, mit möglichst wenig
zusätzlicher Synchronisierung auszukommen, da sonst die Performance leidet.
8.2. WEITERFÜHRENDE ARBEITEN
69
GCI Absorption
Eine Implementierung von GCI Absorption ist gut denkbar. Diese Optimierung bietet
für das Schlussfolgern mit GCIs enorme Vorteile. Durch den vorverarbeitenden Charakter lässt es sich gut mit dem parallelen Ansatz von UUPR kombinieren, da im Beweisprozess selbst kein zusätzlicher Aufwand entsteht. Insbesondere ist keine zusätzliche
Synchronisierung nötig. Ähnlich wie Simplification und die sequentielle Bearbeitung
kleiner Probleme führt GCI Absorption zu einer besseren Granularität der Parallelisierung. Die einfache Kombinierbarkeit mit einem parallelen Ansatz und der positive
Effekt, der damit erzielt werden kann, machen eine mögliche Implementierung von GCI
Absorption sehr interessant. GCI Absorption und dependency directed backtracking
sind für Reasoning mit großen Ontologien wie GALEN [RNG93] besonders wichtig.
Reasoning mit solchen Ontologien wurde erst durch den Einsatz dieser Optimierungen
möglich.
Caching
Bisher ist caching in UUPR nur unvollständig implementiert (siehe wiederum Abschnitt
4.3). Die Erfüllbarkeit von Individuen, die parallel bearbeitet werden, wird nicht im
Cache gespeichert. Um dies zu verbessern müsste die Datenstruktur ABox in UUPR
erweitert werden: In jeder Alternative müsste gespeichert werden, welche Ausdrücke
im Cache die (Un-)Erfüllbarkeit einer Alternative beeinflusst. Wenn eine ABox dann
fertig bearbeitet ist, müssten die entsprechenden Cacheeinträge angepasst werden, wofür
zusätzliche Synchronisation benötigt würde. Ziel ist es hierbei, die Menge an zusätzlicher
Synchronisation so klein wie möglich zu halten.
Ähnlich wie den Workpool kann man auch den gemeinsamen Cache in mehrere
Caches aufteilen. Dabei sind mehrere Varianten möglich. Zum einen könnten statt eines
gemeinsamen Caches mehrere Caches eingesetzt werden, auf die dann jeweils nur eine
Teilmenge der Worker-Threads Zugriff hat. Zum anderen könnte der Cache in mehrere
Teile aufgeteilt werden, auf die der Zugriff dann getrennt synchronisiert werden kann.
Zwei Threads könnten dann auf verschiedene Teile des Caches gleichzeitig zugreifen
ohne sich gegenseitig zu blockieren.
Durch die parallele Verarbeitung werden sogar Erweiterungen zu caching denkbar.
Bisher wird nach der vollständigen Auffaltung des concept sets eines Individuums eine
Anfrage bezüglich der Erfüllbarkeit an den Cache gestellt und der Erfüllbarkeitsstatus von fertig bearbeiteten Individuen im Cache abgelegt. Dies entspricht bis auf die
fehlende Berücksichtigung von Disjunktionen der Vorgehensweise in einer sequentiellen
Implementierung. Dadurch, dass die Erfüllbarkeit eines Individuums von der Erfüllbarkeit seiner unter Umständen vorhandenen Rollennachfolger abhängt, kann zwischen
Anfrage an den Cache vor der Bearbeitung und Erstellung des Cache-Eintrags nach der
Bearbeitung eine gewisse Zeit vergehen. Während dies in sequentiellen Reasonern nicht
von Bedeutung ist kann es in UUPR dadurch jedoch dazu kommen, dass zwei Worker gleichzeitig die Erfüllbarkeit zweier identischer Individuen berechnen. Hier wäre die
Verwendung einer Art vorläufigen Cacheeintrags denkbar. Der erste Worker, der eine
Anfrage zur Erfüllbarkeit eines Individuums an den Cache stellt und dabei feststellt,
70
dass seine Erfüllbarkeit noch nicht berechnet wurde, kann dort eine Markierung hinterlassen um zu verdeutlichen, dass die Erfüllbarkeit dieses Individuums jetzt berechnet
wird. Ein anderer Worker, der dann die Erfüllbarkeit eines identischen Individuums im
Cache erfragen möchte, erfährt so, dass ein solches Individuum bereits bearbeitet wird.
Dieser Worker könnte dann zum Beispiel die Bearbeitung der zu diesem Individuum gehörigen ABox zurückstellen indem er sie mit einer niedrigeren Priorität versehen zurück
in den Pool legt. Damit könnte der Effekt des cachings in einer parallelen Implementierung noch weiter erhöht werden.
8.2.3
Erweiterungen des Sprachumfangs
Für die Verwendung eines parallelen Reasoners im Kontext des Semantic Web ist die Unterstützung einer ausdrucksmächtigeren Beschreibungslogik notwendig. Dies erhöht die
Komplexität des Tableau-Algorithmus’, weshalb der Einfluss dieser zusätzlichen Komplexität auf die Parallelisierbarkeit untersucht werden muss. Sinnvolle Erweiterungen
des Sprachumfangs sind zum Beispiel die Hinzunahme von Möglichkeiten zur Definition inverser Rollen und qualifizierter Kardinalitätseinschränkungen. Eine Beschreibung
dieser Sprachmittel ist in [BCM+ 03] zu finden.
Eine Implikation der Verwendung inverser Rollen ist, dass es nicht mehr möglich
ist, mit Sicherheit zu sagen, wann die Bearbeitung eines Individuums abgeschlossen ist.
Ihre Verarbeitung macht daher eine kompliziertere Form des blockings nötig. Zusätzlich resultiert dies im Kontext eines parallelen Beweisers darin, dass die oben genannte
speichersparende Implementierung von zwischen ABoxen geteilten Referenzen auf gemeinsame Invididuen weiter verkompliziert wird. Es wird möglich, dass ein geteiltes
Individuum in einer Alternative geändert wird, während es in der anderen Alternative
gleich bleibt. Die in UUPR verwendete Implementierung vollständig kopierter ABoxen
umgeht dieses Problem. Eine andere Möglichkeit wäre es, geteilte Individuen bei Bedarf
in zwei Kopien aufzuteilen.
Qualifizierte Kardinalitätseinschränkungen verkomplizieren die Zusammenfassung
von Rollennachfolgern im Falle einer Maximumkardinalitätsrestriktion. Dabei entsteht
allerdings weiterer Nichtdeterminismus, so dass hierin wiederum Potential zur Parallelverarbeitung steckt: Wenn ein Tableau-Knoten ≤ 2 r.C enthält, so muss für jeden
vorhandenen r-Nachfolger entschieden werden, ob dieser zur Gruppe der Nachfolger
zählt, die C erfüllen (C wird zum Nachfolger hinzugefügt) oder nicht (¬C wird zum
Nachfolger hinzugefügt) [HS01]. Die zwei alternativen Möglichkeiten können in zwei
ABoxen aufgeteilt und parallel verarbeitet werden. Die interne Datenstruktur von UUPR unterstützt qualifizierte Kardinalitätseinschränkungen bereits: Sie werden während
des Einlese-Prozesses vollständig eingelesen, im Beweisprozess werden angegebene Qualifikationen momentan ignoriert. Für die Realisierung dieser Spracherweiterung muss
also lediglich die skizzierte Regel implementiert werden.
Anhang A
Testbeispiele
Hier sind die für die Evaluierung von UUPR verwendeten Testfälle vollständig in abstrakter Syntax aufgelistet. DIG-Dateien, die die Testfälle realisieren finden sich auf der
beigefügten CD (siehe auch Anhang C).
A.1
Testfall 1
Anfrage: Ist X2 erfüllbar?
Antwort: f alse
C1 v¬C2 u ¬C3
C2 v¬C2
X2 ≡∃r.C1 u ∃r.C2 u ∃r.C3 u ∃r.C4 u ∃r.C5 u ∃r.C6 u ∃r.C7 u ∃r.C8u
∃r.C9 u ∃r.C10 u ∃r.C11 u ∃r.C12 u ∃r.C13 u ∃r.C14 u ∃r.C15u ≤ 2 r
A.2
Testfall 2
Anfrage: Ist X erfüllbar?
Antwort: true
Aus Platzgründen sind die einzelnen Disjunkte (Ai ) parametrisiert dargestellt, das heißt,
71
72
ANHANG A. TESTBEISPIELE
Ai 01 und Aj 01 sind unterschiedliche Konzepte für i 6= j.
X ≡A1 t A2 t A3 t A4 t A5 t A7 t A7 t A8
Ai ≡∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 01 u ∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 02u
∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 03 u ∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 04u
∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 05 u ∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 06u
∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 07 u ∃p0.∀p1.∀p2.∀p3.∀p4.∀p5.∀p6.¬Ai 65u
∀p0.(∃p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 11u
∃p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 12 u ∃p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 13u
∃p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 14 u ∃p1.∀p2.∀p3.∀p4.∀p5.∀p6.Ai 15u
∀p1.(∃p2.∀p3.∀p4.∀p5.∀p6.Ai 21u
∃p2.∀p3.∀p4.∀p5.∀p6.Ai 22 u ∃p2.∀p3.∀p4.∀p5.∀p6.Ai 23u
∃p2.∀p3.∀p4.∀p5.∀p6.Ai 24 u ∃p2.∀p3.∀p4.∀p5.∀p6.Ai 25u
∀p2.(∃p3.∀p4.∀p5.∀p6.Ai 31u
∃p3.∀p4.∀p5.∀p6.Ai 32 u ∃p3.∀p4.∀p5.∀p6.Ai 33u
∀p3.(∃p4.∀p5.∀p6.Ai 41u
∃p4.∀p5.∀p6.Ai 42 u ∃p4.∀p5.∀p6.Ai 43u
∀p4.(∃p5.∀p6.Ai 51u
∃p5.∀p6.Ai 52 u ∃p5.∀p6.Ai 53u
∀p5.(∃p6.Ai 61u
∃p6.Ai 62 u ∃p6.Ai 63u
∃p6.Ai 64 u ∃p6.Ai 65))))))
A.3
Testfall 3
Eine kleine Familienontologie. Es wird ein Instanztest für
betty : mother having only sisters
simuliert.
Anfrage: Ist die Ontologie erfüllbar?
Antwort: f alse
A.3. TESTFALL 3
73
Rollenaxiome:
has descendant ∈ r+
has child v has descendant
has sister v has sibling
has brother v has sibling
> v ∃ ≤ 1 has gender
∃ ≥ 1 has descendant v human
> v ∀has descendant.human
∃ ≥ 1 has child v parent
∃ ≥ 1 has sibling v sibling
> v ∀has sibling.sibling
> v ∀has sister.sister
> v ∀has brother.brother
> v ∀has gender.(f emale t male)
∃ ≥ 2 has child v ∀has child.sibling
∃has child.sibling v ∃ ≥ 2 has child
f emale, male und human sind disjunkt:
f emale v ¬(human t male)
male v ¬(human t f emale)
human v ¬(f emale t male)
Basiskonzepte einer Familienontologie:
human v ∃ ≥ 1 has gender
woman ≡ human u ∀has gender.f emale
man ≡ human u ∀has gender.male
parent ≡ ∃ ≥ 1 has child
mother ≡ woman u parent
f ather ≡ man u parent
74
ANHANG A. TESTBEISPIELE
Verwandtschaften:
mother having only f emale kids ≡ mother u ∀has child.∀has gender.f emale
mother having only daughters ≡ mother u ∃ ≥ 1 has child u ∀has child.woman
mother with kids ≡ mother u ∃ ≥ 2 has child
grandpa ≡ man u ∃has child.parent
great grandpa ≡ man u ∃has child.(∃has child.parent)
grandma ≡ woman u ∃has child.parent
great grandma ≡ woman u ∃has child.(∃has child.parent)
aunt ≡ woman u ∃has sibling.parent
uncle ≡ man u ∃has sibling.parent
sibling ≡ sister t brother
sister ≡ woman u ∃ ≥ 1 has sibling
brother ≡ man u ∃ ≥ 1 has sibling
mother with siblings ≡ mother u ∀has child.sibling
mother having only sisters ≡ mother u ∀has child.(sister u ∀has sibling.sister)
ABox:
alice : woman u ∃ ≤ 2 has child
(alice, betty) : has child
(alice, charles) : has child
betty : woman u ∃ ≤ 2 has child u ∃ ≤ 1 has sibling
(betty, doris) : has child
(betty, eve) : has child
(betty, charles) : has sibling
charles : brother u ∃ ≤ 1 has sibling
(charles, betty) : has sibling
doris : ∃ ≤ 1 has sibling
eve : ∃ ≤ 1 has sibling
(doris, eve) : has sister
(eve, doris) : has sister
Negierte Anfrage:
betty : ¬mother having only sisters
Anhang B
DIG-Unterstützung
Hier ist das von UUPR unterstützte Fragment von DIG 2.0 näher beschrieben. Dazu
folgt eine Liste der verwendbaren Tags. Eine wichtige Einschränkung in der Verwendbarkeit der Tags ist dabei, dass EquivalentClasses nicht zur Erzeugung von GCIs
verwendet werden kann. Für die Definitionen von GCIs steht SubClassOf zur Verfügung.
Tags zur Ontologiedefinition:
ObjectProperty
SubObjectPropertyOf
TransitiveObjectProperty
EquivalentClasses
SubClassOf
Individual
ObjectPropertyAssertion
ClassAssertion
ObjectAllValuesFrom
ObjectIntersectionOf
ObjectMinCardinality
ObjectMaxCardinality
OWLClass
ObjectComplementOf
ObjectUnionOf
ObjectSomeValuesFrom
OWLClass
Tags zur Anfrageerzeugung:
AreClassesDisjoint
AreClassesEquivalent
IsClassSatisfiable
IsClassSubsumedBy
IsOntologySatisfiable
75
76
ANHANG B. DIG-UNTERSTÜTZUNG
Anhang C
Inhalt der beigefügten CD
Die beigefügte CD enthält folgende Daten.
C.1
Ausarbeitung
Im Ordner Ausarbeitung findet sich diese Diplomarbeit als pdf-Dokument. Im Unterverzeichnis tex sind die entsprechenden tex-Quellen zu finden.
C.2
UUPR
Das Verzeichnis uupr enthält für jede der verwendeten Plattformen eine angepasste
Version von UUPR, jeweils mit allen benötigten Bibliotheken.
C.3
Testdaten
Die in Kapitel 6 genannten Testbeispiele finden als DIG 2.0-Dateien sich im Ordner
Testbeispiele.
C.4
DIG 2.0
Der während der Entstehung dieser Diplomarbeit aktuelle Stand des DIG 2.0-Formates
wird von den XML-Schemata im Verzeichnis dig20 wiedergegeben.
77
78
ANHANG C. INHALT DER BEIGEFÜGTEN CD
Literaturverzeichnis
[BCLM89] S. Bose, E. Clark, D. Long, and S. Michaylov. Parthenon, a parallel theorem
prover for non-horn clauses. In Proceedings of the Fourth Annual Symposium on Logic in computer science, pages 80–89, Piscataway, NJ, USA, 1989.
IEEE Press.
[BCM+ 03] Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi,
and Peter F. Patel-Schneider, editors. The description logic handbook: theory, implementation, and applications. Cambridge University Press, New
York, NY, USA, 2003.
[BHN+ 92]
Franz Baader, Bernhard Hollunder, Bernhard Nebel, Hans-Jürgen Profitlich, and Enrico Franconi. An empirical analysis of optimization techniques
for terminological representation systems or “making KRIS get a move on”.
In B. Nebel, W. Swartout, and C. Rich, editors, Principles of Knowledge
Representation and Reasoning: Proceedings of the 3rd International Conference, pages 270–281, San Mateo, 1992. Morgan Kaufmann.
[BMBW00] Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R.
Wilson. Hoard: A scalable memory allocator for multithreaded applications. In International Conference on Architectural Support for Programming
Languages and Operating Systems (ASPLOS-IX), pages 117–128, Cambridge, MA, November 2000.
[Bon00]
Maria Paola Bonacina. A taxonomy of parallel strategies for deduction.
Annals of Mathematics and Artificial Intelligence, 29(1-4):223–257, 2000.
[BQ95]
F. W. Bergmann and J. J. Quantz. Parallelizing description logics. In
I. Wachsmuth, C.-R. Rollinger, and W. Brauer, editors, KI-95: Advances
in Artificial Intelligence, Bielefield, Germany, pages 137–148. Springer-Verlag, Berlin, 1995.
[GGK03]
Ananth Grama, Anshul Gupta, and George Karypis, editors. Introduction
to Parallel Computing. Addison Wesley, 2003.
[GHVD03] B. Grosof, I. Horrocks, R. Volz, and S. Decker. Description logic programs:
Combining logic programs with description logic, 2003.
79
80
LITERATURVERZEICHNIS
[HM00]
Volker Haarslev and Ralf Möller. Expressive ABox Reasoning with Number
Restrictions, Role Hierarchies, and Transitively Closed Roles. In Int. Conf.
on Principles of Knowledge Representation and Reasoning (KR2000), pages
273–284. Morgan Kaufmann, 2000.
[HM03]
V. Haarslev and R. Möller. Racer: A core inference engine for the semantic
web. In Proceedings of the 2nd International Workshop on Evaluation of
Ontology-based Tools (EON2003), located at the 2nd International Semantic Web Conference ISWC 2003, Sanibel Island, Florida, USA, October 20,
pages 27–36, 2003.
[HMS04]
U. Hustadt, B. Motik, and U. Sattler. Reducing SHIQ description logic to
disjunctive datalog programs. In Proc. of the 9th International Conference
on Knowledge Representation and Reasoning (KR2004), pages 152–162,
2004.
[Hor97]
I. Horrocks. Optimising Tableaux Decision Procedures for Description Logics. PhD thesis, University of Manchester, 1997.
[HPS99]
Ian Horrocks and Peter F. Patel-Schneider. Optimizing description logic
subsumption. Journal of Logic and Computation, 9(3):267–293, 1999.
[HS01]
I. Horrocks and U. Sattler. Ontology reasoning in the SHOQ(D) description
logic. In Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, 2001.
[HT00]
I. Horrocks and S. Tobies. Reasoning with axioms: Theory and practice. In
A. G. Cohn, F. Giunchiglia, and B. Selman, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Seventh International
Conference (KR2000), San Francisco, CA, 2000. Morgan Kaufmann Publishers.
[Lie06]
Thorsten Liebig. Reasoning with OWL – system support and insights –.
Technical Report TR-2006-04, Ulm University, Ulm, Germany, September
2006.
[Lie07]
T. Liebig. Wissensmodellierung und wissensbasierte Systeme, Vorlesungsmanuskript. Universität Ulm, 2007.
[Pon96]
Enrico Pontelli. Adventures in parallel logic programming, 1996.
[PS98]
P. Patel-Schneider. DLP system description, 1998.
[RNG93]
A. Rector, W. Nowlan, and A. Glowinski. Goals for concept representation
in the GALEN project, 1993.
[Sch96]
Johann Schumann. SiCoTHEO: Simple competitive parallel theorem provers. In Conference on Automated Deduction, pages 240–244, 1996.
LITERATURVERZEICHNIS
81
[SL90]
Johann Schumann and Reinhold Letz. PARTHEO: A high-performance
parallel theorem prover. In Conference on Automated Deduction, pages
40–56, 1990.
[SPG+ 06]
Evren Sirin, Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and
Yarden Katz. Pellet: A practical OWL-DL reasoner. In Journal of Web
Semantics, 2006.
[SSS91]
Manfred Schmidt-Schauß and Gert Smolka. Attributive concept descriptions with complements. Artificial Intelligence, 48:1–26, 1991.
[Str05]
A. Strey. Parallele Programmierung, Vorlesungsmanuskript. Universität
Ulm, 2005.
[TH06]
Dmitry Tsarkov and Ian Horrocks. FaCT++ description logic reasoner:
System description. In Proc. of the Int. Joint Conf. on Automated Reasoning (IJCAR 2006), volume 4130 of Lecture Notes in Artificial Intelligence,
pages 292–297. Springer, 2006.
[Vor03]
Andrei Voronkov. Automated Reasoning: Past Story and New Trends. In
Proc. of the Int. Joint Conf. on Artificial Intelligence (IJCAI-2003), pages
1607–1612, 2003.
[Wol98]
Andreas Wolf. p-SETHEO: Strategy parallelism in automated theorem proving. In TABLEAUX ’98: Proceedings of the International Conference on
Automated Reasoning with Analytic Tableaux and Related Methods, pages
320–324, London, UK, 1998. Springer-Verlag.

Entwicklung und Evaluierung eines parallelen

Transcrição

Documentos relacionados

Schmitz-Werke + Co. KG

Jetzt ansehen

CV_ Christina Dubisar

Stellenzeige herunterladen

Ständig unter Strom: Radio und TV in Kroatien

Vorgehen im Softwareentwicklungsprozess - Benutzer

Neuheiten | 2016

PDF - Monzoon Networks AG

Mainz Mainz Weisenau - Grünewald * Baum Bestattungen

PDF-Ansicht dieser Seite