Ü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

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

Chaco Jostle Metis ParMetis hMetis PARTY SCOTCH S-HARP
Geometric Schemes:
Coordinate Nested Dissection
Recursive Inertial Bisection
Space-filling Curve Methods
Spectral Methods:
Recursive Spectral Bisection
Multilevel Spectral Bisection
Combinatorial Schemes:
Levelized Nest Dissection
KL/FM
Multilevel Schemes:
Multilevel Recursive Bisection
Multilevel k-way Partitioning
Multilevel Fill-reducing Ordering
Dynamic Repartitioners:
Diffusive Repartitioning
Scratch-Remap Repartitioning
Parallel Graph Partitioners:
Parallel Static Partitioning
Parallel Dynamic Partitioning
Other Formulations:
Multi-constraint Graph Partitioning
Multi-objective Graph Partitioning