N-Körperrechnung mit dedizierter Hardware: GRAPE

 

Die Berechnung des N-Körper-Problems ist häufig Gegenstand astrophysikalischer Simulationen. Auch bei uns im Zirkular oder in Artikeln der Fachgruppe im VdS-Journal ist es das eine oder andere Mal beschrieben worden. Beim N-Körper-Problem werden Vielteilchensysteme, z.B. wechselwirkende Galaxien, behandelt, bei denen die einzelnen Masseteilchen gravitativ miteinander wechselwirken. Im einfachsten Fall wird die Wechselwirkung eines Teilchens mit allen übrigen berechnet. Dies funktioniert bei kleinen Teilchenzahlen (bei Großrechnern beispielsweise bis N=10 000) ganz gut, jedoch wächst die erforderliche Rechenleistung quadratisch mit der Teilchenzahl an. Die Folge ist, dass bereits bei 100 x so vielen Teilchen eine 10 000 erhöhte Rechenzeit einkalkuliert werden muss. Bei größeren Teilchenzahlen muss man algorithmisch in die Trickkiste greifen, z.B. mit dem Treecode von Barnes und Hut, dem Fast-Multipole-Algorithmus (FMM) oder der Particle-Mesh-Technik.

Bekanntlich führen viele Wege nach Rom. Ein anderer Ansatz ist z.B. die Verwendung von dedizierter Hardware - dediziert in diesem Kontext heißt, dass die Hardware für einen speziellen Zweck zielgerichtet entwickelt wurde; sie steht damit im Gegensatz zur Allzweck-Hardware wie unsere PCs. Für das N-Körperproblem gibt es seit mehr als 20 Jahren das Projekt GRAPE (Gravitational Pipe), welches mittlerweile in die achte Generation eingetreten ist. GRAPE ist genau eine solche dedizierte Hardware, die darauf maßgeschneidert wurde, die gravitative Wechselwirkung des N-Körper-Problems optimal parallelisiert zu berechnen.

Die achte Generation von GRAPE basiert auf Structured ASIC, einer Plattform für programmierbare Hardware, ähnlich zu FPGA. Mittels reprogrammierbarer Hardware lassen sich Verschaltungslogiken realisieren, die für bestimmte Berechnungen ausgelegt sind. Es wird also primär keine Software Programmiert, sondern rekonfigurierbare Hardware (als Sprache kommt oft VHDL zum Einsatz). Ausgereifte Schaltungsdesigns sind oft wesentlich schneller als Algorithmen, die auf Mehrzweckprozessoren wie x86 implementiert werden. Man kann z.B. auf  einem Structured ASIC mehrere Rechenkerne erzeugen, die auf den gleichen Speicher arbeiten. Die Ansteuerung des GRAPE-Systems erfolgt in Verbindung mit einem handelsüblichen PC, dem Host des Gesamtsystems.

Bei der numerischen Integration von GRAPE besitzt jedes einzelne Teilchen sein eigenes Zeitschema, im Gegensatz zu vielen anderen Verfahren (z.B. Runge-Kutta), bei denen alle Probeteilchen des betrachteten Ensembles im identischen Zeitraster integriert werden. Um eine maximale Effizienz bei der Umsetzung in Hardware zu erreichen wurde als Integrationsschema ein Zwei-Schritt-Prädiktor-Korrektor-Verfahren vierter Ordnung (s. 2. Literaturangabe für Details) ausgewählt, wobei für die Interpolation das Hermite-Schema zum Einsatz kommt (Vorteil: größere Schrittweiten möglich).

GRAPE kombiniert zudem die Vorteile rekonfigurierbarer Hardware mit den Algorithmen, die im ersten Absatz aufgezählt wurden. Im Treecode beispielsweise werden bei der Berechnung der gravitativen Wechselwirkung entfernte Massen zusammengefasst und nur noch der gemeinsame Schwerpunkt beachtet. Zudem kann bei entfernten Massenpunkten eine grobmaschigere Zeitskala angewandt werden (erst dadurch bekommt die individuelle Zeitskala für jeden Partikel überhaupt erst einen Sinn). Außerdem wird anhand der nächsten Nachbarn eines jeden Partikels ein Gravitationspotential der unmittelbaren Umgebung bestimmt, die  wiederum die Berechnung der Wechselwirkung abkürzt (Fast Multipole Algorithm).

Der Knackpunkt ist nun, dieses Gemenge an kombinierten Algorithmen zu parallelisieren. Das individuelle Zeitraster für jedes der N Teilchen ist zunächst kontraproduktiv, jedoch lassen sich diese N Zeitraster zu Blöcken von wenigen diskreten Zeitrastern (Schrittweiten als Zweierpotenzen eine Basisschrittweite) umstrukturieren, was der Parallelisierbarkeit wieder entgegenkommt. Wie kann aber nun die Berechnung der gravitativen Wechselwirkung erfolgen? Im einfachsten Fall bekommt jede Recheneinheit ein komplettes Abbild des Ensembles, welches nach der Berechnung wieder an alle übrigen Einheiten verteilt wird. Dies funktioniert jedoch nur bei einer kleinen Anzahl an Cores; die Kommunikationswege für die aktualisierten Daten werden zum Engpass. GRAPE geht einen anderen Weg: die Berechnung der Kräfte fij (Kraft des Teilchens j auf das Teilchen i) führt zu einer Anordnung der Prozessoren in einem zweidimensionalen Feld. Jede Recheneinheit pij verwaltet Teilchen, die sowohl aus der Gruppe i als auch der Gruppe j angehören, und berechnet die Kräfte aufeinander. Die Gesamtkraft wird durch Summation in j-Richtung ermittelt; anschließend aktualisieren die Prozessoren die Gruppe i mit den neuen Daten.

Die Kombination der Blockanordnung der Zeitraster mit dem 2-D-Array führt zu einer ungleichmäßigen Auslastung der Rechenkerne. Mittels des Ninja-Schemas (s. zweite Literaturangabe) lässt sich der Algorithmus noch um ein Load Balancing verfeinern.

Die heutigen Simulationsmodelle beschränken sich oft nicht mehr auf reine N-Körper-Rechnung wie in den Anfangsjahren. Viele Phänomene lassen sich nur dann nachvollziehen, wenn die numerischen Modelle zusätzlich mit weitergehender Physik ausgestattet werden wie die Molekulardynamik, bei der die Van-der-Waals- und die Coulomb-Kräfte berücksichtigt werden müssen. GRAPE wurde daraufhin konzipiert, auch diese Gebiete abzudecken.

Angesichts der bisherigen Langlebigkeit und der immer weiter reichenden algorithmischen Möglichkeiten wird das Projekt GRAPE noch lange nicht am Ende seiner Entwicklung angelangt sein.