1

2

3 \documentclass[a4paper,11pt]{article}

4 %

5 \usepackage{makeidx,geometry,amssymb,graphicx,calc,ifthen,fullpage}

6 %

7 \usepackage[utf8]{inputenc}

8 \usepackage[T1]{fontenc}

9 \usepackage[gen]{eurosym}

10 \usepackage[german]{babel}

11 \usepackage{graphicx}

12 \usepackage{rotating}

13

14 % correct bad hyphenation here

15 \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}

16

17

18 \begin{document}

19 \bibliographystyle{plain}

20 %

21

22 \title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme}

23 \author{Nina Engelhardt}

24

25 \maketitle

26 %

27 \tableofcontents

28

29 %\newpage

30

31 \section{Allgemeinverständliche Zusammenfassung} %Short summary of proposal

32 %Allgemeinverständliche Zusammenfassung mit kurzer Charakterisierung der Ziele und Methoden (nicht mehr als 15 Schreibmaschinenzeilen).

33 %Short summary accessible to the general public with short characterisation of goals and methods (15 lines max.)

34

35 %Summary for Laymen

36

37 %\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.]}

38

39

40 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.

41

42 %Seit 2005 werden auch im Heimcomputerbereich Multiprozessorsysteme verwendet.

43

44 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.

45

46 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.

47

48

49

50 \section{Beschreibung des Forschungsgegenstandes und Vorarbeiten}

51 %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.

52 %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.

53

54 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.

55

56 %\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.]}

57

58 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.

59

60 %\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.] }

61

62 \subsection{Historischer Kontext}

63

64 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.

65

66 %\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.]}

67

68 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.

69

70 %\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.]}

71

72 \subsection{Threads und parallele Programmiermodelle}

73

74 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.

75

76 %\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.]}

77

78 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.

79 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.

80

81 %\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.]}

82

83 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.

84

85 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.

86

87 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.

88

89 %\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.]}

90

91 %[Needs comparison to rival models either here or next]

92

93

94

95

96

97

98 %\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.}

99

100 %\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.]}

101

102 %[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..]

103

104 %If I understood correctly, Barrelfish

105

106 \subsection{Das Virtualized Master-Slave Modell}

107

108 %****Changes here*****

109

110 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.

111

112 %\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.]}

113

114 \begin{figure}[h!]

115 \centering

116 \includegraphics[width=0.25\textwidth]{vms-components.pdf}

117 \caption{Interaktion der Bestandteile von VMS. Quelle: S.Halle \cite{VMS}}

118 \end{figure}

119

120 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.

121

122

123 %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.

124

125 %\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.}

126

127 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.

128

129 %\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!}

130

131 \begin{figure}[bht]

132 \centering

133 \includegraphics[width=0.99\textwidth]{vms-ecosystem.pdf}

134 \caption{VMS-Bestandteile für mehrere Programmiersprachen und mehrere Hardwareklassen. Quelle: S.Halle \cite{VMS}}

135 \end{figure}

136

137 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.

138

139 %\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.]}

140

141

142 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.

143

144 %\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.]}

145

146 %[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 ; ) ]

147

148

149 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.

150

151 %\emph{[The VMS-core is a low-level hardware abstraction, which contains the basic functions necessary for the plugin, such as task switching.]}

152

153

154 \subsection{Kern der Arbeit}

155

156 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.

157

158 %\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.}

159

160 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.

161

162 % und diesen so mit den ausführenden Kernen zu verbinden, dass er diese effizient Kontrollieren kann. Dies verringert den Synchronisations-Overhead.

163

164 %\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.}

165

166

167

168 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.

169

170

171

172 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.

173

174 %\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.}

175

176 Die Herausforderung meiner Arbeit ist, eine generelle und erweiterbare Architektur zu entwickeln, die eine Vielzahl von Programmiermodellen effizient unterstützt.

177

178 %\emph{The challenge of this project is to build a general and extensible architecture that can support a multitude of programming models efficiently.}

179

180 %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.

181

182 %\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.}

183

184 %\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.]}

185

186

187

188

189

190 %\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.]}

191

192 \label{sec:arbeitsschritte}

193 Folgende Arbeitsschritte sind vonnöten:

194

195 ~

196

197 \noindent\textbf{Phase 1: Hardwareentwicklung}

198 \begin{enumerate}

199 \item{\textbf{Kernfunktionen identifizieren}

200

201 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.

202

203 %\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).]}

204 }

205 \item{\textbf{Analyse des Laufzeitverhaltens}

206

207 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.

208

209 %\emph{[Instrument VMS code for profiling to measure the impact of each of these functions.]}

210 }

211 \item{\textbf{Design Space Exploration}

212

213 Mögliche Hardwaredesigns von Beschleunigern für die ausgewählten Funktionen finden und auf ihre Machbarkeit und Effizienz untersuchen.

214

215 %\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.]}

216 }

