Hierarchischer Baumaufbau im Treecode PEPC - Optimierung des Austausches global benötigter Daten

Thema

Der in Jülich entwickelte Code PEPC ist eine hochskalierende Implementation des klassischen Barnes-Hut Treecodes zur Lösung des N-Teilchen-Problemes. Der zu Grunde liegende Algorithmus reduziert die Anzahl der zwischen den Teilchen zu berechnenden Wechselwirkungen von O(N2) auf die Größenordnung O(NlogN). Hierzu wird eine Octtree-Gebietszerlegung benutzt, die eine Gruppierung nah beieinander liegender Teilchen in Cluster ermöglicht. Mit diesen wird kollektiv über ihre Multipolentwicklung gewechselwirkt.

In den vergangenen Monaten wurde PEPC soweit weiterentwickelt, dass es als weltweit erster Barnes-Hut Treecode die komplette Zahl der 300k Prozessoren des JUGENE effizient einsetzen kann. Der Wechselwirkungsteil des Codes skaliert dabei sogar perfekt bis zu dieser Prozessorzahl. Unerlässlich ist vor der eigentlichen Wechselwirkungsberechnung der Austausch von global benötigten Informationen aus dem Octtree. Während dies bei kleinen Prozessorzahlen vollkommen problemlos ist, zeigt sich dass die Kommunikationszeit hierfür ab ca. 128k Prozessoren einen deutlichen Beitrag zur Gesamtlaufzeit liefert.

Ziel des Gaststudentenprojektes ist, die auszutauschende Datenmenge effizient zu reduzieren. Dazu soll statt der derzeit benutzten Jeder-Mit-Jedem Kommunikation in diesem Schritt ein hierarchisches Kommunikationsschema konzeptioniert, implementiert und dessen Tauglichkeit geprüft werden. Dies bereitet den Code auf Architekturen mit noch deutlich größeren Prozessorzahlen vor und ebnet so den Weg zum vermutlich weltweit ersten Petascale Barnes-Hut Treecode.

Literatur

• Pfalzner/Gibbon Buch über Tree Methods
• Heraeus-Paper

Arbeitsschritte

1. Ausgabe und Verifizierung der Baumstruktur
   • Baum ausgeben und visualisieren
   • Referenzdatensatz erstellen
   • Vergleichskriterien entwickeln, z.B. Baum muss nicht vollständig sein (wenn branches auf höherem Level liegen als zuvor), aber alle vorhandenen Knoten müssen korrekte Multipolinformationen enthalten
2. Vorbereitung von Hilfsfunktionen
   • Verstehen und Extraktion des Codes zur Zusammenfassung der Multipolinformationen von Kinderknoten zum Elternknoten (aus tree_local() und tree_global() )
   • Anpassung von tree_walk()
     • Mitschicken des tatsaechlichen Besitzers beim Beantworten von Requests
     • Statt des Senders von Knoteninformationen muss der tatsaechliche Besitzer genutzt und die Information in den Baum eingepflegt werden.
3. Clustern von Branchinformationen
   • Festlegung eines maximalen Branchlevels blev
   • Prozessen, die zu einem speziellen Knoten auf blev beitragen, tauschen ihre branches jeweils vollständig aus und bauen lokal den Baum bis zu diesem Level auf (Prozesse gehören zu mehreren Gruppen)
   • alle Knoten auf blev werden global ausgetauscht
   • jeder Prozess baut den Baum oberhalb von blev wieder lokal für sich bos zur Wurzel auf

Weitere mgl. Anpassungen/Optimierungen

• "prefetching", d.h. es werden neben dem angeforderten Knoten auch seine Kinder, oder mehr, mitgeschickt
• Antworten/Anfragen ggf. sogar an die "Branch-Gruppe" bzw./oder Nachbarn des Anfordernden schicken
• SMP parallelisierung weiterer PEPC Teile, z.B. tree local, fill, properties