Karlsruhe | Viele Informatikanwendungen modellieren Beziehungen zwischen Objekten durch Graphen (Netzwerke) im Sinne der diskreten Mathematik. Eine wichtige Technik, um komplexe Berechnungen auf immer größeren Netzwerken bewältigen zu können ist die Zerlegung (Partitionierung) der Graphen in mehrere Teile. Die Informatiker Prof. Peter Sanders und Dr. Christian Schulz vom Karlsruher Institut für Technologie (KIT) haben mit dem Karlsruhe High Quality Partinioner (Kahip) ein Werkzeug entwickelt, das dabei nach Angaben des Instituts die bisher weltweit besten Lösungen bietet.
Graph zur Berechnung der Strömungseigenschaften eines Flugzeugflügels: Die vier Farben zeigen die Partitionierung des Graphen und damit die Verteilung der Berechnung auf vier Rechner. (Bild: Dr. Christian Schulz, KIT)Die modellierten Objekte (Knoten des Graphen) können durch Kahip so in gleich große Blöcke aufgeteilt werden, dass möglichst wenige Verbindungen (Kanten) zwischen den einzelnen Teilen verlaufen. Auf diese Weise lassen sich beispielsweise Routenplaner beschleunigen: Hier wird das im Routenplaner vorhandene Verkehrsnetz aufgeteilt. Ist nun eine konkrete Strecke, zum Beispiel von Berlin nach Hamburg, gesucht, so müssen große Teile des Verkehrsnetzes bei der Planung der Route gar nicht erst betrachtet werden. Mittels eines Partitionierungswerkzeugs wie Kahip lässt sich die Berechnung einer Strecke so deutlich beschleunigen.
Bei komplexen Berechnungen mit sehr detallierten Graphen wie bei der Berechnung der Strömungseigenschaften eines Flugzeugs reicht ein einzelner Rechner oft nicht aus. In solchen Fällen kann das Programm für eine Berechnung auf mehreren Rechnern gleichzeitig sorgen.
Schulz entwickelte Kahip mit Prof. Sanders bei seiner Dissertation am KIT. Inzwischen steht das Ergebnis als Open Source Programm zur Verfügung. Weitere Informationen zu dem Programm gibt es unter algo2.iti.kit.edu/documents/kahip. kit.edu
