Holzer, M. (2008). Design space exploration for the development of embedded systems [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-16769
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.<br />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. 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. Zuletzt bestimmen Implementierungsvarianten aufgrund algorithmischer Transfomationen 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 problemspezifischen Erweiterungen wird in dieser Arbeit vorgestellt, der eine hohe Abdeckung bei kurzer Ausführungszeit erzielt.<br />Schlussendlich ist die Entwurfsraumanalyse in eine Entwicklungsumgebung namens Open Tool Integration Environment (OTIE) eingebettet, das die Lücken im Entwicklungsfluss bedingt durch inkompatible Entwicklungsprogramme schließt. Diese Entwicklungsumgebung erlaubt es, die unterschiedlichen Abstraktionsebenen einer Systembeschreibung zu erfassen.<br />
de
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, antiblock-brakes.<br />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.<br />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. 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.<br />In this thesis an estimation model for predicting the execution cycle count and the hardware complexity is proposed based on the aforementioned metrics. Finally, the various implementation variants of an algorithm have to be efficiently explored to achieve optimal designs.<br />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 problem specific extensions is proposed that achieves a high coverage of the design space in feasible time.<br />The design space exploration 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.