Graphpartitionierung

Graphpartitionierung
Partitionierter Graph

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

Inhaltsverzeichnis

Graphpartitionierung in der parallelen Programmierung

Formulierung des Problems

Graphpartitionierung findet vor allem in der Parallelverarbeitung Verwendung: Um in einem rechenintensiven Computerprogramm die Vorteile eines parallelen Systems optimal ausnutzen zu können, muss dieses zwei Kriterien erfüllen:

  1. Die Rechenlast muss gleichmäßig 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 immense Ausführungszeit beansprucht.

Das Optimierungsproblem als Graphpartitionierungsproblem

Dieses Optimierungsproblem lässt sich als Graph-Partitionierungsproblem formulieren:

  • Die einzelnen Berechnungsaufgaben im Programm werden als Knoten eines Graphen modelliert.
  • Für jede Berechnung, welche vom Resultat einer anderen Berechnung abhängig ist, werden die entsprechenden Knoten mit einer Kante verbunden.
  • Nach dem Partitionieren spiegeln die berechneten Teilmengen des Graphen die Prozessoren wider, auf welche die Aufgaben verteilt werden sollen.

Damit lautet das Optimierungsproblem neu: Finde eine Partition des gegebenen Graphen so, dass:

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

Kanten, deren adjazente Knoten in unterschiedlichen Teilmengen liegen, werden durch die Partition geschnitten und deshalb als Schnittkanten bezeichnet.

Gewichtete Graphen

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

  1. Das Knotengewicht gleichmäßig 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öße (engl. cutsize, edge-cut) bezeichnet. Die obige, spezielle Formulierung des Optimierungsproblems ist mit diesem äquivalent, wenn alle Kanten und Knoten das Gewicht 1 erhalten.

Beispiel

In der obigen Abbildung wurde ein (ungewichteter) Graph mit sechs Knoten und acht Kanten in zwei Teile geschnitten, zu je drei Knoten. Eine Teilmenge wird Prozessor 1 zugewiesen, die andere Prozessor zwei. Dabei werden zwei Kanten geschnitten, was einen gewissen Kommunikationsaufwand bedeutet. Es existiert keine andere gleichmäßige Verteilung der Knoten, die nicht mehr als zwei Schnittkanten bewirken würde. Somit ist diese Partition optimal.

Algorithmen

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

Diese lassen sich in etwa gliedern nach den Ansätzen, die sie verfolgen:

