Heuristic optimisation methods for system partitioning in HW/SW Co-Design

Abstract

Der Entwurf von eingebetteten Systemen ist heutzutage konfrontiert mit einer Kombination aus hochkomplexen Signalverarbeitungsalgorithmen und einer Vielzahl von rechenintensiven multimedialen Anwendungen. Erschwerend kommt hinzu, dass die Entwicklungszeit bis zum fertigen Produkt dramatisch verkürzt wurde.<br />Besonders innerhalb der mobilen Sparte, die Mobiltelefone, PDAs, und Kameras umfasst, werden diese grundsätzlichen Widrigkeiten noch erschwert durch beträchtliche Anforderungen bezuglich Leistungsaufnahme und Baugröße. Leider konnte die Entwurfsproduktivität nicht mit den ansteigenden Anforderungen Schritt halten, und kämpft bis heute mit der Heterogenität moderner Hardwarearchitektur. Werkzeuge für die Entwurfsautomatisierung offenbaren breite Lücken in ihrer Abdeckung der Entwurfsabfolge, insbesondere wurden bisher folgende Aufgaben nicht zufriedenstellend gelöst: Algorithmencharakterisierung auf höchster Abstraktionsebene, Konvertierung von Fließkomma- zu Fixpunktdarstellung, Systempartitionierung, und Virtual Prototyping. In den letzten Jahren wurde im Christian Doppler Labor für Designmethodik von Signalverarbeitungsalgorithmen eine Entwurfsumgebung, OTIE, entwickelt, die in konsistenter Weise die kritischsten Mängel des Entwurfsprozesses in diesem Bereich zu beheben versucht. Bis auf eines wurden die zuvor genannten Aufgaben mit OTIE in bemerkenswerter Weise gelöst. Der fehlende Entwurfsschritt Systempartitionierung vereint mit einer flexiblen Architekturmodellierung stellt das Thema dieser Dissertation dar.<br />Systempartitionierung ist ein Forschungsgegenstand, der in den letzten 15 Jahren beträchtliche Aufmerksamkeit von Forschungsgruppen im elektronischen Systementwurf erhielt. Aus diesem Grund existiert eine ebenso große Anzahl spezifischer Problemformulierungen wie jeweiliger Lösungsstrategien. Ihre Anwendbarkeit variiert stark mit dem gewählten Abstraktionsgrad des Plattformmodells und dessen Wirklichkeitstreue. In dieser Arbeit werden die tauglichsten Ansätze fur die Partitionierung von Prozessgraphen und in kleinerem Ausmaß jene fur deren Ablaufplanung identifiziert, um diese dann in OTIE zu integrieren. Ein detailliertes Architekturmodell wird vorgestellt, das außergewöhnliche Wirklichkeitstreue mit großer Flexibilität vereint. Mit diesem ist es nun möglich beliebige heterogene Plattformstrukturen zu modellieren, in denen z.B. mehrere Prozessoren, FPGAs, und ASICs mittels mehrerer Busse oder anderer Datenkanäle verbunden werden. Basierend auf diesem Fundament wird das Partitionierungsproblem analysiert und als kombinatorische Mehrzieloptimierung definiert. Weitergehend werden jene Graphen, die für eingebettete Systeme typisch sind, analysiert und deren Eigenschaften herausgearbeitet. Mit Hilfe der erlangten Erkenntnisse werden in dieser Arbeit neue spezialisierte Algorithmen für Partitionierung und Ablaufplanung entwickelt und bestehende Konzepte und Techniken verbessert.<br />

Nowadays, the design of embedded systems is confronted with the combination of complex signal processing algorithms on the one hand and a variety of computational intensive multimedia applications on the other hand, while time to product launch has been extremely reduced.<br />Especially in the wireless domain those challenges are stacked with tough requirements on power consumption and chip size. Unfortunately, design productivity did not undergo a similar progression and therefore fails to cope with the heterogeneity of modern hardware architectures.<br />Until now, electronic design automation do not provide for complete coverage of the design flow. In particular crucial design tasks as high level characterisation of algorithms, floating-point to fixed-point conversion, automated hardware/software partitioning, and automated virtual prototyping are not sufficiently supported or completely absent.<br />In recent years a consistent design framework named Open Tool Integration Environment (OTIE) has been established to address the most crucial shortcomings of the wide spread design problems in this field.<br />As integral part of the OTIE framework powerful tool chains exist that support high level estimation techniques for algorithm characteristics, static code analysis, automatic generation of virtual prototypes, floating-point to fixed-point conversion, and so forth. A very substantial ingredient of OTIE was missing until now: a rich library for architecture modelling of embedded system and algorithms for their precise partitioning and scheduling. Therefore, this thesis examines the research field of system partitioning of embedded systems in the wireless design domain.<br />This field started to find strong advertence of scientists about fifteen years ago. Since a multitude of formulations for the partitioning problem exist, the same multitude could be found in the number of strategies that address this problem. Their feasibility is highly dependent on the platform abstraction and the degree of realism that it features. This thesis identifies the most mature and powerful approaches for system partitioning and to some degree task scheduling in order to integrate them into the OTIE framework. The contribution of this work involves a detailed platform abstraction that combines a high degree of realism with the flexibility to compose arbitrary multi-core multi-bus structures and the theoretical underpinning of the system partitioning in wireless embedded system design as combinatorial optimisation problem. Furthermore, a thorough analysis of the properties of typical system graphs is undertaken. Eventually, the implementation and improvement of the most popular strategies, and the introduction of entirely new algorithms for the system partitioning and scheduling problem is accomplished.