Übersicht Partitionierungsalgorithmen¶

Literatur¶

• Graph Partitioning For High Performance Scientific Simulations: attachment:GraphPartitioningForHighPerformanceScientificSimulations.pdf (Gute Einführung, Erläuterung aller wichtigen Algorithmen und Bibliotheken)
• Graph Partitioning: attachment:GraphPartitioning.ps.gz (Mathematisch fundierte Einführung in die Partitionierung)
• Graph Partitioning Models for Parallel Computing: attachment:GraphPartitioningModelsForParallelComputing.pdf (Schwächen aktueller Partitionierer, neue Methoden, Hypergraphen)
• Load Balancing for Unstructured Mesh Applications (Statische und dynamische Load Balancing Algorithmen)
• The Graph Partitioning Archive (Archiv für Testgraphen und Edge-Cut Benchmarks verschiedener Partitionierungsbibliotheken)

Bibliotheken¶

• Chaco
• Jostle
• Metis
• ParMetis
• hMetis
• PARTY
• SCOTCH
• Zoltan
• S-HARP ⚠ nicht länger verfügbar
• PMRSB ( stb@renaissance.cray.com ) ⚠ nur für Cray
• TOP/DOMDEC ( charbel@boulder.colorado.edu ) ⚠ nur auf Silicon Graphics (IRIS) und IBM RS6000
• WGPP ⚠ nicht verfügbar
• Mondriaan ⚠ nur für dünn besetzte Matrizen
• PaToH ⚠ unvollständiges Manual
• MeshPart ⚠ veraltete Matlab Toolbox

Anmerkung:

Die Bibliothek Metis gibt es in drei Ausführungen. Zum einen die Bibliothek für statische Partitionierung namens Metis. Zur dynamischen Partitionierung (Repartitionierung) auf Parallelrechnern existiert ParMetis. Die Bibliothek hMetis ist speziell für Hypergraphen konzipiert. Zoltan ist ein reines Toolkit für Dynamic Load Balancing, Matrix Ordering, Graph Coloring und Data Migration. Es implementiert keine Algorithmen selbst sondern bietet eine gemeinsame Schnittstelle zu Jostle, ParMetis, PaToH und anderen Bibliotheken. Eine kleine Metis Einführung befindet sich hier.

Verfahren¶