High-Performance Computing in Geoscience - Data Preprocessing by Domain Decomposition and Load Balancing

Abstract

The popularity and availability of computers is a simple fact of life in most of today's world. Computer simulation is a quick and relatively inexpensive alternative to physical experimentation in the scientific realm. Computer operations are meanwhile performed increasingly rapidly; one trillion operations per second are not anything extraordinary these days and are necessary in the field of automotive engineering, weather forecast or applied geology, for example. An interdependency of speed, power and storage space means that if one of these attributes is insufficient or impaired, it will limit the efficacy of the others. Data preprocessing and problem subdivision play a vital role in making real-world problems "computable."

High-performance computing is not only a cornerstone of modern life, but also a compelling topic in itself. The task of descretizing real-world problems and processing models so that these problems can be solved by computers involves obtaining finite amounts of data from real-world problem domains and replacing them by grids consisting of inter-connected nodes and elements which will serve to model the problem in question on a computer. Altering the size of the grid, its number of nodes, etc. to determine the optimal structure to simulate a certain problem on a computer is the ultimate goal here. The more carefully discretization is accomplished, the more successful the outcome of the model processing will be.

Real-world problems and the computation of their models can pose major challenges to software programmers. Some models are complex enough to require special hardware and call for multiprocessors and supercomputers to compute models. Such complicated models demand specialized algorithms and methods. Parallelization, which takes on many forms and acts at various levels, is a key concept here; part of the aim of parallelization is to allow calculational tasks to be performed simultaneously. Operating at the microinstructional level within the microprocessor, it aims at minimizing the idle time imposed on the processor by the external hardware.

The goal of minimizing runtime as much as possible must be kept in mind when selecting the architecture for particular problems. On the other hand, communication overhead must alsobe kept to a minimum to take maximum advantage of the computing environment chosen.

As the models of real-world problems are simplified mathematical representations of given real-world scenarios, sophisticated tools have to be employed to subdivide the problem domains into manageable chunks' that can be distributed on specialized parallel computers with a certain number of processing nodes. There is always a trade off between communication overhead, runtime or memory consumption. Depending on the given situation, the final solutions for the ultimate realization might vary greatly.

Computer sind heute ein fester Bestandteil in unserem täglichen Leben und haben zu einem extremen Fortschritt in den letzten Jahrzehnten beigetragen. In Forschung und Wissenschaft hat der Einsatz von Computersimulationen die Beantwortung vieler wichtiger und spannender Fragen erst ermöglicht. Ohne solche Simulationen können bestimmte, komplexe Sachverhalte gar nicht angegangen werden, weil z.B. der physische Zugang fehlt oder die betrachteten Zeiträume zu lang sind. Die Untersuchung von Prozessen in vielen 100 km Tiefe in unserer Erde, das Verhalten von radioaktivem Müll, der in einem in Bentonit umschlossenen Metallcontainer eingelagert wird, und den dann stattfindenden Prozessen über viele 1000 Jahre oder präzise Wettervorhersagen auf dem Niveau, wie wir es heute gewohnt sind, gehören zu diesen Sachverhalten.

Aber auch trotz des enormen Fortschritts im Sektor der Computertechnik ist es heute immer noch nicht möglich mit Standardcomputern sehr rechenintensive Probleme zu lösen. Hier ist der Einsatz von Spezialhardware von Nöten, die mehrere 10 Mio. Euro kostet. Erst durch die Nutzung von diesen Höchstleistungsrechnern sind z.B. die heutigen Wettervorhersagen überhaupt erst möglich. Aber auch wichtige Fragestellungen in vielen anderen Gebieten der Wissenschaft können nur mit Hilfe solcher "Number Cruncher" angegangen werden.

Für Computersimulationen erstellt man allgemein immer erst ein Modell oder Abbild der Realität, mit dem dann die Antworten auf bestimmte Fragen berechnet werden sollen.

Bei der Entwicklung von Software, die innerhalb solcher Modelle die vorhandenen Daten verarbeitet und Berechnungen vornimmt, ist es wie mit der Entwicklung eines Formel-1 Wagens: Letztlich handelt es sich, aus der Sicht eines Laien betrachtet, immer noch um ein Auto; tatsächlich ist aber jeder einzelne Formel-1 Wagen eine genau angepasste Einzelanfertigung, an der viele, verschiedene Ingenieure mitentwickelt haben. Genauso verhält es sich mit Software, die auf Höchstleistungsrechnern einmal laufen soll. Für den Laien ist es nichts anderes als ein bisschen Software in C oder Fortran, doch tatsächlich handelt es sich bei diesen Programmen um exakt abgestimmte Spezialsoftware, die genau auf die jeweils unterliegende Hardware angepasst sein muss. Viele einzelne Punkte im Parallelisierungsprozess sind wichtig. Aber nur die Gesamtheit aller notwendigen Einzelschritte ergibt letzten Endes ein lauffähiges, genau auf die Maschine ausgerichtetes Höchstleistungscomputerprogramm.

Typischerweise zeichnen sich die Modelle, die mit den Höchstleistungsrechnern berechnet und simuliert werden sollen dadurch aus, dass sie eine enorme Menge an Eingabedaten bewältigen müssen. Eine gezielte Vorverarbeitung dieser Datensets mit oft mehreren 10er Millionen Eingabedaten, ist ein unabdingbarer Schritt,um im späteren Verarbeitungsprozess, die eigentliche Problem- oder Modellparallelisierung erst angehen und durchführen zu können. Nur wenn die Eingabedaten optimal auf- und vorbereitet sind, kann die unterliegende Spezialhardware sinnvoll für die spätere Modellberechnung genutzt werden.

