1.1 Binary file 0__Papers/year1report/report.pdf has changed

     2.1 --- a/0__Papers/year1report/report.tex	Thu Jun 14 18:00:09 2012 +0200
     2.2 +++ b/0__Papers/year1report/report.tex	Fri Jun 15 18:59:03 2012 +0200
     2.3 @@ -16,12 +16,12 @@
     2.4  
     2.5  Ziel meiner Arbeit ist es, durch speziell angepasste Hardware die Synchronisation und Aufgabenverteilung für parallele Programme auf Multicoresystemen zu verbessern. Als Grundlage dient dafür das VMS-System, ein Framework dass es ermöglicht, Laufzeitumgebungen für verschiedenste parallele Programmiermodelle mit nur wenig Aufwand zu implementieren.
     2.6  
     2.7 -\section{}
     2.8 +\section{Ausgeführte Arbeiten}
     2.9  
    2.10 -In den ersten 6 Monaten habe ich wie geplant das VMS-System analysiert. VMS umfasst die Grundlegende Struktur, die allen Laufzeitumgebungen gemein ist: sie beinhaltet den Wechsel zwischen Programm und Laufzeitumgebung, und die Möglichkeit, eine Zeitliche Ordnung zwischen zwei Codepunkten in zwei virtuellen Prozessoren zu garantieren (semantikfreie Synchronisation). Auf Basis dieser Elemente muss der Laufzeitumgebungsentwickler nur noch die jeweilige Semantik der parallelen Umgebung hinzufügen. Diese wird in Form eines Plugins bereitgestellt, das zwei Teile enthält: einen Assigner, der entscheidet, welche Aufgaben als nächstes bearbeitet werden, und einen Request Handler, der die Implementation der parallelen Konstrukte liefert.
    2.11 +In den ersten 6 Monaten habe ich wie geplant das VMS-System analysiert. VMS umfasst die Grundlegende Struktur, die allen Laufzeitumgebungen (Runtimes) gemein ist: sie beinhaltet den Wechsel zwischen Programm und Laufzeitumgebung, und die Möglichkeit, eine Zeitliche Ordnung zwischen zwei Codepunkten in zwei virtuellen Prozessoren zu garantieren (semantikfreie Synchronisation). Auf Basis dieser Elemente muss der Laufzeitumgebungsentwickler nur noch die jeweilige Semantik der parallelen Umgebung hinzufügen. Diese wird in Form eines Plugins bereitgestellt, das zwei Teile enthält: einen Assigner, der entscheidet, welche Aufgaben als nächstes bearbeitet werden, und einen Request Handler, der die Implementation der parallelen Konstrukte liefert.
    2.12  
    2.13  Diese zweiteilige Struktur ermöglicht zwei Ansatzpunkte für die Beschleunigung: den VMS-Kern selbst -- Verbesserungen an dieser Stelle kommen allen Laufzeitumgebungen zu Gute -- und das jeweilige Plugin. VMS ist minimal gehalten und bietet nur wenige Möglichkeiten zur Verbesserung, jedoch haben Änderungen hier den größten Effekt. VMS ist außerdem, da es die grundlegendsten Elemente zusammenfasst, bereits sehr nah an der existierenden Hardware und die häufigen Aufgaben sind gut unterstützt. Zusätzliche Beschleunigung kann hier nur durch sehr ressourcenintensive Lösungen (z.B. zusätzliche Registersätze für schnellen Kontextwechsel) erwartet werden.
    2.14 -Beschleuniger für Pluginfunktionen haben deutlich mehr Spielraum, besonders für Sprachen mit komplexen, hardwarefernen Konstrukten (und dies sind die besonders interessanten, weil sie sich der Struktur des Problems nähern und damit dem Programmierer die Arbeit abnehmen, das Problem in Hardwarenahe Konzepte umzudenken bzw. übersetzen zu müssen.) Da die Pluginfunktionen aber Sprachspezifisch sind, kommen Beschleunigungen an dieser Stelle nur dem Teil der Programme zugute, die in dieser Sprache geschrieben sind. Die Herausforderung wird also sein, Hardwareelemente zu finden, die möglichst flexible und vielfältige Verwendung finden können. Haupsächlich wird aber die Programmiersprache StarSs anvisiert werden, die im Fachgebiet AES häufig Verwendung findet.
    2.15 +Beschleuniger für Pluginfunktionen haben deutlich mehr Spielraum, besonders für Sprachen mit komplexen, hardwarefernen Konstrukten (und dies sind die besonders interessanten, weil sie sich der Struktur des Problems nähern und damit dem Programmierer die Arbeit abnehmen, das Problem in Hardwarenahe Konzepte umzudenken bzw. übersetzen zu müssen.) Da die Pluginfunktionen aber Sprachspezifisch sind, kommen Beschleunigungen an dieser Stelle nur dem Teil der Programme zugute, die in dieser Sprache geschrieben sind. Die Herausforderung wird also sein, Hardwareelemente zu finden, die möglichst flexible und vielfältige Verwendung finden können. Haupsächlich wird aber die Programmiersprache StarSs anvisiert werden, die hier im Fachgebiet AES häufig Verwendung findet.
    2.16  
    2.17  VMS ist die praktische Ausformulierung eines Modells des Parallelismus, die von Dr. Sean Halle unter dem Namen ``Holistic Model of Parallel Computation''[~] vorgeschlagen wurde. Dieses Modell isoliert die schedulingrelevanten Teile eines Programms und legt das Augenmerk besonders auf die Effekte von Scheduling Decisions auf die Performance.
    2.18  
    2.19 @@ -34,28 +34,39 @@
    2.20  Quasi mit dem ersten Lauf stellte sich heraus, dass die Matrixmultiplikation, die ich seit Monaten als Testapplikation verwendete, einige Performanceprobleme hatte. So hatte z.B. der applikationseigene Lastenverteiler einen Bug, sodass von 40 Prozessorkernen nur 3 den Großteil der Arbeit zugeteilt bekamen, und 10 weitere einen kleinen Teil, die 27 restlichen jedoch gar keine. Des weiteren wurde die Arbeit so verteilt, dass der Kern, der den Lastenverteiler ausführt, als erster Arbeit zugeteilt bekam, und diese Arbeit dann den Verteiler für längere Zeit unterbrach, bevor er weiteren Kernen Arbeit zuteilen konnte. All dies war in den Statistiken nicht aufgefallen, in der Visualisierung jedoch offensichtlich. Als ich noch eine detailliertere Aufteilung des Overheads, der für eine bestimmte Arbeitseinheit aufgewendet wird, und mehrere Metriken (Takte, Befehle, Cache Misses) hinzugefügt hatte, wurden auch subtilere Effekte sichtbar. Dabei stellte sich z.B. heraus, dass die zentralisierte Architektur von VMS, das alle Informationen die die Laufzeitumgebung über den Zustand des Programms bereithalten muss in einem gemeinsamen Pool speicherte, auf den nur ein Kern gleichzeitig zugreifen kann, einen größeren Engpass als erwartet darstellte.
    2.21  Da mir keine äquivalenten Performance-debugging Tools bekannt waren, und mehrere Mitarbeiter des Fachgebiets bereits händeringend nach solchen gesucht hatten, habe ich über dieses Tool einen weiteren Artikel verfasst [Anhang?], den ich voraussichtlich im August für die PPoPP-2013 Konferenz einreichen werde.
    2.22  
    2.23 -\section{}
    2.24 +\newpage
    2.25  
    2.26 +\section{Zukünftige Aktivitäten}
    2.27 +Wegen der Arbeit an zwei unvorhergesehenen Veröffentlichungen hat sich die Arbeit an der Hardwareplattform etwas verzögert, sie hat aber mein Verständnis des Problems vertieft und einige neue Blickwinkel eröffnet, die auch in das Design der Plattform einfließen.
    2.28  Aufgrund der gewonnenen Erkentnisse verändert sich mein Plan wie folgt:
    2.29  
    2.30 -Da die Vermutung, dass ein zentralisiertes System, in dem ein Master-Kern die Aufgabenverteilung für das gesamte System übernimmt, die beste Lösung sein würde, nicht so gesichert wie am Anfang erscheint, werde ich mich stärker den verschiedenen Möglichkeiten der Parallelisierung zuwenden. 
    2.31 +Da die Vermutung, dass ein zentralisiertes System, in dem ein Master-Kern die Aufgabenverteilung für das gesamte System übernimmt, die beste Lösung sein würde, nicht so gesichert wie am Anfang erscheint, werde ich mich stärker den verschiedenen Möglichkeiten der Verteilung zuwenden. 
    2.32  Dabei wird mir das BeeFarm-multiprozessorsystem [http://www.bscmsrc.eu/sites/default/files/beefarm.pdf] als Grundlage dienen. Dieses System ist auf MIPS Prozessoren basiert, die eine Coprozessorschnittstelle enthalten, über die zusätzliche Hardwarekomponenten einfach integriert werden können. 
    2.33  
    2.34 -Der erste Schritt wird sein, die VMS-basierte StarSs-Laufzeitumgebung auf die BeeFarm-Platform zu portieren. Diese reine Software-Implementierung wird die Vergleichsbasis gegenüber der der Effekt der unterschiedlichen Hardwarebeschleunigerkonfigurationen gemessen werden kann.
    2.35 +Der erste Schritt wird sein, VMS und die darauf basierten Laufzeitumgebungen (insbesondere StarSs) auf die BeeFarm-Platform zu portieren. Diese reine Software-Implementierung wird die Vergleichsbasis, gegenüber der der Effekt der unterschiedlichen Hardware\-beschleuniger\-konfigurationen gemessen werden kann.
    2.36  
    2.37 -Als nächstes muss ein beschleunigender Coprozessor für das StarSs-Plugin erstellt werden. Wie erwartet besteht der Großteil der StarSs-Runtimeaktivität aus dem Nachschlagen in Hashtabellen, jedoch stellte sich auch heraus, dass das Zuteilen von Speicherplatz über \emph{malloc} überraschend viel Zeit in Anspruch nimmt. Dabei gilt es, zwischen vier unterschiedlichen Möglichkeiten zur Beschleunigung abzuwägen und die richtige Kombination zu treffen: 
    2.38 -\begin{itemize}
    2.39 -\item Spezialisiertere, weniger flexible Hardware ist schneller als programmierbare, multifunktionale Hardware
    2.40 +Als nächstes muss ein beschleunigender Coprozessor für die Plugins erstellt werden. Dabei ist bei der Auswahl der Beschleuniger immer zu berücksichtigen, dass spezialisiertere, weniger flexible Hardware schneller ist als programmierbare, multifunktionale Hardware -- jedoch nur seltener anwendbar.
    2.41 +
    2.42 +StarSs hat die komplizierteste Laufzeitaktivität unter den verfügbaren Plugins, daher werde ich hier zuerst ansetzen. Wie erwartet besteht der Großteil der StarSs-Runtimeaktivität aus dem Nachschlagen in Hashtabellen; diese werden ebenso im SSR-Plugin für die Kommunikation von Nachrichten verwendet. Hashtabellen und ähnliche Assoziativspeicher werden auch anderweitig in vielen Bereichen benutzt, von Routing in Netzwerkprotokollen [http://ccr.sigcomm.org/online/files/sigcomm302-estan.corrected.pdf] bis zu Graph-basierten Algorithmen [http://www.doc.ic.ac.uk/~natasha/fpt11bb.pdf]. Da die einfache Implementierbarkeit von VMS-Plugins besonders der Entwicklung von Domain-Spezifischen Sprachen (und den entsprechenden Laufzeitumgebungen) zugutekommt, ist es wahrscheinlich, dass ein Hashtabellenbeschleuniger auch vielen zukünftigen Plugins von Nutzen sein wird.
    2.43 +
    2.44 +Überraschenderweise stellte sich auch heraus, dass das Zuteilen von Speicherplatz über \emph{malloc} relativ viel Zeit in Anspruch nimmt. Da diese Funktion in sehr vielen Laufzeitumgebungen vorkommt, und häufig in der sequentiellen oder minder parallelen Vorbereitungsphase des Programms vor dem Start der eigentlichen parallelen Arbeit benutzt wird, könnte eine Beschleunigung hier einen großen Einfluss haben.
    2.45 +
    2.46 +Neben der Auswahl ist auch die Anzahl und Platzierung der Beschleuniger abzuwägen.
    2.47 +Im Falle von StarSs gibt es zwei zeitintensive Abläufe mit sehr unterschiedlicher Verteilbarkeit: Die Erstellung von neuen Tasks ist strikt sequentiell definiert, mit nur einem einzigen ``Master'', der neue Tasks in Auftrag geben darf. Die Zugriffsrechte der Tasks auf Ein- und Ausgangsspeicherzonen werden durch die Reihenfolge, in der sie in Auftrag gegeben wurden, bestimmt. Dieser Ablauf findet zwangsläufig nur in einem Kern statt, und ist der einzige, der neue Einträge in der Hashtabelle erstellen kann, sodass es sinnvoll erscheint, hierfür einen speziellen Coprozessor zu erstellen, der nur zu einem designierten ``Master-Kern'' hinzugefügt wird.
    2.48 +Der zweite Ablauf findet zum Ende jedes Tasks statt. Er gibt die Ein- und Ausgangsspeicherzonen auf die der Task Zugriffsrechte hatte frei und prüft nach, welche wartenden Tasks durch diese Freigaben laufbereit werden. Unter den laufbereiten Tasks muss dann einer ausgewählt und auf dem freigewordenen Kern gestartet werden. Dieser Ablauf ist der rechenintensivste in der StarSs-Laufzeitumgebung, sodass hier ein Hardwarebeschleuniger dringend notwendig ist. Er könnte entweder zentralisiert stattfinden -- die ``Arbeiter-Kerne'' müssten dann den Abschluss eines Tasks an den Master melden und auf die Zuteilung eines neuen Tasks warten -- oder dezentral auf dem Kern, der den Task beendet hat. Eine zu starke Zentralisierung führt schnell zu Engpässen, insbesondere für Programme, die viele kurze Tasks enthalten. Auf der anderen Seite wäre es aber sehr ressourcenaufwändig, jedem Kern einen Coprozessor für diesen Ablauf zur Verfügung zu stellen, und dieser wäre unbenutzt während der gesamten Rechenzeit, die im Programm verbracht wird (und dies ist die ``nützliche'' Zeit, und daher hoffentlich die überwältigende Mehrheit). An dieser Stelle wird es also ein interessanter Punkt sein, zu messen, wie viele Kerne sich einen Coprozessor teilen können, ohne dass es zu größeren Verzögerungen kommt.
    2.49 +
    2.50 +Die StarSs-Laufzeitumgebung muss anschließend so angepasst werden, dass sie von den neuen Coprozessoren gebrauch machen kann. Anhand mehrerer bereits in StarSs existierender Programme, darunter Standardbenchmarks und ein H.264 Videoencoder, kann dann die Performance evaluiert werden. Um die Kosten der größeren Flexibilität zu evaluieren, kann des weiteren der StarSs-spezifische Hardwarescheduler Nexus++ herangezogen werden, der hier im Fachgebiet entwickelt wurde, und sämtliche im vorigen Absatz beschriebenen Abläufe übernimmt.
    2.51 +
    2.52 +\end{document}
    2.53 +
    2.54 +
    2.55 +
    2.56 +Drei Möglichkeiten der Parallelisierung werde ich bei der Erstellung der Hardwarebeschleuniger ins Auge fassen:
    2.57 +\begin{enumerate}
    2.58  \item Eigenständige Abläufe können getrennt und parallel ausgeführt werden
    2.59  \item Innerhalb dieser Abläufe kann durch Pipelining der Durchsatz gesteigert werden
    2.60  \item Mehrere Instanzen eines Ablaufs können parallel arbeiten.
    2.61 -\end{itemize}
    2.62 -
    2.63 -Im Falle von StarSs gibt es zwei zeitintensive Abläufe mit sehr unterschiedlicher Verteilbarkeit: Die Erstellung von neuen Tasks ist strikt sequentiell definiert, mit nur einem einzigen ``Master'', der neue Tasks in Auftrag geben darf. Die Zugriffsrechte der Tasks auf Ein- und Ausgangsspeicherzonen werden durch die Reihenfolge, in der sie in Auftrag gegeben wurden, bestimmt. Dieser Ablauf findet zwangsläufig nur in einem Kern statt, und ist der einzige, der neue Einträge in der Hashtabelle erstellen kann, sodass es sinnvoll erscheint, hierfür einen speziellen Coprozessor zu erstellen, der nur zu einem designierten ``Master-Kern'' hinzugefügt wird.
    2.64 -Der zweite Ablauf findet zum Ende jedes Tasks statt. Er gibt die Ein- und Ausgangsspeicherzonen auf die der Task Zugriffsrechte hatte frei und prüft nach, welche wartenden Tasks durch diese Freigaben laufbereit werden. Unter den laufbereiten Tasks muss dann einer ausgewählt und auf dem freigewordenen Kern gestartet werden. Dieser Ablauf ist der rechenintensivste in der StarSs-Laufzeitumgebung, sodass hier ein Hardwarebeschleuniger dringend notwendig ist. Er könnte entweder zentralisiert stattfinden -- die ``Arbeiter-Kerne'' müssten dann den Abschluss eines Tasks an den Master melden und auf die Zuteilung eines neuen Tasks warten -- oder dezentral auf dem Kern, der den Task beendet hat. Eine zu starke Zentralisierung führt schnell zu Engpässen, insbesondere für Programme, die viele kurze Tasks enthalten. Auf der anderen Seite wäre es aber sehr ressourcenaufwändig, jedem Kern einen Coprozessor für diesen Ablauf zur Verfügung zu stellen, und dieser wäre unbenutzt während der gesamten Rechenzeit, die im Programm verbracht wird (und dies ist die ``nützliche'' Zeit, und daher hoffentlich die überwältigende Mehrheit). An dieser Stelle wird es also ein interessanter Punkt sein, zu messen, wie viele Kerne sich einen Coprozessor teilen können, ohne dass es zu größeren Verzögerungen kommt.
    2.65 -
    2.66 -\end{document}
    2.67 -
    2.68 +\end{enumerate}
    2.69  
    2.70  -- what I did
    2.71  -get into vms code, instrument it