<div class="csl-bib-body">
<div class="csl-entry">Knerr, B. (2008). <i>Heuristic optimisation methods for system partitioning in HW/SW Co-Design</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-26081</div>
</div>
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 />
de
dc.description.abstract
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Heuristiken
de
dc.subject
Partitionierung
de
dc.subject
Hardware Software Codesign
de
dc.subject
Eingebettete Systeme
de
dc.subject
Platform Abstraktion
de
dc.subject
Genetische Algorithmen
de
dc.subject
Tabu Suche
de
dc.subject
Simulated Annealing
de
dc.subject
Kernighan-Lin
de
dc.subject
Graphentheorie
de
dc.subject
Heuristics
en
dc.subject
Partitioning
en
dc.subject
Hardware Software Codesign
en
dc.subject
Embedded Systems
en
dc.subject
Platform Abstraction
en
dc.subject
Genetic Algorithm
en
dc.subject
Tabu Search
en
dc.subject
Simulated Annealing
en
dc.subject
Kernighan-Lin
en
dc.subject
Graph Theory
en
dc.title
Heuristic optimisation methods for system partitioning in HW/SW Co-Design
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Bastian Knerr
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Grimm, Christoph
-
tuw.publication.orgunit
E389 - Institut für Nachrichtentechnik und Hochfrequenztechnik
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC05038196
-
dc.description.numberOfPages
156
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-26081
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.orcid
0000-0001-9003-7779
-
item.openaccessfulltext
Open Access
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.grantfulltext
open
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openairetype
doctoral thesis
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E389 - Telecommunications
-
crisitem.author.parentorg
E350 - Fakultät für Elektrotechnik und Informationstechnik