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

     2.1 --- a/0__Papers/year1report/report.tex	Mon Apr 15 12:38:12 2013 +0200
     2.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.3 @@ -1,115 +0,0 @@
     2.4 -
     2.5 -\documentclass[12pt,a4paper]{article}
     2.6 -
     2.7 -\usepackage[german]{babel}
     2.8 -\usepackage{fullpage}
     2.9 -\usepackage[utf8]{inputenc}
    2.10 -
    2.11 -\begin{document}
    2.12 -\setlength{\parindent}{0px} \setlength{\parskip}{1 em}
    2.13 -
    2.14 -\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme\\Zwischenbericht zum 1. Jahr}
    2.15 -\author{Nina Engelhardt}
    2.16 -\date{\today}
    2.17 -\maketitle
    2.18 -
    2.19 -
    2.20 -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 Virtualzed Master-Slave System, kurz VMS, ein Framework dass es ermöglicht, Laufzeitumgebungen für verschiedenste parallele Programmiermodelle mit nur wenig Aufwand zu implementieren.
    2.21 -
    2.22 -\section{Ausgeführte Arbeiten}
    2.23 -
    2.24 -In den ersten 6 Monaten habe ich wie geplant das VMS-System analysiert. VMS umfasst die Grundlegende Struktur, die allen Laufzeitumgebungen (\emph{Runtimes}) gemein ist: sie beinhaltet den Wechsel zwischen Programm- und Umgebungscode und die Möglichkeit, eine zeitliche Ordnung zwischen zwei Codepunkten in zwei virtuellen Prozessoren zu garantieren (semantikfreie Synchronisation). Auf dieser Basis 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 \emph{Assigner}, der entscheidet, welche Aufgaben als nächstes bearbeitet werden, und einen \emph{Request Handler}, der die Implementation der parallelen Konstrukte liefert.
    2.25 -
    2.26 -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. Die von VMS gelieferten grundlegenden Elemente sind sehr nah an der existierenden Hardware, deshalb sind die meisten häufigen Aufgaben bereits 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.27 -Beschleuniger für Pluginfunktionen haben deutlich mehr Spielraum, besonders für Sprachen mit komplexen, hardwarefernen Konstrukten. Diese Sprachen sind von großer Bedeutung, 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 OmpSs anvisiert werden, da sie im Fachgebiet Architektur Eingebetteter Systeme bereits verwendet wird.
    2.28 -
    2.29 -VMS ist die praktische Ausformulierung eines Modells des Parallelismus, die von Dr. Sean Halle unter dem Namen ``Holistic Model of Parallel Computation''\cite{bib:holistic} 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.30 -
    2.31 -Während meiner Analyse von VMS stieß ich auf mehrere Problemstellen in der Theorie, und habe diese in Zusammenarbeit mit Dr. Halle gelöst. Insbesondere habe ich das Modell um das Konzept der Schichten erweitert, das dem Umstand Rechnung trägt, dass in einem System meistens mehrere hierarchisch untergeordnete Scheduler existieren. So werden die Arbeitseinheiten, über die die Laufzeitumgebung als Eins entscheidet, möglicherweise vom Betriebssystem noch einmal unterbrochen und verteilt, spätestens aber vom Prozessor in kleinere Einheiten -- Assemblerbefehle -- zerteilt, und auf unterschiedliche Funktionseinheiten aufgeteilt. Wenn man an Out-of-order Prozessoren denkt, wird deutlich, das auch dies parallele Aufgabenverteilung ist. Das Holistische Modell ist auch auf diese anwendbar. Zur Zeit arbeiten wir an einem Zeitschriftenartikel der das Holistische Modell detailliert darlegt. 
    2.32 -
    2.33 -Zu den Errungenschaften des Holistischen Modells gehören auch zwei grafische Darstellungen, die \emph{Unit Constraint Collection} und der \emph{Scheduling Consequence Graph}, deren Ziel es ist, die Gründe der (guten oder schlechten) Performance eines parallelen Programms ersichtlich zu machen. Die Unit Constraint Collection (kurz UCC) zeigt die Arbeitseinheiten (\emph{units}) die im Programm definiert werden, und die Randbedingungen (\emph{constraints}) ihrer Ausfürbarkeit, die vom Programm selbst ausgehen. Der Consequence Graph (CG) repräsentiert eine realisierte Ausführung des Programms und zeigt die räumliche und zeitliche Platzierung der Arbeitseinheiten, die der Scheduler gewählt hat, sowie die unterschiedlichen Randbedingungen, die diese Wahl eingeschränkt haben. Diese können vom Programm selbst stammen, sich aus Ressourcenbegrenzungen ergeben, oder durch Beschränkungen der Laufzeitumgebung entstehen.
    2.34 -
    2.35 -Nachdem ich bereits für die Analyse des Laufzeitverhaltens Messschnittstellen in VMS eingefügt hatte, habe ich diese Infrastruktur wiederverwendet, um aus den gewonnenen Daten die räumliche und zeitliche Platzierung der Arbeitseinheiten für den Consequence Graph abzuleiten. Zusätzlich habe ich ein VMS-Plugin, das synchrones Senden und Empfangen von Nachrichten zwischen Threads in einem Programm unterstützt (synchronous send-receive, kurz SSR), modifiziert, um die Constraints zu erfassen, die für die Konstruktion der UCC und des CG notwendig sind. Schließlich erstellte ich ein Programm, das diese Aufzeichnungen entgegennehmen und UCC \& CG darstellen kann.
    2.36 -
    2.37 -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 vorherigen, statistischen Analysen 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) zur Visualisierung hinzugefügt hatte, wurden auch weniger offensichtliche 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.38 -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 \cite{bib:perftune}, den ich voraussichtlich im August für die PPoPP-2013 Konferenz einreichen werde.
    2.39 -
    2.40 -%\newpage
    2.41 -
    2.42 -\section{Zukünftige Aktivitäten}
    2.43 -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.44 -Aufgrund der gewonnenen Erkentnisse verändert sich mein Plan wie folgt:
    2.45 -
    2.46 -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.47 -Dabei wird mir das BeeFarm-Multiprozessorsystem\cite{bib:beefarm} als Grundlage dienen, das am Fachgebiet zur Verfügung steht. Dieses System ist auf MIPS Prozessoren basiert, die eine Coprozessorschnittstelle enthalten, über die zusätzliche Hardwarekomponenten einfach integriert werden können. 
    2.48 -
    2.49 -Der erste Schritt wird sein, VMS und die darauf basierten Laufzeitumgebungen (insbesondere OmpSs) auf die BeeFarm-Platform zu portieren. Diese reine Software-Im\-ple\-men\-tie\-rung wird die Vergleichsbasis, gegenüber der der Effekt der unterschiedlichen Hard\-ware\-be\-schleu\-ni\-ger\-kon\-fi\-gu\-ra\-tio\-nen gemessen werden kann.
    2.50 -
    2.51 -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.52 -
    2.53 -OmpSs hat die komplizierteste Laufzeitaktivität unter den verfügbaren Plugins, daher werde ich hier zuerst ansetzen. Wie erwartet besteht der Großteil der OmpSs-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 \cite{bib:routing} bis zu Graph-basierten Algorithmen \cite{bib:graph}. 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.54 -
    2.55 -Zudem stellte sich auch heraus, dass das Allozieren von Speicher über \emph{malloc} relativ viel Zeit in Anspruch nimmt. Da diese Funktion in sehr vielen Plugins enthalten ist, 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.56 -
    2.57 -Neben der Auswahl ist auch die Anzahl und Platzierung der Beschleuniger abzuwägen.
    2.58 -Im Falle von OmpSs gibt es zwei zeitintensive Abläufe mit sehr unterschiedlicher Verteilbarkeit: Die Erstellung von neuen Tasks ist strikt sequentiell definiert, ausgehend von 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. Aus diesem Grund erscheint es sinnvoll, hierfür einen speziellen Coprozessor zu erstellen, der nur zu einem designierten ``Master-Kern'' hinzugefügt wird.
    2.59 -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, welche wartenden Tasks durch diese Freigaben laufbereit werden. Unter den laufbereiten Tasks wählt er einen aus und startet ihn auf dem freigewordenen Kern. Hier wäre Hardwarebeschleunigung dringend notwendig, da dieser Ablauf der rechenintensivste in der OmpSs-Laufzeitumgebung 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. Zudem bliebe dieser ungenutzt während der gesamten Rechenzeit, die im Programm verbracht wird (und dies ist die ``nützliche'' Zeit, und daher idealerweise 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.60 -
    2.61 -Die übrigen Schritte bleiben unverändert. Die OmpSs-Laufzeitumgebung muss anschließend so angepasst werden, dass sie von den neuen Coprozessoren gebrauch machen kann. Anhand mehrerer bereits in OmpSs 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 OmpSs-spezifische Hardwarescheduler Nexus++ herangezogen werden, der hier im Fachgebiet entwickelt wurde, und sämtliche im vorigen Absatz beschriebenen Abläufe übernimmt.
    2.62 -
    2.63 -Zusammengefasst ergibt sich daraus der folgende Zeitplan:
    2.64 -
    2.65 -\begin{table}[h]
    2.66 -\begin{tabular}{|l|c|}
    2.67 -\hline
    2.68 -VMS und OmpSs-Plugin auf BeeFarm portieren & 3 Monate\\
    2.69 -\hline
    2.70 -Hardwarebeschleuniger implementieren & 6 Monate\\
    2.71 -\hline
    2.72 -Varianten erstellen & 3 Monate\\
    2.73 -\hline
    2.74 -Integration in VMS-OmpSs & 3 Monate\\
    2.75 -\hline
    2.76 -Test, Performanceevaluation, Optimierung & 3 Monate\\
    2.77 -\hline
    2.78 -Niederschrift & 6 Monate\\
    2.79 -\hline
    2.80 -\end{tabular}
    2.81 -\end{table}
    2.82 -
    2.83 -\begin{thebibliography}{9}
    2.84 -\bibitem{bib:perftune} Nina Engelhardt, Sean Halle, Ben Juurlink; \emph{Integrated Performance Tuning Using Semantic Information Collected by Instrumenting the Language Runtime}; in progress
    2.85 -\bibitem{bib:holistic} Sean Halle, Albert Cohen; \emph{Support of Collective Effort Towards Performance Portability}; Proceedings of 3rd USENIX Workshop on Hot Topics in Parallelism, May 2011
    2.86 -\bibitem{bib:beefarm} Nehir Sonmez, Oriol Arcas, Gokhan Sayilar, Osman S. Unsal, Adrián Cristal, Ibrahim Hur, Satnam Singh, and Mateo Valero; \emph{From plasma to beefarm: design experience of an FPGA-based multicore prototype}; Proceedings of the 7th international conference on Reconfigurable computing: architectures, tools and applications (ARC'11), 2011
    2.87 -\bibitem{bib:routing} Lorenzo De Carli, Yi Pan, Amit Kumar, Cristian Estan, Karthikeyan Sankaralingam; \emph{PLUG: Flexible Lookup Modules for Rapid Deployment of New Protocols in High-speed Routers}; SIGCOMM, August 2009
    2.88 -\bibitem{bib:graph} Betkaoui, B., Thomas, D.B., Luk, W., Przulj, N.; \emph{A framework for FPGA acceleration of large graph problems: Graphlet counting case study}; International Conference on Field-Programmable Technology (FPT), 2011 
    2.89 -\end{thebibliography}
    2.90 -
    2.91 -\end{document}
    2.92 -
    2.93 -
    2.94 -
    2.95 -Drei Möglichkeiten der Parallelisierung werde ich bei der Erstellung der Hardwarebeschleuniger ins Auge fassen:
    2.96 -\begin{enumerate}
    2.97 -\item Eigenständige Abläufe können getrennt und parallel ausgeführt werden
    2.98 -\item Innerhalb dieser Abläufe kann durch Pipelining der Durchsatz gesteigert werden
    2.99 -\item Mehrere Instanzen eines Ablaufs können parallel arbeiten.
   2.100 -\end{enumerate}
   2.101 -
   2.102 --- what I did
   2.103 --get into vms code, instrument it
   2.104 --find vague places in theory, fix them
   2.105 -->find slowdowns in vms, lead to new version
   2.106 -->notice instrumentation + theory makes good perf tuning tool, write paper about that
   2.107 -->write paper about theory
   2.108 -
   2.109 --- how it compares to projected plan
   2.110 --first 6 months match
   2.111 --then more theory than concrete solutions
   2.112 -->revealed 1 master probably not best solution
   2.113 -->revealed additional levels of performance issues not originally considered
   2.114 -
   2.115 --- what I'm going to do next
   2.116 --build hardware, but instead of putting accelerators only on 1 master core, experiment with how often to replicate accelerators
   2.117 --assemblage of lm32 cores, each w/ non-coherent cache
   2.118 --OmpSs? w/ message passing for in/out

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/2__Other/fitweltweit/Nina_proposal_3.tex	Tue May 14 12:03:39 2013 +0200
     3.3 @@ -0,0 +1,505 @@
     3.4 +
     3.5 +
     3.6 +\documentclass[a4paper,11pt]{article}
     3.7 +%
     3.8 +\usepackage{makeidx,geometry,amssymb,graphicx,calc,ifthen,fullpage}
     3.9 +%
    3.10 +\usepackage[utf8]{inputenc}
    3.11 +\usepackage[T1]{fontenc}
    3.12 +\usepackage[gen]{eurosym} 
    3.13 +\usepackage[german]{babel}
    3.14 +\usepackage{graphicx}
    3.15 +\usepackage{rotating}
    3.16 +
    3.17 +% correct bad hyphenation here
    3.18 +\hyphenation{op-tical net-works semi-conduc-tor takt-frequenz rechen-ge-schwin-dig-keit außer-euro-päischen pa-ral-lel pa-ral-lele pa-ral-le-len hard-ware-be-schleu-ni-ger}
    3.19 +
    3.20 +
    3.21 +\begin{document}
    3.22 +\bibliographystyle{plain}
    3.23 +%
    3.24 +
    3.25 +\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme}
    3.26 +\author{Nina Engelhardt}
    3.27 +
    3.28 +\maketitle             
    3.29 +%
    3.30 +\tableofcontents
    3.31 +
    3.32 +%\newpage
    3.33 +
    3.34 +\section{Allgemeinverständliche Zusammenfassung} %Short summary of proposal
    3.35 +%Allgemeinverständliche Zusammenfassung mit kurzer Charakterisierung der Ziele und Methoden (nicht mehr als 15 Schreibmaschinenzeilen).
    3.36 +%Short summary accessible to the general public with short characterisation of goals and methods (15 lines max.)
    3.37 +
    3.38 +%Summary for Laymen
    3.39 +
    3.40 +%\emph{[Until approximately the year 2005, every new generation of Central Processing Unit, or CPU, was faster than the previous one, and so for most machines, there was only a need for a single CPU.  This was good in general because a single CPU is easier to program than trying to make many CPUs work together on the same task. Since the year 2005, however, CPUs are no longer getting faster, due to technology constraints.  All the important Halbleiterhersteller such as Intel and AMD have been placing several CPUs (or \emph{cores}, as they are usually called) on a single chip. This means, however, that the more difficult kind of programming that makes many cores work together has to be done.  This kind of programming is called parallel programming and uses a parallel programming language.  Such languages usually force the programmer to know details about the design of the machine the program will run on.  The programmer must make choices in their program that make it work better on that one machine.  If the program is run on a different machine, those program-choices have to be different, so the program has to be changed.  Currently, no widely accepted parallel languages exist that are both easy to use and hide the details of the machine from the programmer.  Finding such a language is known as the "productivity and portability challenge".  It is this challenge that VMS is designed for.  It provides the support necessary for the collective effort of many research groups to work together to solve this very difficult challenge.]}
    3.41 +
    3.42 +
    3.43 +Das Herzstück eines Rechners ist der Prozessor. Über lange Zeit verdoppelte sich mit jeder Prozessorgeneration die Rechenleistung. In 2005 war diese technologische Entwicklung jedoch ausgereizt, eine natürliche Grenze der Leistung eines einzelnen Prozessors erreicht. Die Computerindustrie stieg daraufhin auf Multiprozessorsysteme um, sodass die Rechenleistung nun nicht mehr durch schnelleres Ausführen einer Aufgabe, sondern durch die gleichzeitige Ausführung mehrerer Aufgaben gesteigert wird. 
    3.44 +
    3.45 +%Seit 2005 werden auch im Heimcomputerbereich Multiprozessorsysteme verwendet.
    3.46 +
    3.47 +Unabhängigkeit zweier Aufgaben wird in den heutigen Betriebssystemen durch sog. \emph{Threads}, dargestellt. Dieses Modell ist gut geeignet, wenn sich zwei Programme einen einzelnen Prozessor teilen müssen, ohne sich gegenseitig zu beeinflussen. Mit der steigenden Zahl der Prozessoren wird dieses Modell jedoch immer ineffizienter, da es nur unzureichende Möglichkeiten zur Koordination bereithält. Um diese Unzulänglichkeiten zu beheben, wird eine neue Abstraktion, genannt Virtualized Master-Slave, kurz VMS, entwickelt.
    3.48 +
    3.49 +In dieser Entwicklung wird es meine Aufgabe sein, den für die Koordination von Rechenaufgaben zuständigen Teil des VMS-Systems zu beschleunigen. Hierzu muss der VMS-Code begutachtet, häufig auftretende Rechenfolgen identifiziert, eine auf diese Rechenfolgen zugeschnittene spezielle Hardware entwickelt, und letztlich der VMS-Code an die neue Hardware angepasst werden.
    3.50 +
    3.51 +
    3.52 +
    3.53 +\section{Beschreibung des Forschungsgegenstandes und Vorarbeiten}
    3.54 +%Das Forschungsproblem ist in knapper Form in seinen wesentlichen Merkmalen, Methoden und Zielsetzungen mit Gründen für die Auswahl des Vorhabens durch den Bearbeiter/die Bearbeiterin zu beschreiben. Dazu gehören Angaben zum gegenwärtigen wissenschaftlichen Kenntnisstand sowie zur Literatur- und Quellenlage. Es muss erkennbar sein, dass der Bearbeiter/die Bearbeiterin die zentralen Fragestellungen und Ziele für den eigenen Untersuchungsansatz in Auseinandersetzung mit dem Kenntnisstand entwickelt hat. Der Stand der bisherigen eigenen Arbeit ist zu beschreiben.
    3.55 +%The object of research needs to be described concisely in its essential characteristics, methods and goals, with reasons for the choice of subject by the applicant. This includes information on the current state of the art as well as on availability of literature and sources. It has to be apparent that the applicant developed the central questions and goals for their approach based on the state of the art. The state of previous own work is to be described.
    3.56 +
    3.57 +Durch meine Bachelorarbeit über Messungen zur elektrischen Leistungsverteilung in Prozessoren gewann ich einen ersten Einblick in die Problematik der Energieeffizienz und Rechenleistung. Ich interessierte mich zunächst für Grafikkarten, die aufgrund ihrer massiven Parallelität eine hohe Rechenleistung per Watt aufweisen, musste aber feststellen, dass diese Plattform von hohem Arbeitsaufwand einer Portierung, geringer Portabilität selbst zwischen Geräten der gleichen Hersteller und einer beschränkten Art von Programmen, die sich zur Portierung eignen, gezeichnet ist. Da die Anpassung von Software an diverse Hardware wenig ermutigende Perspektiven aufzeigte, wandte ich mich dem gegenteiligen Problem zu: dem Entwurf von applikationsspezifischer Hardware. In meiner Masterarbeit befasste ich mich mit dem automatischen Entwurf von Hardwaredatenpfaden für applikationsspezifische Prozessoren. An diese Arbeit schloss sich mein Praktikum an der Universität Potsdam an, in dem ich an Rechenmustererkennung in .NET bytecode zur Beschleunigung durch applikationsspezifische Hardware forschte.
    3.58 +
    3.59 +%\emph{[My first internship, on the subject of measurement of power density in processors, gave me a first idea about the tension between energy efficiency and performance. I started looking at GPUs as a solution, since they are very energy efficient by dint of their massive parallelity. However I found that platform disappointing due to the high cost in programmer time of porting an app; low portability even between gPUs of the same family, and the restricted class of programs suitable for porting. Since adjusting software to hardware seemed not so promising, I looked at adapting the hardware to software instead, and wrote my master's thesis on automatic generation of hardware data paths for ASIPs. I continued on this approach in my internship at U. Potsdam, looking at ways to recognize computation patterns suitable for hardware acceleration in .NET bytecode.]}
    3.60 +
    3.61 +Während dieser Forschung begegnete ich dem VMS-Projekt \cite{VMS}, einem vielversprechenden Ansatz um durch eine flexible Hardwareabstraktion die parallele Programmierung sowohl portabel als auch effizient zu gestalten, und dadurch einen größeren Spielraum zur unabhängigen Weiterentwicklung von Software und Hardware zu eröffnen.
    3.62 +
    3.63 +%\emph{[During this research, I encountered the VMS project, which solves all my woes by presenting a flexible hardware abstraction for making parallel programming both portable and efficient, thus allowing more space for independent development of hardware and software.] }
    3.64 +
    3.65 +\subsection{Historischer Kontext}
    3.66 +
    3.67 +Der Fortschritt in der Rechenleistung von Prozessoren wurde lange Zeit durch die kontinuierliche Erhöhung der Taktrate erzielt. In den Jahren 2004-2005 stieß diese Entwicklung an ihre Grenzen, da die elektrische Leistung und somit auch die Hitzeentwicklung mit der Frequenz unerwartet schnell anstieg, und Prozessoren oberhalb der 4GHz nicht mehr mit den gängigen Lüftern, sondern nur noch mit ungleich teureren Flüssigkeitskühlsystemen betreibbar wären. Zudem ließ der Trend hin zu batteriebetriebenen Geräten die Nachfrage nach energieeffizienten Prozessoren enorm anwachsen, sodass ein Paradigmenwechsel dringend vonnöten war. Multiprozessor- und Multicoresysteme, die vorher nur in spezialisierten Hochleistungsrechnern zum Einsatz kamen, hielten nun auch im Heimcomputer Einzug.
    3.68 +
    3.69 +%\emph{[Advances in computing power were for a long time achieved by raising the clock frequency. This development came to a sudden end in 04-05 because power consumption and thus heat rose more quickly than anticipated, making processors above 4GHz impossible to cool with air, requiring unjustifiably more expensive liquid cooling. At the same time the trend towards mobile devices made demand for energy efficient processors grow a lot, necessitating a paradigm shift. Multi-processor and multi-core systems, previously only found in specialized high performance computers, now entered the consumer market.]}
    3.70 +
    3.71 +Um effizient auf Multicoresystemen laufen zu können, müssen Programme explizit parallel geschrieben werden. Die parallele Programmierung hat sich im Laufe der Jahre jedoch als ungleich komplizierter als die sequentielle Programmierung erwiesen, sodass eine Reihe von parallelen Programmiermodellen und dazugehörigen -sprachen entwickelt wurde, die den parallelen Entwurf vereinfachen sollen. Da sich verschiedene Modelle unterschiedlich gut für diverse Programmklassen eignen, ist es wichtig, viele davon zu unterstützen. Heutige Betriebssysteme benutzen jedoch ein einziges Modell als unterste Abstraktionsebene: das Thread-Modell. Alle anderen Programmiermodelle müssen daher auf Threads basierend implementiert werden, was ihre Performance beeinträchtigt.
    3.72 +
    3.73 +%\emph{[To run efficiently on multicore systems, programs have to be written explicitly parallel. Up to now operating systems present the process and thread model as an abstraction of parallelity. In this model each program is a process, containing several threads, each with their own code, and running, conceptually, on their own virtual processor. A real system however contains only one or a few processors, so the system has to divide processor time and memory space between threads without the program noticing.]}
    3.74 +
    3.75 +\subsection{Threads und parallele Programmiermodelle}
    3.76 +
    3.77 +Im Thread-Modell besteht ein Programm aus einem Prozess. Ein Prozess kann mehrere Threads enthalten. Jeder Thread hat seinen eigenen Assemblercode, der die Anweisungen enthält, die er ausführen soll. Konzeptuell wird jeder Thread auf einem eigenen, virtuellen Prozessor ausgeführt, teilt sich jedoch den Speicher mit allen anderen Threads die zu dem gleichen Prozess gehören. Reell enthält ein System aber nur einen oder wenige Prozessoren, die sich unterschiedliche Threads und Prozesse teilen müssen. Das System muss sich daher ohne zutun des Programms darum kümmern, den Threads Rechenzeit und Speicherplatz zuzuteilen, und sie zu unterbrechen und wiederaufzunehmen, ohne dass sie von der Präsenz anderer Prozesse auf dem gleichen Kern beeinflusst werden.
    3.78 +
    3.79 +%\emph{[The experience of writing parallel code has proven much more difficult than writing sequential code, despite nearly 50 years of research on how to make parallel programming the same level of difficulty as sequential programming. Since different models work more or less well for different problems, it's important to support many of them. In addition, parallel code has proven more expensive than sequential code because it has been necessary to modify the source when it is run on a different machine, in order to get acceptable performance on the new hardware architecture.]}
    3.80 +
    3.81 +Aktuell wird die Performance paralleler Programme jedoch durch mangelnde Kontrolle über die Verteilung von Threads auf Prozessoren begrenzt. Dies führt zu unnötigen Wartezeiten, z.B. wenn Cacheaffinität nicht berücksichtigt wird oder wenn mehrere Berechnungen synchron ausgeführt werden müssen.
    3.82 +Unterschiedliche parallele Programmiermodelle haben unterschiedliche Anforderungen an die (zeitliche und räumliche) Ablaufplanung und Synchronisierung, sodass ein vom Programm unabhängiger Scheduler nicht effizient ist.
    3.83 +
    3.84 +%\emph{[Currently, performance of these programming models is hurt by lack of control over placement of threads on processors and scheduling. This causes unnecessary waiting, e.g. when cache affinity is not taken into account or when several calculations need to be synchronized. Different parallel programming models have different requirements for placement, scheduling, and synchronizationm so that an independent scheduler is inefficient.]}
    3.85 +
    3.86 +Bisherige Versuche, dieses Problem zu lösen, indem man die Hardware direkter dem Benutzer präsentiert, wie z.B. im experimentellen Betriebssystem Barrelfish \cite{barrelfish}, haben eine bessere Performance erreicht, jedoch die Programmierung dadurch noch schwieriger gestaltet. In Barrelfish enthält jedes Programm einen eigenen Aufgabenverteiler, der vom System Ressourcen wie z.B. Rechenzeit anfordert. Das System teilt je nach Verfügbarkeit dem Programm Zeitscheiben auf bestimmten Kernen zu, auf die das Programm dann seine Aufgaben eigenständig verteilen kann.
    3.87 +
    3.88 +Das Sequoia-Programmiermodell \cite{sequoia} verfolgt einen ähnlichen Ansatz. Aufgaben in Sequoia sind parametrisierbar, um sie schnell und einfach an verschiedene Hardware-Gegebenheiten anpassen zu können. Der Programmierer muss jedoch die Parameter für jede einzelne Hardware\-konfiguration per Hand bestimmen, was die Portabilität erheblich limitiert.
    3.89 +
    3.90 +Im Gegensatz hierzu stellt VMS ein sowohl flexibles als auch portables Modell dar, was mehrere Programmiermodelle direkt auf der untersten Abstraktionsebene unterstützen kann. Der Anwender kann ohne Leistungseinbußen und ohne zusätzlichen Aufwand die für das Programm am besten geeignete parallele Programmiersprache verwenden. Das System ist auch einfach erweiterbar: Native Unterstützung für neue parallele Programmiersprachen (durch ein Plug-in, s.u.) kann durch eine spezielle virtuelle Zeitdefinition sequentiell implementiert werden. Diese Reduktion auf die einfachere sequentielle Programmierung mindert sowohl Programmieraufwand als auch Fehleranfälligkeit erheblich.
    3.91 +
    3.92 +%\emph{[VMS, through its plugin library, presents a flexible and portable model that can support several programming models efficiently. Its special definition of virtual time makes it possible to implement the constructs underlying a parallel programming model sequentially, lowering both effort of programming and susceptibility to bugs.]}
    3.93 +
    3.94 +%[Needs comparison to rival models either here or next]
    3.95 +
    3.96 +
    3.97 +
    3.98 +
    3.99 +
   3.100 +
   3.101 +%\emph{[The direct rival to VMS is the Thread model, which enjoys extensive hardware support in the form of special lock instructions like CompareAndSwap, and is at the base of most Operating Systems.  VMS is the first of its kind -- an extensible hardware abstraction.  It is more primitive than Threads, or any programming language, and is essentially a definition of time with a standard interface for building programming and execution models like Threads, TBB, OpenMP, Cilk, and other languages on top of.}
   3.102 +
   3.103 +%\emph{High performance parallel languages implement their own user-level thread package inside, or else directly use the hardware thread support instructions.  They then implement their parallelism constructs on top of that Thread implementation.  This may provide integration between the parallelism constructs and the scheduler, but only for a single detailed implementation of the language on particular hardware.  This method doesn't capture any reusable patterns that allow portability.  There is no separate installation of a plugin nor a base with standard interface for the runtime -- everything is re-done by hand for every machine, and that language development effort is only applicable for that one language.  In constrast, the core VMS is implemented only once per hardware, and is less than 2000 lines of code.  This is then re-used by all plugins for all languages for that hardware.  VMS both decreases the effort per machine, and increases the reuse of that effort.]}
   3.104 +
   3.105 +%[Nina: Barrelfish is an OS and is still based on Thread concepts, although it gives more control over the relationship between Threads and hardware.  It does have some similar advantages to VMS in that it has a simple kernel on each core that is "sequential", but it doesn't have any integration between synchronization constructs and scheduling of Threads onto cores..  it doesn't have any facilities for constructing parallel languages..  The similarity that I see is that VMS's implementation for shared-memory multi-core has a separate core\_loop and masterVP for each core, just like barrelfish has a separate CPU driver for each core..  but that's an implementation similarity only..  coincidence, not anything fundamental..]
   3.106 +
   3.107 +%If I understood correctly, Barrelfish 
   3.108 +
   3.109 +\subsection{Das Virtualized Master-Slave Modell}
   3.110 +
   3.111 +%****Changes here*****
   3.112 +
   3.113 +VMS entkoppelt Hardware und Software durch ein dreiteiliges System: ein Programmier\-sprachen\-spezifischen Compiler, einen Hardwarespezifischen VMS-Kern und ein Plug-in, das die beiden verbindet.
   3.114 +
   3.115 +%\emph{[VMS achieves separation of hardware and software through three components: a compiler front-end for the software, a VMS core for the hardware, and a plugin that connects the two.  The plugin is chosen according to both the language and the hardware, with a different plugin for every combination (except that a plugin is designed for a class of hardware, so the same one can be used on all hardware in that class).  The plugin contains the language's parallelism constructs and a hardware-specific scheduler.]}
   3.116 +
   3.117 +\begin{figure}[h!]
   3.118 +  \centering
   3.119 +    \includegraphics[width=0.25\textwidth]{vms-components.pdf}
   3.120 +      \caption{Interaktion der Bestandteile von VMS.  Quelle: S.Halle \cite{VMS}}
   3.121 +\end{figure}
   3.122 +
   3.123 +Um auf einer bestimmten Hardware effizient ausgeführt werden zu können, muss die parallele Aufgabenverteilung, und insbesondere die Größe einer einzelnen parallelen Aufgabe, die konkreten Eigenschaften der Hardware, wie z.B. Cachegröße oder Rechengeschwindigkeit, berücksichtigen. Man kann allerdings nicht wie im High Performance Computing das Programm für jeden einzelnen Rechner neu kompilieren, deshalb muss das kompilierte Programm unabhängig von diesen Parametern bleiben. Um diesen Konflikt zu lösen, generiert der VMS-Compiler während der Übersetzung Funktionen, die die Aufgabengröße modifizieren können, und fügt diese dem Programm hinzu. Zur Laufzeit kann so das System die Aufgabenverteilung genau anpassen.
   3.124 +
   3.125 +
   3.126 +%Dieses Programm wird dann für mehrere Hardwareklassen (generell durch einen gemeinsamen Befehlssatz definiert) separat kompiliert und die resultierenden Binärcodes in ein gemeinsames Paket gespeichert. Dadurch ist zur Laufzeit sowohl Portabilität über mehrere Hardwareklassen als auch eine genaue Anpassung der Aufgabenverteilung an die spezifische Konfiguration innerhalb der Hardwareklasse gegeben.
   3.127 +
   3.128 +%\emph{[In order to efficiently execute a parallel program on a given hardware, the size of a single parallel task has to be adjusted to hardware parameters such as cache size and cycles to move data between caches.  But to be portable, the executable must be independent of such parameters, so the task size cannot be encoded in the executable.  The solution that VMS uses is for the compiler to generate functions that can manipulate task size.  It places these functions into the executable, and they are called during a run by the scheduler in the plugin.}
   3.129 +
   3.130 +Ein zweiter wichtiger Performance-Faktor sind Datentransfers zwischen Caches. Wenn z.B. eine Berechnung auf einem Kern ausgeführt wird, dessen Cache bereits die nötigen Daten enthält, findet keine Kommunikation statt. Falls diese Berechnung jedoch einem Kern zugeteilt wird, der sich auf einem anderen Sockel befindet, müssen die Daten über den Front Side Bus angefordert werden, was mehrere Tausend Prozessorzyklen dauert. Die Platzierung von Aufgaben muss also sorgfältig gewählt werden. Es ist jedoch nicht möglich, darüber bereits während der Kompilierung zu entscheiden, weil die Rechenzeit der Aufgaben nicht voraussehbar ist. (Man kann zwar eine Obergrenze berechnen, doch dann würde jede kürzere Rechnung den Prozessor, der ihm zugeteilt wurde, im Leerlauf lassen.) Es ist also notwendig, dem System zur Laufzeit mitzuteilen, welche Daten sich wo befinden, damit es die beste Entscheidung treffen kann. Ein VMS-Compiler muss daher auch alle Informationen über Datenabhängigkeiten, die ihm zugänglich sind, in Funktionen kapseln und dem Programm beifügen.
   3.131 +
   3.132 +%\emph{A second requirement for good performance is to minimize the movement of data between caches.  If a task is placed on a core whose cache already contains the data needed, then no communication takes place.  In contrast, if a task is placed on a core residing in a different socket from the one that contains the needed data, then the data has to be moved across the external system bus, requiring thousands of extra cycles.  Hence, where a task is placed has a large impact on performance.  In addition, it is wasteful to choose the placement of tasks during compilation if the execution time of a task can vary -- it causes cores with short tasks to sit idle waiting for cores with longer tasks to finish.  So task placement has to be decided during the run.  But the decision of the best place to put a task requires knowing where the data resides!}
   3.133 +
   3.134 +\begin{figure}[bht]
   3.135 +  \centering
   3.136 +    \includegraphics[width=0.99\textwidth]{vms-ecosystem.pdf}
   3.137 +      \caption{VMS-Bestandteile für mehrere Programmiersprachen und mehrere Hardwareklassen. Quelle: S.Halle \cite{VMS}}
   3.138 +\end{figure}
   3.139 +
   3.140 +Um diese beiden Anforderungen zu erfüllen, besteht ein VMS-Compiler aus zwei Teilen: Das Front-End analysiert eine parallele Programmiersprache, die Anpassung der Aufgabengröße unterstützt, übersetzt sie in eine sequentielle Zwischensprache und fügt die o.g. Funktionen hinzu. Ein sequentieller Compiler erstellt daraus dann optimierte Binärdateien für unterschiedliche Maschinenbefehlssätze. Als Zwischensprache wurde C gewählt, weil hierfür gute Compiler für eine große Anzahl Befehlssätze existieren.
   3.141 +
   3.142 +%\emph{The solution that VMS takes is for the compiler to extract task data-usage information and encode it in functions that the plugin's scheduler calls during the run. To satisfy both requirements, a VMS-compatible compiler is made of two parts: a front-end supporting a parallel programming language that has task-resizing constructs, and a sequential back-end compiling task code to an instruction set. The interface language between front-end and back-end is C, which has the advantage of availability of good-quality sequential compilers for a large variety of instruction sets.]}
   3.143 +
   3.144 +
   3.145 +Das Plug-in enthält den wichtigsten Bestandteil der Laufzeitumgebung: einen Pro\-grammier\-spra\-chen- und Hardwarespezifischen Aufgabenverteiler. Das Plug-in kennt den generellen Aufbau der Hardware (z.B. ein SMP-System mit hierarchischem Cache-Layout) und kann die exakten Parameter (Anzahl der Rechenkerne, Größe und Verteilung der Caches) vom VMS-Kern anfordern. Es kennt auch die Strukturen, die von der parallelen Programmiersprache definiert werden, und kann die Details der jeweiligen Applikation (welche Datenabhängigkeiten gibt es, wie variiert die Rechenzeit, ...) über die o.g. Funktionen erfahren. Aufgrund dieser Informationen kann die Verteilung und Ausführung der parallelen Berechnungen genau gesteuert werden.
   3.146 +
   3.147 +%\emph{[A plugin is both language-specific and specific to a certain class of hardware. A class is constituted by a group of hardware that has the same general architecture (e.g. a SMP system with hierarchical cache layout). The plugin can query the exact parameters (e.g. number of cache levels, number of cores) from the VMS-core. It has thus all the elements required to make the best scheduling decisions: it knows the exact hardware configuration (cache sizes, execution speed...) and it knows task properties inherent to the application (what data is needed, how much execution time varies, which dependencies occur, how it can modify the size of tasks...). It also contains all the synchronization constructs specific to the parallel programming language used (locks and mutexes for threads, send and receive for SSR, spawn and sync for Cilk,...). The plugin completes an invisible, virtual, master ``entity'' that controls activity of all virtual slaves.  The virtual slaves run the parallel tasks of the application, and the Master invisibly assigns them to physical cores.]}
   3.148 +
   3.149 +%[Nina: the Master is an abstract entity that enforces the semantics of the language's synchronization constructs -- that is, the Master entity includes the plugin -- the plugin is part of the Master -- it's a bit weird because in VMS, no physical hardware is visible to the application -- the Master has all the physical hardware hidden inside it.  So, the Master isn't a virtual processor, but much more -- it creates virtual processors, it enforces guarantees about the relationship between time in one virtual processor vs time in a different virtual processor, and so on.  Strange, I know, but had to be done that way to get a consistent theoretical definition of VMS.  The plugin doesn't actually "run" in the Master entity -- instead, the plugin is part of the Master entity.  Before the plugin is there, the Master entity is incomplete -- it can't do anything -- the plugin adds the missing parts that lets the Master be used by an application.  It's weird, but doing it that way has some really good stuff as a consequence -- to understand this well will take a while getting into the details of what's inside a parallel language and scheduling and so forth, then the choice to make the Master that way will make sense  ; )   In PhD, this paragraph would be drawn as the professor at the black-board with a bunch of equations, with the little words "a miracle happens here" and then some more equations ; ) ]
   3.150 +
   3.151 +
   3.152 +Der VMS-Kern ist eine systemnahe Hardware-Abstraktion, die die grundlegenden Funktionen zur Koordination von Aufgaben, wie z.B. Start und Stopp der Ausführung von virtuellen Kernen auf einem reellen Kern, bereitstellt. Gemeinsam mit dem Plug-in stellt der VMS-Kern den ``Master'' in \emph{Virtualized Master-Slave} dar, der virtuelle ``Slave''-Kerne, die parallele Aufgaben ausführen, kontrolliert.
   3.153 +
   3.154 +%\emph{[The VMS-core is a low-level hardware abstraction, which contains the basic functions necessary for the plugin, such as task switching.]}
   3.155 +
   3.156 +
   3.157 +\subsection{Kern der Arbeit}
   3.158 +
   3.159 +Meine Arbeit wird Ansätze untersuchen, die Synchronisation und Aufgabenverteilung für parallele Programme in VMS zu verbessern. Durch diese Verbesserung verringert sich die Größe der Rechenabschnitte, die effizient parallel ausgeführt werden können (Task-Level Parallelism). Es wird erwartet, dass Abschnitte von nur wenigen Hundert Befehlen sinnvoll nutzbar werden, was eine Verbesserung von zwei Größenordnungen gegenüber bisherigen Implementationen von VMS, und drei Größenordnungen gegenüber dem Thread-Modell darstellt. Viele Programme, die bisher keinen Vorteil aus Parallelität ziehen konnten, könnten so parallel ausgeführt werden, und existierende parallele Programme können ihre Effizienz steigern.
   3.160 +
   3.161 +%\emph{[This project will investigate two sources of improving synchronization and scheduling during execution of a parallel application.  These improvements will reduce the size of task that can be profitably run in parallel.   It is expected that tasks of only a few hundred instructions will become profitable, an improvement of two orders of magnitude or more over software implementations of VMS, and three orders of magnitude or more over traditional Thread-based approaches.  This reduction in profitable task size enables new classes of application to be profitably run in parallel, and increases the amount of useful parallelism available in most existing applications.  This in turn allows them to be run faster and with lower energy.}
   3.162 +
   3.163 +Ziel der Arbeit ist, einen speziellen Kern zu entwickeln, der den Master besonders effizient ausführt. Ausgehend von einem Softcore wie z.B. MicroBlaze oder OpenRISC, sollen spezielle Hardwarekonstrukte hinzugefügt werden, die häufige Operationen der Synchronisationsobjekte beschleunigen, wie z.B. Nachschlagen in Hashtabellen oder musterbasierte Suche in Assoziativspeichern. Spezielle Konstrukte zur Beschleunigung der Aufgabenverteilung werden ebenfalls untersucht. Diese haben einen zweiten Vorteil: wenn bessere Scheduling\-entscheidungen schneller getroffen werden können, sinkt die systemweite Kommunikation, was sowohl die Leistung erhöht als auch den Energieverbrauch senkt.
   3.164 +
   3.165 +% und diesen so mit den ausführenden Kernen zu verbinden, dass er diese effizient Kontrollieren kann. Dies verringert den Synchronisations-Overhead.
   3.166 +
   3.167 +%\emph{The approach is to design hardware that speeds up the plugin by providing a specially-designed core to act as the Master entity, and providing special linkage between this Master core and the cores that perform the work.  The overhead of performing a synchronization construct comes from the overhead of the Master entity, execution of the plugin's parallelism constructs, and execution of the scheduling decision.}
   3.168 +
   3.169 +
   3.170 +
   3.171 +Ein spezialisierter Scheduling-Kern mit Hardwarebeschleunigern kann so die Ausführungszeit eines Programms deutlich verbessern, ohne dass das Programm oder die ausführenden Kerne verändert werden müssten.
   3.172 +
   3.173 +
   3.174 +
   3.175 +Es wurden bereits mehrere Hardwarebeschleuniger zur Aufgabenverteilung entwickelt, darunter auch im Fachbereich Architektur Eingebetteter Systeme der TU Berlin \cite{MJ09}. Auch die Carbon Architektur \cite{carbon} zeigt, dass Hardwaregesteuerte Ablaufplanung es ermöglicht, Programme um ein Vielfaches effizienter auszuführen. Diese Plattformen sind jedoch immer auf ein einziges Programmiermodell spezialisiert (\emph{StarSs} im Falle der von AES entwickelten Architektur, \emph{RMS} für Carbon), und können nur bestimmte Klassen von Programmen ausführen.
   3.176 +
   3.177 +%\emph{Several accelerators for Scheduling have been developed, also in the AES group. Similarly, Carbon shows that hardware scheduling can be several times more efficient than software. However, these platforms are always specialized to a single programming model (StarSs for the AES work, RMS for carbon), and can only execute certain classes of applications.}
   3.178 +
   3.179 +Die Herausforderung meiner Arbeit ist, eine generelle und erweiterbare Architektur zu entwickeln, die eine Vielzahl von Programmiermodellen effizient unterstützt.
   3.180 +
   3.181 +%\emph{The challenge of this project is to build a general and extensible architecture that can support a multitude of programming models efficiently.}
   3.182 +
   3.183 +%Das Ziel der Arbeit ist es, einen Satz von Hardwarebeschleunigern zu entwickeln, die auf die Planungs- und Synchronisierungprozesse zugeschnitten sind, die das Hertzstück von VMS ausmachen. Diese Hardwarebeschleuniger werden dem Master zur Verfügung gestellt, der die Rechenaufgaben plant, auf die Slave-Kerne verteilt und koordiniert bzw. synchronisiert. Dies ermöglicht ein feineres Management der Aktivität und erhöht dadurch automatisch die globale Leistung des Systems, ohne dass die darauf laufenden Programme modifiziert werden müssten.
   3.184 +
   3.185 +%\emph{The design of the core and the special linkage will reduce the overhead of the Master.  Custom hardware accelerators for operations commonly performed inside synchronization constructs will reduce their execution time.  Examples of such operations are hash-table lookup and pattern-matching via content-addressable-memory.  Custom hardware accelerators for the scheduling decisions will also be investigated. The primary example is a search accelerator that speeds up finding optimal or near-optimal scheduling decisions.}
   3.186 +
   3.187 +%\emph{The scheduling accelerators have a second benefit: they allow better quality decisions to be made, which reduces the total communication of data in the system, which increases performance and at the same time decreases energy usage.  If we create a specialized scheduling core with hardware acceleration for the most common scheduling and synchronization operations, we can massively increase performance of an application without ever having to change anything in the source code or in the cores on which it runs.]}
   3.188 +
   3.189 +
   3.190 +
   3.191 +
   3.192 +
   3.193 +%\emph{[This project aims to explore creating hardware accelerators for the synchronization and scheduling processes that lie at the heart of VMS, and parallel performance.  Any application written in a VMS-implemented language will automatically inherit the use and benefits of these accelerators, thanks to VMS's plugin architecture.]}
   3.194 +
   3.195 +\label{sec:arbeitsschritte}
   3.196 +Folgende Arbeitsschritte sind vonnöten:
   3.197 +
   3.198 +~
   3.199 +
   3.200 +\noindent\textbf{Phase 1: Hardwareentwicklung}
   3.201 +\begin{enumerate}
   3.202 +\item{\textbf{Kernfunktionen identifizieren}
   3.203 +
   3.204 +Den Code der Scheduler und der parallelen Konstrukte durchsuchen, um die wichtigsten Funktionen zu identifizieren und auf Hardwaretauglichkeit zu prüfen. Voraussichtlich werden Hashfunktionen und SAT-Solver (die zur Suche nach optimalen Scheduling-Lösungen dienen) zu den aussichtsreichen Kandidaten zur Beschleunigung gehören.
   3.205 +
   3.206 +%\emph{[Research frequent and rechenintensive functions performed inside schedulers and parallel construct implementations, to verify candidates to be accelerated in hardware. Projected candidates include hash functions (frequently used in scheduling) and support for sat-solvers (used to search for optimal scheduling decisions).]}
   3.207 +}
   3.208 +\item{\textbf{Analyse des Laufzeitverhaltens}
   3.209 +
   3.210 +Den VMS-Code instrumentieren und profilieren, um den Anteil der Rechenzeit der Funktionen zu erfassen und einen ersten Eindruck der zu erwartenden Beschleunigung zu bekommen. Die besten Kandidaten zur Hardwarebeschleunigung auswählen.
   3.211 +
   3.212 +%\emph{[Instrument VMS code for profiling to measure the impact of each of these functions.]}
   3.213 +}
   3.214 +\item{\textbf{Design Space Exploration}
   3.215 +
   3.216 +Mögliche Hardwaredesigns von Beschleunigern für die ausgewählten Funktionen finden und auf ihre Machbarkeit und Effizienz untersuchen.
   3.217 +
   3.218 +%\emph{[Explore available softcores and integrated cores and evaluate suitability as VMS master core. Propose hardware implementations for the most important functions and evaluate their feasibility.]}
   3.219 +}
   3.220 +\item{\textbf{Lösung implementieren}
   3.221 +
   3.222 +Die besten Lösungsansätze in einer Hardware Description Language realisieren, in einem FPGA testen und ihre tatsächliche Leistung messen.
   3.223 +
   3.224 +%\emph{[Implement the most promising solution in a hardware-description-language and measure its performance.]}
   3.225 +}
   3.226 +\item{\textbf{Hardwareintegration}
   3.227 +
   3.228 +Die Hardwarebeschleuniger mit einem programmierbaren Hardwarescheduler, der von einem anderen Mitglied des Fachbereichs entwickelt wird, integrieren, um einen VMS umfassend unterstützenden Kern zu erhalten.
   3.229 +
   3.230 +%\emph{[Integrate the new hardware with the programmable scheduler being developed in the lab.]}
   3.231 +}
   3.232 +\newcounter{enumi_saved}
   3.233 +\setcounter{enumi_saved}{\value{enumi}}
   3.234 +\end{enumerate}
   3.235 +
   3.236 +\noindent\textbf{Phase 2: Software-/Systemunterstützung der neuen Hardware}
   3.237 +
   3.238 +\begin{enumerate}
   3.239 +\setcounter{enumi}{\value{enumi_saved}}
   3.240 +\item{\textbf{VMS-Core}
   3.241 +
   3.242 +Einen hardwarespezifischen VMS-Core für die neue Hardware entwickeln, der die Hardwarebeschleuniger ausnutzen kann.
   3.243 +
   3.244 +%\emph{[Work with the implementor of the VMS interface for Linux to integrate the hardware into the Linux implementation of VMS.]}
   3.245 +}
   3.246 +
   3.247 +\item{\textbf{Plug-ins}
   3.248 +
   3.249 +Plug-ins für einige parallele Programmiersprachen (voraussichtlich \emph{SSR, pthreads, StarSs}\cite{starss} und \emph{Cilk}\cite{cilk}) für die neue Hardware entwickeln, um VMS-Benchmarks ausführen zu können.
   3.250 +
   3.251 +%\emph{[Write a plugin that uses the new hardware to implement parallelism constructs and scheduling, to show efficiency on real-life problems.]}
   3.252 +}
   3.253 +
   3.254 +\item{\textbf{Minimalistisches Runtime}
   3.255 +
   3.256 +Ein minimalistisches Betriebssystem implementieren, das das System initialisieren, Programme laden, zwischen Programmen wechseln, und den Programmen einige Libraryfunktionen wie z.B. I/O zur Verfügung stellen kann.
   3.257 +}
   3.258 +
   3.259 +\item{\textbf{Performanceevaluierung}
   3.260 +
   3.261 +Die Performance der neuen Hardware an den Standard-VMS-Benchmarks testen, und mit der Architektur ohne Hardwarebeschleunigung vergleichen. Für das \emph{StarSs}-Programmiermodell kann die Performance auch mit dem spezialisierten \emph{StarSs}-Hardwarescheduler, der im Fachbereich entwickelt wurde, verglichen werden.
   3.262 +
   3.263 +%\emph{[Test the performance of the standard VMS benchmarks running on the new hardware, with scheduling acceleration vs without]}
   3.264 +}
   3.265 +\end{enumerate}
   3.266 +
   3.267 +
   3.268 +
   3.269 +\subsection{Eigene Vorarbeiten}
   3.270 +
   3.271 +
   3.272 +%\emph{[This work is going to require a variety of skills that I have acquired throughout my career, making me uniquely suited for the project.]}
   3.273 +
   3.274 +Der Kern dieser Arbeit ist Hardwarebeschleunigung, ein Thema mit dem ich mich seit mehreren Jahren auseinandersetze. In meiner Masterarbeit über den Entwurf von Daten\-pfaden für spezialisierte Prozesssorbefehle \cite{masterarbeit} 
   3.275 +vertiefte ich dieses Wissen, und werde nun die daraus gewonnenen Erkenntnisse und Erfahrungen in ein System einbringen, dass ein breiteres Anwendungs\-spektrum verspricht.
   3.276 +
   3.277 +Des weiteren habe ich auch in der Erstellung von Leistungsprofilen, die besonders zu Anfang der Arbeit wichtig ist (s.o. Arbeitsschritte 1 \& 2), einige Erfahrung: In 2008 habe ich in einem zweimonatigen Praktikum im Zuse-Institut Berlin eine Anwendung mithilfe von CUDA auf eine Grafikkarte portiert, was eine genaue Beachtung der Rechenzeitverteilung voraussetzt. Zudem beschäftige ich mich zur Zeit an der Universität Potsdam mit der automatisierten Erfassung von Leistungsprofilen in .NET und Schätzung der durch bestimmte Hardwarebeschleuniger zu erwartenden Beschleunigung.
   3.278 +
   3.279 +Bei der Arbeit mit CUDA muss ein Großteil der Scheduling- und Speicher\-zu\-teilungs\-entschei\-dungen per Hand getroffen werden. Das daraus resultierende Wissen über die Abläufe während der Ausführung und ihren Einfluss auf die Performance werden mir bei der Integration in den bestehenden Scheduler und bei dem Entwurf eines Plug-ins für den von mir entwickelten Kern von großem Nutzen sein. Auch die detaillierten Kenntnisse zum Prozessordesign, die ich in den Kursen und in der Zusammenarbeit mit André Seznec während eines Praktikums erworben habe, werden mir hier behilflich sein.
   3.280 +
   3.281 +%\begin{itemize}
   3.282 +%\item
   3.283 +%\emph{[Most obviously, the core of this project is generation of hardware accelerators, which is what I have spent the last two years on (that's half of my scientific career).]}
   3.284 +%\item
   3.285 +%\emph{[The profiling required to find the right functions to accelerate is something I have a) done by hand while porting an app to CUDA and also b) automatized recently for the work on .NET.]}
   3.286 +%\item
   3.287 +%\emph{[Working with CUDA also requires to do a lot of scheduling and memory layout by hand, which will help with scheduler integration and writing the plugin.
   3.288 +%This part will also profit from the detailed knowledge of processor design I got from Andre Seznec (both classes \& bachelor internship).]}
   3.289 +%
   3.290 +%\end{itemize}
   3.291 +
   3.292 +%In my Master's thesis I have worked on automatic generations of hardware datapaths for application-specific instruction set processors. The skills acquired in this work translate directly to steps 3 and 4.
   3.293 +%Since then I have been working at the university of Potsdam on detection of computationally intensive patterns in .NET CIL bytecode for the purpose of hardware acceleration, which will help me with steps 1 and 2.
   3.294 +
   3.295 +% [Ben wants me to reference the work I did in Andr\'e Seznec's group, but I don't really see how researching if it's possible to deduce on-chip power distribution from temperature sensor measurements could help me here...]
   3.296 +% 
   3.297 +%  I agree with Ben, the point is to say "In addition, I have successfully completed and published research with Andre Seznec at [the place] which was hardware-level and related to power distributed across a processor[cite].  It made me familiar with the details of processors and their hardware implementation, which will be helpful background in this project."  The idea is to set yourself apart from others -- a successfully published paper gives you extra points compared to other students trying to get this scholarship.  It's not important how it applies to this work, but instead is important to show that you are a good bet to spend their money on.  It shows you can successfully complete world-class research and get it published -- reduces the risk of the committee if they pick you.  They can say "see, she already has succeeded in research, she's a good choice!"
   3.298 +% 
   3.299 +% Sounds nice, unfortunately none of that is true! 
   3.300 +
   3.301 +%\subsection{What else?}
   3.302 +
   3.303 +\section{Arbeits-/Zeitplan}
   3.304 +%Das Stipendium wird zunächst für einen Zeitraum bis zu zwei Jahren gewährt; die Möglichkeit der Weiterförderung wird vor Ablauf des ersten und des zweiten Jahres geprüft. Dazu legt der Stipendiat/die Stipendiatin einen Arbeitsbericht vor, aus dem sich der sachliche und zeitliche Verlauf der bisherigen Arbeit und ein Zeitplan für die Fertigstellung der Arbeit ergeben. Die Förderung endet spätestens nach drei Jahren.
   3.305 +%Mit Blick auf diesen zeitlichen Rahmen sind die geplanten Arbeitsschritte möglichst detailliert darzustellen. Der Zeitplan (beginnend ab Förderanfang) ist nach Monaten gegliedert tabellarisch zusammenzufassen.
   3.306 +
   3.307 +%The scholarship is first granted for a period of up to two years; possibility of further funding is examined before the end of the first and second year. For this the scholarship holder presents a work report laying out the temporal and technical advancement of the work and a schedule for termination thereof. The funding ends after three years at the latest.
   3.308 +%With respect to these constraints the steps in the project have to be described with as much detail as possible. The schedule (beginning with the start of funding) has to be summarized in a table segmented by months.
   3.309 +
   3.310 +%start of funding would be July 1st btw
   3.311 +
   3.312 +
   3.313 +Der Zeitplan folgt in großen Zügen den Arbeitsschritten, die in Abschnitt \ref{sec:arbeitsschritte} beschrieben wurden. Es gibt zwei Phasen: in den ersten zwei Jahren wird die Hardware fertiggestellt und getestet, im dritten Jahr die Systemsoftware dafür entwickelt.
   3.314 +
   3.315 +~
   3.316 +
   3.317 +\noindent Die benötigte Zeit für die Arbeitsschritte wird wie folgt veranschlagt:
   3.318 +\begin{description}
   3.319 +\item[Hardwareentwicklung:]{ 21 Monate
   3.320 +
   3.321 +\begin{enumerate}
   3.322 +\item Kernfunktionen identifizieren: 3 Monate
   3.323 +\item Analyse des Laufzeitverhaltens: 3 Monate
   3.324 +\item Design Space Exploration: 3 Monate
   3.325 +\item Lösung implementieren: 6 Monate
   3.326 +\item Schedulerintegration: 3 Monate
   3.327 +\item Integrationstest \& Debugging: 3 Monate
   3.328 +\setcounter{enumi_saved}{\value{enumi}}
   3.329 +\end{enumerate}
   3.330 +}
   3.331 +\item[Softwareunterstützung:]{ 12 Monate
   3.332 +
   3.333 +\begin{enumerate}
   3.334 +\setcounter{enumi}{\value{enumi_saved}}
   3.335 +\item VMS-Core: 3 Monate
   3.336 +\item Plug-ins: 3 Monate
   3.337 +\item Runtime: 3 Monate
   3.338 +\item Integrationstest, Performanceevaluation \& Optimierung: 3 Monate 
   3.339 +\end{enumerate}
   3.340 +} 
   3.341 +
   3.342 +\item[Niederschrift:] 3 Monate
   3.343 +\end{description}
   3.344 +
   3.345 +
   3.346 +%1. \& 2. Find functions to accelerate - 6m
   3.347 +%3. Explore hardware possibilities - 3m
   3.348 +%4. Implement accelerators - 6m
   3.349 +%5. Integrate with Tamer's HW - 3m
   3.350 +%7. VMS-Core - 3m
   3.351 +%6. Integration test and debugging of system - 3m
   3.352 +%8. Plug-ins - 3m
   3.353 +%9. Mini-runtime - 3m
   3.354 +%10. Performance evaluation, optimization - 3m
   3.355 +%11. Write thesis - 3m
   3.356 +
   3.357 +Daraus ergibt sich der Zeitplan in Abb. \ref{gantt}.
   3.358 +
   3.359 +\begin{sidewaysfigure}
   3.360 +	\centering
   3.361 +	\includegraphics[width=0.99\textwidth]{gantt.pdf}
   3.362 +	\caption{Zeitplan}
   3.363 +	\label{gantt}
   3.364 +\end{sidewaysfigure}
   3.365 +
   3.366 +
   3.367 +Arbeitsschritte 1 \& 2 wurden zeitlich zusammengefasst, da ``wichtige Funktionen'' nur in Zusammenhang mit ihrer Rechenzeit und der Häufigkeit der Aufrufe sinnvoll definiert werden können. Auch bei den weiteren Arbeitsschritten sind Überlappung bzw. Feedback zu erwarten, z.B. falls während der Implementierung (Schritt 4) festgestellt werden sollte, dass die in Schritt 3 gedachte Architektur sich anders verhält als vorgesehen, und der Entwurf angepasst werden muss.
   3.368 +
   3.369 +Am Ende jedes Arbeitsschrittes ist eine kurze Evaluationsphase vorgesehen, um zu überprüfen, dass das Ergebnis den Anforderungen entspricht, sowie eine erste Niederschrift der erfolgten Arbeit, die später als Rohentwurf des entsprechenden Kapitels der Dissertation oder als Grundlage für einen Vortrag oder eine Veröffentlichung dient.
   3.370 +
   3.371 +~
   3.372 +
   3.373 +\noindent Folgende Meilensteine werden festgelegt:
   3.374 +\begin{description}
   3.375 +\setlength{\itemsep}{0em}
   3.376 +\item[12 Monate:] Der Lösungsraum der Hardwarebeschleuniger wurde durchsucht, ein detaillierter Plan der Architektur steht fest.
   3.377 +\item[24 Monate:] Lauffähige Hardware und einige vorläufige Daten zur Performance liegen vor.
   3.378 +\item[36 Monate:] Voll funktionsfähiges System, detaillierte Performanceanalyse.
   3.379 +\end{description}
   3.380 +
   3.381 +
   3.382 +\section{Einordnung des Vorhabens}
   3.383 +
   3.384 +Diese Arbeit wird im Rahmen der Forschungsgruppe Architektur eingebetteter Systeme (AES) an der TU Berlin ausgeführt. Die Forschungsschwerpunkte des Fachgebiets AES sind u.a. Vielkern-Architekturen, Hardwaregestützte Ablaufplanung und neue Programmierparadigmen zur effizienten Ausnutzung heterogener Mehrkernarchitekturen.
   3.385 +Alle drei Schwerpunkte, insbesondere die Hardwaregestützte Ablaufplanung, werden in dieser Arbeit behandelt.
   3.386 +
   3.387 +Sie erweitert und ergänzt die bisherige Arbeit des Fachgebiets zur Unterstützung des StarSs Programmiermodells. Durch die Einbindung von VMS werden sowohl StarSs-Applikationen als auch in anderen Programmiermodellen geschriebene Programme automatisch von der hardwarebeschleunigten Ablaufplanung profitieren, ohne dass der Source\-code modifiziert werden muss.
   3.388 +
   3.389 +%This proposal fits perfectly with the research activities of the AES group. As indicated on the website (http://www.aes.tu-berlin.de/menue/home/parameter/en/), Forschungsschwerpunkte of the AES group include multi- and many-core architectures, hardware support for task management and scheduling, and novel parallel programming paradigms for heterogeneous multi-/many-core architectures.
   3.390 +%This proposal matches these Forschungschwerpunkte perfectly, in particular the Forschungsschwerpunkt hardware support for task management and scheduling.
   3.391 +%Furthermore, it is complementary to the work currently being performed in this Forschungsschwerpunkt since this work targets the StarSs programming model~\cite{?} while this proposal targets VMS.
   3.392 +%This proposal therefore both expands and generalizes the work currently being performed in the AES group, since due to the encapsulation of VMS, applications implemented using VMS-implemented languages will automatically inherit the benefits of the acceleration hardware without having to modify the source code.
   3.393 +
   3.394 +\section{Reisemittel}
   3.395 +
   3.396 +Der Besuch von wissenschaftlichen Tagungen und Konferenzen ist unabdingbar, um den Stand meiner Arbeit zu präsentieren sowie mich über den Stand der Forschung auf dem Laufenden zu halten und ggf. Entwicklungen, die in das Gebiet meiner Arbeit fallen, mit einzuarbeiten.
   3.397 +Im Laufe ihrer Arbeit besuchen die Doktoranden des Fachgebiets AES im Durchschnitt drei bis sechs wissenschaftliche Konferenzen. Das Fachgebiet hat jedoch nur begrenzte Mittel zur Verfügung. Der Besuch einer innerhalb Europas stattfinden\-den Tagung verursacht gewöhnlich Kosten im Rahmen von 1000\euro, einer außer\-euro\-päischen Konferenz rund 1500\euro. Bei anzunehmendem Besuch von zwei europäischen und zwei außereuropäischen Tagungen während meiner Arbeit,  veranschlage ich Reisemittel in Höhe von 5000\euro.
   3.398 +
   3.399 +%From conversations with members of the AES group it became clear that on average PhD students attend 3 to 6 scientific conferences to present their work. The group, however, has limited funds to cover these expenses. It also became clear that to attend a European conference costs about E 1000 and a conference outside Europe about E 1500. Assuming 2 European conferences and 2 conferences outside Europe, we request a travel budget of 2x1000 + 2x1500 = 5000 E. Additional travels should be financed from other funding sources, such as the travel budget of the group.
   3.400 +
   3.401 +\section{Vorschläge für weitere Gutachter}
   3.402 +
   3.403 +Dr. Christophe Bobda\\
   3.404 +Associate Professor, 
   3.405 +Computer Science and Computer Engineering\\
   3.406 +University of Arkansas\\
   3.407 +Phone: (479) 575-4797\\
   3.408 +E-mail: cbobda@uark.edu\\
   3.409 +
   3.410 +\noindent Dr. Christian Haubelt\\
   3.411 +Lehrstuhl für Informatik 12\\
   3.412 +(Hardware-Software-Co-Design)\\
   3.413 +Universität Erlangen-Nürnberg\\
   3.414 +Am Weichselgarten 3\\
   3.415 +91058 Erlangen\\
   3.416 +haubelt@cs.fau.de \\
   3.417 +
   3.418 +\noindent Prof. Dr. Theo Ungerer\\
   3.419 +Lehrstuhl für Systemnahe Informatik und Kommunikationssysteme,\\
   3.420 +Institut für Informatik.\\
   3.421 +Eichleitnerstr. 30,\\
   3.422 +Universität Augsburg,\\
   3.423 +86135 Augsburg \\
   3.424 +Tel. 0821-598-2350 / -2351\\
   3.425 +ungerer@informatik.uni-augsburg.de \\
   3.426 +
   3.427 +\begin{thebibliography}{9}
   3.428 +
   3.429 +\bibitem{VMS}
   3.430 +Sean Halle,
   3.431 +\emph{Support of Collective Effort Towards Performance Portability},
   3.432 +in Proceedings of 3rd USENIX Workshop on Hot Topics in Parallelism, May 2011
   3.433 +
   3.434 +\bibitem{barrelfish}
   3.435 +  Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania, 
   3.436 +  \emph{The Multikernel: A new OS architecture for scalable multicore systems,} 
   3.437 +  in Proceedings of the 22nd ACM Symposium on OS Principles, Big Sky, MT, USA, Oktober 2009.
   3.438 +
   3.439 +\bibitem{MJ09}
   3.440 +C.H. Meenderinck and B.H.H. Juurlink,
   3.441 +\emph{A Case for Hardware Task Management Support for the StarSS Programming Model,}
   3.442 +in Proceedings Conference on Digital System Design Architectures, Methods and Tools; special session on Multicore Systems: Design and Application, September 2010.
   3.443 +
   3.444 +\bibitem{carbon}
   3.445 +S. Kumar, C. Hughes, and A. Nguyen, 
   3.446 +\emph{Carbon: Architectural
   3.447 +Support for Fine-Grained Parallelism on Chip Multiprocessors},
   3.448 +in Proc. Int. Conf. on Computer Architecture, 2007.
   3.449 +
   3.450 +\bibitem{masterarbeit}
   3.451 + Nina Engelhardt,
   3.452 +\emph{Application of multimode high-level synthesis techniques to ASIP synthesis}, 
   3.453 +Masterarbeit, Cairn, IRISA, Juni 2010.
   3.454 +
   3.455 +\bibitem{cilk}
   3.456 +Keith H. Randall,
   3.457 +\emph{Cilk: Efficient Multithreaded Computing},
   3.458 +Thesis (Ph. D.), Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998. 
   3.459 +
   3.460 +\bibitem{starss}
   3.461 +J. Planas, R. Badia, E. Ayguadé, and J. Labarta,
   3.462 +\emph{Hierarchical Task-Based Programming With StarSs,}
   3.463 +Int. Journal of High Performance Computing Applications, vol. 23, no. 3, 2009.
   3.464 +
   3.465 +\bibitem{sequoia}
   3.466 +Kayvon Fatahalian, Daniel Reiter Horn, Timothy J. Knight, Larkhoon Leem, Mike Houston, Ji Young Park, Mattan Erez, Manman Ren, Alex Aiken, William J. Dally, and Pat Hanrahan,
   3.467 +\emph{Sequoia: programming the memory hierarchy},
   3.468 +in SC ’06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing, page 83, 2006.
   3.469 +
   3.470 +\end{thebibliography}
   3.471 +
   3.472 +\end{document}
   3.473 +
   3.474 +
   3.475 +
   3.476 +%\subsection{Introduction and Overview of Proposed Project}
   3.477 +
   3.478 +%  The experience of writing parallel code has proven much more difficult than writing sequential code, despite nearly 50 years of research on how to make parallel programming the same level of difficulty as sequential programming.  In addition, parallel code has proven more expensive than sequential code because it has been necessary to modify the source when it is run on a different machine, in order to get acceptable performance on the new hardware architecture.
   3.479 +
   3.480 +%However, despite these programming challenges, parallel processor chips have been forced into the mainstream because of the energy efficiency advantages of parallel hardware.  As a result, the need for high productivity languages for writing parallel code and the need for that code to be portable with good performance to future processor chips has reached a critical level.  Indeed, the economic cost will be immense if these productivity and portability challenges fail to be solved.
   3.481 +
   3.482 +%It is increasingly clear that a software-only approach may not be sufficient.  In particular, at the heart of a running parallel program is the synchronization activity and scheduling activity, which chooses tasks and assigns them to processing cores.  Synchronization and scheduling are the keys to parallel performance, and the software overhead of them is currently a major limitation on performance. Hardware that speeds up the synchronization and scheduling activities will have a multiplicative effect on improving overall parallel performance.
   3.483 +
   3.484 +%A recently discovered extensible hardware abstraction, called VMS, provides a convenient framework for introducing such hardware.  VMS replaces the traditional Thread model, and encapsulates the synchronization and scheduling activities inside the abstraction.  This separates them from the application, providing the necessary ingredient for portability.  It is currently being investigated as a platform upon which to implement high productivity parallel languages that have good portability across a wide range of hardware targets.
   3.485 +
   3.486 +%The encapsulation presents a good opportunity to introduce custom hardware to accelerate the synchronization and scheduling activities in a transparent way.  Thanks to the encapsulation, applications written to VMS-implemented languages will automatically inherit the benefits of the acceleration hardware without modification of the source code.
   3.487 +
   3.488 +%If successful, the benefits for science in general will be immense due to the ever-accelerating shift to doing scientific experiments on computer models.  Such experiments require parallel programming and parallel computation.  A successful outcome of the proposed project will advance VMS, which will in turn advance VMS's ability to support the solution of the productivity and portability challenges.  Solution of those challenges will benefit scientists in all disciplines that rely on computer modeling for their work.  Examples of scientific disciplines that will benefit include climate and weather, plate tectonics, new medicine discovery, high-energy particle physics, bio-engineering, chemistry, materials-science, and so on.  Improvements in these branches of science, will in turn benefit every day life for the average European citizen. 
   3.489 +
   3.490 +%\subsection{Background on Threads and VMS}
   3.491 +
   3.492 +%  Threads are currently the base hardware abstraction, sitting at the boundary between hardware and software.  But they were designed to abstract a single sequential processor and are ill suited for parallelism.  Not only are they difficult to program with, but their scheduler blocks the application from controlling which work is assigned to which computation core, losing affinity
   3.493 +%  and hurting performance.  The new hardware abstraction, called VMS, allows the
   3.494 +%  language to define both parallelism constructs and the scheduler, then plug
   3.495 +%  them in.
   3.496 +   
   3.497 +%  VMS has two benefits for productivity. First, sequential algorithms are used
   3.498 +%  to implement the parallelism constructs. This is enabled by a virtual time line that
   3.499 +%sequentializes events that are simultaneous in the application code.  Second, VMS 
   3.500 +%  simplifies debugging with a separate ``deterministic'' scheduling phase for debugging
   3.501 +%  basic functionality independently from concurrency.
   3.502 +%
   3.503 +%More importantly, VMS enables rapid exploration of radical parallelism constructs, which is the key to speeding up the search for easy-to-use parallel languages.  Several candidate languages that promise to simplify parallel programming and improve portability and maintainability of large projects have been proposed for VMS and are separately being pusued.  This is the true benefit VMS offers for increasing parallel programming productivity.
   3.504 +%
   3.505 +% VMS is essentially a definition of time-lines within a parallel program, plus a way to relate those program time-lines to each other.  The distinguishing feature of VMS is that it has no application-level semantics, but rather gains those from a plugin.  This contrasts to the other approaches to parallelism, which all provide {\em{language-level}} parallel constructs.  For example, Threads provides locks, semaphores, mutexes, condition variables, and so on, with which to control the ways that program time-lines may relate to each other.  In contrast, VMS requires that, first, a definition of such constructs be plugged in to it, then the application is written to those constructs.  Thus VMS is more primitive than Threads, or than any parallel language or execution model.  In fact, to show this, an implementation of Threads was built as a VMS plugin.
   3.506 +%
   3.507 +
   3.508 +

     4.1 Binary file 2__Other/fitweltweit/darstellung_des_vorhabens.pdf has changed

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/2__Other/fitweltweit/darstellung_des_vorhabens.tex	Tue May 14 12:03:39 2013 +0200
     5.3 @@ -0,0 +1,48 @@
     5.4 +\documentclass[a4paper,11pt]{article}
     5.5 +%
     5.6 +\usepackage{makeidx,geometry,amssymb,graphicx,calc,ifthen,fullpage}
     5.7 +%
     5.8 +\usepackage[utf8]{inputenc}
     5.9 +\usepackage[T1]{fontenc}
    5.10 +\usepackage[gen]{eurosym} 
    5.11 +\usepackage[german]{babel}
    5.12 +\usepackage{graphicx}
    5.13 +\usepackage{rotating}
    5.14 +
    5.15 +% correct bad hyphenation here
    5.16 +\hyphenation{op-tical net-works semi-conduc-tor takt-frequenz rechen-ge-schwin-dig-keit außer-euro-päischen pa-ral-lel pa-ral-lele pa-ral-le-len hard-ware-be-schleu-ni-ger}
    5.17 +
    5.18 +
    5.19 +\begin{document}
    5.20 +\bibliographystyle{plain}
    5.21 +%
    5.22 +
    5.23 +\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme}
    5.24 +\author{Nina Engelhardt}
    5.25 +
    5.26 +\maketitle             
    5.27 +%
    5.28 +\tableofcontents
    5.29 +
    5.30 +%\newpage
    5.31 +
    5.32 +\abstract{
    5.33 +Die Supercomputer von Gestern sind die eingebetteten Systeme von Morgen. Massive Anzahlen von Prozessorkernen, wie man sie einst nur in Rechenzentren fand, halten bereits Einzug in Autos und Handys.
    5.34 +Damit weitet sich das altbekannte Problem aus, dass es viel schwerer ist, Programme zu schreiben, die viele Kerne gleichzeitig effizient benutzen können, als Programme für nur einen Kern zu schreiben.
    5.35 +
    5.36 +Ein vielversprechender Lösungsansatz sind dömänenspezifische parallele Programmiersprachen. Die Programmierung gelingt schneller und fehlerfreier, wenn die Konzepte der Programmiersprache denen der Anwendung angepasst sind. Allerdings haben spezifischere Programmiersprachen eine kleinere Nutzerbasis, sodass sich die Entwicklungskosten für die Sprache und die dazugehörigen Tools schnell nicht mehr rentieren. 
    5.37 +Das VMS-Framework, das Subjekt meines Dissertationsvorhabens ist, erleichtert die Entwicklung von Runtimes für parallele Programmiermodelle, indem es grundlegende Funktionalitäten wie Synchronisation übernimmt. Um ein bestimmtes Modell zu unterstützen, muss der Entwickler nur noch einige Funktionen in Form eines Plugins hinzufügen. Diese Pluginfunktionen sind einfach zu schreiben, da sie die üblichen strengen Auflagen wie Thread-safety oder Reentrancy nicht erfüllen müssen.
    5.38 +
    5.39 +
    5.40 +
    5.41 +I have been evaluating the performance of the current VMS implementation. It was designed for cache-coherent shared memory machines not exceeding a dozen cores and performs well on these machines, offering comparable performance to the default runtime libraries for programming models such as OmpSs[2]. However, some of the assumptions in the VMS abstractions are unsuited to larger and/or distributed systems.
    5.42 +}
    5.43 +
    5.44 +\section{Beschreibung des Forschungsgegenstands}
    5.45 +
    5.46 +Um effizient auf Multicoresystemen laufen zu können, müssen Programme explizit parallel geschrieben werden. Die parallele Programmierung hat sich im Laufe der Jahre jedoch als ungleich komplizierter als die sequentielle Programmierung erwiesen, sodass eine Reihe von parallelen Programmiermodellen und dazugehörigen -sprachen entwickelt wurde, die den parallelen Entwurf vereinfachen sollen. Da sich verschiedene Modelle unterschiedlich gut für diverse Programmklassen eignen, ist es wichtig, viele davon zu unterstützen. Heutige Betriebssysteme benutzen jedoch ein einziges Modell als unterste Abstraktionsebene: das Thread-Modell. Alle anderen Programmiermodelle müssen daher auf Threads basierend implementiert werden, in Form einer Runtime Library.
    5.47 +
    5.48 +\section{Bereits ausgeführte Arbeiten}
    5.49 +
    5.50 +\end{document}
    5.51 +

     6.1 Binary file 2__Other/jsps_proposal/deckblatt.pdf has changed

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/2__Other/jsps_proposal/deckblatt.tex	Tue May 14 12:03:39 2013 +0200
     7.3 @@ -0,0 +1,42 @@
     7.4 +\documentclass[a4paper,11pt]{dinbrief} 
     7.5 +\usepackage{german} 
     7.6 +%\usepackage[T1]{fontenc} 
     7.7 +\usepackage[utf8]{inputenc} 
     7.8 +\begin{document} 
     7.9 +\subject{\textbf{Betreff: JSPS Postdoctoral Fellowship Program (short term)}} 
    7.10 +\backaddress{Nina Engelhardt · TU Berlin EN 12 · Einsteinufer 17, 10587 Berlin} 
    7.11 +\signature{Nina Engelhardt} 
    7.12 +\Datum{\today} 
    7.13 +\address{M.Sc. Nina Engelhardt\\
    7.14 +EN 12/Raum EN 647\\
    7.15 +TU Berlin - Fakultät IV - Elektrotechnik und Informatik\\
    7.16 +Fachgebiet Architektur Eingebetteter Systeme (AES)\\
    7.17 +Einsteinufer 17, 10587 Berlin, Germany} 
    7.18 +\begin{letter} 
    7.19 +{An: \\ 
    7.20 +DAAD\\
    7.21 +Referat 424\\
    7.22 +Stefanie Hellweg\\
    7.23 +Postfach 20 04 04\\
    7.24 +53134 Bonn} 
    7.25 +% Dies ist übrigens ein Befehl: \begin{letter}{Adresse} 
    7.26 +\opening{Sehr geehrte Frau Hellweg,}
    7.27 +
    7.28 +Hiermit möchte ich mich auf das JSPS Postdoctoral Fellowship Program (short term) bewerben.
    7.29 +Es handelt sich um ein Projekt aus dem Fach Informatik.
    7.30 +Anbei finden Sie folgende Bewerbungsunterlagen (zweifach):
    7.31 +\begin{itemize}
    7.32 +\item Antragsformular
    7.33 +\item Lebenslauf
    7.34 +\item Empfehlungsschreiben des Doktorvaters (Prof. B. Juurlink, TU Berlin)
    7.35 +\item Betreuungszusage des Gastgebers (Prof. S. Matsuoka, Tokyo Institute of Technology)
    7.36 +\item Kopie des Masterzeugnisses mit Übersetzung
    7.37 +\item Bestätigung der Fakultät über die Annahme als Doktorand mit voraussichtlichem Zeitpunkt des Abschlusses und Übersetzung
    7.38 +\item Sprachzeugnis Englisch (TOEIC)
    7.39 +\item Teilnahmebestätigung Japanischkurs und Übersetzung.
    7.40 +\end{itemize}
    7.41 +
    7.42 +\closing{Mit freundlichen Grüßen,} 
    7.43 +
    7.44 +\end{letter} 
    7.45 +\end{document} 

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/2__Other/jsps_proposal/past research	Tue May 14 12:03:39 2013 +0200
     8.3 @@ -0,0 +1,14 @@
     8.4 +16. Subject and Achievement of Past Research 
     8.5 +
     8.6 +I have been involved in research in the domain of computer architecture since my entrance into ENS Cachan, a higher education institution dedicated to training academics.
     8.7 +
     8.8 +My first research efforts, for my bachelor's degree, were undertaken in the computer architecture research group of Prof. André Seznec at IRISA Rennes. There, I examined whether the measurements from on-chip temperature sensors included in modern CPUs could be used to determine the approximate power distribution on the chip. This turned out to be difficult, as even in an idealized model sensors were unable to reliably distinguish separate areas with different power densities.
     8.9 +
    8.10 +Following this, I worked on parallelizing the temperature simulator used for the previous research. This work was carried out in the High Performance Computing group at Zuse Institut Berlin. I implemented and compared parallel versions in several programming models. From this I took an appreciation of the advantages, inconvenients and trade-offs in development of the different models, in particular OpenMP, CUDA, and threads.
    8.11 +
    8.12 +Having explored software options for improving performance, I chose a Master's thesis project that would give me a complementary perspective. In the reconfigurable computing group at IRISA Rennes, I developed a high-level synthesis tool that, given the description of an instruction set, can generate an optimized datapath for implementation as an application-specific instruction-set processor softcore in an FPGA.
    8.13 +
    8.14 +I continued in this direction in my subsequent internship at Potsdam University, where I implemented an LLVM compiler analysis pass that finds frequent computation patterns suitable for implementation as an application-specific instruction in an extensible or reconfigurable processor.
    8.15 +
    8.16 +In my PhD project in the embedded systems architecture group at TU Berlin under the direction of Prof. Ben Juurlink, I pursue my investigation of the frontier between hardware and software. In my first year I examined the VMS runtime framework and its theoretical foundations. I formalized the underlying principles and instrumented the VMS code to analyze its performance. This work is presented in a paper currently under review at the EuroPar 2013 conference.
    8.17 +Since then, I have implemented runtimes for several parallel programming models using the VMS framework, notably Cilk and OmpSs. Using the previously developed instrumentation, I analyzed the performance commonalities and different requirements of the various models, with a view to developing a set of hardware accelerators that can support many different runtimes.

     9.1 --- a/2__Other/jsps_proposal/research plan	Mon Apr 15 12:38:12 2013 +0200
     9.2 +++ b/2__Other/jsps_proposal/research plan	Tue May 14 12:03:39 2013 +0200
     9.3 @@ -1,34 +1,45 @@
     9.4  15. Research Plan in Japan
     9.5  a.  Present research related to research plan
     9.6  
     9.7 -I am currently working on a PhD in the domain of runtimes for parallel programming models. The object of my research is to improve the VMS runtime framework. VMS addresses the productivity gap between sequential and parallel programming. The difficulty of parallel programming is reduced when the programming model offers high-level concepts that closely match the application's concepts. However, the more specialized a programming model is, the less users it has, and so less effort can be spent on developing the model due to diminishing returns (it becomes useless when the time to write the runtime is larger than the extra time it takes to write the applications in a less suitable model).
     9.8 +I am currently working on a PhD in the domain of runtimes for parallel programming models. The object of my research is to improve the VMS[1] runtime framework. VMS addresses the productivity gap between sequential and parallel programming. The difficulty of parallel programming is reduced when the programming model offers high-level concepts that closely match the application's concepts. However, the more specialized a programming model is, the less users it has, and so less effort can be spent on developing the model due to diminishing returns (it becomes useless when the time to write the runtime is larger than the extra time it takes to write the applications in a less suitable model).
     9.9  
    9.10  VMS brings the simplicity of sequential programming to the development of parallel runtimes by providing a base layer that takes charge of the most difficult aspect, synchronization. Building on this, the runtime writer only needs to provide specific methods in the form of a plugin to support a certain programming model. These plugin methods are easy to write because they need to be neither thread-safe nor reentrant.
    9.11  
    9.12 -I have been evaluating the performance of the current VMS implementation. It was designed for cache-coherent shared memory machines not exceeding a dozen cores and performs well on these machines, offering comparable performance to the default runtime libraries for models such as OmpSs. However, some of the assumptions in the VMS abstractions are unsuited to larger and/or distributed systems. Preparing for the research to take place during the exchange period, additional benchmarks using different combinations of features will be developed to evaluate the runtime's performance, and establish a baseline to compare improvements to. Next, a distributed version of VMS will be developed. The goal is to have a first working implementation ready that will be improved using the combined knowledge of distributed systems at TokyoTech and parallel runtimes at TU Berlin.
    9.13 +I have been evaluating the performance of the current VMS implementation. It was designed for cache-coherent shared memory machines not exceeding a dozen cores and performs well on these machines, offering comparable performance to the default runtime libraries for programming models such as OmpSs[2]. However, some of the assumptions in the VMS abstractions are unsuited to larger and/or distributed systems. I have started development of a distributed version of VMS. The goal is to have a first working implementation ready that will be improved during the research stay using the combined knowledge of distributed systems at TokyoTech and parallel runtimes at TU Berlin.
    9.14 +
    9.15 +Concurrently, additional benchmarks using different combinations of features will be developed to evaluate the runtime's performance, and establish a baseline to compare improvements to.
    9.16  
    9.17  b.  Purpose of proposed research
    9.18  
    9.19 -Often, a significant part of the runtime overhead is spent on ensuring compatibility with a wide range of features of the programming model, or even with other programming models, even though most of these features will not be used in this particular application. If the runtime could know if these features were needed or not, it would be possible to reduce overhead by eliding the unnecessary functionalities.
    9.20 +The embedded systems of tomorrow are increasingly resembling the high-performance systems of today, featuring computationally intense parallel applications and complex arrangements of large numbers of cores. In both contexts, the goal is to extract maximal performance with minimal energy usage from these systems. Domain Specific Languages are generally recognized as the most promising tool to efficiently achieve this end. However, DSLs are themselves a programming challenge, which we wish to solve. This project aims to harness the combined experience and resources from the TU Berlin Embedded Systems Architecture lab and TokyoTech's Matsuoka lab to solve critical performance and productivity issues that affect parallel and distributed application development.
    9.21  
    9.22 -The proposed research will enable building modularized runtimes that can load a reduced feature set based on the developer's indication of which features they wish to use. A further aim is to allow development of  hardware support that can be flexibly used by replacing selected runtime models with ones taking advantage of special-purpose hardware when it is available.
    9.23  
    9.24  c.  Proposed plan
    9.25  
    9.26 +In this cooperation, we wish to bring the VMS approach from TU Berlin, which has proven successful for consumer applications on commodity hardware, to specialty systems such as the Tsubame 2.0 supercomputer from TokyoTech. Our devised plan takes extensive advantage of the complementary expertise of both labs, combining the strengths in parallel and distributed application development of TokyoTech with the knowledge of low-level hardware and runtime detail from TU Berlin.
    9.27 +
    9.28  Main tasks during the research stay:
    9.29  	- Define a set of basic abstractions suited to distributed systems that enable plugins for many different programming models. These abstractions should support several goals:
    9.30 -		1. Generality: allow implementation of different types of programming models (thread-based, task-based, dataflow, ...)
    9.31 -		2. Simplicity: present only very few basic abstractions that can be quickly understood
    9.32 -		3. Modularity: encourage separation of the different runtime functionalities. Modularity enables two approaches to boost performance. One is to selectively load only the necessary functionalities for a specific application, eschewing overhead due to preparing features that are never actually used. The other is to make it easier to integrate specialized hardware that can support specific runtime functions.
    9.33 +		1. Generality: allow implementation of different types of programming models (thread-based, task-based, dataflow, ...). This way, all programming models based on a common foundation will profit from improvements to the efficiency of the base layer. Sharing a basic structure will also increase compatibility between different models, removing an important barrier for Hybrid Programming, an approach that is gaining popularity rapidly.
    9.34 +		2. Simplicity: present only very few basic abstractions that can be quickly understood. This increases productivity of the runtime developers, makes it easier to implement the abstractions for different architectures, and reduces occasions for mistakes.
    9.35 +		3. Modularity: encourage separation of the different runtime functionalities. Modularity enables two approaches to boost performance. 
    9.36 +			One is to selectively load only the necessary functionalities for a specific application. Often, a significant part of the runtime overhead is spent on ensuring compatibility with a wide range of features of the programming model, or even with other programming models, even though most of these features will not be used in this particular application. If the runtime could know if these features were needed or not, it would be possible to reduce overhead by eliding the unnecessary functionalities.
    9.37 +			The other is to make it easier to integrate specialized hardware that accelerates runtime functions. As a solution to ever larger amounts of transistors available but ever tighter energy budgets, future architectures will include numerous specialized units that can be selectively activated when an application can profit from them. If the runtime is highly modular, only a small part of the runtime needs to be replaced with a variant that takes advantage of special-purpose hardware.
    9.38  
    9.39  Possibly offer simplified abstractions for common models (thread- and task-based programming models in particular).
    9.40  
    9.41 -	- Develop a modularized plugin for the OmpSs programming model using the new abstractions. This programming model will serve as case study to evaluate the suitability of the abstractions both from a productivity and from a performance perspective.
    9.42 +	- Develop a modularized plugin for the OmpSs[2] and MPI[3] programming models using the new abstractions. These programming models will serve as case study to evaluate the suitability of the abstractions both from a productivity and from a performance perspective. Simultaneously, this will allow us to investigate whether certain scalability challenges in dynamic dependency tracking are solvable or inherent to the problem.
    9.43 +
    9.44 +	- Apply the improved runtimes to selected scientific and engineering applications developed at TokyoTech. In particular, we wish to take advantage of more fine-grained parallelism in the Fast Multipole Method, a calculation which serves in many physics and chemistry simulations such as of molecular dynamics and plasma physics. Additionally, we aim to port common kernels such as LU/Cholesky  decomposition, iterative methods, and structure/unstructured grid.
    9.45  
    9.46  d.  Expected results and impacts
    9.47  
    9.48  The expected immediate benefit is to have a runtime whose overhead is proportional to the featureset actually used by the application. This allows the usage of powerful programming models for a larger group of applications.
    9.49  
    9.50 -This work will also enable important future research both at TokyoTech and TU Berlin. Future plans are to use the improved VMS platform to develop runtimes that can automatically adjust task size to different systems' capabilities (number of cores, computation vs. communication speed, etc). It will also serve to develop a set of hardware accelerators for schedulers.
    9.51 +Through the cooperation, Matsuoka lab at TokyoTech and more generally the Japanese HPC community will obtain more efficient runtimes and hands-on experience in their use, while the AES lab from TU Berlin will gain access to important real-world applications and resources beyond consumer scale.
    9.52  
    9.53 -The embedded systems of tomorrow are increasingly resembling the high-performance systems of today, and both domains share the drive to extract maximum performance from the systems. Combining the experience and techniques from both domains is profitable for both sides.
    9.54 +Beyond the direct impact, this work will also lay the foundation for future collaboration between TokyoTech and TU Berlin. Using the distributed VMS platform, we plan to investigate runtimes that can automatically adjust task size to different systems' capabilities (number of cores, computation vs. communication speed, etc). It will also serve as basis to develop a set of hardware accelerators for schedulers.
    9.55 +
    9.56 +[1] Halle, S., Cohen, A.: A mutable hardware abstraction to replace threads. 24th Intl. Workshop on Languages and Compilers for Parallel Languages (2011)
    9.57 +[2] Duran, A., Ayguade, E., Badia, R. M., Labarta, J., Martinell, L., Martorell, X., & Planas, J. (2011). Ompss: a proposal for programming heterogeneous multi-core architectures. Parallel Processing Letters, 21(02), 173-193.
    9.58 +[3] Gropp, W., Lusk, E. L., & Skjellum, A. (1999). Using MPI: Portable Parallel Programming with the Message Passing Interface (Vol. 1). MIT press.

    10.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    10.2 +++ b/2__Other/jsps_proposal/skb-ja	Tue May 14 12:03:39 2013 +0200
    10.3 @@ -0,0 +1,30 @@
    10.4 +TU Berlin - FR 4-6 - Franklinstraße 28/29 - Raum 1504 - D-10587 Berlin
    10.5 +
    10.6 +Sprach- und Kulturbörse
    10.7 +
    10.8 +
    10.9 +
   10.10 +
   10.11 +Date: 12/07/12
   10.12 +
   10.13 +
   10.14 +
   10.15 +
   10.16 +CERTIFICATE
   10.17 +
   10.18 +
   10.19 +We hereby confirm that Ms/Mr Nina Engelhardt has successfully 
   10.20 +completed a language class at the Sprach- und Kulturbörse 
   10.21 +of TU Berlin from 03/05/12 to 12/07/12.
   10.22 +
   10.23 +
   10.24 +Language: Japanese
   10.25 +
   10.26 +Level B1.3
   10.27 +
   10.28 +Hours of instruction: 40h
   10.29 +
   10.30 +
   10.31 +Sprach- und Kulturbörse of TU
   10.32 +
   10.33 +Tanakai Wataru

    11.1 Binary file 2__Other/jsps_proposal/skb-ja.odt has changed

    12.1 Binary file 2__Other/jsps_proposal/transcript.odt has changed

    13.1 Binary file 2__Other/year1report/report.pdf has changed

    14.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    14.2 +++ b/2__Other/year1report/report.tex	Tue May 14 12:03:39 2013 +0200
    14.3 @@ -0,0 +1,115 @@
    14.4 +
    14.5 +\documentclass[12pt,a4paper]{article}
    14.6 +
    14.7 +\usepackage[german]{babel}
    14.8 +\usepackage{fullpage}
    14.9 +\usepackage[utf8]{inputenc}
   14.10 +
   14.11 +\begin{document}
   14.12 +\setlength{\parindent}{0px} \setlength{\parskip}{1 em}
   14.13 +
   14.14 +\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme\\Zwischenbericht zum 1. Jahr}
   14.15 +\author{Nina Engelhardt}
   14.16 +\date{\today}
   14.17 +\maketitle
   14.18 +
   14.19 +
   14.20 +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 Virtualzed Master-Slave System, kurz VMS, ein Framework dass es ermöglicht, Laufzeitumgebungen für verschiedenste parallele Programmiermodelle mit nur wenig Aufwand zu implementieren.
   14.21 +
   14.22 +\section{Ausgeführte Arbeiten}
   14.23 +
   14.24 +In den ersten 6 Monaten habe ich wie geplant das VMS-System analysiert. VMS umfasst die Grundlegende Struktur, die allen Laufzeitumgebungen (\emph{Runtimes}) gemein ist: sie beinhaltet den Wechsel zwischen Programm- und Umgebungscode und die Möglichkeit, eine zeitliche Ordnung zwischen zwei Codepunkten in zwei virtuellen Prozessoren zu garantieren (semantikfreie Synchronisation). Auf dieser Basis 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 \emph{Assigner}, der entscheidet, welche Aufgaben als nächstes bearbeitet werden, und einen \emph{Request Handler}, der die Implementation der parallelen Konstrukte liefert.
   14.25 +
   14.26 +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. Die von VMS gelieferten grundlegenden Elemente sind sehr nah an der existierenden Hardware, deshalb sind die meisten häufigen Aufgaben bereits 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.
   14.27 +Beschleuniger für Pluginfunktionen haben deutlich mehr Spielraum, besonders für Sprachen mit komplexen, hardwarefernen Konstrukten. Diese Sprachen sind von großer Bedeutung, 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 OmpSs anvisiert werden, da sie im Fachgebiet Architektur Eingebetteter Systeme bereits verwendet wird.
   14.28 +
   14.29 +VMS ist die praktische Ausformulierung eines Modells des Parallelismus, die von Dr. Sean Halle unter dem Namen ``Holistic Model of Parallel Computation''\cite{bib:holistic} vorgeschlagen wurde. Dieses Modell isoliert die schedulingrelevanten Teile eines Programms und legt das Augenmerk besonders auf die Effekte von Scheduling Decisions auf die Performance.
   14.30 +
   14.31 +Während meiner Analyse von VMS stieß ich auf mehrere Problemstellen in der Theorie, und habe diese in Zusammenarbeit mit Dr. Halle gelöst. Insbesondere habe ich das Modell um das Konzept der Schichten erweitert, das dem Umstand Rechnung trägt, dass in einem System meistens mehrere hierarchisch untergeordnete Scheduler existieren. So werden die Arbeitseinheiten, über die die Laufzeitumgebung als Eins entscheidet, möglicherweise vom Betriebssystem noch einmal unterbrochen und verteilt, spätestens aber vom Prozessor in kleinere Einheiten -- Assemblerbefehle -- zerteilt, und auf unterschiedliche Funktionseinheiten aufgeteilt. Wenn man an Out-of-order Prozessoren denkt, wird deutlich, das auch dies parallele Aufgabenverteilung ist. Das Holistische Modell ist auch auf diese anwendbar. Zur Zeit arbeiten wir an einem Zeitschriftenartikel der das Holistische Modell detailliert darlegt. 
   14.32 +
   14.33 +Zu den Errungenschaften des Holistischen Modells gehören auch zwei grafische Darstellungen, die \emph{Unit Constraint Collection} und der \emph{Scheduling Consequence Graph}, deren Ziel es ist, die Gründe der (guten oder schlechten) Performance eines parallelen Programms ersichtlich zu machen. Die Unit Constraint Collection (kurz UCC) zeigt die Arbeitseinheiten (\emph{units}) die im Programm definiert werden, und die Randbedingungen (\emph{constraints}) ihrer Ausfürbarkeit, die vom Programm selbst ausgehen. Der Consequence Graph (CG) repräsentiert eine realisierte Ausführung des Programms und zeigt die räumliche und zeitliche Platzierung der Arbeitseinheiten, die der Scheduler gewählt hat, sowie die unterschiedlichen Randbedingungen, die diese Wahl eingeschränkt haben. Diese können vom Programm selbst stammen, sich aus Ressourcenbegrenzungen ergeben, oder durch Beschränkungen der Laufzeitumgebung entstehen.
   14.34 +
   14.35 +Nachdem ich bereits für die Analyse des Laufzeitverhaltens Messschnittstellen in VMS eingefügt hatte, habe ich diese Infrastruktur wiederverwendet, um aus den gewonnenen Daten die räumliche und zeitliche Platzierung der Arbeitseinheiten für den Consequence Graph abzuleiten. Zusätzlich habe ich ein VMS-Plugin, das synchrones Senden und Empfangen von Nachrichten zwischen Threads in einem Programm unterstützt (synchronous send-receive, kurz SSR), modifiziert, um die Constraints zu erfassen, die für die Konstruktion der UCC und des CG notwendig sind. Schließlich erstellte ich ein Programm, das diese Aufzeichnungen entgegennehmen und UCC \& CG darstellen kann.
   14.36 +
   14.37 +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 vorherigen, statistischen Analysen 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) zur Visualisierung hinzugefügt hatte, wurden auch weniger offensichtliche 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.
   14.38 +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 \cite{bib:perftune}, den ich voraussichtlich im August für die PPoPP-2013 Konferenz einreichen werde.
   14.39 +
   14.40 +%\newpage
   14.41 +
   14.42 +\section{Zukünftige Aktivitäten}
   14.43 +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.
   14.44 +Aufgrund der gewonnenen Erkentnisse verändert sich mein Plan wie folgt:
   14.45 +
   14.46 +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. 
   14.47 +Dabei wird mir das BeeFarm-Multiprozessorsystem\cite{bib:beefarm} als Grundlage dienen, das am Fachgebiet zur Verfügung steht. Dieses System ist auf MIPS Prozessoren basiert, die eine Coprozessorschnittstelle enthalten, über die zusätzliche Hardwarekomponenten einfach integriert werden können. 
   14.48 +
   14.49 +Der erste Schritt wird sein, VMS und die darauf basierten Laufzeitumgebungen (insbesondere OmpSs) auf die BeeFarm-Platform zu portieren. Diese reine Software-Im\-ple\-men\-tie\-rung wird die Vergleichsbasis, gegenüber der der Effekt der unterschiedlichen Hard\-ware\-be\-schleu\-ni\-ger\-kon\-fi\-gu\-ra\-tio\-nen gemessen werden kann.
   14.50 +
   14.51 +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.
   14.52 +
   14.53 +OmpSs hat die komplizierteste Laufzeitaktivität unter den verfügbaren Plugins, daher werde ich hier zuerst ansetzen. Wie erwartet besteht der Großteil der OmpSs-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 \cite{bib:routing} bis zu Graph-basierten Algorithmen \cite{bib:graph}. 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.
   14.54 +
   14.55 +Zudem stellte sich auch heraus, dass das Allozieren von Speicher über \emph{malloc} relativ viel Zeit in Anspruch nimmt. Da diese Funktion in sehr vielen Plugins enthalten ist, 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.
   14.56 +
   14.57 +Neben der Auswahl ist auch die Anzahl und Platzierung der Beschleuniger abzuwägen.
   14.58 +Im Falle von OmpSs gibt es zwei zeitintensive Abläufe mit sehr unterschiedlicher Verteilbarkeit: Die Erstellung von neuen Tasks ist strikt sequentiell definiert, ausgehend von 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. Aus diesem Grund erscheint es sinnvoll, hierfür einen speziellen Coprozessor zu erstellen, der nur zu einem designierten ``Master-Kern'' hinzugefügt wird.
   14.59 +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, welche wartenden Tasks durch diese Freigaben laufbereit werden. Unter den laufbereiten Tasks wählt er einen aus und startet ihn auf dem freigewordenen Kern. Hier wäre Hardwarebeschleunigung dringend notwendig, da dieser Ablauf der rechenintensivste in der OmpSs-Laufzeitumgebung 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. Zudem bliebe dieser ungenutzt während der gesamten Rechenzeit, die im Programm verbracht wird (und dies ist die ``nützliche'' Zeit, und daher idealerweise 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.
   14.60 +
   14.61 +Die übrigen Schritte bleiben unverändert. Die OmpSs-Laufzeitumgebung muss anschließend so angepasst werden, dass sie von den neuen Coprozessoren gebrauch machen kann. Anhand mehrerer bereits in OmpSs 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 OmpSs-spezifische Hardwarescheduler Nexus++ herangezogen werden, der hier im Fachgebiet entwickelt wurde, und sämtliche im vorigen Absatz beschriebenen Abläufe übernimmt.
   14.62 +
   14.63 +Zusammengefasst ergibt sich daraus der folgende Zeitplan:
   14.64 +
   14.65 +\begin{table}[h]
   14.66 +\begin{tabular}{|l|c|}
   14.67 +\hline
   14.68 +VMS und OmpSs-Plugin auf BeeFarm portieren & 3 Monate\\
   14.69 +\hline
   14.70 +Hardwarebeschleuniger implementieren & 6 Monate\\
   14.71 +\hline
   14.72 +Varianten erstellen & 3 Monate\\
   14.73 +\hline
   14.74 +Integration in VMS-OmpSs & 3 Monate\\
   14.75 +\hline
   14.76 +Test, Performanceevaluation, Optimierung & 3 Monate\\
   14.77 +\hline
   14.78 +Niederschrift & 6 Monate\\
   14.79 +\hline
   14.80 +\end{tabular}
   14.81 +\end{table}
   14.82 +
   14.83 +\begin{thebibliography}{9}
   14.84 +\bibitem{bib:perftune} Nina Engelhardt, Sean Halle, Ben Juurlink; \emph{Integrated Performance Tuning Using Semantic Information Collected by Instrumenting the Language Runtime}; in progress
   14.85 +\bibitem{bib:holistic} Sean Halle, Albert Cohen; \emph{Support of Collective Effort Towards Performance Portability}; Proceedings of 3rd USENIX Workshop on Hot Topics in Parallelism, May 2011
   14.86 +\bibitem{bib:beefarm} Nehir Sonmez, Oriol Arcas, Gokhan Sayilar, Osman S. Unsal, Adrián Cristal, Ibrahim Hur, Satnam Singh, and Mateo Valero; \emph{From plasma to beefarm: design experience of an FPGA-based multicore prototype}; Proceedings of the 7th international conference on Reconfigurable computing: architectures, tools and applications (ARC'11), 2011
   14.87 +\bibitem{bib:routing} Lorenzo De Carli, Yi Pan, Amit Kumar, Cristian Estan, Karthikeyan Sankaralingam; \emph{PLUG: Flexible Lookup Modules for Rapid Deployment of New Protocols in High-speed Routers}; SIGCOMM, August 2009
   14.88 +\bibitem{bib:graph} Betkaoui, B., Thomas, D.B., Luk, W., Przulj, N.; \emph{A framework for FPGA acceleration of large graph problems: Graphlet counting case study}; International Conference on Field-Programmable Technology (FPT), 2011 
   14.89 +\end{thebibliography}
   14.90 +
   14.91 +\end{document}
   14.92 +
   14.93 +
   14.94 +
   14.95 +Drei Möglichkeiten der Parallelisierung werde ich bei der Erstellung der Hardwarebeschleuniger ins Auge fassen:
   14.96 +\begin{enumerate}
   14.97 +\item Eigenständige Abläufe können getrennt und parallel ausgeführt werden
   14.98 +\item Innerhalb dieser Abläufe kann durch Pipelining der Durchsatz gesteigert werden
   14.99 +\item Mehrere Instanzen eines Ablaufs können parallel arbeiten.
  14.100 +\end{enumerate}
  14.101 +
  14.102 +-- what I did
  14.103 +-get into vms code, instrument it
  14.104 +-find vague places in theory, fix them
  14.105 +->find slowdowns in vms, lead to new version
  14.106 +->notice instrumentation + theory makes good perf tuning tool, write paper about that
  14.107 +->write paper about theory
  14.108 +
  14.109 +-- how it compares to projected plan
  14.110 +-first 6 months match
  14.111 +-then more theory than concrete solutions
  14.112 +->revealed 1 master probably not best solution
  14.113 +->revealed additional levels of performance issues not originally considered
  14.114 +
  14.115 +-- what I'm going to do next
  14.116 +-build hardware, but instead of putting accelerators only on 1 master core, experiment with how often to replicate accelerators
  14.117 +-assemblage of lm32 cores, each w/ non-coherent cache
  14.118 +-OmpSs? w/ message passing for in/out

    15.1 Binary file 2__Other/year2report/report.pdf has changed

    16.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    16.2 +++ b/2__Other/year2report/report.tex	Tue May 14 12:03:39 2013 +0200
    16.3 @@ -0,0 +1,21 @@
    16.4 +\documentclass[12pt,a4paper]{article}
    16.5 +
    16.6 +\usepackage[german]{babel}
    16.7 +\usepackage{fullpage}
    16.8 +\usepackage[utf8]{inputenc}
    16.9 +
   16.10 +\begin{document}
   16.11 +\setlength{\parindent}{0px} \setlength{\parskip}{1 em}
   16.12 +
   16.13 +\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme\\Zwischenbericht zum 1. Jahr}
   16.14 +\author{Nina Engelhardt}
   16.15 +\date{\today}
   16.16 +\maketitle
   16.17 +
   16.18 +
   16.19 +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 Virtualzed Master-Slave System, kurz VMS, ein Framework dass es ermöglicht, Laufzeitumgebungen für verschiedenste parallele Programmiermodelle mit nur wenig Aufwand zu implementieren.
   16.20 +
   16.21 +\section{Ausgeführte Arbeiten}
   16.22 +
   16.23 +
   16.24 +\end{document}