Ein HPC-tauglicher Spektralelemente-Löser auf der Grundlage von statischer Kondensation und Mehrgittermethoden

Arbeitstitel: Erweiterte mathematische Methoden zur Simulation von turbulenten Strömungsvorgängen auf parallelen Rechnern:Inhaltsverzeichnis 1 Einleitung 3 2 Numerische Simulation physikalischer Prozesse 6 2.1 Königsdisziplin - Turbulente Strömungssimulation 6 2.2 Vom mathematischen Modell zur numerischen Lösung 9 2.2.1 Räumliche und zeitliche Diskretisierung 9 2.2.2 Allgemeine Reduktion auf Poisson- und Helmholtz-Gleichungen 11 2.3 Anforderungen an effiziente Lösungsverfahren 12 3 Basiskomponenten des entwickelten Verfahrens 16 3.1 Spektralelemente-Methode 16 3.1.1 Grundlagen 17 3.1.2 Gewählte Ansatzfunktionen und Stützstellen 20 3.1.3 Struktur des linearen Operators 24 3.2 Statische Kondensation 25 3.3 Geometrisches Mehrgitterverfahren 26 4 Das Spektralelemente basierte Mehrgitterverfahren auf kondensierten Gittern 31 4.1 Stand der Forschung 31 4.2 Mehrgitterverfahren auf kondensierten Gittern 32 4.2.1 Konzeption wirkungsvoller Glätter 34 4.3 Nachweis optimaler Eigenschaften 41 4.3.1 Lineare Komplexität 41 4.3.2 Ausgezeichnete Konvergenzgeschwindigkeit 43 4.3.3 Robustheit gegenüber Gitterverfeinerung 46 5 Konzeption des parallelen Mehrgitterlösers 49 5.1 Parallelrechner und Leistungsbewertungskriterien 49 5.2 Stand der Forschung 52 5.3 Grundlegende Struktur und Parallelisierung 54 5.3.1 Analyse des Speicherbedarfs 54 5.3.2 Zwei- und dreidimensionale Zerlegung 58 5.3.3 Parallelisierung und Kommunikation 62 6 Ergebnisse 65 6.1 Implementierung des Lösers 65 6.2 Hardwarespezifikation des Testsystems 66 6.3 Bewertung der Implementierung 68 6.3.1 Sequentieller Anwendungsfall 68 6.3.2 Nachweis der Skalierbarkeit im parallelen Anwendungsfall 76 6.3.3 Vergleich mit etablierten Lösungsansätzen bzw. Lösern 87 7 Zusammenfassung und Ausblick 89 Abbildungsverzeichnis 92 Tabellenverzeichnis 94 Abkürzungsverzeichnis 95 Symbolverzeichnis 96 Literaturverzeichnis 98 A Weiterführende Messergebnisse 106 A.1 Relative Mehrkosten der parallelen Implementierung 106 A.2 Sequentielle Lösungszeiten ohne Nachglättung im 2D-Fall 107 A.3 Sequentielle Lösungszeiten ohne Nachglättung im 3D-Fall 108Die rechnergestützte Simulation physikalischer Prozesse ist ein fester Bestandteil im Alltag von Wissenschaftlern aus den unterschiedlichsten Wissensbereichen. Unabhängig davon, ob das Ziel die Vorhersage des Wetters von morgen, die Konzentrationsbestimmung von Fluidteilchen in Mischprozessen oder die Erschaffung von Werkstoffen mit optimalen Materialeigenschaften ist, ohne den Einsatz von leistungsfähigen Rechnern ist dieses Ziel nicht zu erreichen. Aus dieser inhärenten Kopplung lässt sich eine grundlegende Aussage bzgl. der Laufzeit durchzuführender Simulationen ableiten. Schnellere Rechentechnik reduziert automatisch die Laufzeit einer bereits bestehenden Simulation und somit auch die Wartezeit auf die potentiell zu erwartenden Erkenntnisse. Zeitgleich ist die so erreichte Reduktion der Berechnungszeit auch ein Maß für die mögliche Erhöhung des Detailgrades einer bestehenden Simulation und somit auch ein Indikator für den zusätzlich zu erwartenden Erkenntnisgewinn. Ein Blick auf die seit 1993 herausgegebene Top500-Liste der schnellsten Supercomputer zeigt ein annähernd gleichbleibend exponentielles Wachstum der Rechenleistung. Dieser durch eine Interpretation von „Moores-Law“ beschriebene Sachverhalt wird laut aktuellen Prognosen auch in den nächsten Jahren bestehen bleiben. Für die im Bereich der Simulation tätigen Wissenschaftler gleicht dies einem Versprechen, dass ohne deren Zutun auch in Zukunft mit stetig kürzeren Simulationszeiten zu rechnen ist. Immer vorausgesetzt, es können genug finanzielle Mittel für die neue Hardware akquiriert werden. Doch dieser Schein trügt. Eine genauere Analyse der Entwicklung der Rechentechnik der letzten Jahre zeigt zwei maßgebliche Veränderungen. Zum einen stagniert die maximale Taktrate einer einzelnen CPU seit Erreichen der 4 GHz Grenze im Jahr 2004 und zum anderen wird, insbesondere seit der Einführung der ersten Dual Core CPU’s 2005, gesteigerte Rechenleistung fast gänzlich durch die Verwendung einer Vielzahl von Rechenkernen erreicht. Das aktuell mit mehr als zehn Millionen Rechenkernen an Position 1 der Top500-Liste geführte System TaihuLight (deu. Licht der Göttlichkeit) verdeutlicht die Dimensionen dieser Entwicklung. Die für dieses System in Aussicht gestellte maximale Rechenleistung von circa 125 Billiarden gleitkommaoperationen pro Sekunde, kann dabei nur von einer perfekt parallelisierten Simulationsrechnung erreicht werden. „Amdahls-Law“ zeigt jedoch, dass dieser perfekte Zustand, aufgrund von unvermeidlichen sequentiellen Abschnitten in den einzelnen im Programm verwendeten Algorithmen, nicht zu erreichen ist. Die genaue Abweichung vom vollparallelisierten Idealzustand wird dabei durch die sogenannte parallele Effizienz quantifiziert. Deren Wert muss hierbei per Definition zwischen Null und Eins liegen. Dem Paradigma „eine hohe parallele Effizienz ergibt eine hohe Rechenleistung und dies führt zur kürzestmöglichen Simulationslaufzeit“ folgend, wurden in den letzten Jahren die unterschiedlichsten Simulationsprogramme auf eben diese Effizienz getrimmt. In den meisten Fällen wurden hierfür Codes verwendet, die auf eine sehr lange Historie zurückgreifen, so dass alte bestehende Strukturen und Algorithmen unabhängig von deren wirklicher Eignung parallelisiert wurden. Diese Entwicklung führt jedoch mehr und mehr dazu, dass die Entwickler den Blick für die Vielseitigkeit der Faktoren, die zu einer akzeptablen Simulationslaufzeit führen, verlieren. Werden zum Beispiel Methoden niederer Ordnung, wie dies etwa bei den Standard Finite-Differenzen-Verfahren der Fall ist, zur Diskretisierung des Simulationsgebietes eingesetzt, steigt die Zahl der für kleine Lösungsfehler benötigten Gitterpunkte so schnell an, dass jedweder Arbeitsspeicher vor Erreichen der benötigten Genauigkeit aufgebraucht ist. Im Gegensatz dazu sind Methoden höherer Ordnung, wie dies etwa bei den Standard Finite-Elemente-Verfahren der Fall ist, aufgrund ihrer suboptimalen numerischen Komplexität kaum besser geeignet. Ein ähnliches Bild ergibt sich bei den Algorithmen, mit denen die Gleichungssysteme in den einzelnen Simulationsschritten gelöst werden. Stellvertretend sei hier das Jacobi-Verfahren genannt, welches sich zwar durch eine parallele Effizienz nahe Eins auszeichnet, jedoch zum einen eine nicht optimale quadratische numerische Komplexität und zum anderen eine von der Auflösung des Simulationsgitters abhängige maximale Iterationszahl besitzt. Sofern die Anwender der etablierten Simulationsprogramme keine Kosten für den Zugang zu Hochleistungsrechnern zu erwarten haben und diese Rechner immer wieder massiv ausgebaut werden, stellen die genannten Einschränkungen fürs Erste nur bedingt ein Problem dar. Denn, eine Simulation die nach Hinzunahme einer bestimmten Zahl von Rechenkernen um annähernd diesen Faktor beschleunigt wird ist etwas Ausgezeichnetes. Werden den Anwendern jedoch, wie bereits von immer mehr Universitätsrechenzentren diskutiert und in der Industrie bereits gängige Praxis, die Kosten für den Energieverbrauch in Rechnung gestellt, ergibt sich ein gänzlich anderes Bild. Ein Bild, in dem der Effizienz, die die angewandten Methoden bzw. die eingesetzten Algorithmen erreichen, die größte Bedeutung zufällt. Die Effizienz einer Methode wird hierbei ungenauerweise oft nur anhand deren Implementierung als Algorithmus bestimmt. Jedoch kann eine effizient implementierte Methode mit numerisch ungünstigen Eigenschaften einer nicht effizient implementierten Methode mit numerisch optimalen Eigenschaften deutlich unterlegen sein. Demnach ist es offensichtlich, dass nur für eine effizient implementierte Methode mit optimalen numerischen Eigenschaften die kürzestmögliche Simulationslaufzeit erreicht werden kann. Der Fokus der vorliegenden Arbeit liegt deshalb zu allererst auf dem Nachweis der optimalen numerisch/mathematischen Eigenschaften der entwickelten Methode. Diese Eigenschaften sind: lineare numerische Komplexität, Robustheit des Verfahrens gegenüber Gitterverfeinerungen im Simulationsgebiet und eine bisher unerreichte Konvergenzrate. Abschließend wird zusätzlich die Eignung der Methoden bzgl. deren Verwendung auf aktuellen Hochleistungsrechnern unter Verwendung von Zehntausenden von Rechenkernen belegt und auch deren effiziente Implementierung bzw. Umsetzung dargelegt. Ziel dieser Arbeit ist die Entwicklung effizienter mathematischer Methoden zur numerischen Simulation von physikalischen Prozessen und deren hochskalierende Implementierung auf Hochleistungsrechnern. Unter allen denkbaren Aufgabenstellungen zählen hierbei insbesondere diejenigen zu den herausforderndsten, die der Strömungsmechanik zugeordnet sind. Besonders die direkte numerische Simulation (DNS), welche zur Analyse von turbulenten Strömungsphänomenen eingesetzt wird, stellt hierbei höchste Ansprüche an die eingesetzten numerischen Verfahren. Die Entwicklung und Umsetzung der im Rahmen dieser Arbeit vorgestellten Methoden ist deshalb auf die Anwendung im Rahmen der turbulenten Strömungssimulation ausgerichtet. Diese Fokussierung dient jedoch allein dem Beleg der Leistungsfähigkeit und stellt keine prinzipielle Einschränkung der Methode dar.:Inhaltsverzeichnis 1 Einleitung 3 2 Numerische Simulation physikalischer Prozesse 6 2.1 Königsdisziplin - Turbulente Strömungssimulation 6 2.2 Vom mathematischen Modell zur numerischen Lösung 9 2.2.1 Räumliche und zeitliche Diskretisierung 9 2.2.2 Allgemeine Reduktion auf Poisson- und Helmholtz-Gleichungen 11 2.3 Anforderungen an effiziente Lösungsverfahren 12 3 Basiskomponenten des entwickelten Verfahrens 16 3.1 Spektralelemente-Methode 16 3.1.1 Grundlagen 17 3.1.2 Gewählte Ansatzfunktionen und Stützstellen 20 3.1.3 Struktur des linearen Operators 24 3.2 Statische Kondensation 25 3.3 Geometrisches Mehrgitterverfahren 26 4 Das Spektralelemente basierte Mehrgitterverfahren auf kondensierten Gittern 31 4.1 Stand der Forschung 31 4.2 Mehrgitterverfahren auf kondensierten Gittern 32 4.2.1 Konzeption wirkungsvoller Glätter 34 4.3 Nachweis optimaler Eigenschaften 41 4.3.1 Lineare Komplexität 41 4.3.2 Ausgezeichnete Konvergenzgeschwindigkeit 43 4.3.3 Robustheit gegenüber Gitterverfeinerung 46 5 Konzeption des parallelen Mehrgitterlösers 49 5.1 Parallelrechner und Leistungsbewertungskriterien 49 5.2 Stand der Forschung 52 5.3 Grundlegende Struktur und Parallelisierung 54 5.3.1 Analyse des Speicherbedarfs 54 5.3.2 Zwei- und dreidimensionale Zerlegung 58 5.3.3 Parallelisierung und Kommunikation 62 6 Ergebnisse 65 6.1 Implementierung des Lösers 65 6.2 Hardwarespezifikation des Testsystems 66 6.3 Bewertung der Implementierung 68 6.3.1 Sequentieller Anwendungsfall 68 6.3.2 Nachweis der Skalierbarkeit im parallelen Anwendungsfall 76 6.3.3 Vergleich mit etablierten Lösungsansätzen bzw. Lösern 87 7 Zusammenfassung und Ausblick 89 Abbildungsverzeichnis 92 Tabellenverzeichnis 94 Abkürzungsverzeichnis 95 Symbolverzeichnis 96 Literaturverzeichnis 98 A Weiterführende Messergebnisse 106 A.1 Relative Mehrkosten der parallelen Implementierung 106 A.2 Sequentielle Lösungszeiten ohne Nachglättung im 2D-Fall 107 A.3 Sequentielle Lösungszeiten ohne Nachglättung im 3D-Fall 10