KaHIP, ein Open-Source-Tool für die Partitionierung von Berechnungen. Hier zeigen die unterschiedlichen Farben die einzelnen Partitionen. Quelle: Karlsruher Institut für Technologie (KIT)
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.
Der digitale Zwilling einer Organisation bildet reale Geschäftsprozesse virtuell ab und schafft die Grundlage für…
Bestehenden Systeme im Kundenservice stießen an ihre Grenzen. Klassische Chatbots konnten einfache Fragen beantworten.
Kundennähe entsteht nicht per Knopfdruck – sie verlangt Haltung, Aufmerksamkeit und eine klare Strategie. Gerade…
KI wird zunehmend zum Ziel von Cyberangriffen durch Prompt Injections, warnt Christian Nern von KPMG.
Oracle Cloud Isolated Regions sind sichere, vom Internet getrennte Cloud-Lösungen.
Nur Vier Prozent der Unternehmen verfügen über eine definierte Strategie für das Quantencomputing.