Personal tools

SCCS Colloquium - July, 30, 2008

From Sccswiki

Jump to: navigation, search
Date: July 30
Room: 02.07.023
Time: 5 pm, s.t.

17:00 Uhr - Christian Konrad: Numerische Aspekte und Aspekte der Parallelisierung zur Lösung des gekoppelten Maxwell/Vlasov Systems (IDP)

Raumfüllende Kurven als Mittel zur Partitionierung von Rechengittern haben sich in den letzten Jahren zunehmend etabliert da die Methodik ausgesprochen schnell ist, sie automatisch zu einer Cache-effizienten Datenspeicherung fuehrt und die Partitionen zufriedenstellende Kantenschnitte aufweisen. Parallele Simulationen für multi-physics Probleme, wie in unserem Falle die Particle-In-Cell Diskretisierungsmethode für das gekoppelte Maxwell/Vlasov System, stellen Gebietszerlegungsprobleme dar, die es erfordern, mehrere Bedingungen gleichzeitig zu balancieren (multi-constraint problems). Insbesondere erhalten wir ein 2-constraint Problem. Im Unterschied zu 1-constraint Problemen reicht es hier nicht aus die Indices der Gitterelemente bzgl. einer raumfuellenden Kurve zu berechnen, diese zu sortieren und Partitionen als zusammenhaengende Intervalle zu bestimmen. Da es in unserer speziellen Anwendung nötig ist während der Simulation mehrmals erneut zu partitionieren wird ein schneller Partitionierer benötigt.

Im Rahmen dieser Diplomarbeit wurde eine neue, auf raumfüllenden Kurven basierende Methodik für 2-constraint Probleme entwickelt. Diese Methode fuehrt zu einem interessanten, kombinatorischen (und NP-kompletten) Problem, dem wir mit einer Erweiterung des Karmarkar-Karp Algorithmus (bekannt als die beste Heuristik für das Aufteilungsproblem einer Menge von Integerzahlen) begegnen. Wir vergleichen unsere Partitionierungsergebnisse mit Ergebnissen, die der Graph-Partitionierer MeTiS erzielt. Dabei ist festzustellen, dass unsere Methode etwa 100 mal schneller ist und im Mittel zu Kantenschnitten fuehrt, die etwa 2 bis 3 Mal so hoch sind, wie sie MeTiS erzeugt.