
nengel@8: 
nengel@8: 
nengel@8: \documentclass[a4paper,11pt]{article}
nengel@8: %
nengel@8: \usepackage{makeidx,geometry,amssymb,graphicx,calc,ifthen,fullpage}
nengel@8: %
nengel@8: \usepackage[utf8]{inputenc}
nengel@8: \usepackage[T1]{fontenc}
nengel@8: \usepackage[gen]{eurosym} 
nengel@8: \usepackage[german]{babel}
nengel@8: \usepackage{graphicx}
nengel@8: \usepackage{rotating}
nengel@8: 
nengel@8: % correct bad hyphenation here
nengel@8: \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}
nengel@8: 
nengel@8: 
nengel@8: \begin{document}
nengel@8: \bibliographystyle{plain}
nengel@8: %
nengel@8: 
nengel@8: \title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme}
nengel@8: \author{Nina Engelhardt}
nengel@8: 
nengel@8: \maketitle             
nengel@8: %
nengel@8: \tableofcontents
nengel@8: 
nengel@8: %\newpage
nengel@8: 
nengel@8: \section{Allgemeinverständliche Zusammenfassung} %Short summary of proposal
nengel@8: %Allgemeinverständliche Zusammenfassung mit kurzer Charakterisierung der Ziele und Methoden (nicht mehr als 15 Schreibmaschinenzeilen).
nengel@8: %Short summary accessible to the general public with short characterisation of goals and methods (15 lines max.)
nengel@8: 
nengel@8: %Summary for Laymen
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 
nengel@8: 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. 
nengel@8: 
nengel@8: %Seit 2005 werden auch im Heimcomputerbereich Multiprozessorsysteme verwendet.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: \section{Beschreibung des Forschungsgegenstandes und Vorarbeiten}
nengel@8: %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.
nengel@8: %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.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.] }
nengel@8: 
nengel@8: \subsection{Historischer Kontext}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: \subsection{Threads und parallele Programmiermodelle}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 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.
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: %[Needs comparison to rival models either here or next]
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: %\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.}
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: %[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..]
nengel@8: 
nengel@8: %If I understood correctly, Barrelfish 
nengel@8: 
nengel@8: \subsection{Das Virtualized Master-Slave Modell}
nengel@8: 
nengel@8: %****Changes here*****
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: \begin{figure}[h!]
nengel@8:   \centering
nengel@8:     \includegraphics[width=0.25\textwidth]{vms-components.pdf}
nengel@8:       \caption{Interaktion der Bestandteile von VMS.  Quelle: S.Halle \cite{VMS}}
nengel@8: \end{figure}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: %\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.}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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!}
nengel@8: 
nengel@8: \begin{figure}[bht]
nengel@8:   \centering
nengel@8:     \includegraphics[width=0.99\textwidth]{vms-ecosystem.pdf}
nengel@8:       \caption{VMS-Bestandteile für mehrere Programmiersprachen und mehrere Hardwareklassen. Quelle: S.Halle \cite{VMS}}
nengel@8: \end{figure}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: %[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 ; ) ]
nengel@8: 
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\emph{[The VMS-core is a low-level hardware abstraction, which contains the basic functions necessary for the plugin, such as task switching.]}
nengel@8: 
nengel@8: 
nengel@8: \subsection{Kern der Arbeit}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: % und diesen so mit den ausführenden Kernen zu verbinden, dass er diese effizient Kontrollieren kann. Dies verringert den Synchronisations-Overhead.
nengel@8: 
nengel@8: %\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.}
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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.}
nengel@8: 
nengel@8: Die Herausforderung meiner Arbeit ist, eine generelle und erweiterbare Architektur zu entwickeln, die eine Vielzahl von Programmiermodellen effizient unterstützt.
nengel@8: 
nengel@8: %\emph{The challenge of this project is to build a general and extensible architecture that can support a multitude of programming models efficiently.}
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: %\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.}
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: \label{sec:arbeitsschritte}
nengel@8: Folgende Arbeitsschritte sind vonnöten:
nengel@8: 
nengel@8: ~
nengel@8: 
nengel@8: \noindent\textbf{Phase 1: Hardwareentwicklung}
nengel@8: \begin{enumerate}
nengel@8: \item{\textbf{Kernfunktionen identifizieren}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\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).]}
nengel@8: }
nengel@8: \item{\textbf{Analyse des Laufzeitverhaltens}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\emph{[Instrument VMS code for profiling to measure the impact of each of these functions.]}
nengel@8: }
nengel@8: \item{\textbf{Design Space Exploration}
nengel@8: 
nengel@8: Mögliche Hardwaredesigns von Beschleunigern für die ausgewählten Funktionen finden und auf ihre Machbarkeit und Effizienz untersuchen.
nengel@8: 
nengel@8: %\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.]}
nengel@8: }
nengel@8: \item{\textbf{Lösung implementieren}
nengel@8: 
nengel@8: Die besten Lösungsansätze in einer Hardware Description Language realisieren, in einem FPGA testen und ihre tatsächliche Leistung messen.
nengel@8: 
nengel@8: %\emph{[Implement the most promising solution in a hardware-description-language and measure its performance.]}
nengel@8: }
nengel@8: \item{\textbf{Hardwareintegration}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\emph{[Integrate the new hardware with the programmable scheduler being developed in the lab.]}
nengel@8: }
nengel@8: \newcounter{enumi_saved}
nengel@8: \setcounter{enumi_saved}{\value{enumi}}
nengel@8: \end{enumerate}
nengel@8: 
nengel@8: \noindent\textbf{Phase 2: Software-/Systemunterstützung der neuen Hardware}
nengel@8: 
nengel@8: \begin{enumerate}
nengel@8: \setcounter{enumi}{\value{enumi_saved}}
nengel@8: \item{\textbf{VMS-Core}
nengel@8: 
nengel@8: Einen hardwarespezifischen VMS-Core für die neue Hardware entwickeln, der die Hardwarebeschleuniger ausnutzen kann.
nengel@8: 
nengel@8: %\emph{[Work with the implementor of the VMS interface for Linux to integrate the hardware into the Linux implementation of VMS.]}
nengel@8: }
nengel@8: 
nengel@8: \item{\textbf{Plug-ins}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\emph{[Write a plugin that uses the new hardware to implement parallelism constructs and scheduling, to show efficiency on real-life problems.]}
nengel@8: }
nengel@8: 
nengel@8: \item{\textbf{Minimalistisches Runtime}
nengel@8: 
nengel@8: 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.
nengel@8: }
nengel@8: 
nengel@8: \item{\textbf{Performanceevaluierung}
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\emph{[Test the performance of the standard VMS benchmarks running on the new hardware, with scheduling acceleration vs without]}
nengel@8: }
nengel@8: \end{enumerate}
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: \subsection{Eigene Vorarbeiten}
nengel@8: 
nengel@8: 
nengel@8: %\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.]}
nengel@8: 
nengel@8: 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} 
nengel@8: vertiefte ich dieses Wissen, und werde nun die daraus gewonnenen Erkenntnisse und Erfahrungen in ein System einbringen, dass ein breiteres Anwendungs\-spektrum verspricht.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %\begin{itemize}
nengel@8: %\item
nengel@8: %\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).]}
nengel@8: %\item
nengel@8: %\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.]}
nengel@8: %\item
nengel@8: %\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.
nengel@8: %This part will also profit from the detailed knowledge of processor design I got from Andre Seznec (both classes \& bachelor internship).]}
nengel@8: %
nengel@8: %\end{itemize}
nengel@8: 
nengel@8: %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.
nengel@8: %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.
nengel@8: 
nengel@8: % [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...]
nengel@8: % 
nengel@8: %  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!"
nengel@8: % 
nengel@8: % Sounds nice, unfortunately none of that is true! 
nengel@8: 
nengel@8: %\subsection{What else?}
nengel@8: 
nengel@8: \section{Arbeits-/Zeitplan}
nengel@8: %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.
nengel@8: %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.
nengel@8: 
nengel@8: %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.
nengel@8: %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.
nengel@8: 
nengel@8: %start of funding would be July 1st btw
nengel@8: 
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: ~
nengel@8: 
nengel@8: \noindent Die benötigte Zeit für die Arbeitsschritte wird wie folgt veranschlagt:
nengel@8: \begin{description}
nengel@8: \item[Hardwareentwicklung:]{ 21 Monate
nengel@8: 
nengel@8: \begin{enumerate}
nengel@8: \item Kernfunktionen identifizieren: 3 Monate
nengel@8: \item Analyse des Laufzeitverhaltens: 3 Monate
nengel@8: \item Design Space Exploration: 3 Monate
nengel@8: \item Lösung implementieren: 6 Monate
nengel@8: \item Schedulerintegration: 3 Monate
nengel@8: \item Integrationstest \& Debugging: 3 Monate
nengel@8: \setcounter{enumi_saved}{\value{enumi}}
nengel@8: \end{enumerate}
nengel@8: }
nengel@8: \item[Softwareunterstützung:]{ 12 Monate
nengel@8: 
nengel@8: \begin{enumerate}
nengel@8: \setcounter{enumi}{\value{enumi_saved}}
nengel@8: \item VMS-Core: 3 Monate
nengel@8: \item Plug-ins: 3 Monate
nengel@8: \item Runtime: 3 Monate
nengel@8: \item Integrationstest, Performanceevaluation \& Optimierung: 3 Monate 
nengel@8: \end{enumerate}
nengel@8: } 
nengel@8: 
nengel@8: \item[Niederschrift:] 3 Monate
nengel@8: \end{description}
nengel@8: 
nengel@8: 
nengel@8: %1. \& 2. Find functions to accelerate - 6m
nengel@8: %3. Explore hardware possibilities - 3m
nengel@8: %4. Implement accelerators - 6m
nengel@8: %5. Integrate with Tamer's HW - 3m
nengel@8: %7. VMS-Core - 3m
nengel@8: %6. Integration test and debugging of system - 3m
nengel@8: %8. Plug-ins - 3m
nengel@8: %9. Mini-runtime - 3m
nengel@8: %10. Performance evaluation, optimization - 3m
nengel@8: %11. Write thesis - 3m
nengel@8: 
nengel@8: Daraus ergibt sich der Zeitplan in Abb. \ref{gantt}.
nengel@8: 
nengel@8: \begin{sidewaysfigure}
nengel@8: 	\centering
nengel@8: 	\includegraphics[width=0.99\textwidth]{gantt.pdf}
nengel@8: 	\caption{Zeitplan}
nengel@8: 	\label{gantt}
nengel@8: \end{sidewaysfigure}
nengel@8: 
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: ~
nengel@8: 
nengel@8: \noindent Folgende Meilensteine werden festgelegt:
nengel@8: \begin{description}
nengel@8: \setlength{\itemsep}{0em}
nengel@8: \item[12 Monate:] Der Lösungsraum der Hardwarebeschleuniger wurde durchsucht, ein detaillierter Plan der Architektur steht fest.
nengel@8: \item[24 Monate:] Lauffähige Hardware und einige vorläufige Daten zur Performance liegen vor.
nengel@8: \item[36 Monate:] Voll funktionsfähiges System, detaillierte Performanceanalyse.
nengel@8: \end{description}
nengel@8: 
nengel@8: 
nengel@8: \section{Einordnung des Vorhabens}
nengel@8: 
nengel@8: 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.
nengel@8: Alle drei Schwerpunkte, insbesondere die Hardwaregestützte Ablaufplanung, werden in dieser Arbeit behandelt.
nengel@8: 
nengel@8: 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.
nengel@8: 
nengel@8: %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.
nengel@8: %This proposal matches these Forschungschwerpunkte perfectly, in particular the Forschungsschwerpunkt hardware support for task management and scheduling.
nengel@8: %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.
nengel@8: %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.
nengel@8: 
nengel@8: \section{Reisemittel}
nengel@8: 
nengel@8: 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.
nengel@8: 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.
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: \section{Vorschläge für weitere Gutachter}
nengel@8: 
nengel@8: Dr. Christophe Bobda\\
nengel@8: Associate Professor, 
nengel@8: Computer Science and Computer Engineering\\
nengel@8: University of Arkansas\\
nengel@8: Phone: (479) 575-4797\\
nengel@8: E-mail: cbobda@uark.edu\\
nengel@8: 
nengel@8: \noindent Dr. Christian Haubelt\\
nengel@8: Lehrstuhl für Informatik 12\\
nengel@8: (Hardware-Software-Co-Design)\\
nengel@8: Universität Erlangen-Nürnberg\\
nengel@8: Am Weichselgarten 3\\
nengel@8: 91058 Erlangen\\
nengel@8: haubelt@cs.fau.de \\
nengel@8: 
nengel@8: \noindent Prof. Dr. Theo Ungerer\\
nengel@8: Lehrstuhl für Systemnahe Informatik und Kommunikationssysteme,\\
nengel@8: Institut für Informatik.\\
nengel@8: Eichleitnerstr. 30,\\
nengel@8: Universität Augsburg,\\
nengel@8: 86135 Augsburg \\
nengel@8: Tel. 0821-598-2350 / -2351\\
nengel@8: ungerer@informatik.uni-augsburg.de \\
nengel@8: 
nengel@8: \begin{thebibliography}{9}
nengel@8: 
nengel@8: \bibitem{VMS}
nengel@8: Sean Halle,
nengel@8: \emph{Support of Collective Effort Towards Performance Portability},
nengel@8: in Proceedings of 3rd USENIX Workshop on Hot Topics in Parallelism, May 2011
nengel@8: 
nengel@8: \bibitem{barrelfish}
nengel@8:   Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania, 
nengel@8:   \emph{The Multikernel: A new OS architecture for scalable multicore systems,} 
nengel@8:   in Proceedings of the 22nd ACM Symposium on OS Principles, Big Sky, MT, USA, Oktober 2009.
nengel@8: 
nengel@8: \bibitem{MJ09}
nengel@8: C.H. Meenderinck and B.H.H. Juurlink,
nengel@8: \emph{A Case for Hardware Task Management Support for the StarSS Programming Model,}
nengel@8: in Proceedings Conference on Digital System Design Architectures, Methods and Tools; special session on Multicore Systems: Design and Application, September 2010.
nengel@8: 
nengel@8: \bibitem{carbon}
nengel@8: S. Kumar, C. Hughes, and A. Nguyen, 
nengel@8: \emph{Carbon: Architectural
nengel@8: Support for Fine-Grained Parallelism on Chip Multiprocessors},
nengel@8: in Proc. Int. Conf. on Computer Architecture, 2007.
nengel@8: 
nengel@8: \bibitem{masterarbeit}
nengel@8:  Nina Engelhardt,
nengel@8: \emph{Application of multimode high-level synthesis techniques to ASIP synthesis}, 
nengel@8: Masterarbeit, Cairn, IRISA, Juni 2010.
nengel@8: 
nengel@8: \bibitem{cilk}
nengel@8: Keith H. Randall,
nengel@8: \emph{Cilk: Efficient Multithreaded Computing},
nengel@8: Thesis (Ph. D.), Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998. 
nengel@8: 
nengel@8: \bibitem{starss}
nengel@8: J. Planas, R. Badia, E. Ayguadé, and J. Labarta,
nengel@8: \emph{Hierarchical Task-Based Programming With StarSs,}
nengel@8: Int. Journal of High Performance Computing Applications, vol. 23, no. 3, 2009.
nengel@8: 
nengel@8: \bibitem{sequoia}
nengel@8: 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,
nengel@8: \emph{Sequoia: programming the memory hierarchy},
nengel@8: in SC ’06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing, page 83, 2006.
nengel@8: 
nengel@8: \end{thebibliography}
nengel@8: 
nengel@8: \end{document}
nengel@8: 
nengel@8: 
nengel@8: 
nengel@8: %\subsection{Introduction and Overview of Proposed Project}
nengel@8: 
nengel@8: %  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.
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: %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.
nengel@8: 
nengel@8: %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. 
nengel@8: 
nengel@8: %\subsection{Background on Threads and VMS}
nengel@8: 
nengel@8: %  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
nengel@8: %  and hurting performance.  The new hardware abstraction, called VMS, allows the
nengel@8: %  language to define both parallelism constructs and the scheduler, then plug
nengel@8: %  them in.
nengel@8:    
nengel@8: %  VMS has two benefits for productivity. First, sequential algorithms are used
nengel@8: %  to implement the parallelism constructs. This is enabled by a virtual time line that
nengel@8: %sequentializes events that are simultaneous in the application code.  Second, VMS 
nengel@8: %  simplifies debugging with a separate ``deterministic'' scheduling phase for debugging
nengel@8: %  basic functionality independently from concurrency.
nengel@8: %
nengel@8: %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.
nengel@8: %
nengel@8: % 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.
nengel@8: %
nengel@8: 
nengel@8: 




