Mehrstufige Parallelisierung von Graph-Mining-Algorithmen

Student:Bernd Schöbel
Title:Mehrstufige Parallelisierung von Graph-Mining-Algorithmen
Type:diploma thesis
Advisors:Wörlein, M.; Philippsen, M.
State:submitted on May 3, 2010
Prerequisits:

Die Arbeitsgruppe ParSeMiS (Parallele und Sequentielle graph Mining Suite) beschäftigt sich mit der Suche nach häufigen interessanten Strukturen in Graphdatenbanken; ein Forschungsgebiet, das in den letzten Jahren sehr reges Interesse geweckt hat. Da viele Forschungs- und Wirtschaftsdaten in strukturierter Form erfasst werden können, bietet sich die Speicherung komplexer Zusammenhänge in Form von allgemeinen oder speziellen Graphen an. Diese meist unüberschaubaren Datenmengen sind nur schwer mit Hand und Auge zu erfassen, sodass Algorithmen zur Entdeckung interessanter Korrelationen unabdingbar sind. Da das Entdecken dieser Zusammenhänge in Graphen im Allgemeinen sehr aufwändig ist, ist die Suche nach parallelen und spezialisierten Algorithmen notwendig, die den benötigten Rechenzeit- und Speicheranforderungen auch bei immer größer werdenden Datenmengen gewachsen sind.

Topic:

Durch die Entwicklung der Multi-Core-Rechner lösen diese nach und nach die Single-Core-Rechner ab. So stehen neben großen Shared-Memory-Prozessor(SMP)-Rechnern und Single-Core-Clustern neuerdings auch kleinere SMP-Computer einzeln oder im Verband zur Verfügung. Ein Cluster aus Multi-Core-Rechnern stellt eine gewisse Hierarchie an Parallelität zur Verfügung. Man hat einerseits (zahlenmäßig kleine) Recheneinheitsgruppen zur Verfügung, die schnell über gemeinsammenen Speicher kommunizieren können. Andererseits stehen diese Gruppen im Cluster untereinander über ein "langsames" Netzwerk im Kontakt. Eine solche Hierarchie wurde bei den bisherigen Entwicklungen und Implementierungen von ParSeMiS noch nicht betrachtet.

Der Kern dieser Arbeit besteht darin, zu analysieren wie sich die gegebene Graph-Mining-Umgebung auf mehrstufig parallele Systeme anpassen lässt. Hierbei soll vor allem untersucht werden, ob die bisher von verschiedenen Threads sequenziell durchgeführte Suche nach Erweiterungen eines Graphfragments auf Multi-Core-Rechnern effizient parallelisierbar ist. Hierfür wird folgendes Vorgehen vorgeschlagen:

  • Einarbeitung in die bisherigen (parallelen) Graph-Mining-Strukturen und JavaParty [1]
  • Kombination der bisherigen SMP- und Cluster-Parallelisierung zu einer (einfachen) hybriden Parallelisierung bei gleichartiger Aufgabenteilung
  • Analyse und Implementierung von alternativen fein granularen Parallelisierungsmustern an Hand des gSpan-Algorithmus, wie z. B. des Pipeline-Patterns aus [2]
  • Vermessung und Vergleich der bisherigen und neuen Parallelisierungsverfahren
  • Optional: Portierung der besten Verfahren auf andere Algorithmen wie DAGMA und Gaston

[1] JavaParty: http://svn.ipd.uni-karlsruhe.de/trac/javaparty/wiki/JavaParty
[2] T.G. Mattson, B.A. Sanders, and B. Massingil. Patterns for Parallel Programming. Addison-Wesley Professional. 09/15/2004

watermark seal