Diplomarbeit

Auswertung von XPath-Ausdrücken auf der Basis von CUDA

Die generische Auszeichnungssprache XML ist mittlerweile als ein Standardformat für strukturierte Daten etabliert. Zahlreiche Anwendungen verwenden XML-basierte Sprachen zum Speichern und Austauschen von Informationen. XML-Kommunikation bildet die Grundlage für Webdienste und -anwendungen. XML-Datenbanken ermöglichen es, große Mengen strukturierter Daten vorzuhalten und bereitzustellen.

Als Kernkomponenten der standardisierten XML-Verarbeitung haben sich XML Schema, XSLT und XQuery herausgestellt. Mit XML Schema können XML-basierte Sprachen spezifiziert und die Konformität von XML-Dokumenten bezüglich eines Schemas validiert werden. XSLT ermöglicht die Umwandlung von XML-Dokumenten zwischen verschiedenen XML-basierten Sprachen. XQuery ist eine Abfragesprache für XML-Datenbanken.

Diese Kernkomponenten werden in einer Vielzahl von Anwendungen und Diensten verwendet. Daher ist es wichtig, dass sie XML-Daten schnell verarbeiten können. Dies ist aufgrund zunehmender Komplexität und wachsenden Datenmengen keine leichte Aufgabe. Zwar ist zeitgleich auch die theoretisch verfügbare Rechenleistung stetig gestiegen, aber zumindest in den letzten Jahren hauptsächlich durch veränderte Rechnerarchitekturen. Mehrkern-Prozessoren und generisch nutzbare Grafikkarten sind inzwischen weit verbreitet.

Insbesondere die theoretische Rechenleistung moderner Grafikkarten ist in den letzten Jahren stark gestiegen und übertrifft die vom Hauptprozessor mittlerweile um mehrere Größenordnungen. Durch Frameworks wie CUDA von NVIDIA oder das Stream SDK von AMD lassen sich die Ressourcen von Grafikkarten auch für andere Anwendungen als Grafikberechnungen verwenden. Seit kurzem existiert mit OpenCL auch ein herstellerübergreifendes Framework.

Trotzdem lassen sich bestehende Anwendungen nicht ohne Weiteres auf die Grafikkarte portieren. Der Grund dafür ist, dass die verwendeten Algorithmen und Datenstrukturen häufig nur für die übliche von-Neumann-Architektur mit einem Hauptprozessor und einem Arbeitsspeicher effizient sind. Heutige Grafikkarten haben allerdings eine massiv-parallele Architektur mit hunderten von Prozessoren und Hierarchien von verteiltem Speicher.

Das Problem besteht also darin, die parallele Rechenleistung moderner Grafikkarten auszunutzen, um XML-Verarbeitung zu beschleunigen. Dazu identifizieren wir XPath als gemeinsam verwendete Schnittstelle in der XML-Verarbeitung, analysieren deren Funktionalität und entwickeln einen effizienten parallelen Algorithmus. Dieser wird im CUDA-Framework implementiert und zu Testzwecken in den XSLT-Prozessor Xalan integriert. Die Korrektheit des Algorithmus wird formal bewiesen.

Auswertung von XPath-Ausdrücken auf der Basis von CUDA (PDF)

Studienarbeit

Der Einfluss neuronaler Topologien auf die Effizienz der Parameteroptimierung

Die Optimierung großer Neuronaler Netze ist im allgemeinen schwierig. Gründe dafür sind die große Anzahl einstellbarer Parameter (Curse of Dimensionality) und die oft schlechte Kondition des Optimierungsproblems. Verfahren zur Parameteroptimierung dieser Netze sind daher manchmal ineffektiv, häufig aber weniger effizient als bei kleineren, gut konditionierten Problemen. Ziel der Arbeit ist es, ein Verfahren zu entwickeln mit dem die Anzahl der Parameter reduziert und die Kondition verbessert werden kann, ohne den Fehler des Neuronalen Netzes zu verschlechtern.

Wir erzeugen Neuronale Netze mit EANT2. Die Netztopologie wird dabei durch einen Genetischen Algorithmus erstellt, die Parameter werden mit CMA-ES optimiert. EANT2 wurde bereits erfolgreich auf verschiedene Problemstellungen, wie Visual Servoing und Edge/Corner Detection angewandt. Unsere Versuche mit verschiedenen Problemstellungen haben gezeigt, dass die Neuronalen Netze schnell auf eine Größe von etwa 100 Neuronenverbindungen anwachsen, von denen einige unnotig sind, und dass die Netze schlecht konditioniert sind.

Der Einfluss neuronaler Topologien auf die Effizienz der Parameteroptimierung (PDF)