Suche...
Generic filters
Exact matches only
Search in title
Search in excerpt
Search in content

Karlsruher Graphpartitionierer vereinfacht komplexes Rechnen

Kategorie:
Autor: Jonas Völker

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

atp weekly

Der Newsletter der Branche

Ihr kostenfreier E-Mail-Newsletter für alle Belange der Automatiserung.

Das könnte Sie auch interessieren:

Bitkom zur Regierungsbildung: Digitalisierung darf keine Verhandlungsmasse sein
Industrie 4.0: Bildungsangebot mit neuen Lehrgängen
NOA: Neues Buch stellt das Konzept und Praxisbeispiele vor

Sie möchten das atp magazin testen

Bestellen Sie Ihr kostenloses Probeheft

Überzeugen Sie sich selbst: Gerne senden wir Ihnen das atp magazin kostenlos und unverbindlich zur Probe!

Finance Illustration 03