Tour durch die Forschungsschwerpunkte

Nichtdeterminismus ist eine inhärente Eigenschaft paralleler Programme, die unabhängig von den eingesetzten Programmierparadigmen und Kommunikationsmodellen auftritt. Nichtdeterminismus kann einerseits mit der Intention der Leistungssteigerung oder des impliziten Lastausgleichs gezielt verwendet werden, andererseits aber auch durch fehlerhafte Interprozeßkommunikation entstehen. Beide Fälle können während der Phasen des Testens und der Fehlersuche zu erheblichen Schwierigkeiten führen. Es ist daher notwendig, eine Methode zur Verfügung zu stellen, die eine deterministische Programmausführung gewährleistet. Die existierenden Verfahren replay und controlled execution können nichtdeterministische Effekte nicht vollständig ausschließen, da sie entweder auf einer Spuraufzeichnung beruhen (die mit einem probe effect einhergeht) oder lediglich einen Prozeß der parallelen Anwendung kontrollieren.

Deshalb wurden Methoden und Werkzeuge entworfen, die keinen der beiden oben genannten Nachteile mehr aufweisen. Die Arbeit unterteilte sich in zwei Phasen: Zunächst wurde auf Basis des am Lehrstuhl entwickelten Programmiermodells MMK eine Studie (DAMTOP) durchgeführt; auf den daraus gewonnenen Erkenntnissen wurde das endgültige Design des Werkzeugs (codex) entwickelt.

Das Ziel von DAMTOP (Deterministic tAsk Management Tool fOr Parallel systems) bestand darin, mögliche Freiheiten im Kommunikationsverhalten einer parallelen Anwendung durch eine vorgegebene Spezifikation systematisch auszunutzen, um einen deterministischen Programmablauf festzulegen [Obe95]. Die Spezifikation erfolgte durch eine auf den MMK zugeschnittene Sprache, die einen Automaten beschreibt, der die globale Reihenfolge aller Kommunikationsereignisse festlegt. Zur Vereinfachung der Spezifikation dienten zwei vordefinierte Schablonen, aus denen der Automat zusammengesetzt wird. Die erste dieser Schablonen erzeugt ein Round-Robin-Scheduling aller Kommunikationsereignisse, während die zweite jeweils dem Prozeß mit der höchsten Priorität das Auslösen des nächsten Kommunikationsereignisses erlaubt, wobei jedoch in beiden Fällen die Synchronisation in der Anwendung berücksichtigt wird. Als Konsequenz dieses globalen Schedulings wurde die Anwendung jedoch effektiv sequentialisiert. Desweiteren mußte der Benutzer die Anwendung sehr detailliert kennen, um die Spezifikation formulieren zu können.

Mit codex (controlled deterministic execution) wurde beruhend auf den gewonnenen Erfahrungen mit DAMTOP ein Instrument erstellt, das diese Nachteile vermeidet. Als neue Ziele wurde angestrebt, den Benutzer zu kritischen Situationen zu führen und andererseits einen Ansatz zu verfolgen, der effizient und programmiermodellunabhängig ist. Der letzte Punkt konnte im bisher im Rahmen von codex fertiggestellt werden [FO97]. Als Erweiterungen dieses Standes werden für die erwähnte Benutzerführung z.Zt. eine graphische Benutzungsschnittstelle und eine statische Analyse des parallelen Programmes konzipiert. In Entwicklung befindet sich derzeit auch ein Zusatzmodul zur Erkennung von races während der Laufzeit, das auf der im Teilprojekt B2 entwickelten Baum-Zeitstempel-Methode beruht. Mit Hilfe dieses Moduls kann die Kontrolle durch codex auf die relevanten (d.h. Nichtdeterminismus erzeugenden) Kommunikationsobjekte eingeschränkt werden.

Eine wesentliche Komponente bei der Entwicklung von codex war die Bereitstellung eines abstrakten Modells zur Repräsentation des parallelen Programms. Das erarbeitete Modell, genannt POEM (Parallel Object Execution Model), ist sowohl unabhängig vom Programmier- und Kommunikationsmodell als auch von individuellen Programmabläufen. Die Darstellung eines parallelen Programms mittels POEM gibt eine Menge möglicher (nicht notwendigerweise aller) Programmabläufe wieder. Diese Darstellung besteht im wesentlichen aus zwei Arten von Objekten: Ausführungsobjekte, z.B. Prozesse, Threads oder Tasks, und Kommunikationsobjekte, also alle Medien, die zur Kommunikation zwischen Ausführungsobjekten verwendet werden. Auf Kommunikationsobjekten ist eine Anzahl primitiver Zugriffsoperationen vorgegeben, mit deren Hilfe verschiedenste Formen der Kommunikation modelliert werden können.

Zur Spezifikation eines deterministischen Ablaufs werden in codex hierarchische Muster verwendet, die die Zugriffe auf Kommunikationsobjekte festlegen. Die Muster können auf alle oder nur auf einzelne Kommunikationsobjekte angewendet werden, so daß entweder genau ein Programmablauf oder eine Menge von Programmabläufen während der Ausführungsphase erlaubt sind. Die Muster werden wiederum auf endliche Automaten abgebildet, die jedoch in codex nur für jeweils ein Kommunikationsobjekt verantwortlich sind, so daß keine globale Steuerung mehr notwendig ist. Die Parallelität wird aufgrund dieser Verteilung der Kontrolle nicht mehr eingeschränkt. Jedoch können im Gegensatz zu DAMTOP nun durch Muster auch Verklemmungen erzeugt werden, was die Testunterstützung aber sogar noch verbessert. Ist das Muster nämlich aufgrund der Spezifikation des Programms zulässig, bedeutet eine Verklemmung, daß dessen Implementierung fehlerhaft ist.

Die Implementierung des Prototypen erfolgte für PVM. Dazu mußten zunächst abstrakte Identifikatoren für PVM-Objekte eingeführt werden, die auch bei einer Wiederholung der Programmausführung gültig eindeutig sind. Da in PVM die Kommunikationsobjekte an den empfangenden Prozeß gebunden sind, sind die Kontrolleinheiten jeweils diesen Prozessen zugeordnet. Zur Laufzeit werden die Muster von den Kontrolleinheiten ausgewertet und für den empfangenden Prozeß der Eindruck erweckt, als ob die Zugriffe der Sender in der durch das Muster vorgegebenen Reihenfolge stattgefunden hätten.

Der in codex verfolgte Ansatz wurde in einer Zusammenarbeit mit dem Teilprojekt 2.3 des Graduiertenkollegs ,,Kooperation und Ressourcenmanagement in verteilten Systemen`` auch dazu verwendet, die Testabdeckung paralleler Programme bezüglich temporal-logischer Ausdrücke zu erhöhen [FO97].