Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Mehr Effizienz für komplexes Rechnen

29.11.2013
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/

Weiterer Kontakt:
Sebastian Schäfer, Fakultät für Informatik, Öffentlichkeitsarbeit, Tel.: +49 721 608-44344, Fax: +49 721 608-4177, E-Mail: sebastian.schaefer@kit.edu

Das Karlsruher Institut für Technologie (KIT) ist eine Körperschaft des öffentlichen Rechts nach den Gesetzen des Landes Baden-Württemberg. Es nimmt sowohl die Mission einer Universität als auch die Mission eines nationalen Forschungszentrums in der Helmholtz-Gemeinschaft wahr. Thematische Schwerpunkte der Forschung sind Energie, natürliche und gebaute Umwelt sowie Gesellschaft und Technik, von fundamentalen Fragen bis zur Anwendung. Mit rund 9000 Mitarbeiterinnen und Mitarbeitern, darunter knapp 6000 in Wissenschaft und Lehre, sowie 24 000 Studierenden ist das KIT eine der größten Forschungs- und Lehreinrichtungen Europas. Das KIT verfolgt seine Aufgaben im Wissensdreieck Forschung – Lehre – Innovation.

Monika Landgraf | idw
Weitere Informationen:
http://www.kit.edu

Weitere Berichte zu: Graphen-Speicher Routenplaner Simulation Verkehrsnetz

Weitere Nachrichten aus der Kategorie Interdisziplinäre Forschung:

nachricht Speiseröhrenkrebs einfacher erkennen
06.03.2017 | Helmholtz Zentrum München - Deutsches Forschungszentrum für Gesundheit und Umwelt

nachricht Neues Labor für die Aufbautechnik von ultradünnen Mikrosystemen
21.02.2017 | Hahn-Schickard

Alle Nachrichten aus der Kategorie: Interdisziplinäre Forschung >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Das anwachsende Ende der Ordnung

Physiker aus Konstanz weisen sogenannte Mermin-Wagner-Fluktuationen experimentell nach

Ein Kristall besteht aus perfekt angeordneten Teilchen, aus einer lückenlos symmetrischen Atomstruktur – dies besagt die klassische Definition aus der Physik....

Im Focus: Wegweisende Erkenntnisse für die Biomedizin: NAD⁺ hilft bei Reparatur geschädigter Erbinformationen

Eine internationale Forschergruppe mit dem Bayreuther Biochemiker Prof. Dr. Clemens Steegborn präsentiert in 'Science' neue, für die Biomedizin wegweisende Forschungsergebnisse zur Rolle des Moleküls NAD⁺ bei der Korrektur von Schäden am Erbgut.

Die Zellen von Menschen und Tieren können Schäden an der DNA, dem Träger der Erbinformation, bis zu einem gewissen Umfang selbst reparieren. Diese Fähigkeit...

Im Focus: Designer-Proteine falten DNA

Florian Praetorius und Prof. Hendrik Dietz von der Technischen Universität München (TUM) haben eine neue Methode entwickelt, mit deren Hilfe sie definierte Hybrid-Strukturen aus DNA und Proteinen aufbauen können. Die Methode eröffnet Möglichkeiten für die zellbiologische Grundlagenforschung und für die Anwendung in Medizin und Biotechnologie.

Desoxyribonukleinsäure – besser bekannt unter der englischen Abkürzung DNA – ist die Trägerin unserer Erbinformation. Für Prof. Hendrik Dietz und Florian...

Im Focus: Fliegende Intensivstationen: Ultraschallgeräte in Rettungshubschraubern können Leben retten

Etwa 21 Millionen Menschen treffen jährlich in deutschen Notaufnahmen ein. Im Kampf zwischen Leben und Tod zählt für diese Patienten jede Minute. Wenn sie schon kurz nach dem Unfall zielgerichtet behandelt werden können, verbessern sich ihre Überlebenschancen erheblich. Damit Notfallmediziner in solchen Fällen schnell die richtige Diagnose stellen können, kommen in den Rettungshubschraubern der DRF Luftrettung und zunehmend auch in Notarzteinsatzfahrzeugen mobile Ultraschallgeräte zum Einsatz. Experten der Deutschen Gesellschaft für Ultraschall in der Medizin e.V. (DEGUM) schulen die Notärzte und Rettungsassistenten.

Mit mobilen Ultraschallgeräten können Notärzte beispielsweise innere Blutungen direkt am Unfallort identifizieren und sie bei Bedarf auch für Untersuchungen im...

Im Focus: Gigantische Magnetfelder im Universum

Astronomen aus Bonn und Tautenburg in Thüringen beobachteten mit dem 100-m-Radioteleskop Effelsberg Galaxienhaufen, das sind Ansammlungen von Sternsystemen, heißem Gas und geladenen Teilchen. An den Rändern dieser Galaxienhaufen fanden sie außergewöhnlich geordnete Magnetfelder, die sich über viele Millionen Lichtjahre erstrecken. Sie stellen die größten bekannten Magnetfelder im Universum dar.

Die Ergebnisse werden am 22. März in der Fachzeitschrift „Astronomy & Astrophysics“ veröffentlicht.

Galaxienhaufen sind die größten gravitativ gebundenen Strukturen im Universum, mit einer Ausdehnung von etwa zehn Millionen Lichtjahren. Im Vergleich dazu ist...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics
Veranstaltungen

Wie Menschen wachsen

27.03.2017 | Veranstaltungen

Zweites Symposium 4SMARTS zeigt Potenziale aktiver, intelligenter und adaptiver Systeme

27.03.2017 | Veranstaltungen

Rund 500 Fachleute aus Wissenschaft und Wirtschaft diskutierten über technologische Zukunftsthemen

24.03.2017 | Veranstaltungen

 
VideoLinks
B2B-VideoLinks
Weitere VideoLinks >>>
Aktuelle Beiträge

Fließender Übergang zwischen Design und Simulation

27.03.2017 | HANNOVER MESSE

Industrial Data Space macht neue Geschäftsmodelle möglich

27.03.2017 | HANNOVER MESSE

Neue Sicherheitstechnik ermöglicht Teamarbeit

27.03.2017 | HANNOVER MESSE