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 Studie für Patienten mit Prostatakrebs: Einteilung in genomische Gruppen soll Therapie präzisieren
21.08.2017 | Universitätsklinikum Heidelberg

nachricht Fake News finden und bekämpfen
17.08.2017 | Fraunhofer-Institut für Sichere Informationstechnologie SIT

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: Wissenschaftler entdecken seltene Ordnung von Elektronen in einem supraleitenden Kristall

In einem Artikel der aktuellen Ausgabe des Forschungsmagazins „Nature“ berichten Wissenschaftler vom Max-Planck-Institut für Chemische Physik fester Stoffe in Dresden von der Entdeckung eines seltenen Materiezustandes, bei dem sich die Elektronen in einem Kristall gemeinsam in einer Richtung bewegen. Diese Entdeckung berührt eine der offenen Fragestellungen im Bereich der Festkörperphysik: Was passiert, wenn sich Elektronen gemeinsam im Kollektiv verhalten, in sogenannten „stark korrelierten Elektronensystemen“, und wie „einigen sich“ die Elektronen auf ein gemeinsames Verhalten?

In den meisten Metallen beeinflussen sich Elektronen gegenseitig nur wenig und leiten Wärme und elektrischen Strom weitgehend unabhängig voneinander durch das...

Im Focus: Wie ein Bakterium von Methanol leben kann

Bei einem Bakterium, das Methanol als Nährstoff nutzen kann, identifizierten ETH-Forscher alle dafür benötigten Gene. Die Erkenntnis hilft, diesen Rohstoff für die Biotechnologie besser nutzbar zu machen.

Viele Chemiker erforschen derzeit, wie man aus den kleinen Kohlenstoffverbindungen Methan und Methanol grössere Moleküle herstellt. Denn Methan kommt auf der...

Im Focus: Topologische Quantenzustände einfach aufspüren

Durch gezieltes Aufheizen von Quantenmaterie können exotische Materiezustände aufgespürt werden. Zu diesem überraschenden Ergebnis kommen Theoretische Physiker um Nathan Goldman (Brüssel) und Peter Zoller (Innsbruck) in einer aktuellen Arbeit im Fachmagazin Science Advances. Sie liefern damit ein universell einsetzbares Werkzeug für die Suche nach topologischen Quantenzuständen.

In der Physik existieren gewisse Größen nur als ganzzahlige Vielfache elementarer und unteilbarer Bestandteile. Wie das antike Konzept des Atoms bezeugt, ist...

Im Focus: Unterwasserroboter soll nach einem Jahr in der arktischen Tiefsee auftauchen

Am Dienstag, den 22. August wird das Forschungsschiff Polarstern im norwegischen Tromsø zu einer besonderen Expedition in die Arktis starten: Der autonome Unterwasserroboter TRAMPER soll nach einem Jahr Einsatzzeit am arktischen Tiefseeboden auftauchen. Dieses Gerät und weitere robotische Systeme, die Tiefsee- und Weltraumforscher im Rahmen der Helmholtz-Allianz ROBEX gemeinsam entwickelt haben, werden nun knapp drei Wochen lang unter Realbedingungen getestet. ROBEX hat das Ziel, neue Technologien für die Erkundung schwer erreichbarer Gebiete mit extremen Umweltbedingungen zu entwickeln.

„Auftauchen wird der TRAMPER“, sagt Dr. Frank Wenzhöfer vom Alfred-Wegener-Institut, Helmholtz-Zentrum für Polar- und Meeresforschung (AWI) selbstbewusst. Der...

Im Focus: Mit Barcodes der Zellentwicklung auf der Spur

Darüber, wie sich Blutzellen entwickeln, existieren verschiedene Auffassungen – sie basieren jedoch fast ausschließlich auf Experimenten, die lediglich Momentaufnahmen widerspiegeln. Wissenschaftler des Deutschen Krebsforschungszentrums stellen nun im Fachjournal Nature eine neue Technik vor, mit der sich das Geschehen dynamisch erfassen lässt: Mithilfe eines „Zufallsgenerators“ versehen sie Blutstammzellen mit genetischen Barcodes und können so verfolgen, welche Zelltypen aus der Stammzelle hervorgehen. Diese Technik erlaubt künftig völlig neue Einblicke in die Entwicklung unterschiedlicher Gewebe sowie in die Krebsentstehung.

Wie entsteht die Vielzahl verschiedener Zelltypen im Blut? Diese Frage beschäftigt Wissenschaftler schon lange. Nach der klassischen Vorstellung fächern sich...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

International führende Informatiker in Paderborn

21.08.2017 | Veranstaltungen

Wissenschaftliche Grundlagen für eine erfolgreiche Klimapolitik

21.08.2017 | Veranstaltungen

DGI-Forum in Wittenberg: Fake News und Stimmungsmache im Netz

21.08.2017 | Veranstaltungen

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

Wissenschaftler entdecken seltene Ordnung von Elektronen in einem supraleitenden Kristall

22.08.2017 | Physik Astronomie

Forscher beschreiben neuartigen Antikörper als möglichen Wirkstoff gegen Alzheimer

22.08.2017 | Biowissenschaften Chemie

Virus mit Eierschale

22.08.2017 | Biowissenschaften Chemie