Neues Verfahren minimiert Festplattenzugriffe und übetrifft MIT-Rekord Weltrekord im Sortieren riesiger Datenmengen - scinexx | Das Wissensmagazin
Anzeige
Anzeige

Neues Verfahren minimiert Festplattenzugriffe und übetrifft MIT-Rekord

Weltrekord im Sortieren riesiger Datenmengen

Deutsche Wissenschaftler haben in zwei Kategorien einen neuen Weltrekord im Sortieren von digitalen Daten aufgestellt. Dank eines neuen, robusteren Sortierverfahrens übertrafen sie den bisherigen Rekord des Massachusetts Institute of Technology (MIT) sogar bei geringerem Hardwareaufwand. Wichtig ist dies vor alle angesichts der stetig wachsenden Informationsmengen.

{1l}

Über das Internet vernetzte Rechner erzeugen immer größere Datenmengen. Um diese auswerten zu können, muss man sie zunächst nach einem bestimmten Kriterium ordnen. Das effiziente Sortieren von Daten ist von zentraler Bedeutung für Suchmaschinen oder Datenbanken – und damit ein wichtiges Forschungsthema in der theoretischen wie auch in der praktischen Informatik. Der seit Jahren etablierte SortBenchmark, eine im Internet veröffentlichte Tabelle, über die Fachleute etwa von den Unternehmen Microsoft und Hewlett-Packard entscheiden, verzeichnet die jeweils aktuellen Rekorde im Sortieren. In der Königsdisziplin müssen mindestens 10 hoch 12 Datensätze, also insgesamt 100 Terabyte sortiert werden.

564 GB pro Minute mit 200 Rechenknoten

Ein Forscherteam um Professor Peter Sanders am Institut für Theoretische Informatik hat sich nun in zwei Kategorien des SortBenchmark gegen die Konkurrenz durchgesetzt. So sortierten die Wissenschaftler, neben Sanders Mirko Rahn, Johannes Singler und Tim Kieritz, 100 Billionen Byte Daten in etwas weniger als drei Stunden, was einem Durchsatz von 564 GB pro Minute entspricht. Dafür nutzten sie einen Computerverbund mit 200 Rechenknoten, den Mitarbeiter des Steinbuch Centre for Computing (SCC) am KIT konfiguriert hatten. Ein Team des Internet-Giganten Yahoo schaffte zwar einen minimal besseren Wert, nutzte dafür aber mehr als 17mal so viele Rechenknoten.

Die KIT-Forscher erhöhten außerdem die Rekordzahl an Datensätzen, die in unter einer Minute sortiert werden können, auf 9,5 Milliarden (950 GB). Das ist mehr als das Dreifache des bisher vom MIT gehaltenen Rekords, der zudem auf einer größeren Maschine erzielt worden war. Auch der von Yahoo in dieser Kategorie neu eingereichte Wert lag um den Faktor zwei niedriger. Zudem verbesserten die Karlsruher Wissenschaftler einen von Google im November 2008 aufgestellten Rekord beim schnellen Sortieren von

Anzeige

einer Billion Byte Daten Wert von 68 Sekunden auf 64 Sekunden, wiederum mit viel geringerem Hardware- Aufwand.

Neues Verfahren minimiert Festplattenzugriffe

Der Vorsprung des Karlsruher Teams, so erläutert Peter Sanders, „ergibt sich vor allem aus einem neuen Verfahren, das sowohl die Anzahl der Festplattenzugriffe als auch die erforderliche Netzwerkkommunikation in die Nähe der minimal denkbaren Werte rückt.“ Der Sortieralgorithmus sei zudem robuster als die meisten Konkurrenzverfahren, weil er gute Leistung für beliebige Eingabedatensätze garantiere. Hinzu komme, so Sanders, „eine besonders effiziente Implementierung, welche die jeweils vier Festplatten und acht Prozessor-Kerne jedes Rechenknotens sehr gut auslasten kann.“ Ermöglicht hätten dies am Institut entwickelte Software-Bibliotheken.

Im Karlsruher Institut für Technologie (KIT) schließen sich das Forschungszentrum Karlsruhe in der Helmholtz-Gemeinschaft und die Universität Karlsruhe zusammen. Damit wird eine Einrichtung international herausragender Forschung und Lehre in den Natur- und Ingenieurwissenschaften aufgebaut. Im KIT arbeiten insgesamt 8000 Beschäftigte mit einem jährlichen Budget von 700 Millionen Euro. Das KIT baut auf das Wissensdreieck Forschung – Lehre – Innovation.

(Karlsruher Institut für Technologie, 29.05.2009 – NPO)

Anzeige

In den Schlagzeilen

Diaschauen zum Thema

Dossiers zum Thema

Nanoröhrchen - Kohlenstoffwinzlinge als Bausteine für Computer der Zukunft

News des Tages

Jupiter

Jupiters Wanderung enträtselt

Gehirn erneuert sich bis ins hohe Alter

US-Küste: Ursache der Methan-Austritte geklärt

Wirkt die Keto-Diät nur bei Männern?

Bücher zum Thema

Just for Fun - Wie ein Freak die Computerwelt revolutionierte von Linus Torvalds und David Diamond

Maschinen mit Bewusstsein - Wohin führt die künstliche Intelligenz? von Bernd Vowinkel

Die Wunder maschine - Die unendliche Geschichte der Daten- verarbeitung von Herbert Matis

Menschmaschinen - Wie uns die Zukunftstechnologien neu erschaffen von Rodney Brooks

Das Affenpuzzle - Und weitere bad news aus der Computerwelt von David Harel

Top-Clicks der Woche

Anzeige
Anzeige