Shared-memory-Implementierung der Gamma-Operation auf Multimengen

More about the book

Der angenehme Programmierstil des Gamma-Modells verbindet die nichtdeterministische Modellierung chemischer Reaktionen mit der Möglichkeit massiver paralleler Implementierungen. Ein zentraler Aspekt ist die Analyse der Gamma-Schemata, um die Anzahl der zu überprüfenden Tupel von Bagelementen zu reduzieren. Die Arbeit präsentiert Techniken zur Verkleinerung des Suchraums und zur Maximierung der Parallelität der Algorithmen. Die Implementierungen wurden auf einem Parallelrechner mit gemeinsamem Speicher durchgeführt, beginnend mit der Untersuchung konjunktiver Gamma-Schemata, die durch boolesche Verknüpfungen von atomaren Prädikaten gekennzeichnet sind. Verschiedene Techniken für die effiziente parallele Implementierung wurden diskutiert, darunter die Anordnung der Schleifen, die frühzeitige Auswertung von Teilprädikaten und die Nutzung arithmetischer Eigenschaften zur Einschränkung der Schleifenbearbeitung. Zudem wurde gezeigt, wie die Mehrfachbetrachtung gleicher Tupel vermieden werden kann, und eine Locking-Prozedur gewährleistet den konkurrierenden Verbrauch von Bagelementen ohne Verklemmungen. Eine abstrakte Maschine wurde definiert, um die konjunktiven Gamma-Schemata parallel zu verarbeiten, was die Effizienz des Ansatzes unterstreicht. Anschließend wurden (k, l, m)-Schemata untersucht, insbesondere die Funktion fold, mit vier Algorithmen zur Realisierung. Die Laufzeiten belegen die Vorteile der flexiblen und modifizierten