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

     2.1 --- a/2__Other/year2report/report.tex	Tue May 14 12:03:39 2013 +0200
     2.2 +++ b/2__Other/year2report/report.tex	Wed Jun 19 16:16:04 2013 +0200
     2.3 @@ -3,19 +3,98 @@
     2.4  \usepackage[german]{babel}
     2.5  \usepackage{fullpage}
     2.6  \usepackage[utf8]{inputenc}
     2.7 +\usepackage{multirow,bigdelim}
     2.8  
     2.9  \begin{document}
    2.10  \setlength{\parindent}{0px} \setlength{\parskip}{1 em}
    2.11  
    2.12 -\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme\\Zwischenbericht zum 1. Jahr}
    2.13 +\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme\\Zwischenbericht zum 2. Jahr}
    2.14  \author{Nina Engelhardt}
    2.15  \date{\today}
    2.16  \maketitle
    2.17  
    2.18  
    2.19 -Ziel meiner Arbeit ist es, durch speziell angepasste Hardware die Synchronisation und Aufgabenverteilung für parallele Programme auf Multicoresystemen zu verbessern. Als Grundlage dient dafür das Virtualzed Master-Slave System, kurz VMS, ein Framework dass es ermöglicht, Laufzeitumgebungen für verschiedenste parallele Programmiermodelle mit nur wenig Aufwand zu implementieren.
    2.20 +Die Supercomputer von Gestern sind die eingebetteten Systeme von Morgen. Massive Anzahlen von Prozessorkernen, wie man sie einst nur in Rechenzentren fand, halten bereits Einzug in Autos.
    2.21 +Damit weitet sich das altbekannte Problem aus, dass es viel schwerer ist, Programme zu schreiben, die viele Kerne gleichzeitig effizient benutzen können, als Programme für nur einen Kern zu schreiben.
    2.22 +
    2.23 +Ein vielversprechender Lösungsansatz sind dömänenspezifische parallele Programmiersprachen \cite{DSLs}. Die Programmierung gelingt schneller und fehlerfreier, wenn die Konzepte der Programmiersprache denen der Anwendung angepasst sind. Allerdings haben spezifischere Programmiersprachen eine kleinere Nutzerbasis, sodass sich die Entwicklungskosten für die Sprache und die dazugehörigen Tools schnell nicht mehr rentieren.
    2.24 +Das Virtualized Master-Slave Framework\cite{bib:holistic}, kurz VMS, das Subjekt meines Dissertationsvorhabens ist, erleichtert die Entwicklung von Runtimes für parallele Programmiermodelle, indem es grundlegende Funktionalitäten wie Synchronisation übernimmt. Um ein bestimmtes Modell zu unterstützen, muss der Entwickler nur noch einige Funktionen in Form eines \emph{Plugins} hinzufügen. Diese Pluginfunktionen sind einfach zu schreiben, da sie die üblichen strengen Auflagen wie Thread-safety oder Reentrancy nicht erfüllen müssen.
    2.25 +
    2.26 +Damit diese Strategie Erfolg hat, sollten die resultierenden Runtimes ähnliche Performance wie Runtimes für unspezifische Programmiermodelle haben. Ziel meiner Arbeit ist es daher, Ansätze zu finden, die die Performance von vielen VMS-basierten Runtimes gleichzeitig verbessern, insbesondere mit Augenmerk auf Hardwarelösungen.
    2.27  
    2.28  \section{Ausgeführte Arbeiten}
    2.29  
    2.30 +Aufgrund des Ausscheidens von Dr. Halle aus dem Fachbereich musste ich dieses Jahr die gesamte Entwicklungsarbeit für das VMS-System übernehmen. (Vorher war diese unter vier Mitgliedern des Fachgebiets geteilt.) Dies bedeutete, dass ich mich zunächst nicht wie geplant der Portierung von VMS auf die Beefarm-Plattform\cite{bib:beefarm} widmen konnte. Sowohl für meine als auch für andere Arbeiten des Fachgebiets war eine VMS-basierte Implementation des OmpSs Programmiermodells\cite{ompss} eingeplant, die zwar zur Verfügung stand, aber noch erhebliche Fehler enthielt. Des weiteren waren auch einige Features noch nicht implementiert, die für die komplizierteren Benchmarks wie z.B. den H.264-Videodecoder\cite{chi} benötigt wurden.
    2.31 +
    2.32 +Die Entwicklungsarbeit bis die Benchmarks problemlos ausgeführt wurden, dauerte bis März 2013. In dieser Zeit habe ich neben der Fehlerbehebung folgende Funktionalitäten zum VMS-System bzw. dem OmpSs-Plugin hinzugefügt:
    2.33 +\begin{itemize}
    2.34 +\item Unterstützung für den Präprozessorbefehl \emph{\#pragma omp taskwait on(*p)}, der es einem Thread oder Task erlaubt, auf die Beendung aller im System befindlichen Tasks zu warten, die die Datenstruktur \emph{p} verändern.
    2.35 +\item Unterstützung für den Präprozessorbefehl \emph{\#pragma omp critical(name)}, der Wechselseitigen Ausschluss garantiert.
    2.36 +\item Die Möglichkeit, die Erstellung von neuen Tasks zu unterbinden, wenn bereits eine große Anzahl lauffähiger Tasks im System existiert (\emph{throttling}).
    2.37 +\item Automatische Erkennung von Deadlocks im Programm unabhängig vom eingesetzten Programmiermodell.
    2.38 +\item Initialisierung und Beendung des VMS-Runtimes ohne dass diese Funktionen aus dem Programm explizit aufgerufen werden müssen.
    2.39 +\item Die Möglichkeit, den API-Funktionen des Programmiermodells eine beliebige Signatur zu geben (Entfernung von bisherigen Pflichtargumenten). Gemeinsam mit dem vorigen Feature erlaubt dies, API-kompatible Ersatzbibliotheken für bereits existierende Programmiermodelle zu erstellen. Somit kann man existierende Benchmarks bzw. Programme für diese Modelle ohne Änderungen übernehmen.
    2.40 +\item Ein Interface für externe Dependency Resolution-Mechanismen, wie z.B. das im Fachgebiet entwickelte Nexus++ board\cite{nexus}.
    2.41 +\end{itemize}
    2.42 +
    2.43 +Des weiteren habe ich den geplanten Artikel über das letztes Jahr entwickelte Instrumentationsinterface von VMS verfasst. Der notwendige Aufwand, bis die interessanteren Benchmarks ausgeführt werden konnten, hatte jedoch zur Folge, dass ich nur einfache Beispiele vorbereiten konnte. Diese konnten nicht auf dem hohen Niveau der anvisierten Konferenz überzeugen und der Artikel wurde nicht zur Ver\-öffentlichung angenommen. Zurzeit überarbeite ich ihn, um ihn mit zusätzlichen Beispielen erneut einzureichen.
    2.44 +
    2.45 +\section{Zukünftige Aktivitäten}
    2.46 +
    2.47 +Eine weitere Herausforderung ist der Teil des VMS-systems, der für die Kohärenz der internen Zustandsdaten des Runtimes sorgt. Die jetztige Implementierung ist ein Proof-of-Concept, in dem die Kohärenz sichergestellt wird, indem alle Runtimefunktionen über ein globales Mutex sequentialisiert werden. Diese Lösung ist sehr einfach zu implementieren und bietet unter gewissen Bedingungen nur geringfügig schlechtere Performance als eine Lösung die die einzelnen Bestandteile getrennt synchronisiert. Dies ist der Fall, solange die Anzahl Prozessorkerne im System ein Dutzend nicht überschreitet, und die Runtimeaufrufe im Vergleich zu den Berechnungen der Anwendung nur wenig Rechenzeit benötigen.
    2.48 +Insbesondere jedoch für Anwendungen die keine größeren unabhängigen Abschnitte sondern nur sehr fein granularen Parallelismus aufweisen, ist diese Lösung suboptimal. Verschärfend kommt hinzu, das gerade in diesen Fällen parallele Programmiermodelle wünschenswert sind, die die Komplexität aus der Programmierung nehmen und sie anstattdessen in das Runtime verschieben.
    2.49 +
    2.50 +Für die Entwicklung der unterstützenden Hardware für das VMS-System sind diese Einschränkungen hinnehmbar, da es keinen Einfluss auf die Funktionalität hat. Bei der Performanceevaluation hingegen würde dies zu einer Überbewertung des Effekts der Hardware führen, da diese Lösung besonders empfindlich auf die Länge der Runtimeaufrufe reagiert. Daher war ursprünglich geplant, dass ich die Hardware zunächst auf Basis der jetztigen Lösung entwickle, und dann mit der inzwischen vorangetriebenen verteilten Version von VMS integriere. Aufgrund des Ausscheidens von Dr. Halle kann nun nicht mehr erwartet werden, dass diese Version ohne mein Zutun fertiggestellt wird.
    2.51 +
    2.52 +Eine verteilte Version von VMS wäre aber nicht nur für die Evaluation von spezialisierter Hardware von Nutzen, sondern würde auch die Benutzung von VMS für größere Systeme, verteilte Systeme, und Anwendungen mit niedrigem Parallelismus ermöglichen. Das Matsuoka Lab des Tokyo Institute of Technology in Japan hat Interesse bekundet, an einer verteilten Version mitzuwirken, um damit ein modulares OmpSs-runtime zu implementieren. Das Konzept dieses modularen Runtimes ist, dass nur die von der Anwendung wirklich benötigten Funktionalitäten auch geladen werden. So kann z.B. auf Tests von Konditionen verzichtet werden, die nur zutreffen können, wenn man in der Anwendung nicht vorkommende Funktionen aufruft. Dadurch wird die Rechenzeit verringert, die im Runtime verbracht wird.
    2.53 +
    2.54 +Wird diese Kooperation erfolgreich abgeschlossen, eröffnen sich weitere For\-schungs\-möglich\-keiten. Eine davon ist die automatische Anpassung von der Taskgröße an die Fähigkeiten der Hardware. Dies ist in zwei Richtungen möglich: Zum einen kann man eine Gesamtaufgabe angeben, sowie eine Methode um diese aufzuteilen und später wieder zusammenzuführen. Dieses Prinzip findet bereits Verwendung in VMS, in Form des Divider-Kernel-Undivider Patterns\cite{dku}. Zum anderen kann man die kleinstmöglichsten Tasks spezifizieren und die Zusammenführung zu größeren Einheiten dem Runtime über\-lassen. Dabei besteht die Komplexität darin, das die Zusammenführung kaum Overhead hinzufügen darf, da sie bei feingranularen Tasks extrem häufig stattfinden muss. Eine erfolgreiche Anwendung dieses Prinzips gibt es daher haupt\-sächlich für das Cilk\cite{cilk} Programmiermodell, das für den extrem niedrigen Overhead seines Runtimes bekannt ist. VMS hat ebenfalls niedrige Overheads beim Taskwechsel, wenn geeignete Plugins verwendet werden, sodass dieser Ansatz auch hier Anwendung finden könnte.
    2.55 +
    2.56 +Als Teil dieser Zusammenarbeit plane ich die Monate Oktober bis März am Tokyo Institute of Technology zu verbringen. Das Matsuoka Lab ist Teil des GSIC Exzellenzzentrums für Supercomputing und ist in der Programmierung großer und verteilter Systeme spezialisiert. Ein Fokus der Forschungsgruppe ist auf neuartige Programmiermodelle. Es ergeben sich so sowohl gemeinsame Interessen als auch sich ergänzende Expertise.
    2.57 +
    2.58 +Bis Ende September plane ich, eine erste alpha-Version des verteilten VMS-Systems zu implementieren, und diese dann in der ersten Zeit am Tokyo Institute of Technology zu verbessern. Darauf aufbauend werde ich ein modulares OmpSs-Plugin implementieren und anhand der Benchmarks und Wissenschaftlichen Anwendungen des Fachgebiets AES und des Matsuoka Lab evaluieren. Bei der Implementierung werde ich stets auf die Trennung der verschiedenen Bestandteile des Runtimes achten und die Abstraktionen so gestalten, dass sie sich auch als Schnittstellen zu Modulen mit Hardwareunterstützung eignen. Dadurch muss für die Integration von verschiedenen Hardwaremodulen nur sehr wenig Code modifiziert werden, und Module können einfach kombiniert und ausgetauscht werden.
    2.59 +
    2.60 +Nach meiner Rückkehr werde ich einige Hardwarebeschleuniger in die neue verteilte VMS-Version einbauen. Zusätzlich zu der geplanten Unterstützung für Hashtabellen bietet diese Version neue Ansatzpunkte, insbesondere die Unterstützung der Kommunikation von Runtime-Updates zwischen Prozessorkernen.
    2.61 +
    2.62 +Durch die Refokusierung auf die verteilte VMS-Version werde ich diese Hardwarelösungen nicht so umfangreich betrachten können wie ursprünglich geplant. Jedoch können VMS-basierte Runtimes wie das OmpSs-Runtime bereits jetzt vergleichbare Laufzeit mit den offiziellen Runtimes aufweisen, und 80\% der zurzeit im VMS-Runtime verbrachten Zeit ist Blockierung durch das Mutex-Problem, das ich durch die verteilte VMS-Version beheben werde. Das ursprüngliche Ziel, VMS-basierte Runtimes mit handoptimierten Runtimes konkurrenzfähig zu machen, sollte also durch diese Softwarelösung bereits erreicht werden.
    2.63 +
    2.64 +Zusammenfassend ergibt sich folgender Zeitplan:
    2.65 +\vspace{-0.5em}
    2.66 +\begin{table}[h]
    2.67 +\centering
    2.68 +\renewcommand{\arraystretch}{1.2}
    2.69 +\begin{tabular}{|l|l|c|l}
    2.70 +\cline{1-3}
    2.71 +Verteilte VMS-Version & Juni - September 2013 & 4 Monate &\\
    2.72 +\cline{1-3}
    2.73 +Abstraktionen verfeinern & Oktober - November 2013 & 2 Monate &\rdelim\}{3}{5em}[am GSIC]\\
    2.74 +\cline{1-3}
    2.75 +Modulares OmpSs Plugin & Dezember 2013 - Januar 2014 & 3 Monate & \\
    2.76 +\cline{1-3}
    2.77 +Evaluation & März 2014 & 1 Monat &\\
    2.78 +\cline{1-3}
    2.79 +Hardwareintegration & April - Juni 2013 & 3 Monate &\\
    2.80 +\cline{1-3}
    2.81 +Gesamtevaluation & Juli - August 2014 & 2 Monate &\\
    2.82 +\cline{1-3}
    2.83 +Niederschrift & September 2013 - Februar 2014 & 6 Monate &\\
    2.84 +\cline{1-3}
    2.85 +\end{tabular}
    2.86 +\caption{Zeitplan}
    2.87 +\end{table}
    2.88 +
    2.89 +
    2.90 +
    2.91 +\begin{thebibliography}{9}
    2.92 +%\bibitem{bib:perftune} Nina Engelhardt, Sean Halle, Ben Juurlink; \emph{Integrated Performance Tuning Using Semantic Information Collected by Instrumenting the Language Runtime}; in progress
    2.93 +\bibitem{chi} M. Andersch, C. C. Chi, and B. Juurlink; \emph{Using OpenMP Superscalar for Parallelization of Embedded and Consumer Applications}; Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation; 2012
    2.94 +\bibitem{cilk} R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou; \emph{Cilk: an efficient multithreaded runtime system}; SIGPLAN Not. 30, 8; 1995 
    2.95 +\bibitem{nexus} T. Dallou, B. Juurlink; \emph{Hardware-Based Task Dependency Resolution for the StarSs Programming Model}; Parallel Processing Workshops (ICPPW), 2012
    2.96 +\bibitem{ompss} A. Duran, E. Ayguade, R. M. Badia, J. Labarta, L. Martinell, X. Martorell, J. Planas; \emph{Ompss: a proposal for programming heterogeneous multi-core architectures}; Parallel Processing Letters, 21(02); 2011
    2.97 +\bibitem{bib:holistic} S. Halle, A. Cohen; \emph{Support of Collective Effort Towards Performance Portability}; Proceedings of 3rd USENIX Workshop on Hot Topics in Parallelism, May 2011
    2.98 +\bibitem{dku} S. Halle, A. Cohen;  \emph{The DKU Pattern for Performance Portable Parallel Programming}; 2009
    2.99 +\bibitem{DSLs}M. Mernik, J. Heering, A. M. Sloane; \emph{When and how to develop domain-specific languages}; ACM Comput. Surv. 37, 4; 2005
   2.100 +\bibitem{bib:beefarm} N. Sonmez, O. Arcas, G. Sayilar, O. S. Unsal, A. Cristal, I. Hur, S. Singh, M. Valero; \emph{From plasma to beefarm: design experience of an FPGA-based multicore prototype}; Proceedings of the 7th international conference on Reconfigurable computing: architectures, tools and applications (ARC'11), 2011
   2.101 +\end{thebibliography}
   2.102  
   2.103  \end{document}