Das Thema Parallelisierung ist für die Wissensrepräsentation in zweierlei Hinsicht relevant. Zum einen verwenden Wissensrepräsentationssysteme komplexe und oft sehr zeitaufwendige Algorithmen, deren Effizienz sich durch eine geeignete Parallelisierung erheblich steigern lassen kann. Wissensrepräsentationssysteme sind also selbst geeignete Gegenstände einer Parallelisierung. Zum andern ist die Parallelisierung von Algorithmen eine schwierige Aufgabe, und es liegt nahe, für die Lösung dieses komplexen Problems Techniken der Wissensrepräsentation zu verwenden. Beide Aspekte sollen im Graduiertenkolleg bearbeitet werden. Wir erläutern hier zunächst den zweiten Aspekt.
Dem Vorteil einer erhöhten Rechen- und Speicherkapazität beim Einsatz von Parallelrechnern steht eine schwierigere und langwierigere Programmierung gegenüber, insbesondere bei Rechnern mit verteiltem Speicher. Die Schwierigkeiten liegen im wesentlichen darin, daß die Aufgabenverteilung und der benötigte Informationsaustausch explizit gewählt und programmiert werden muß, aber deren Effekt auf die zu erzielende parallele Effizienz zunächst nicht absehbar ist. Die Parallelisierung einer Anwendung oder eines Algorithmus ist eine komplexe Aufgabe, die Datenaufteilung, Lastverteilung und Schedulingprobleme umfaßt. Einschränkungen bei der Durchführung dieser Teilaufgaben stellen Daten- und Kontrollabhängigkeiten dar. Im Rahmen dieser Einschränkungen gibt es aber immer noch vielfältige Möglichkeiten für eine parallele Implementierung.
Geeignete Werkzeuge könnten den Programmierprozeß unterstützen, etwa parallelisierende Compiler für sequentielle Programme oder automatische und halbautomatische Übersetzungswerkzeuge für Algorithmen in einer bereits potentiell parallelen Sprache. Dabei ist die Aufgabe eines Übersetzers für Parallelrechner wesentlich komplexer als die Aufgabe eines Übersetzers für sequentielle Rechner, da für Parallelrechner zusätzlich oben genannte Implementierungsentscheidungen getroffen werden müssen, die erhebliche Auswirkungen auf die Laufzeit des erzeugten Programmes haben. Zu den Aufgaben des Übersetzers gehören Analysen über Abhängigkeiten oder Transformationen, aber auch Entscheidungen z.B. über Datenauslegungen oder Ausnutzung potentieller Parallelität. Jede dieser Entscheidungen ist schwierig und für sich betrachtet bereits NP-vollständig.
Traditionelle Compiler übersetzen Programme, ohne Informationen über vorher übersetzte Programme auszunutzen. Für Compiler für Parallelrechner wäre es sinnvoller, sich die bei der Übersetzung früherer Programme gewonnenen Erkenntnisse (z.B. über eine gute Datenverteilung für eine spezielle Datenstruktur mit speziellem Zugriffsmuster) zu merken, damit die Analyse eines neuen Programmes durch Anwendung des Wissens vereinfacht werden kann. Wissen aus früheren Programmübersetzungen kann dabei entweder genutzt werden, um die Analysezeit zu verkürzen, oder um bei einer wiederholten Compilierung genauere Analysen durchzuführen. Des weiteren sind Informationen über die spezielle Hardware und deren benötigte Rechen- und Kommunikationszeit wichtig; das gleiche gilt für die verwendete Programmiersprache und ihr Programmiermodell.
In diesem Kontext ist ein Einsatz von wissensbasierten Techniken sinnvoll, der es erlaubt, das Wissen aus früheren Programm- und Laufzeitanalysen geeignet zu strukturieren und abrufbar zu machen. Wissensbasierte Techniken für die Compilierung auf Parallelrechner sind bisher noch wenig betrachtet worden, siehe etwa [ZC95]. Ansätze zu Transformationen, Optimierungen und Analysen finden sich in [Bos88, WG89, HJ90, IFKW90]. Parallelisierungstrategien werden in [AHMZ95] betrachtet.
Obige Themen befassen sich mit der Anwendung wissensbasierter Techniken auf den Bereich der Parallelisierung. Umgekehrt können Wissensrepräsentationssysteme, wie zu Beginn dieses Abschnitts bereits erwähnt, selber als Anwendungen für Parallelisierungen betrachtet werden, da es sich ja um große zeit- und speicherintensive Systeme handelt.
Bei der Parallelisierung von Wissensrepräsentationssystemen fallen die entsprechenden Aufgaben der Untersuchung von Abhängigkeiten, potentiellem Parallelismus und geeigneter Abbildung auf die parallele Maschine an. Hier gibt es einige Ansätze, etwa im Bereich regel-basierter Systeme oder semantischer Netzwerke; eine Übersicht findet sich z.B. in [Mol93]. Zu untersuchen wäre, welche Parallelisierungsstrategien, parallelen Programmiermodelle und Parallelrechnertypen für dieses Anwendungsgebiet adäquat sind. Es ergibt sich hier eine enge Verbindung zu Schwerpunkt B, wo im Kontext der Integration logischer und funktionaler Programmiersprachen auch Möglichkeiten der Parallelisierung untersucht werden sollen.
Mögliche Dissertationsthemen:
Entwurf der Struktur eines wissensbasierten Übersetzungssystems für Parallelrechner.
Parallelisierungsstrategien für Wissensrepräsentationssysteme