Implementation and Evaluation of Algorithmic Skeletons: Parallelisation of Computer Algebra Algorithms

Die vorliegende Arbeit beschreibt den Entwurf und die Implementierung paralleler Computeralgebraalgorithmen mithilfe von algorithmischen Skeletten und weiteren Ansätzen, wie datenparallele Arithmetik und Actors. Wir implementieren algorithmische Skelette für Divide and Conquer und spezielle, spekulative parallele Schleifen. Ähnlich zu den Skeletten ist die rationale datenparallele Arith- metik ebenfalls ein Parallelisierungschema, allerdings ist dieses speziell für Algorithmen der Computeralgebra ausgelegt. Die Parallelisierung wird in der parallelen funktionalen Sprache Eden vorgenommen. Eden ist eine Erweiterung von Haskell. Mit Eden ist es möglich, sowohl die Skelette als auch die Programme in einer Sprache zu definieren. Ein ähnlicher Ansatz erlaubt uns, die „innere“ und die „äußere“ Sprache einer Computeralgebra-Implementierung zu vereinigen. Desweiteren schlägt diese Arbeit eine Methode zur Auswertung und Abschätzung der parallelen Laufzeiten vor. Im Gegensatz zu den gängigen Ansätzen werden statistische Verfahren verwendet. Da- durch können wir sehr überzeugende Vorhersagen liefern. Im Vergleich zu den anderen Verfahren verwenden unsere Methoden deutlich weniger Datenpunkte. Eine von uns eingeführte Komponente der parallelen Laufzeit erlaubt eine strikte Kontrolle der Güte der Parallelität. Wir führen sowohl die Qualitätsmerkmale als auch die Abschätzung der parallelen Laufzeit für die in der Arbeit vorgestellte Implementierungen aus. Mit den Divide and Conquer Skeletten werden die Algorithmen für schnelle Multiplikation, nämlich Karatsuba Algorithmus und Strassen Matrixmultiplikation sowie die schnelle Fouriertransformation, entwickelt. Letzteres wird auch mit einem map-and-transpose Skelett umgesetzt. Damit haben wir eine gute Parallelisierungmerkmale beobachtet. Wir verwenden die schnelle Fouriertransformation, um eine schnelle Faltung von Polynomen umzusetzen, was zu einem weiteren Algorithmus zur schnellen Multiplikation führt. Der parallele Algorithmus von Karatsuba zeigt sehr gute Parallelisierungmerkmale. Für den Algorithmus von Strassen implementieren wir ein Actors-basiertes Divide and Conquer Skelett. Wir analysieren die Messungen ausführlich, um die Güte der Parallelisierung sicherzustellen. Wir stellen ein map+reduce Schema vor. Es erlaubt, gängige parallele Skelette wie parMap, farm, workpool mit einer Abbruchsklausel zu versehen. Wir setzen mit diesem Skelettschema die Algorithmen zu probabilistischen Primzahlprüfung um. Wir implementieren den Rabin–Miller-Test und den Jacobi-Summen-Test. Bei dem ersten optimieren wir die Aufgaben- und Prozessorenanzahl. Bei dem Jacobi-Summen-Test beweisen wir zuerst, dass es überhaupt möglich ist, unseren Ansatz zu verwenden. Danach wird die Implementierung erzeugt und parallelisiert. Dabei nehmen wir eine Optimierung der Aufgabenreihenfolge vor, was die Speedup Werte deutlich verbessert. Ebenfalls werden auch hier die beiden Implementierungen ausführlich analysiert. Die Laufzeiten werden für weitere Problemgrößen und Prozessorenzahlen abgeschätzt. Die datenparallele Arithmetik wurde nicht nur für ganze Zahlen, sondern auch für Brüche umgesetzt. Wir stellen eine neuartige Lösung vor, die die gemeinsamen Faktoren des Zähler oder Nenner des Bruches mit der Zahl eliminiert, modulo der man rechnet. Das ist notwendig um eine hinreichende Skalierung der multimodularen Arithmetik zu ermöglichen. Unter Verwendung dieser Erkenntnisse haben wir die Determinantenberechnung mittels Gauß Elimination parallelisiert. Eine vergleichbare Berechnung in Maple zeigte die großen Vorteile unseres Ansatzes. Die vorliegende Dissertation präsentiert Implementierung und gründliche Auswertung von high-level Parallelisierungen verschiedener Computeralgebraalgorithmen.