Rekursive Bisektion

Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete Divide-and-conquer-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen geschnitten wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl k von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. k = 2t für ein t \in \{1,2,3,...\} (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der 2t Prozessoren enthält.

Durch Anwendung von rekursiver Bisektion nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.

Geometrische Algorithmen

Geometrische Algorithmen machen Gebrauch von Koordinateninformationen der Knoten. Ein Graph besitzt als solches keine Koordinaten. Bei manchen Anwendungsbereichen wird der Graph aber aus einem zwei- oder dreidimensionalen Netz gebildet. Das ist z. B. der Fall, wenn in einer physikalischen Simulation ein reelles Objekt mittels eines Netzes modelliert wird, an welchem dann Berechnungen in jedem Knoten durchgeführt werden sollen. Meist sind diese jeweils nur von den Resultaten der benachbarten Knoten abhängig, so dass das Netz direkt als Graph für die Partitionierung übernommen werden kann. Die Koordinateninformationen solcher Netze widerspiegeln dann ziemlich gut die Topologie des Graphen.

Beispiele für geometrische Algorithmen:

  • Koordinatenbisektion: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.
  • Inertialbisektion: Berechne die Inertialachse und wähle diese anstelle einer Koordinatenachse.

Spektrale Bisektion

Die Idee der spektralen Bisektion ist, das (diskrete) Optimierungsproblem mathematisch in einem stetigen Gleichungssystem zu formulieren und die Lösung analytisch herzuleiten. Danach versucht man, die Lösung des stetigen Gleichungssystems diskret anzunähern.

Kombinatorische Algorithmen

Für Graphpartitionierung ohne Koordinateninformation gibt es eine Reihe kombinatorischer Algorithmen, welche hier nur namentlich erwähnt werden:

Multilevel-Partitionierung

Einfaches Beispiel einer ML-Partitionierung (1→2: coarsening, 2→3: Partitionierung, 3→4: refinement)

Die Idee hierbei ist, einen großen Graphen mittels sogenannter Matchings zusammenzuschrumpfen zu einem kleineren, welcher die globale Struktur des ursprünglichen repräsentiert. Diese Schrumpfung (engl. coarsening) wird mehrmals wiederholt, bis nur noch wenige (z. B. weniger als 100) Knoten vorhanden sind. Danach wird der kleinste Graph partitioniert. Die Partitionierung wird auf den nächstgrößeren Graphen zurückgerechnet und dort z. B. mittels Kernighan-Lin optimiert (engl. refinement), danach wieder auf den nächstgrößeren Graphen zurückgerechnet, bis man beim ursprünglichen Graphen gelandet ist. Mit diesem Schema wird sowohl die lokale als auch die globale Topologie des Graphen berücksichtigt, was zu sehr guten Ergebnissen führt.

Literatur

  • U. Elsner: Graph partitioning - a survey. 1997 (englisch).

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Partitionierungsproblem — Das Partitionierungsproblem ist ein mathematisches Problem, das durch seine NP Schwere eine große Bedeutung in der Informatik erlangt hat. Es beschäftigt sich mit der Frage, einen Algorithmus zu finden, mit dem sich Zahlen in additive… …   Deutsch Wikipedia

  • Nichtsequentielle Programmierung — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Parallele Programmierung ist ein Programmierparadigma. Damit ist… …   Deutsch Wikipedia

  • Nichtsequenzielle Programmierung — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Parallele Programmierung ist ein Programmierparadigma. Damit ist… …   Deutsch Wikipedia

  • Partitionen — Partition (lat. partitio ‚Abschnitt, Teil‘), beziehungsweise teils auch Partitionierung (‚Aufteilung‘), steht in der Politik für die Landesteilung für eine logische Unterteilung von Systemressourcen, siehe Partition (Festplatte) für die… …   Deutsch Wikipedia

  • Partitionieren — Partition (lat. partitio ‚Abschnitt, Teil‘), beziehungsweise teils auch Partitionierung (‚Aufteilung‘), steht in der Politik für die Landesteilung für eine logische Unterteilung von Systemressourcen, siehe Partition (Festplatte) für die… …   Deutsch Wikipedia

  • Partitionierung — Partition (lat. partitio ‚Abschnitt, Teil‘), beziehungsweise teils auch Partitionierung (‚Aufteilung‘), steht in der Politik für die Landesteilung für eine logische Unterteilung von Systemressourcen, siehe Partition (Festplatte) für die… …   Deutsch Wikipedia

  • Arcflag — (eng. Kantenflagge) (2005, Möhring et al.[1]), Arc Flag oder Arcflags, ist eine zielgerichtete Beschleunigungstechnik für den Dijkstra Algorithmus zur Suche des kürzesten Pfades zwischen zwei Knoten in einem gewichteten Graphen. Die Grundidee… …   Deutsch Wikipedia

  • Funktionsbaum — Ein Funktionsbaum für Spaghetti Bolognese Ein Funktionsbaum ist ein Diagramm, das die Abhängigkeit von Funktionen eines Systems untereinander beschreibt. Man könnte auch sagen, ein Funktionsbaum zeigt, wie sich ein Problem (bzw. eine… …   Deutsch Wikipedia

  • Parallele Programmierung — ist ein Programmierparadigma. Es umfasst zum einen Methoden, ein Computerprogramm in einzelne Teilstücke aufzuteilen, die nebenläufig ausgeführt werden können, zum anderen Methoden, nebenläufige Programmabschnitte zu synchronisieren. Dies steht… …   Deutsch Wikipedia

  • Schnitt (Graphentheorie) — Ein Schnitt bezeichnet in der Graphentheorie eine Menge von Kanten eines Graphen G = (V,E), die zwischen zwei Mengen von Knoten bzw. zwischen einer Menge und der Restmenge liegt. Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”