1.1 --- a/0__Papers/holistic_model/holistic_model_detailed.tex	Mon Apr 23 17:07:28 2012 +0200
     1.2 +++ b/0__Papers/holistic_model/holistic_model_detailed.tex	Fri Jun 08 14:19:26 2012 +0200
     1.3 @@ -21,6 +21,10 @@
     1.4  \maketitle
     1.5  \tableofcontents
     1.6  
     1.7 +\begin{abstract}
     1.8 +As processors multiply and communication models diversify in systems, increasing attention must be paid to scheduling, as the limiting factor for performance becomes the organisation of communications in such a way as to minimize stalling or idling in wait for data. In this context, good scheduling results can only be obtained if scheduled units follow Application logic. To coherently investigate interactions between Application, Hardware, and Scheduler, and their combined effects on desired metrics - execution time, energy, etc - we propose a model that captures the essential characteristics of an Application and their interaction with hardware and runtime during execution.
     1.9 +\end{abstract}
    1.10 +
    1.11  Problem statement -- as processors multiply and communication models diversify in systems, increasing attention must be paid to scheduling, as the limiting factor for performance becomes the organisation of communications in such a way as to minimize stalling or idling in wait for data. In this context, good scheduling results can only be obtained if scheduled units follow Application logic.
    1.12  
    1.13  Purpose -- to investigate interactions between Application, Hardware, and Scheduler, and its effects on desired metrics - execution time, energy, etc.

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

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/0__Papers/year1report/report.tex	Fri Jun 08 14:19:26 2012 +0200
     3.3 @@ -0,0 +1,52 @@
     3.4 +
     3.5 +\documentclass[11pt,a4paper]{article}
     3.6 +
     3.7 +\usepackage[german]{babel}
     3.8 +\usepackage{fullpage}
     3.9 +\usepackage[utf8]{inputenc}
    3.10 +
    3.11 +\begin{document}
    3.12 +\title{Hardwarebeschleunigung von paralleler Ablaufplanung für Multicoresysteme\\Zwischenbericht zum 1. Jahr}
    3.13 +\author{Nina Engelhardt}
    3.14 +\date{\today}
    3.15 +\maketitle
    3.16 +
    3.17 +
    3.18 +
    3.19 +\section{Aims}
    3.20 +
    3.21 +Ziel meiner Arbeit ist es, durch speziell angepasste Hardware die Synchronisation und Aufgabenverteilung für parallele Programme auf Multicoresystemen zu verbessern. Als Grundlage dient dafür das VMS-System, ein Framework dass es ermöglicht, Laufzeitumgebungen für verschiedenste parallele Programmiermodelle mit nur wenig Aufwand zu implementieren.
    3.22 +
    3.23 +In den ersten 6 Monaten habe ich wie geplant das VMS-System analysiert. VMS umfasst die Grundlegende Struktur, die allen Laufzeitumgebungen gemein ist: sie beinhaltet den Wechsel zwischen Programm und Laufzeitumgebung, und die Möglichkeit, eine Zeitliche Ordnung zwischen zwei Codepunkten in zwei virtuellen Prozessoren zu garantieren (semantikfreie Synchronisation). Auf Basis dieser Elemente muss der/die Laufzeitumgebungsentwickler\_in nur noch die jeweilige Semantik der parallelen Umgebung hinzufügen, in Form eines Plugins, dass Handlers für jedes parallele Konstrukt und einen Assigner, der entscheidet, welche Aufgaben als nächstes bearbeitet werden, bereitstellt.
    3.24 +
    3.25 +Diese zweiteilige Struktur ermöglicht zwei Ansatzpunkte für die Beschleunigung: den VMS-Kern selbst -- Verbesserungen an dieser Stelle kommen allen Laufzeitumgebungen zu Gute -- und das jeweilige Plugin. VMS ist minimal gehalten und bietet nur wenige Möglichkeiten zur Verbesserung, jedoch haben Änderungen hier den größten Effekt. VMS ist außerdem, da es die grundlegendsten Elemente zusammenfasst, bereits sehr nah an der existierenden Hardware und die häufigen Aufgaben sind gut unterstützt. Zusätzliche Beschleunigung kann hier nur durch sehr ressourcenintensive Lösungen (z.B. zusätzliche Registersätze für schnellen Kontextwechsel) erwartet werden.
    3.26 +Beschleuniger für Pluginfunktionen haben deutlich mehr Spielraum, besonders für Sprachen mit komplexen, hardwarefernen Konstrukten (und dies sind die besonders interessanten, weil sie sich der Struktur des Problems nähern und damit dem Programmierer die Arbeit abnehmen, das Problem in Hardwarenahe Konzepte umzudenken bzw. übersetzen zu müssen.) Da die Pluginfunktionen aber Sprachspezifisch sind, kommen Beschleunigungen an dieser Stelle nur dem Teil der Programme zugute, die in dieser Sprache geschrieben sind. Die Herausforderung wird also sein, Hardwareelemente zu finden, die möglichst flexible und vielfältige Verwendung finden können. Haupsächlich wird aber die Programmiersprache StarSs anvisiert werden, die im Fachgebiet AES häufig Verwendung findet.
    3.27 +
    3.28 +VMS ist die praktische Ausformulierung eines Modells des Parallelismus, die von Dr. Sean Halle unter dem Namen ``Holistic Model of Parallel Computation''[~] vorgeschlagen wurde. Dieses Modell isoliert die schedulingrelevanten Teile eines Programms und legt das Augenmerk besonders auf die Effekte von Scheduling Decisions auf die Performance.
    3.29 +
    3.30 +Während meiner Analyse von VMS stieß ich auf mehrere unklare Stellen in der Theorie, und habe diese in Zusammenarbeit mit Dr. Halle ausgearbeitet. Insbesondere habe ich das Modell um das Konzept der Schichten erweitert, das dem Umstand Rechnung trägt, dass in einem System meistens mehrere hierarchisch untergeordnete Scheduler existieren. So werden die Arbeitseinheiten, über die die Laufzeitumgebung als Eins entscheidet, möglicherweise vom Betriebssystem noch einmal unterbrochen und verteilt, spätestens aber vom Prozessor in kleinere Einheiten -- Assemblerbefehle -- zerteilt, und auf unterschiedliche Funktionseinheiten aufgeteilt. Im Fall von Out-of-order Prozessoren wird deutlich, das auch dies parallele Aufgabenverteilung ist, und das Holistische Modell auch auf diese anwendbar ist. Zur Zeit kollaborieren wir an einem Journal Article der das Holistische Modell detailliert darlegt. 
    3.31 +
    3.32 +Zu den Errungenschaften des Holistischen Modells gehören auch zwei grafische Darstellungen, die Unit Constraint Collection und der Scheduling Consequence Graph, deren Ziel es ist, die Gründe der (guten oder schlechten) Performance eines parallelen Programms ersichtlich zu machen. Die Unit Constraint Collection (kurz UCC) zeigt die Arbeitseinheiten (units) die im Programm definiert werden und die Randbedingungen (constraints) ihrer Ausfürbarkeit, die vom Programm selbst ausgehen. Der Consequence Graph (CG) repräsentiert eine realisierte Ausführung des Programms und zeigt die räumliche und zeitliche Platzierung der Arbeitseinheiten, die der Scheduler gewählt hat, sowie die unterschiedlichen Randbedingungen, die diese Wahl eingeschränkt haben. Diese können vom Programm selbst stammen, sich aus Ressourcenbegrenzungen ergeben, oder durch Beschränkungen der Laufzeitumgebung entstehen.
    3.33 +
    3.34 +
    3.35 +
    3.36 +\end{document}
    3.37 +
    3.38 +
    3.39 +-- what I did
    3.40 +-get into vms code, instrument it
    3.41 +-find vague places in theory, fix them
    3.42 +->find slowdowns in vms, lead to new version
    3.43 +->notice instrumentation + theory makes good perf tuning tool, write paper about that
    3.44 +->write paper about theory
    3.45 +
    3.46 +-- how it compares to projected plan
    3.47 +-first 6 months match
    3.48 +-then more theory than concrete solutions
    3.49 +->revealed 1 master probably not best solution
    3.50 +->revealed additional levels of performance issues not originally considered
    3.51 +
    3.52 +-- what I'm going to do next
    3.53 +-build hardware, but instead of putting accelerators only on 1 master core, experiment with how often to replicate accelerators
    3.54 +-assemblage of lm32 cores, each w/ non-coherent cache
    3.55 +-starss? w/ message passing for in/out