Entfernung überflüssiger Thread-Synchronisationen in NGAPL

Student:Philipp Weissmann
Title:Entfernung überflüssiger Thread-Synchronisationen in NGAPL
Type:masters thesis
Advisors:Veldema, R.; Philippsen, M.
State:submitted on April 26, 2013
Prerequisits:
Topic:

Voraussetzungen

Imperative/OO Programmiersprachen mit Unterstützung für parallele Programmierung haben kritische Regionen um konkurrierende Zugriffe zu gemeinsamen Daten auszuschließen. Dies wird entweder mit atomic regions (Transactional Memory) oder Locks implementiert. In beide Fällen muss der Programmierer kritische Regionen selbst erkennen und schützen. Unterläuft dem Programmierer hierbei ein Fehler entstehen race conditions (Wettlaufbedingungen), welche nur schwierig zu finden sind. Ein anderer Ansatz ist alle Methoden per default mit einem Lock/Unlock Paar zu schützen. In diesen Fall ist das Programm vor race conditions geschützt, jedoch wirkt sich dies negativ auf die Performance auf, da viele der Lock-Operationen überflüssig sind. Ein Lock für ein Datum ist überflüssig, wenn das Datum nur von einen Thread gleichzeitig geändert wird. Daten, die nur gelesen werden, brauchen ebenfalls kein Lock.
Einige Möglichkeiten den Code zu beeinflussen:

  • Inlining
  • Scheduling von Methoden auf Prozessorkerne
  • Spezialisierung von Methoden

Eine Nebenbedingung für dieses System ist die Limitation des Speicherplatzes. Da nur eine begrenzte Menge an Speicher zur Verfügung steht, ist es nicht immer möglich alle Funktionen zu inlinen bzw. zu klonen. Die Auswahl der Methoden, die durch inline/klonen beschleunigt werden, soll anhand der Laufzeitvorteile erfolgen. Alle Objekte haben zwei zugehörige Lockobjekte: Ein globales Lock um die statischen Felder zu schützen und ein Lock, welches in das Objekt selbst instanziiert ist. Wenn eines oder beide der Locks überflüssig sind (keine Lock-Operationen mehr im Programm), ist es nicht notwendig Speicher für diese zu reservieren. Durch Verschmelzung von Locks kann man weitere Lock Objekte (und Operationen) entfernen. Existieren beispielsweise Objekt A und Objekt B stets nur gleichzeitig, kann man das Lock aus Objekt B löschen und nur das Lock von Objekt A verwenden. Die richtige Wahl der Implementierung für ein bestimmtes lock stellt ein orthogonales Problem dar, da es eine Vielzahl von Typen gibt. (kernel/pthread locks, spin lock, ticketing lock, recursive locks,preemptive locks, eager/lazy locking, hierarchical locks, etc.) Jede dieser Implementierungen hat einen Anwendungsfall, in dem sie den anderen Implementierungen überlegen ist. Wird beispielsweise ein Lock sehr lange gesperrt, so eignet sich insbesondere ein pthread-lock besonders gut, da es den Prozessor-Core freigibt. Wartet hingegen ein Thread auf ein Lock, so eigenet sich ein spin-lock sehr gut. Wollen hingegen nur wenige Threads eine kurze „kritische Region" durchlaufen Auch können bei sehr einfachen Funktionen primitive, atomare Operatoren implementiert werden, z. B. eine einfache inc() Methode kann oftmals mittels einer atomic-add Instruktion implementiert werden.

Thema

Um die Analyse zu vereinfachen wird alles in das NGAPL Framework/Sprache implementiert. NGAPL besitzt statisch erkennbare Parallelität (statt dynamischer Thread Erzeugung), was Static-scheduling vereinfacht. Auch verbietet NGAPL Sprachfeatures, die reine Daten/Alias/Fluss Analyse verkomplizieren.
NGAPL's virtual machine soll erweitert werden mit:

  • Einem statischen Schedulingverfahren, dass Methoden mit einem gemeinsamen Objekt auf gleiche Cores scheduled.
  • Reine Übersetzeranalyse, um überflüssige Synchronisation zu entfernen. (Call/Heapgraph-analyse, Inlining, Verschmelzung, Parallel-for Coarsening, usw.)
  • Übersetzer/Feed-back basierte Übersetzung um die richtige Lock-Implementierung zu wählen.

Literatur

NGAPL manual (auf Anfrage).

Meilensteine

  • Inlining/Spezializierung von Code um Lock-Verwendung klarer zu machen
  • Lock-Objekt Entfernung
  • Static scheduler implementieren, in der NGAPL-VM (wie oben beschrieben)
  • Verschmelzung der Locks gleichzeitig aktiver Objekte
  • Compiler Analyse zur einfachen Entfernung überflüssiger Synchronisationen
  • Lock Implementierungs-Auswahlverfahren
watermark seal