Entwicklung und Implementierung einer GPU basierten Indexstruktur

von Hagen Schmidtchen (18, Martin-Andersen-Nexö-Gymnasium Dresden)

Kategorie: Mathematik/Informatik 2011
Betreuer: Dipl-Inf Peter Benjamin Volk (Technische Universität Dresden)
Wettbewerbsart: Jugend forscht

Gewonnene Preise:
  • Sonderpreis "Preis für Informatik" im Bundeswettbewerb
  • Landessieger
  • Regionalsieger

Mit einem Anteil von etwa 55% sind Datenbanken mit Abstand der Hauptbestandteil des World Wide Web. Im Zuge der rasant fortschreitenden Entwicklungen im gesamten Bereich der Informationstechnologie müssen auch sie immer effizienter werden und immer größere Datenmengen verwalten.

Eine der Hauptkomponenten bei der Verwaltung von Daten ist die jeweilige Indexstruktur der Datenbank, indem sie eine optimierte Such-Datenstruktur bietet. Spätere Suchanfragen können so schneller bearbeitet werden. Bisher basierten diese Strukturen auf dem Hauptprozessor – der CPU.
Seit relativ kurzer Zeit ist es nun auch möglich, auf Grafikkarten, sogenannten GPUs  rechenintensive Anwendungen auszuführen. Im Gegensatz zu einer CPU, welche in der Regel nicht mehr als 8 Mikroprozessoren in sich vereint, finden auf GPUs mehrere hundert davon Platz.

Daraus ergibt sich für neue Indexstrukturen ein gewaltiges Potential zur Leistungssteigerung der Algorithmen:
Mehreren hundert Mikroprozessoren können hunderte Rechenoperationen zeitgleich durchgeführt werden. Für eine Datenbank bedeutet das zum Beispiel, dass man bei einer Suchabfrage nicht nur einige wenige, sondern gleich hunderte  Datensätze zeitlich parallel auf Übereinstimmung überprüfen kann.

Die GPU mit ihrer Parallelstruktur bietet deshalb für Datenbankentwickler viele unerforschte Möglichkeiten und wird in Zukunft mit sehr hoher Wahrscheinlichkeit die CPU auf dem Gebiet der Hochleistungsdatenbanken ablösen.

Diese wissenschaftliche Projektarbeit beinhaltet die Entwicklung und Umsetzung einer eigenen GPU-basierten Indexstruktur und zeigt, wie weit konventionelle CPU-Versionen in Sachen Leistungsfähigkeit in den Schatten gestellt werden können.

Entwicklung und Implementierung einer GPU basierten Indexstruktur