Graphpartitionierung

Grundidee und Ziel

Graphpartitionierung bedeutet, mit geeigneten Algorithmen eine Partition, also eine Aufteilung, der Knoten eines Graphen zu berechnen. Gesucht sind dabei Teilmengen mit bestimmten gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn seine Knoten in r Teile aufgeteilt werden können, sodass die Endknoten jeder Kante in verschiedenen Partitionsklassen liegen.

Besonders wichtig ist Graphpartitionierung in der parallelen Programmierung. Dort soll ein rechenintensives Programm auf mehrere Recheneinheiten, zum Beispiel Prozessoren, verteilt werden. Dabei müssen zwei Ziele gleichzeitig erfüllt werden: Die Rechenlast soll möglichst gleichmäßig verteilt sein, und die Kommunikation zwischen den Recheneinheiten soll möglichst klein bleiben, weil Kommunikation viel Ausführungszeit beanspruchen kann.

Modellierung als Optimierungsproblem

Das Verteilungsproblem eines parallelen Programms kann als Graphpartitionierungsproblem beschrieben werden. Einzelne Berechnungsaufgaben werden als Knoten eines Graphen modelliert. Wenn eine Berechnung vom Ergebnis einer anderen Berechnung abhängt, werden die entsprechenden Knoten durch eine Kante verbunden.

Nach der Partitionierung stehen die Teilmengen des Graphen für die Prozessoren, auf die die Aufgaben verteilt werden sollen. Das Ziel lautet dann: Die Knoten sollen gleichmäßig auf die Teilmengen verteilt werden, und möglichst wenige Kanten sollen Knoten verbinden, die in verschiedenen Teilmengen liegen.

Kanten, deren inzidente Knoten in unterschiedlichen Teilmengen liegen, heißen Schnittkanten. Sie stehen in der Anwendung für Kommunikation zwischen Prozessoren. Eine gute Partition hat daher eine ausgewogene Verteilung der Knoten und nur wenige Schnittkanten.

Gewichtete Graphen und Schnittgröße

Das Problem lässt sich allgemeiner für gewichtete Graphen formulieren. Ein Knotengewicht kann ausdrücken, dass Berechnungsaufgaben unterschiedlich aufwendig sind. Ein Kantengewicht kann ausdrücken, dass zwischen zwei Aufgaben unterschiedlich große Datenmengen ausgetauscht werden müssen.

In dieser allgemeineren Form soll das Knotengewicht gleichmäßig auf die Teilmengen verteilt werden. Gleichzeitig soll die Summe der Gewichte der geschnittenen Kanten minimiert werden. Diese Summe heißt Schnittgröße, auf Englisch cutsize oder edge-cut.

Die ungewichtete Form des Problems ist ein Spezialfall davon: Wenn alle Kanten und alle Knoten das Gewicht 1 erhalten, entspricht sie der gewichteten Formulierung.

Beispiel einer optimalen Partition

Das Beispiel im Artikel beschreibt einen ungewichteten Graphen mit sechs Knoten und acht Kanten. Er wird in zwei Teile mit jeweils drei Knoten geschnitten. Eine Teilmenge wird Prozessor 1 zugewiesen, die andere Teilmenge Prozessor 2.

Bei dieser Aufteilung werden zwei Kanten geschnitten. Diese Schnittkanten bedeuten einen Kommunikationsaufwand zwischen den Prozessoren. Laut Artikel gibt es keine andere gleichmäßige Verteilung der Knoten, die höchstens zwei Schnittkanten bewirkt. Deshalb ist diese Partition optimal.

Algorithmische Grundprobleme und wichtige Verfahren

Die optimale Partition eines Graphen zu berechnen, ist ein NP-äquivalentes Problem. Deshalb verwendet man häufig Heuristiken. Eine Heuristik ist ein Verfahren, das in kurzer Zeit eine gute, aber nicht unbedingt perfekte Lösung finden soll.

Ein verbreitetes Grundverfahren ist die rekursive Bisektion. Dabei wird der Graph zunächst nur in 2 Teilmengen zerlegt. Die entstehenden Teilgraphen werden dann wieder in zwei Teile zerlegt, bis die gewünschte Anzahl k von Teilmengen erreicht ist. Dafür muss k eine Zweierpotenz sein, also k = 2^t für ein t aus {1,2,3,...}. Diese Methode folgt dem Divide-and-conquer-Prinzip. Man nimmt dabei eine suboptimale Lösung in Kauf, gewinnt aber viel Zeit.

Geometrische Algorithmen nutzen Koordinateninformationen der Knoten. Ein Graph hat zwar normalerweise keine Koordinaten, aber in manchen Anwendungen entsteht er aus einem zwei- oder dreidimensionalen Netz, etwa bei einer physikalischen Simulation eines realen Objekts. Beispiele sind die Koordinatenbisektion und die Inertialbisektion. Bei der Koordinatenbisektion wählt man die Koordinate, in der die Knoten am weitesten auseinanderliegen, und einen Grenzwert c, sodass für die Hälfte der Knoten zum Beispiel x > c gilt. Bei der Inertialbisektion wird statt einer Koordinatenachse die Inertialachse verwendet.

Die spektrale Bisektion versucht, das diskrete Optimierungsproblem zuerst als stetiges Gleichungssystem zu formulieren und analytisch zu lösen. Anschließend wird versucht, diese stetige Lösung diskret anzunähern.

Für Graphen ohne Koordinateninformation gibt es kombinatorische Algorithmen. Der Artikel nennt Graph growing, Greedy-Algorithmen sowie Kernighan-Lin/Fidduccia-Mattheyses.

Multilevel-, Streaming- und Softwareansätze

Bei der Multilevel-Partitionierung wird ein großer Graph durch sogenannte Matchings schrittweise zu einem kleineren Graphen zusammengeschrumpft. Dieser Vorgang heißt coarsening. Er wird mehrfach wiederholt, bis nur noch wenige Knoten vorhanden sind, zum Beispiel weniger als 100. Danach wird der kleinste Graph partitioniert. Diese Partitionierung wird anschließend auf den nächstgrößeren Graphen zurückgerechnet und dort zum Beispiel mit Kernighan-Lin verbessert; dieser Schritt heißt refinement. So arbeitet man sich bis zum ursprünglichen Graphen zurück. Das Verfahren berücksichtigt lokale und globale Topologie des Graphen und führt laut Artikel zu sehr guten Ergebnissen.

Streaming-Algorithmen lesen Kanten oder Knoten in beliebiger Reihenfolge ein und verteilen sie nacheinander mithilfe einer Heuristik auf Partitionen. Der Vorteil ist, dass nicht der gesamte Graph im Speicher gehalten werden muss. Außerdem haben Streaming-Algorithmen wegen ihrer einfachen Heuristik eine geringe Latenz. Werden Knoten gestreamt, spricht man von Edge-Cut; im Fall von Kanten spricht man von Vertex-Cut. Als Beispiele nennt der Artikel HDRF und Greedy.

Ein besonderer Streaming-Ansatz ist ADWISE. Dieser Algorithmus verwendet zusätzlich einen Kanten-Buffer. Innerhalb der Buffergröße kann er seine Kantenzuweisungen optimieren. Über die Buffergröße lässt sich auch die Laufzeit beeinflussen: Je größer der Buffer ist, desto besser wird die berechnete Partitionierung, aber desto größer ist auch die Latenz.

Als Open-Source-Pakete zur Graphpartitionierung nennt der Artikel KaHIP, ausgeschrieben Karlsruhe High Quality Partitioning, außerdem kMetis und Scotch.