Eine kleine Metis Einführung¶

Achtung: Kommandozeilen-Interface hat sich in metis 5.0 deutlich geändert.

Ziel¶

Ziel dieser kleinen Einführung ist es die Metis Bibliothek zu installieren und ein paar Beispielgraphen zu partitionieren. Zur Erstellung von Beispielgraphen und zur Visualisierung der Partitionierung werden wir auf zwei kleine Python-Skripte zurückgreifen.

Installation¶

Die Installation wird beispielhaft auf einem Ubuntu 8.10 System durchgeführt und geht auf jedem anderen Linux-System ähnlich von statten. Im Falle eines auf rpm-basierenden Systems müssen die folgenden Kommandos entsprechend geändert werden.

• Build-Tools:
  Compiler und Build-Tools installieren:
  

  sudo apt-get install build-essential
     

• Metis Bibliothek:
  Metis runterladen, entpacken und kompilieren:
  

  wget http://glaros.dtc.umn.edu/gkhome/fetch/sw/metis/metis-4.0.tar.gz
  tar xvfz metis-4.0.tar.gz
  cd metis-4.0
  make
    

  
  Optional alle Binaries nach /usr/local/bin verschieben, das in der PATH-Variable angegeben ist:
  

  sudo cp @find ./ -maxdepth 1 -executable -type f@ /usr/local/bin
    

• GraphViz Bibliothek:
  Diese Bibliothek wird zur Visualisierung der Graphen benötigt. Die Bibliothek kann hier heruntergeladen und dann kompiliert werden. Einfacher ist die Installation über die Paketverwaltung:
  

  sudo apt-get install graphviz
    

• Python Bindings für GraphViz:
  Die Bindings können hier heruntergeladen und danach kompiliert werden oder man installiert sie über die Paketverwaltung:
  

  sudo apt-get install python-pygraphviz
    

• Python-Skripte zur Generierung und Visualisierung:
  Auf allen aktuellen Linux-Distributionen ist mindestens Python 2.5 installiert, somit genügt es die beiden Skripte : Graphgen.py und : Graphvis.py nach /usr/local/bin zu kopieren. Danach müssen die beiden Dateien noch ausführbar gemacht werden:
  

  sudo chmod +x /usr/local/bin/Graphgen.py /usr/local/bin/Graphvis.py
    

Kleines Beispiel¶

Wir erstellen einen quadratischen 5x5 Graphen, wie er beispielsweise aus einem FEM-Gitter entstanden sein könnte.

Graphgen.py 5

Es entsteht die Datei graph-5x5 im Metis-Graph-Format. Die erste Zeile der Datei gibt die Anzahl der Knoten und Kanten des Graphen an. In den verbleibenden n Zeilen werden in der i-ten Zeile alle Knoten angegeben, die eine Kante zum Knoten i besitzen. In dem Beispiel steht in der ersten Zeile "25 40", da der Graph 25 Knoten und 40 Kanten besitzt. In den restlichen 25 Zeilen werden jeweils die Nachbarknoten der 25 Knoten aufgelistet. Weitere Details zu dem Format auch bzgl. Gewichtung von Knoten und Kanten sind der Metis-Dokumentation ab Seite 15 zu entnehmen.

Dieser Graph ohne Partitionierung kann mit Graphvis.py in ein SVG-Bild umgewandelt werden.

Graphvis.py graph-5x5

Man erhält die Datei graph-5x5.svg. Der Graph sieht folgendermaßen aus:

Die Metis Bibliothek enthält zwei standalone Programme zur Graphpartitionierung pmetis und kmetis. Das Programm pmetis verwendet ein rekursives Multilevel-Bisektions Verfahren während kmetis ein Multilevel k-fach Partitionierungsverfahren verwendet. Bis zu 8 Partitionen ist pmetis zu empfehlen, darüber hinaus liefert kmetis bessere und schnellere Ergebnisse.

Um den Graph in 3 Teile zu partitionieren verwenden wir pmetis:

pmetis graph-5x5 3

Man erhält die Datei graph-5x5.part.3, welche die Partitionierung für graph-5x5 enthält. In der Ausgabedatei entspricht jede Zeile einem Knoten und enthält eine Zahl welche der Partitionsnummer entspricht. Knoten mit gleicher Partitionsnummer sind in der selben Partition.

Mit Graphvis lässt sich die Partitionierung des Graphen visualisieren:

Graphvis.py graph-5x5 graph-5x5.part.3

Als Ausgabe erhält man die Datei graph-5x5.part.3.svg:

Größeres Beispiel¶

Mit Graphgen.py können auch nicht quadratische Gitter erstellt werden:

Graphgen.py 25 50

Wir partitionieren diesmal in 9 Teile und visualisieren die Partitionierung:

kmetis graph-25x50 9
Graphvis.py graph-25x50 graph-25x50.part.9

Man erhält graph-25x50.part.9.svg (hier stark verkleinert!):

Abschließendes¶

Die normale Verwendung von Metis erfolgt über die Bibliotheksfunktionen, welche ausführlich in der Metis Dokumentation beschrieben werden. Die Bibliotheksfunktionen bieten die Möglichkeit neben dem Edge-Cut auch das Total Communication Volume zu minimieren und auch die Verfahren in der Coarsening und Refinement Phase des Multilevel Verfahrens lassen sich modifizieren.