Parallelisierter Fractal Tree als FPGA Indexstruktur

- Bachelorarbeit -


Beschreibung:

Die steigende Menge an Daten innerhalb heutiger Datenbanksysteme erfordert immer wieder neue Konzepte zur Erstellung und Instandhaltung eines Indexes über diese. Neben der Steigerung der Taktraten und der Erweiterung auf Mehrkern-Architekturen bei Prozessoren, sind spezialisierte Komponenten, wie GPUs oder FPGAs, eine weitere Möglichkeit diese Aufgabe zu bewältigen.

Ein FPGA (Field Programmable Gate Array)  ist eine spezialisierte Hardware, die auf spezielle Problembereiche fokussiert eingesetzt werden kann.  Dabei biete er Endkunden die Möglichkeit Konfigurationen vorzunehmen ohne vom Hersteller abhängig zu sein („In the Field programmable“). Durch diese Flexibilität und die hohe Parallelität innerhalb des FPGAs können neue Konzepte verfolgt und kontinuierlich angepasst werden.

In dieser Arbeit soll das Konzept eines Fractal Tree als Indexstruktur auf einem FPGA aus einer vorherigen Arbeit aufgegriffen und weitergeführt werden. Dabei sollte der Fokus auf der Parallelität bei der Indexkonstruktion und Suche liegen.

Für das Einfügen,  die Einzel-, sowie die Bereichssuche der Daten soll ein Fractal Tree als Indexstruktur genutzt werden. Dieser gilt als besonders geeignet für diese Aufgaben. Weiterhin soll es ermöglicht werden Daten im Fractal Tree zu entfernen.

Für die Verarbeitung der Daten soll ein System entwickelt werden, welches auf dem FPGA lauffähig ist und per PCIe-Schnittstelle angesprochen werden kann.

Abschließend bietet sich ein Performance-Vergleich der Fractal Tree-Implementierungen auf dem FPGA mit bestehenden Software-Lösungen an.

Anforderungen/Kenntnisse:
-Indexkonstruktion
-VHDL (Einarbeitung möglich)

Bearbeitung:
Thore Mehr

Ergebnis:

Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden


Betreuung:
Dennis Heinrich, M. Sc.

Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 500 5705