Titelaufnahme

Titel
Heuristic optimisation methods for system partitioning in HW/SW Co-Design / Bastian Knerr
VerfasserKnerr, Bastian
Begutachter / BegutachterinRupp, Markus ; Grimm, Christoph
Erschienen2008
UmfangXIII, 156 S. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2008
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)Heuristiken / Partitionierung / Hardware Software Codesign / Eingebettete Systeme / Platform Abstraktion / Genetische Algorithmen / Tabu Suche / Simulated Annealing / Kernighan-Lin / Graphentheorie
Schlagwörter (EN)Heuristics / Partitioning / Hardware Software Codesign / Embedded Systems / Platform Abstraction / Genetic Algorithm / Tabu Search / Simulated Annealing / Kernighan-Lin / Graph Theory
Schlagwörter (GND)Eingebettetes System / CASHE / Partitionierung / Heuristik
URNurn:nbn:at:at-ubtuw:1-26081 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Heuristic optimisation methods for system partitioning in HW/SW Co-Design [15.7 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

error: u'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\xfcrzt wurde.

Besonders innerhalb der mobilen Sparte, die Mobiltelefone, PDAs, und Kameras umfasst, werden diese grunds\xe4tzlichen Widrigkeiten noch erschwert durch betr\xe4chtliche Anforderungen bezuglich Leistungsaufnahme und Baugr\xf6\xdfe. Leider konnte die Entwurfsproduktivit\xe4t nicht mit den ansteigenden Anforderungen Schritt halten, und k\xe4mpft bis heute mit der Heterogenit\xe4t moderner Hardwarearchitektur. Werkzeuge f\xfcr die Entwurfsautomatisierung offenbaren breite L\xfccken in ihrer Abdeckung der Entwurfsabfolge, insbesondere wurden bisher folgende Aufgaben nicht zufriedenstellend gel\xf6st: Algorithmencharakterisierung auf h\xf6chster Abstraktionsebene, Konvertierung von Flie\xdf\x19komma- zu Fixpunktdarstellung, Systempartitionierung, und Virtual Prototyping. In den letzten Jahren wurde im Christian Doppler Labor f\xfcr Designmethodik von Signalverarbeitungsalgorithmen eine Entwurfsumgebung, OTIE, entwickelt, die in konsistenter Weise die kritischsten M\xe4ngel des Entwurfsprozesses in diesem Bereich zu beheben versucht. Bis auf eines wurden die zuvor genannten Aufgaben mit OTIE in bemerkenswerter Weise gel\xf6st. Der fehlende Entwurfsschritt Systempartitionierung vereint mit einer flexiblen Architekturmodellierung stellt das Thema dieser Dissertation dar.

Systempartitionierung ist ein Forschungsgegenstand, der in den letzten 15 Jahren betr\xe4chtliche Aufmerksamkeit von Forschungsgruppen im elektronischen Systementwurf erhielt. Aus diesem Grund existiert eine ebenso gro\xdfe Anzahl spezifischer Problemformulierungen wie jeweiliger' error: u'L\xf6sungsstrategien. Ihre Anwendbarkeit variiert stark mit dem gew\xe4hlten Abstraktionsgrad des Plattformmodells und dessen Wirklichkeitstreue. In dieser Arbeit werden die tauglichsten Ans\xe4tze fur die Partitionierung von Prozessgraphen und in kleinerem Ausma\x19\xdf jene fur deren Ablaufplanung identifiziert, um diese dann in OTIE zu integrieren. Ein detailliertes Architekturmodell wird vorgestellt, das au\x19\xdfergew\xf6hnliche Wirklichkeitstreue mit gro\x19\xdfer Flexibilit\xe4t vereint. Mit diesem ist es nun m\xf6glich beliebige heterogene Plattformstrukturen zu modellieren, in denen z.B. mehrere Prozessoren, FPGAs, und ASICs mittels mehrerer Busse oder anderer Datenkan\xe4le verbunden werden. Basierend auf diesem Fundament wird das Partitionierungsproblem analysiert und als kombinatorische Mehrzieloptimierung definiert. Weitergehend werden jene Graphen, die f\xfcr eingebettete Systeme typisch sind, analysiert und deren Eigenschaften herausgearbeitet. Mit Hilfe der erlangten Erkenntnisse werden in dieser Arbeit neue spezialisierte Algorithmen f\xfcr Partitionierung und Ablaufplanung entwickelt und bestehende Konzepte und Techniken verbessert.

'

Zusammenfassung (Englisch)

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.

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.

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.

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.

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.

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.