[Back]

M. Holzer:
"Design Space Exploration for the Development of Embedded Systems";
Supervisor, Reviewer: M. Rupp, A. Jantsch; Institut für Nachrichten- und Hochfrequenztechnik, 2008; oral examination: 04-14-2008.

The evolution of electronic devices has made a tremendous progress within the last 50 years. In today's world they can be found nearly everywhere, such as cell phones, camcorders, and antiblock-brakes. The design of such complex systems, that consist of hardware and software has to cope with several obstacles like for example high system complexity and increasing economical demands like shortened time-to-market. Those barriers become especially visible in the wireless domain. Here, design productivity lacks behind the possible computational complexity famously described by Moore's law. The importance to cope efficiently with these problems of system design has been highlighted by the International Technology Roadmap for Semiconductors. This thesis examines one of the design tasks namely design space exploration. Since the description of systems raises constantly its level of abstraction which causes a higher ability for exploring design variants, the automatic derivation of alternatives becomes a high importance. Current approaches for design space exploration are based on manual exploration and hence suffer from a time consuming exploration, leading to sub-optimal solutions. Even automated approaches are restricted due to the high system complexity and need to be enhanced. In this thesis a fast and efficient design space exploration approach is proposed. This is based on the characterisation of a system description, the estimation of design properties, and the automatic evaluation of design variants. Thus, as first step a set of system description properties is derived that builds a basis for an initial quantitative description of an algorithm. This system characterisation is embedded in a design framework the Open Tool Integration Environment (OTIE) that closes the fragmentation of the design flow, caused by incompatible tools. This framework exhibits its ability for representing a design at various abstraction levels. Another important ingredient for the design space exploration is the fast and accurate estimation of final implementation properties such as area consumption and execution time. In this thesis an estimation model for predicting the execution cycle count and the hardware complexity is proposed based on the aforementioned metrics. Those rapid estimation methods that are based on static characterisation preserve relative ordering where a fidelity value of 100\% is achievable. Furthermore, those estimations are applied to the characterisation of one function regarding its timing profile and the minimisation of the overall execution time for structural verification. A new method which combines execution time profiling and feasible path analysis of the control flow graph is presented. This allows for exact estimation of the process run time interval. Furthermore, a new extension of Poole's algorithm for identifying a basis is presented that allows for reducing the time effort for structural verification significantly. Finally, the various implementation variants of an algorithm have to be efficiently explored to achieve optimal designs. Those variants are determined by algorithmic transformations like loop unrolling or tree height reduction. The exponential growth of this implementation variants with the system size causes an impossible coverage of the complete design space. Hence, an evolutionary algorithm with a two-staged fitness function and an extreme value elitism feature is presented that allows for increasing the coverage of the design space exploration by more than 20\% compared to existing approaches. Furthermore, the trade-offs for time and area for a given task set are utilised to increase the efficiency of a schedule for run-time reconfigurable systems. An algorithm is presented that reduces the number of design alternatives that are used for the scheduling. A depth first search algorithm is applied that constructs solutions in feasible time compared to a classical level strip packing formulation with comparable performance results. With the extension to a heuristic algorithm the typical run time is further reduced to several seconds.

