Details

Abstrakt in Englisch

Embedded systems are more and more implemented as multi-processor systems. The growing number of applications running in parallel as well as the increasing complexity of the applications result in an increasing number of processors within those systems. Thus, the design space of such systems grows non-linearly. Design space exploration therefore tries to answer the following questions: “How many processors are necessary to fulfill the requirements defined by the application scenario?” and “How can the given application scenario be mapped to the parallel architecture appropriately?”

In existing approaches the applications are either manually or automatically mapped to the system. Performance figures are derived either analytically or by running simulations. The results are then used for modifying single applications or improving either architecture or mapping. Due to the complexity of the mapping problem, current approaches following this methodology are too time consuming to permit the exploration of huge design spaces. In this work an approach is presented, that enables global exploration via parallelism analysis. A mapping is not required until the candidate systems identified in the global exploration are inspected in more detail. It is shown that the mapping problem can be regarded as packing problem and solved with linear programming. The comparison of this reference point with the simple heuristic of list-scheduling will show that the latter produces comparatively good results at low computational complexity. This low complexity also allows for using the heuristic approach for dynamic mapping at run-time.

Abstrakt in Deutsch

Eingebettete Systeme werden zunehmend als Multi-Prozessor-Systeme umgesetzt. Die wachsende Anzahl parallel zu bearbeitender Applikationen sowie die steigende Komplexität der einzelnen Applikationen selbst führt dabei zu einer stetig steigenden Anzahl der Prozessoren in diesen Systemen, wodurch der zu betrachtende Entwurfsraum nicht-linear anwächst. Mit der Entwurfsraumexploration wird daher versucht, insbesondere folgende Fragen zu beantworten: “Welche und wie viele Prozessoren sind notwendig, um die aus dem Applikationsszenario resultierenden Anforderungen zu erfüllen?” sowie “Wie kann das gegebene Applikationsszenario sinnvoll auf die parallele Architektur abgebildet werden?”.

Bisherige Ansätze bilden dafür die einzelnen Applikationen manuell oder automatisch auf das zu untersuchende System ab und bestimmen die notwendigen Kennzahlen entweder analytisch oder mithilfe von Simulationen. Die so gewonnenen Ergebnisse werden dann zur Verbesserung einzelner Applikationen, der Architektur oder der Abbildung der Applikationen auf die Architektur verwendet. Bedingt durch die Komplexität des Problems der Bestimmung einer geeigneten Abbildung sind diese Ansätze jedoch zu zeitintensiv als dass sie die Exploration großer Entwurfsräume erlauben. In dieser Arbeit wird daher ein Ansatz vorgestellt, der die globale Exploration über Parallelitätsanalyse ohne die konkrete Abbildung der Applikation auf das System ermöglicht. Erst zur lokalen Optimierung des Systems wird auf die Methode der Abbildung der Applikation auf das System zurückgegriffen. Es wird gezeigt, dass dieses Problem als Packungsproblem aufgefasst und mit linearer Programmierung gelöst werden kann. Der Vergleich des so definierten Referenzpunkts mit der einfachen Heuristik des listenbasierten Schedulings wird zeigen, dass letzteres Vorgehen vergleichsweise gute Ergebnisse ohne das Iterieren über verschiedene Abbildungen liefert. Die geringe Komplexität des Ansatzes erlaubt zudem die Nutzung desselben zur dynamischen Abbildung der Applikationen auf das System zur Laufzeit.