217 \item{\textbf{Lösung implementieren}

218

219 Die besten Lösungsansätze in einer Hardware Description Language realisieren, in einem FPGA testen und ihre tatsächliche Leistung messen.

220

221 %\emph{[Implement the most promising solution in a hardware-description-language and measure its performance.]}

222 }

223 \item{\textbf{Hardwareintegration}

224

225 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.

226

227 %\emph{[Integrate the new hardware with the programmable scheduler being developed in the lab.]}

228 }

229 \newcounter{enumi_saved}

230 \setcounter{enumi_saved}{\value{enumi}}

231 \end{enumerate}

232

233 \noindent\textbf{Phase 2: Software-/Systemunterstützung der neuen Hardware}

234

235 \begin{enumerate}

236 \setcounter{enumi}{\value{enumi_saved}}

237 \item{\textbf{VMS-Core}

238

239 Einen hardwarespezifischen VMS-Core für die neue Hardware entwickeln, der die Hardwarebeschleuniger ausnutzen kann.

240

241 %\emph{[Work with the implementor of the VMS interface for Linux to integrate the hardware into the Linux implementation of VMS.]}

242 }

243

244 \item{\textbf{Plug-ins}

245

246 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.

247

248 %\emph{[Write a plugin that uses the new hardware to implement parallelism constructs and scheduling, to show efficiency on real-life problems.]}

249 }

250

251 \item{\textbf{Minimalistisches Runtime}

252

253 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.

254 }

255

256 \item{\textbf{Performanceevaluierung}

257

258 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.

259

260 %\emph{[Test the performance of the standard VMS benchmarks running on the new hardware, with scheduling acceleration vs without]}

261 }

262 \end{enumerate}

263

264

265

266 \subsection{Eigene Vorarbeiten}

267

268

269 %\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.]}

270

271 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}

272 vertiefte ich dieses Wissen, und werde nun die daraus gewonnenen Erkenntnisse und Erfahrungen in ein System einbringen, dass ein breiteres Anwendungs\-spektrum verspricht.

273

274 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.

275

276 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.

277

278 %\begin{itemize}

279 %\item

280 %\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).]}

281 %\item

282 %\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.]}

283 %\item

284 %\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.

285 %This part will also profit from the detailed knowledge of processor design I got from Andre Seznec (both classes \& bachelor internship).]}

286 %

287 %\end{itemize}

288

289 %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.

290 %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.

291

292 % [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...]

293 %

294 % 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!"

295 %

296 % Sounds nice, unfortunately none of that is true!

297

298 %\subsection{What else?}

299

300 \section{Arbeits-/Zeitplan}

301 %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.

302 %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.

303

304 %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.

305 %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.

306

307 %start of funding would be July 1st btw

308

309

310 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.

311

312 ~

313

314 \noindent Die benötigte Zeit für die Arbeitsschritte wird wie folgt veranschlagt:

315 \begin{description}

316 \item[Hardwareentwicklung:]{ 21 Monate

317

318 \begin{enumerate}

319 \item Kernfunktionen identifizieren: 3 Monate

320 \item Analyse des Laufzeitverhaltens: 3 Monate

321 \item Design Space Exploration: 3 Monate

322 \item Lösung implementieren: 6 Monate

323 \item Schedulerintegration: 3 Monate

324 \item Integrationstest \& Debugging: 3 Monate

325 \setcounter{enumi_saved}{\value{enumi}}

326 \end{enumerate}

327 }

328 \item[Softwareunterstützung:]{ 12 Monate

329

330 \begin{enumerate}

331 \setcounter{enumi}{\value{enumi_saved}}

332 \item VMS-Core: 3 Monate

333 \item Plug-ins: 3 Monate

334 \item Runtime: 3 Monate

335 \item Integrationstest, Performanceevaluation \& Optimierung: 3 Monate

336 \end{enumerate}

337 }

338

339 \item[Niederschrift:] 3 Monate

340 \end{description}

341

342

343 %1. \& 2. Find functions to accelerate - 6m

344 %3. Explore hardware possibilities - 3m

345 %4. Implement accelerators - 6m

346 %5. Integrate with Tamer's HW - 3m

347 %7. VMS-Core - 3m

348 %6. Integration test and debugging of system - 3m

349 %8. Plug-ins - 3m

350 %9. Mini-runtime - 3m

351 %10. Performance evaluation, optimization - 3m

352 %11. Write thesis - 3m

353

354 Daraus ergibt sich der Zeitplan in Abb. \ref{gantt}.

355

356 \begin{sidewaysfigure}

357 \centering

358 \includegraphics[width=0.99\textwidth]{gantt.pdf}

359 \caption{Zeitplan}

360 \label{gantt}

361 \end{sidewaysfigure}

362

363

364 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.

365

366 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.

367

368 ~

369

370 \noindent Folgende Meilensteine werden festgelegt:

371 \begin{description}

