Graphpartitionierung

Graphpartitionierung bezeichnet die Anwendung geeigneter Algorithmen zur Berechnung von Graphpartitionen (vgl. Schnitt (Graphentheorie)) mit gewünschten Eigenschaften.

Graphpartitionierung in der parallelen Programmierung

Um die Vorteile eines parallelen Systems optimal ausnutzen zu können, sind zwei Kriterien zu erfüllen:

1. Die Rechenlast muss gleichmässig auf die Recheneinheiten verteilt werden.
2. Die zur Abarbeitung des Programms nötige Kommunikation zwischen den Recheneinheiten soll möglichst klein gehalten werden, da diese zusätzliche Ausführungszeit beansprucht.

Dieses Optimierungsproblem lässt sich als Graph-Partitionierungsproblem formulieren, wenn die einzelnen Berechnungsaufgaben als Knoten eines Graphen modelliert werden. Für jede Berechnung, welche vom Resultat einer andern Berechnung abhängig ist, werden die entsprechenden Knoten mit einer Kante verbunden. Die einzelnen Teilmengen des Graphen widerspiegeln die Recheneinheiten, auf welche die Aufgaben verteilt werden sollen. Damit lautet das Optimierungsproblem neu: Finde eine Partition des gegebenen Graphen so, dass:

1. Die Knoten gleichmässig auf die Teilmengen verteilt sind.
2. Möglichst wenig Kanten Knoten aus verschiedenen Partitionen verbinden.

Kanten, deren adjazente Knoten in unterschiedlichen Partitionen liegen, werden Schnittkanten genannt.

Man kann das Optimierungsproblem auch für gewichtete Graphen formulieren. Damit lassen sich unterschiedlich schwierige Rechenaufgaben durch verschiedene Knotengewichte darstellen. Ebenso kann durch gewichtete Kanten der Datenaustausch von unterschiedlichen Datenmengen modelliert werden. Das Optimierungsproblem heisst also allgemeiner:

1. Das Knotengewicht gleichmässig auf die Teilmengen aufteilen und
2. die Summe der Gewichte der geschnittenen Kanten minimieren.

Die Summe der Gewichte der geschnittenen Kanten wird auch als Schnittgrösse (engl. cutsize, edge-cut) bezeichnet. Die obige, spezielle Formulierung des Optimierungsproblems ist mit diesem äquivalent, wenn alle Kanten und Knoten das Gewicht 1 erhalten.

Algorithmen

Die optimale Partition für einen Graphen zu finden, ist ein NP-vollständiges Problem. Deshalb existiert eine Reihe von vorgeschlagenen Algorithmen oder Ansätzen, um in kurzer Zeit wenigstens annähernd optimale Partitionen zu finden:

• Recursive Bisection: Teile den Graphen in 2 Teile (engl. Bisection, Schnitt). Diese werden rekursiv wiederum zweigeteilt, usw., bis die gewünschte Anzahl Teilmengen erreicht ist (muss für diese Anwendung eine Potenz von 2 sein, $n=2^{k}$)
• Coordinate Nested Dissection
• Spectral Bisection
• Multilevel schemes
• Kernighan-Lin/Fidduccia-Mattheyses
• ...

Quellen

• Artikel "Graph Partitioning - a survey" von U. Elsner, s. http://www.mathematik.tu-chemnitz.de/preprint/1997/SFB393_27.html