Die Entwicklung elektronischer Geräte hat innerhalb der letzten 50 Jahre enorme Fortschritte gemacht. Elektronische Komponenten können in fast allen Bereichen des täglichen Lebens angetroffen werden, wie z.B. in Mobiltelefonen, Camcordern, oder Antiblockiersystemen. Die Entwicklung von diesen Systemen bestehend aus Hardware und Software hat einige technische Schwierigkeiten, wie z.B. hohe Systemkomplexität und ökonomischen Anforderungen wie die immer kürzer werdenden Produktzyklen zu überwinden. Diese Barrieren treffen im besonderen Maß auf den Mobilkommunikationsbereich zu. Hier werden wesentlich höhere Fortschritte im Bereich der physikalischen Integration von Transistoren, bestimmt durch das Mooresche Gesetz, als bei der Entwicklungsproduktivität erzielt. Die entscheidende Bedeutung einer automatisierten Entwicklung zur Produktivitätssteigerung wurde bereits von der International Technology Roadmap for Semiconductors aufgezeigt. Diese Arbeit befasst sich mit einem bestimmten Arbeitsschritt, nämlich der Analyse des Entwurfsraums, wobei einer automatischen Analyse immer größere Bedeutung zukommt. Zur Zeit wird diese Aufgabe mit hohem zeitlichen Aufwand manuell durchgeführt und führt oft nur zu suboptimalen Lösungen. Sogar automatisierte Ansätze stoßen aufgrund der Systemkomplexität schnell an ihre Grenzen. In dieser Arbeit wird eine schnelle und effiziente Entwurfsraumanalyse basierend auf einer statischen Analyse der Systembeschreibung, einer schnellen Schätzung von Implementierungsaspekten und der effizienten Generierung von Implementierungsalternativen vorgestellt. Dazu wird zuerst eine algorithmische Beschreibung analysiert und markante Metriken ermittelt, um eine quantifizierte Charakterisierung zu erhalten. Diese automatische Systemcharakterisierung ist in eine Entwicklungsumgebung namens Open Tool Integration Environment (OTIE) eingebettet, welche die Lücken im Entwicklungsfluss bedingt durch inkompatible Entwicklungsprogramme schließt. Diese Entwicklungsumgebung erlaubt es, die unterschiedlichen Abstraktionsebenen einer Systembeschreibung zu erfassen.
Ein weiterer wichtiger Schritt zur Entwurfsraumermittlung ist die genaue und schnelle Abschätzung von Implementierungseigenschaften wie z.B. Ausführungszeit und Flächenverbrauch mittels der zuvor beschriebenen Metriken. Diese schnellen Schätzmethoden basierend auf statischen Metriken erhalten die relative Ordnung zueinander wobei ein Zuversichtswert von 100% erreicht wird. Diese Schätzungsmethoden werden verwendet, um eine Funktion bezüglich ihres Ausführungszeitprofils zu charakterisieren und um den Verifikationsaufwand für strukturelles Testen zu minimieren. Eine neue Methode, die Ausführungszeitanalyse und zulässige Pfadanalyse kombiniert, wird vorgestellt. Diese Methode erlaubt eine exakte Abschätzung des Laufzeitintervalls. Weiters wird eine Erweiterung des Pooleschen Algorithmus zur Bestimmung einer Verifikationsbasis vorgestellt, die den zeitlichen Aufwand für strukturelles Testen erheblich reduziert. Zuletzt bestimmen Implementierungsvarianten aufgrund algorithmischer Transformationen wie z.B. loop-unrolling den zu untersuchenden Entwurfsraum. Das exponentielle Wachstum dieser Varianten mit der Systemgröße macht es aber unmögliche diese Varianten vollständig aufzuzählen. Ein genetischer Algorithmus mit einer zweiphasigen Fitnessfunktion und einem Elitismusschema wird vorgestellt, der eine Verbesserung der Entwurfsraumabdeckung von mehr als 20% gegenüber bestehen Methoden erreicht. Weiters wird diese Entwurfsraumanalyse verwendet, um die Ausnutzung von zur Laufzeit rekonfigurierbarer Systeme zu erhöhen. Ein Algorithmus wird vorgestellt, der die Anzahl von Implementierungsalternativen reduziert, um die Problemgröße zu verkleinern. Weiters wird eine Tiefensuche wird verwendet, um eine Lösung verglichen mit einer klassischen Formulierung als ganzzahliges lineares Programmierungsproblem mit praktikablen Zeitauwand zu erreichen. Eine weitere Erweiterung von diesem Algorithmus zu einer Heuristik reduziert die Laufzeit auf wenige Sekunden.

http://publik.tuwien.ac.at/files/pub-et_13743.pdf