Datenlokalität und Datenverteilung im JaMP-Programmiermodell

Student:Ronny T. Lampert
Title:Datenlokalität und Datenverteilung im JaMP-Programmiermodell
Type:diploma thesis
Advisors:Klemm, M.; Philippsen, M.
State:submitted on August 7, 2006
Prerequisits:

Datenlokalität und Datenverteilung sind zwei wichtige Gesichtspunkte, um bei der Ausführung einer Applikation auf einem Rechnerbündel die Leistungsfähigkeit des Systems auszuschöpfen. Durch die (im Vergleich zur reinen CPU-Geschwindigkeit) hohe Latenz des Kommunikationsnetzes zwischen den einzelnen Knoten des Rechnerbündels ist es besonders wichtig, die zur Berechnung nötigen Daten möglichst dort vorzuhalten, wo auch die Berechnung stattfindet. Ein unnötiger Transfer von Daten verursacht einen merklichen Abfall in der Leistung.

Ein Programmierer muss folglich dafür Sorge tragen, dass die Daten über das System so verteilt werden, dass

  • möglichst wenig Kommunikation stattfindet,
  • die zur Verarbeitung der Daten nötige Rechenleistung möglichst gleichmäßig verteilt,
  • und Daten nach Möglichkeit bereits vorzeitig angefordert werden.

Diese Teilaufgaben erfordern ein hohes Maß an Aufwand in der Planung und in der Umsetzung der Datenverteilung. Ebenso muss die Platzierung der Aufrufe zum Datenaustausch sorgfältig durchdacht sein. Ein DSM-System kann hier dem Programmierer helfen, indem es die Details der Datenverteilung vor dem Programmierer versteckt und der Applikation einen globalen Adressraum (gemeinsamer Speicher, "Shared-Memory") zur Verfügung stellt. Der Datenzugriff erfolgt in diesem Fall dann ohne Zutun des Programmierers automatisch.

Als weitere Vereinfachung der Programmierung von Systemen mit gemeinsamen Speicher (insbes. DSM-System) hat sich OpenMP als Standard etabliert. Mittels OpenMP ist es möglich, dem Übersetzer mitzuteilen, auf welche Weise ein Programm parallelisiert werden kann. Der Übersetzer übernimmt dann die Parallelisierung des Programms und entbindet den Programmierer von den Aufgaben der Parallelisierung (z.B. Erzeugen von Aktivitätsträgern, Synchronisation usw.).

Mit dem Jackal-System existiert ein DSM-System für Java, welches ein OpenMP-ähnliches Programmiermodell (JaMP) erlaubt. Vergleichbar mit OpenMP kann mittels JaMP eine Parallelisierung auf Meta-Ebene beschrieben werden und der Übersetzer setzt diese Beschreibung auf die Java Threading API um.

Topic:

Bislang nutzt JaMP zur Datenverteilung das generische DSM-Protokoll des Jackal-Systems. Dieses besitzt im Allgemeinen kein Wissen darüber, wie die Applikation durch den Programmierer parallelisiert wurde. Im Gegensatz dazu kennt der JaMP-Übersetzer jedoch die Parallelisierung bis ins kleinste Detail. Dieses Wissen soll im Rahmen der Arbeit genutzt werden, um die Datenverteilung und damit die Datenlokalität zu verbessern.

Beispielsweise können Daten, die zur Berechnung benötigt werden, von Anfang an auf dem Knoten alloziert werden, auf dem später auch die Berechnung ablaufen wird. Ebenso ist es denkbar, die Daten vor Beginn der Berechnung entsprechend umzuspeichern. Welche Strategien hierbei von Nutzen sind, soll ebenfalls im Rahmen der Arbeit geklärt werden.

Weiterhin muss das parallelisierte Java-Programm immer noch dem Java Memory Model folgen. D.h. es müssen bei Erreichen eines Synchronisationspunktes alle geänderten Daten zurückgeschrieben werden, sodass diese von anderen Aktivitätsträgern bzw. Knoten gesehen werden können. Für einen Großteil der Daten ist dies nicht nötig, da sie stets nur von einem Knoten verwendet werden. Um zu erkennen, welche Datenbereiche lokal genutzt werden, sollen Analyseverfahren für Übersetzer untersucht werden, die ihm dieses Wissen vermitteln. Das Wissen um die Lokalitätseigenschaften der verwendeten Daten soll dann in ein spezialisiertes DSM-Protokoll einfließen, das genutzt wird, wenn eine parallele Berechnung mittels JaMP durchgeführt wird.

Die Assoziation gleichzeitig verwendeter Daten stellt eine weitere Möglichkeit dar. Durch die Assoziation dieser Daten läßt sich die gesamte Datenmenge in einem Block übertragen sobald ein Teil benötigt wird. Dabei muss dafür Sorge getragen werden, dass nicht mehr Daten miteinander assoziiert werden, als nötig. Ebenso muss die Assoziation rechtzeitig aufgebrochen werden, falls festgestellt wird, dass sich das Zugriffsverhalten der Applikation geändert wird.

Die Arbeit teilt sich somit grob in zwei Teile: Erstens sollen Mechanismen entwickelt werden, die es erlauben, eine durch JaMP-Meta-Kommentare gesteuerte Umspeicherung bzw. Allokation der Daten durchzuführen. Zweitens muss geklärt werden, inwiefern sich Lokalitätseigenschaften ausnutzen lassen, sodass nicht die gesamte Datenmenge zurückgeschrieben werden muss, wenn ein Synchronisationspunkt erreicht wird (Spezialisierung des DSM-Protokolls für JaMP). Abschließend sind die implementierten Verfahren auf ihre Leistungsfähigkeit hin zu überprüfen. Dazu sollen geeignete Benchmarks ausgewählt und ausgemessen werden. Die Ergebnisse sind detailliert zu interpretieren.

Meilensteine

  • Verteilte Datenallokation
  • Umspeichern vor der Berechnung
  • Untersuchung von Übersetzeranalysen zur Beurteilung der Lokalität von Daten (optional)
  • Assoziation gleichzeitig benötigter Daten zur blockweisen Übertragung
  • Ausnutzung der Lokalitätseigenschaften der Parallelisierung durch ein eigenes, spezialisiertes DSM-Protokoll
  • Messungen und Interpretation der Ergebnisse
  • Ausarbeitung
watermark seal