KIT-Forscher liefern Open-Source-Tool für komplexe Berechnungen

Für viele wissenschaftliche Anwendungen stellen so genannte Graphen (Netzwerke) eine wichtige Komponente dar. Damit lassen sich Freundschaftsbeziehungen genauso simulieren, wie die Luftströmungen eines Flugzeugs. Wenn die Beziehungen zwischen Objekten zu komplex werden, dann unterteilt man diese Graphen, um diese dann in unterschiedlichen Rechnern simulieren zu können.

Professor Peter Sanders und Dr. Christian Schulz des Karlsruher Institut für Technologie (KIT) haben jetzt mit dem quelleoffenen Karlsruhe High Quality Partitioner (KaHIP) eine neue Technologie für die Partitionierung solcher Berechnungen vorgelegt.

“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 (partitioniert)”, teilt das KIT mit. Damit kann zum Beispiel eine Suche nach einer Wegstrecke von München nach Hamburg beschleunigt werden, weil große Teile der Karte für das gewünschte Ergebnis gar nicht gebraucht werden. So könne laut Aussage der Wissenschaftler die Berechnung einer Strecke auf diese Weise um ein Vielfaches beschleunigt werden.

Bei komplexen Berechnungen mit sehr detaillierten Graphen, wie beispielsweise bei der Berechnung der Strömungseigenschaften eines Flugzeugs, reicht oftmals ein einzelner Rechner nicht mehr aus. Hier kann KaHIP die Berechnungen sinnvoll verteilen und dadurch für eine effiziente, gleichzeitige Berechnung auf mehreren Rechnern der Simulation sorgen. Ausschlaggebend hierfür ist die Anzahl an Kanten, die in einem Graphen zerschnitten werden müssen.

“Das geht umso schneller, je weniger Kanten im Graphen zerschnitten werden. Unser System bietet eine praktikable Lösung des Graphpartitionierungsproblems und zerschneidet dabei bis zu dreimal weniger Kanten als vergleichbare Werkzeuge auf dem Markt”, erklärt Dr. Christian Schulz, wissenschaftlicher Mitarbeiter am Institut für Theoretische Informatik des KIT.

Christian Schulz hat KaHIP im Rahmen seiner Dissertation am KIT gemeinsam mit Professor Peter Sanders entwickelt. Schon in der Entwicklungsphase stieß das Tool in Wissenschaftskreisen wie auch in der Wirtschaft auf Interesse. Nun steht KaHIP als Open Source Programm zur Verfügung. Im internationalen Vergleich konnte die Entwicklung aus Karlsruhe bereits erste Erfolge erzielen. Dass die Karlsruher hier ganze Arbeit geleistet haben, belegen der gewonnen Wettbewerbe DIMACS Implementation Challenge und der “Walshaw Benchmark”, in dem sich Graphpartitionierer aus der ganzen Welt miteinander messen.