title: Implementation and Evaluation of Algorithmic Skeletons: Parallelisation of Computer Algebra Algorithms
title: Implementation and Evaluation of Algorithmic Skeletons: Parallelisation of Computer Algebra Algorithms
title: Implementierung und Evaluation algorithmischer Skelette: Parallelisierung von Computeralgebraalgorithmen
Creators: name: Lobachev, Oleg
Publisher: name: Philipps-Universität Marburg
Year: 2011
Subjects: high-level
skeleton
Eden
Computeralgebra
Skeleton
Haskell
HASKELL
Informatik
parallelisation
Teilauswertung
computer algebra

description: 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.
description: This thesis presents design and
      implementation approaches for the parallel algorithms of
      computer algebra. We use algorithmic skeletons and also
      further approaches, like data parallel arithmetic and actors.
      We have implemented skeletons for divide and conquer
      algorithms and some special parallel loops, that we call
      ‘repeated computation with a possibility of premature
      termination’. We introduce in this thesis a rational data
      parallel arithmetic. We focus on parallel symbolic
      computation algorithms, for these algorithms our arithmetic
      provides a generic parallelisation approach. The
      implementation is carried out in Eden, a parallel functional
      programming language based on Haskell. This choice enables us
      to encode both the skeletons and the programs in the same
      language. Moreover, it allows us to refrain from using two
      different languages—one for the implementation and one for
      the interface—for our implementation of computer algebra
      algorithms. Further, this thesis presents methods for
      evaluation and estimation of parallel execution times. We
      partition the parallel execution time into two components.
      One of them accounts for the quality of the parallelisation,
      we call it the ‘parallel penalty’. The other is the
      sequential execution time. For the estimation, we predict
      both components separately, using statistical methods. This
      enables very confident estimations, although using
      drastically less measurement points than other methods. We
      have applied both our evaluation and estimation approaches to
      the parallel programs presented in this thesis. We haven also
      used existing estimation methods. We developed divide and
      conquer skeletons for the implementation of fast parallel
      multiplication. We have implemented the Karatsuba algorithm,
      Strassen’s matrix multiplication algorithm and the fast
      Fourier transform. The latter was used to implement
      polynomial convolution that leads to a further fast
      multiplication algorithm. Specially for our implementation of
      Strassen algorithm we have designed and implemented a divide
      and conquer skeleton basing on actors. We have implemented
      the parallel fast Fourier transform, and not only did we use
      new divide and conquer skeletons, but also developed a
      map-and-transpose skeleton. It enables good parallelisation
      of the Fourier transform. The parallelisation of Karatsuba
      multiplication shows a very good performance. We have
      analysed the parallel penalty of our programs and compared it
      to the serial fraction—an approach, known from literature. We
      also performed execution time estimations of our divide and
      conquer programs. This thesis presents a parallel map+reduce
      skeleton scheme. It allows us to combine the usual parallel
      map skeletons, like parMap, farm, workpool, with a premature
      termination property. We use this to implement the so-called
      ‘parallel repeated computation’, a special form of a
      speculative parallel loop. We have implemented two
      probabilistic primality tests: the Rabin–Miller test and the
      Jacobi sum test. We parallelised both with our approach. We
      analysed the task distribution and stated the fitting
      configurations of the Jacobi sum test. We have shown formally
      that the Jacobi sum test can be implemented in parallel.
      Subsequently, we parallelised it, analysed the load balancing
      issues, and produced an optimisation. The latter enabled a
      good implementation, as verified using the parallel penalty.
      We have also estimated the performance of the tests for
      further input sizes and numbers of processing elements.
      Parallelisation of the Jacobi sum test and our generic
      parallelisation scheme for the repeated computation is our
      original contribution. The data parallel arithmetic was
      defined not only for integers, which is already known, but
      also for rationals. We handled the common factors of the
      numerator or denominator of the fraction with the modulus in
      a novel manner. This is required to obtain a true
      multiple-residue arithmetic, a novel result of our research.
      Using these mathematical advances, we have parallelised the
      determinant computation using the Gauß elimination. As
      always, we have performed task distribution analysis and
      estimation of the parallel execution time of our
      implementation. A similar computation in Maple emphasised the
      potential of our approach. Data parallel arithmetic enables
      parallelisation of entire classes of computer algebra
      algorithms. Summarising, this thesis presents and thoroughly
      evaluates new and existing design decisions for high-level
      parallelisations of computer algebra algorithms.