Home | english  | Impressum | Sitemap | Intranet | KIT
Portrait Monika Landgraf
Kontakt:
Monika Landgraf
Pressesprecherin, Leitung Presse

Tel: +49 721 608-47414
Fax: +49 721 608-43658
E-Mail

Abonnement der Presseinformationen

per RSS-Feed

per E-Mail

Presseinformation 155/2013

Mehr Effizienz für komplexes Rechnen

Karlsruher Graphpartitionierer KaHIP schlägt internationale Konkurrenz
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 (Grafik: Dr. Christian Schulz, KIT)
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 (Grafik: Dr. Christian Schulz, KIT)

Sei es das Planen der Wegstrecke von Berlin nach Hamburg, die Simulation von Luftströmungen um ein neues Passagierflugzeug oder Freundschaftsbeziehungen in Facebook - viele wichtige 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 Professor Peter Sanders und Dr. Christian Schulz vom KIT haben nun mit dem Karlsruhe High Quality Partitioner (KaHIP) ein Werkzeug entwickelt, das dabei die bisher weltweit besten Lösungen bietet.

 

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). Sucht man nun eine konkrete Strecke beispielsweise von Berlin nach Hamburg, so müssen große Teile dieses Verkehrsnetzes bei der Planung der Route gar nicht erst betrachtet werden. Insgesamt kann durch die Verwendung eines Partitionierungswerkzeugs wie KaHIP die Berechnung einer Strecke so 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.

 

KaHIP – Open Source

Christian Schulz entwickelte KaHIP im Rahmen seiner Dissertation am KIT gemeinsam mit Professor Peter Sanders. Bereits während der Entwicklungsphase fanden sich in Wissenschaftskreisen wie auch in der Wirtschaft diverse Interessenten für das Programm. Nun steht KaHIP als Open Source Programm zur Verfügung. Im internationalen Vergleich konnte die Entwicklung aus Karlsruhe bereits erste Erfolge erzielen. So setzte sich KaHIP in der zehnten DIMACS Implementation Challenge, einer internationalen Fachkonferenz, ebenso durch, wie im „Walshaw Benchmark“, in dem sich Graphpartitionierer aus der ganzen Welt miteinander messen.

 

„Basierend auf unserer jahrelangen Erfahrung mit der Verarbeitung von Graphen können wir mit KaHIP nun ein Werkzeug anbieten, das für eine Vielzahl von Anwendungen die aktuell weltweit beste Lösungsqualität liefert“, so Professor Peter Sanders vom Institut für Theoretische Informatik am KIT.

 

Für seine bisherige Arbeit an Algorithmen für die Verarbeitung von Graphen wurde Professor Sanders bereits mehrfach ausgezeichnet. Zuletzt im Jahr 2012 mit dem Landesforschungspreis und einem „Google Focused Research Award“ sowie im Jahr 2011 mit dem Gottfried Wilhelm Leibniz-Preis.

 

Nähere Informationen zu KaHIP: http://algo2.iti.kit.edu/documents/kahip/

 

Das Karlsruher Institut für Technologie (KIT) verbindet seine drei Kernaufgaben Forschung, Lehre und Innovation zu einer Mission. Mit rund 9 300 Mitarbeiterinnen und Mitarbeitern sowie 25 000 Studierenden ist das KIT eine der großen natur- und ingenieurwissenschaftlichen Forschungs- und Lehreinrichtungen Europas.

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

le, 29.11.2013

Weiterer Kontakt:

Sebastian Schäfer
Fakultät für Informatik, Öffentlichkeitsarbeit
Tel.: +49 721 608-44344
Fax: +49 721 608-4177
E-Mail: sebastian schaeferBrl9∂kit edu
Das Foto kann in druckfähiger Qualität angefordert werden unter: presseMxh7∂kit edu oder +49 721 608-47414. Die Presseinformation steht auch als PDF-Datei zur Verfügung.