Shared-memory-Implementierung der Gamma-Operation auf Multimengen

Der angenehme, von deklarativen Sprachen her bekannte Programmierstil wird beim Gamma-Modell, das das einer chemischen Reaktion zugrundeliegende nichtdeterministische (Berechnungs)- Modell auf Multimengen (Bags) modelliert, mit der Möglichkeit von (massiv) parallelen Implementierungen verknüpft. Der entscheidende Punkt bei der Erstellung effizienter Implementierungen ist die Analyse der Gamma-Schemata mit dem Ziel, eine Reduzierung der Anzahl der zu überprüfenden Tupel von Bagelementen zu bewirken. Im Rahmen dieser Arbeit wurden verschiedene Techniken vorgestellt, um zum einen eine Verkleinerung des Suchraums, d. h. eine Verringerung der Anzahl der möglichen Kombinationen von Bagelementen, zu erzielen und zum anderen insbesondere im Hinblick auf eine Parallele Realisierung einen möglichst hohen Parallelitätsgrad der Algorithmen zu erhalten. Die vorgestellten Implementierungen wurden auf einem Parallelrechner mit gemeinsamen Speicher vorgenommen. Zuerst sind die Konjunktiven Gamma-Schemata untersucht worden. Diese zeichnen sich dadurch aus, dass die Reaktionsbedingung eine boolesche Verknüpfung von atomaren Prädikaten ist. Es wurden verschiedene Techniken für eine effiziente parallele Implementierung dieser Schemata diskutiert. Dabei handelte es sich um eine geeignete Anordnung der Schleifen, eine frühstmögliche Auswertung (eager evaluation) von Teilprädikaten der Reaktionsbedingung und die Ausnutzung von Eigenschaften der arithmetischen Operationen, um damit eine Bereichseinschränkung für die Schleifenabarbeitung zu erzielen. Weiterhin ist gezeigt worden, wie die Mehrfachbetrachtung von gleichen Tupeln von Bagelementen verhindert werden kann. Durch eine ausgefeilte Locking-Prozedur wurde schließlich der konkurrierende Verbrauch von Bagelementen sichergestellt. Es wurde gezeigt, dass diese Locking-Prozedur verklemmungsfrei ist. Um die Konjunktiven Gamma-Schemata parallel abzuarbeiten, ist eine abstrakte Maschine definiert worden. Die erzielten Laufzeiten unterstrichen in eindrucksvoller Weise die Nützlichkeit und Effizenz des gewählten Ansatzes. Anschließend sind die (k, l, m)-Schemata näher untersucht worden. Für die Klasse der (2, true ,1)-Schemata, insbesondere die Funktion fold, die die Elemente eines Bags mittels einer Vorgegebenen Operation verknüpft, wurden vier Algorithmen vorgestellt, mit denen diese Schemata realisiert werden können. Es handelte sich dabei um a) das Einfache Folding-Schema EFS, das eine feste Verknüpfungsreihenfolge vorschreibt, b) den Globalen Synchronisationspunkt GSP, bei dem die Suche nach Reaktionspartnern über eine globale Synchronisationsstelle, die allerdings schnell zum Engpass werden kann, geregelt wird, c) den Flexiblen Folding-Algorithmus FFA, bei dem die Bagelemente verknüpft werden können, sobald sie vorliegen und d) den Modifizierten Folding-Algorithmus MFA, der mit weniger Sperroperationen als FFA auskommt. Für eine Reihe von Anwendungen belegten die erzielten Laufzeiten den Vorteil der beiden letztgenannten Algorithmen insbesondere bei solchen chemischen Reaktionen, bei denen die Komplexität stark variiert. Mit Varianten dieser beiden Algorithmen lassen sich auch andere Instanzen der (k, l, m)-Schemata effizient realisieren.