Parallele Numerik

Mittels elementarer Beispiele werden zunächst aus algorithmischer Sicht der Begriff der Parallelität sowie andere grundlegende Begriffe und Konzepte eingeführt.

Bei der Lösung numerischer Anwendungsprobleme mit parallelen Verfahren sind im Hinblick auf die zu nutzende Rechnerumgebung drei wesentliche Gesichtspunkte von Bedeutung:

Die Basisalgorithmen der linearen Algebra bilden die Elementarbausteine vieler numerischer Algorithmen. Die Effizienz dieser Algorithmen ist daher von entscheidender Bedeutung für Vielzahl numerischer Anwendungen. Ein Maximum an Optimierung ist jedoch nur unter bestmöglicher Ausnutzung aller relevanten Merkmale der jeweils verwendeten Hardware zu erreichen. In der Konsequenz erhält man meist prozessor- oder architekturspezifische Algorithmen, die kaum in einer höheren Programmiersprache zu realisieren sind, sondern eher eine Assembler-Programmierung erfordern. Um dem daraus resultierenden Mangel an Portabilität zu begegnen, hat sich vor einigen Jahren die BLAS-Initiative mit dem Ziel einer praxisorientierten Standardisierung formiert (Abschnitt 3.2.6). Die Basisalgorithmen der linearen Algebra weisen natürliche parallele Strukturen auf, die es gestatten, anhand sehr einfacher Aufgabenstellungen zumindest grundlegende Techniken zur Parallelisierung, Vektorisierung und Optimierung einzuführen. Die Basisalgorithmen lassen sich in Anlehnung an die Systematik der BLAS-Routinen entsprechend ihrer Komplexität hierarchisch in mehrere Gruppen gliedern:

Die Lösung linearer Gleichungssysteme gehört zu den am häufigsten auftretenden Aufgabenstellungen der Numerischen Mathematik. Ohne Anspruch auf Vollständigkeit beschränken wir uns auf die Beschreibung von parallelen Verfahren und Algorithmen für einige gängige Aufgabenstellungen. Wir unterscheiden

für Systeme mit folgenden Typen von Koeffizientenmatrizen:

Stellvertretend für Integral-Transformationen wie die Fourier-, die Laplace- oder die Rader-Transformation betrachten wir Algorithmen für die diskrete Form der bekanntesten Transformation, der Fourier-Transformation.

Bei der Entwicklung paralleler Algorithmen lässt sich eine ausreichende Granularität der Teilaufgaben, insbesondere zur Überdeckung des auf Parallelrechnern mit verteiltem Speicher in vielen Fällen erheblichen Kommunikationsaufwandes durch einen hinreichend umfangreichen „Rechenaufwand“, am besten erreichen, wenn parallele Strukturen frühzeitig, das heißt auf einer möglichst hohen Ebene der Problemlösung, geschaffen werden. Im Kapitel 5 wurden (parallele) Lösungsverfahren für unterschiedliche Typen linearer Gleichungssysteme hergeleitet. Dabei hat sich gezeigt, etwa im Falle der Schnellen Direkten Löser, dass diese Ebene der Parallelisierung für Parallelrechner mit verteiltem Speicher nicht immer ausreichend ist. Gleichungssysteme stellen eine bereits sehr konkrete Ebene der mathematischen Problemlösung dar. Im Falle der numerischen Lösung partieller Differentialgleichungen sind sie das Resultat der Diskretisierung eines kontinuierlichen Problems durch Anwendung beispielsweise eines Differenzen-, Finite-Elemente- oder Finite-Volumen-Verfahrens. In diesem Abschnitt stellen wir eine Vorgehensweise vor, in der die Parallelisierung grundsätzlich auf der Ebene des kontinuierlichen Problems, gegebenenfalls sogar schon während der Modellbildung vorgenommen wird. Das Prinzip der Gebietszerlegung wurde zunächst zur Lösung linearer elliptischer partieller Randwertprobleme eingeführt, später aber auch vielfach bei der Behandlung parabolischer und hyperbolischer Probleme sowie für nichtlineare und zeitabhängige Aufgaben eingesetzt.