ATP!Info

Karlsruher Graphpartitionierer vereinfacht komplexes Rechnen

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) 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

Verwandte Themen
NAMUR-Hauptsitzung: Vorläufiges Programm der Workshops und Vorträge online weiter
Messehallen der 13. FMB – Zuliefermesse Maschinenbau 2017 vollständig belegt weiter
Überarbeitet: NAMUR Empfehlung 131 weiter
VDMA: Robotik und Automation erwirtschaften Rekordumsatz weiter
Starkes Wachstum in der elektrischen Prozessautomation weiter
Intuitiver Balancer für mehr Ergonomie und Sicherheit weiter

Relevante Publikationen für Sie:

„Smarte“ Sensoren in der Feldebene Cover

„Smarte“ Sensoren in der Feldebene

Intelligente Überwachung von industriellen Anlagen
Thomas Glock/FZI Forschungszentrum Informatik / Martin Hillenbrand/FZI Forschungszentrum Informatik / Christoph Weiler/Siemens / Michael Hübner/Ruhr-Universität Bochum, FZI Forschungszentrum Informatik

mehr
µPlant: Modellfabrik für vernetzte heterogene Anlagen Cover

µPlant: Modellfabrik für vernetzte heterogene Anlagen

Automatisierungstechnische Konzeption und Realisierung
Andreas Kroll/Universität Kassel / Axel Dürrbaum/Universität Kassel / David arengas/Universität Kassel / Hassan al Mawla/Universität Kassel / Lars Kistner/Universität Kassel / Alexander Rehmer/Universität Kassel

mehr
Zuverlässigkeitsbewertung in frühen Entwicklungsphasen Cover

Zuverlässigkeitsbewertung in frühen Entwicklungsphasen

Ansatz basierend auf rigide definierten Softwarekomponenten
MICHAEL WEDEL/Universität Stuttgart

mehr