Trotz der hochwertigen Ausstattung der Höchstleistungsrechner sind auch physikalische Grenzen gesetzt was z.B. die Speichergröße oder die Taktfrequenzen betrifft. Je nach Typ der zu Grunde liegenden Hardware sind verschiedene Beschränkungen vorhanden. Kein Großrechner gleicht notwendigerweise dem anderen, da es keine klassischen Rechner von der Stange sind, wie man sie auf jedem Schreibtisch findet.

In der Regel zeichnen sich Höchstleistungsrechner dadurch aus, dass sie sehr viele extrem schnelle Verarbeitungseinheiten, also Prozessoren besitzen, die untereinander in einer gewissen Weise vernetzt und vor allem auf enorme Rechengeschwindigkeiten bei der Verarbeitung von Gleichungssystemen ausgelegt sind. Die höchsten Verarbeitungsgeschwindigkeiten werden dann erzielt, wenn jeder einzelne Prozessor möglichst ungestört nonstop vor sich hinrechnen kann. Jede Unterbrechung, egal aus welchem Grund, treibt die eigentliche Gesamtverarbeitungszeit nach oben. Daher ist es ein erklärtes Ziel bei dem Einsatz solcher Multiprozessorsysteme, die Unterbrechungszeiten und -mengen so gering wie möglich zu halten.

Auf der anderen Seite werden die Modelle, die berechnet werden sollen, normalerweise durch enorm komplexe partielle Differentialgleichungssysteme dargestellt, die auf den vorhandenen Eingabedaten operieren. Wenn nun mittels eines Höchstleistungsrechners solch ein Problem/Modell gelöst werden soll, müssen zum optimalen Einsatz eines solchen Multiprozessorsystems, die vielen Millionen Eingabedaten sinnvoll auf die einzelnen Verarbeitungseinheiten verteilt werden, so dass die unterliegenden mathematischen Gleichungen und Rechenschritte immer noch korrekt und sinnvoll sind. Man kann also nicht einfach hingehen und die vorhandenen Datensets beliebig auseinanderreißen um sie gezielt zu verteilen. Hier sind ausgefeilte Algorithmen von Nöten, die die Eingabedaten ganz bewusst so in Untersets zerlegen, dass die Gesamtmodellberechnung immer noch korrekt bleibt.

Dabei muss darauf geachtet werden, dass die Zerlegung des Ausgangsproblems derart passiert, dass die Daten optimal auf die einzelnen Verarbeitungseinheiten des Grossrechners verteilt werden. Die Datenverteilung darf nicht dazu führen, dass einige Prozessoren sehr viel arbeiten müssen, während andere die meiste Zeit untätig sind. Nur bei einer vernünftigen sogenannten Lastbalancierung, ist eine optimale und schnellst mögliche Berechnung mittels der Spezialsoftware und den vorhandenen Eingabedaten möglich. Die Lastbalancierung sorgt dafür, dass die Rechenlast gleichmäßig auf die einzelnen Prozessoren verteilt wird.

Bei der Vorverarbeitung dieser großen Eingabedatenmengen müssen viele temporäre Zwischenergebnisse sowie Hilfsvariablen im Speicher gehalten werden. Nicht nur die eigentliche Menge an Eingabedaten muss vernünftig in schnellen und optimal angepassten Datenstrukturen gespeichert werden, sondern auch diese zusätzlichen, weiteren Datenmengen. Obwohl bei den heutigen Großrechnern zwar gewöhnlich bereits schon schnellere und größere Speicher zum Einsatz kommen, ist trotzdem auch deren tatsächliche physikalische Grenze irgendwann einmal erreicht. Ohne den Einsatz einer Datenstruktur, die nicht nur auf die Datenmengen und deren Speicherung für die spätere Weiterverarbeitung angepasst sein muss, sondern gleichzeitig auch auf die optimale Nutzung und Anpassung der unterliegenden Hardware des Großrechners abgestimmt ist, wird direkt automatisch kostbare Rechenleistung durch z.B. unnötige, zusätzliche Verarbeitungsschritte bei der Modellberechnung verschenkt. Die Laufzeiten gehen unnötigerweise in die Höhe und im schlimmsten Fall ist sogar eine Berechnung des Modells durch die Eingabedatenflut erst gar nicht möglich.

Bei einer sinnvollen Vorverarbeitung ist es daher unabdingbar, all diese wichtigen Aspekte optimal miteinander zu vereinigen, auch wenn bestimmte Punkte beinahe widersprüchlich zu einander sind. Nur ein perfekt abgestimmtes Zusammenspiel zwischen Datenstruktur, Lastbalancierung und Gebietszerlegung ermöglicht letzten Endes eine gute Grundlage für eine spätere schnelle und effiziente Parallelisierung des Gesamtproblems.

In der vorliegenden Arbeit ist genau dies das Ziel: bestehende große Eingabedatensets sollen nicht nur perfekt so in Unterprobleme zerlegt werden, dass die mathematischen Gegebenheiten stets ihre Korrektheit behalten, sondern es soll gleichzeitig auch der Kommunikationsoverhead zwischen den vorhandenen späteren Prozessoren zum Zusammenfügen der Einzel- und Zwischenergebnisse minimiert werden, um dadurch die Gesamtrechenzeit zu verkürzen. Ausserdem ist es wichtig auf dem eingesetzten Höchstleistungsrechners durch eine schnelle und platzsparende Datenstruktur den Speicher so optimal wie möglich zu nutzen. Durch diese genau auf das individuelle Problem abgestimmte Vorverarbeitung der gegebenen Daten ist eine optimale parallele Weiterverarbeitung der Eingabedaten zu einem späteren Zeitpunkt erst möglich.

Um die einzelnen Aspekte zu verdeutlichen, die notwenig sind dieses Ziel zu erreichen, wird der Leser schrittweise an die vorhandenen Teilprobleme heran geführt.