372 \setlength{\itemsep}{0em}

373 \item[12 Monate:] Der Lösungsraum der Hardwarebeschleuniger wurde durchsucht, ein detaillierter Plan der Architektur steht fest.

374 \item[24 Monate:] Lauffähige Hardware und einige vorläufige Daten zur Performance liegen vor.

375 \item[36 Monate:] Voll funktionsfähiges System, detaillierte Performanceanalyse.

376 \end{description}

377

378

379 \section{Einordnung des Vorhabens}

380

381 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.

382 Alle drei Schwerpunkte, insbesondere die Hardwaregestützte Ablaufplanung, werden in dieser Arbeit behandelt.

383

384 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.

385

386 %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.

387 %This proposal matches these Forschungschwerpunkte perfectly, in particular the Forschungsschwerpunkt hardware support for task management and scheduling.

388 %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.

389 %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.

390

391 \section{Reisemittel}

392

393 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.

394 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.

395

396 %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.

397

398 \section{Vorschläge für weitere Gutachter}

399

400 Dr. Christophe Bobda\\

401 Associate Professor,

402 Computer Science and Computer Engineering\\

403 University of Arkansas\\

404 Phone: (479) 575-4797\\

405 E-mail: cbobda@uark.edu\\

406

407 \noindent Dr. Christian Haubelt\\

408 Lehrstuhl für Informatik 12\\

409 (Hardware-Software-Co-Design)\\

410 Universität Erlangen-Nürnberg\\

411 Am Weichselgarten 3\\

412 91058 Erlangen\\

413 haubelt@cs.fau.de \\

414

415 \noindent Prof. Dr. Theo Ungerer\\

416 Lehrstuhl für Systemnahe Informatik und Kommunikationssysteme,\\

417 Institut für Informatik.\\

418 Eichleitnerstr. 30,\\

419 Universität Augsburg,\\

420 86135 Augsburg \\

421 Tel. 0821-598-2350 / -2351\\

422 ungerer@informatik.uni-augsburg.de \\

423

424 \begin{thebibliography}{9}

425

426 \bibitem{VMS}

427 Sean Halle,

428 \emph{Support of Collective Effort Towards Performance Portability},

429 in Proceedings of 3rd USENIX Workshop on Hot Topics in Parallelism, May 2011

430

431 \bibitem{barrelfish}

432 Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania,

433 \emph{The Multikernel: A new OS architecture for scalable multicore systems,}

434 in Proceedings of the 22nd ACM Symposium on OS Principles, Big Sky, MT, USA, Oktober 2009.

435

436 \bibitem{MJ09}

437 C.H. Meenderinck and B.H.H. Juurlink,

438 \emph{A Case for Hardware Task Management Support for the StarSS Programming Model,}

439 in Proceedings Conference on Digital System Design Architectures, Methods and Tools; special session on Multicore Systems: Design and Application, September 2010.

440

441 \bibitem{carbon}

442 S. Kumar, C. Hughes, and A. Nguyen,

443 \emph{Carbon: Architectural

444 Support for Fine-Grained Parallelism on Chip Multiprocessors},

445 in Proc. Int. Conf. on Computer Architecture, 2007.

446

447 \bibitem{masterarbeit}

448 Nina Engelhardt,

449 \emph{Application of multimode high-level synthesis techniques to ASIP synthesis},

450 Masterarbeit, Cairn, IRISA, Juni 2010.

451

452 \bibitem{cilk}

453 Keith H. Randall,

454 \emph{Cilk: Efficient Multithreaded Computing},

455 Thesis (Ph. D.), Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.

456

457 \bibitem{starss}

458 J. Planas, R. Badia, E. Ayguadé, and J. Labarta,

459 \emph{Hierarchical Task-Based Programming With StarSs,}

460 Int. Journal of High Performance Computing Applications, vol. 23, no. 3, 2009.

461

462 \bibitem{sequoia}

463 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,

464 \emph{Sequoia: programming the memory hierarchy},

465 in SC ’06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing, page 83, 2006.

466

467 \end{thebibliography}

468

469 \end{document}

470

471

472

473 %\subsection{Introduction and Overview of Proposed Project}

474

475 % 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.

476

477 %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.

478

479 %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.

480

481 %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.

482

483 %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.

484

485 %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.

486

487 %\subsection{Background on Threads and VMS}

488

489 % 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

490 % and hurting performance. The new hardware abstraction, called VMS, allows the

491 % language to define both parallelism constructs and the scheduler, then plug

492 % them in.

493

494 % VMS has two benefits for productivity. First, sequential algorithms are used

495 % to implement the parallelism constructs. This is enabled by a virtual time line that

496 %sequentializes events that are simultaneous in the application code. Second, VMS

497 % simplifies debugging with a separate ``deterministic'' scheduling phase for debugging

498 % basic functionality independently from concurrency.

499 %

500 %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.

501 %

502 % 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.

503 %

504

505