Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-860
Main Title: High-Level-Synthese aus flachen Kontroll-/Datenflussgraphen
Translated Title: High-Level-Synthesis from flat Control-/Dataflowgraphs
Author(s): Gremzow, Carsten
Advisor(s): Post, Hans-Ulrich
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: German
Language Code: de
Abstract: Das Gebiet der Verhaltenssynthese (engl. High-Level-Synthesis) beschäftigt sich mit der rechnergestützten Ableitung von Register-Transfer-Strukturen aus algorithmischen Schaltungsspezifikationen. Als zentrales Problem stellt sich hierbei die effektive Zuordnung von Operationen der Spezifikation zu arithmetisch/logischen Funktionseinheiten unter Einhaltung der Syntheserandbedingungen - dem Scheduling - heraus. Sowohl gegenwärtige exakte als auch heuristische Ansätze zur Lösung des Scheduling-Problems sind in erster Linie für eine lokale Anwendung auf Basisblöcke geeignet, d. h. Zustandszuteilung und Funktionseinheitenauswahl erfolgen jeweils auf Operationsfolgen eines einzelnen Kontrollflusszustandes. Folglich kann das Hauptoptimierungspotenzial, die Ausnutzung inhärenter Operatorparallelität, auch nur auf der Ebene eines Basisblocks ausgeschöpft werden. Die kontrollflussübergreifende Entwicklung des Operationsflusses bleibt außer Acht. Einen weiteren Aspekt, der beim Entwurf von High-Level-Syntheseverfahren nicht nachhaltig berücksichtigt wurde, stellt die Integration der Zielschaltung in das Systemumfeld dar. Die bisherige Herangehensweise, Operanden und Ergebnisse im lokalen Speicher zu verwalten, kann gerade für komplexere Anwendungen zu leistungs- und flächenineffizienten Ergebnissen führen. Stattdessen sehen Architekturen des modernen Systementwurfs (System-On-Chip) immer häufiger zentralistische Speichermodelle vor, in denen Komponenten über dedizierte Speicherkanäle Anbindung finden. Diese Kanäle stellen eine begrenzte Ressource dar und erfordern eine entsprechende Berücksichtigung in den Phasen der High-Level-Synthese. In dieser Arbeit wird ein Ansatz zur Verschmelzung von Kontroll- und Datenfluss in eine integrale Darstellung vorgestellt und es werden Methoden zur Ablaufplanung und Bereitstellung von Funktionseinheiten auf dieser hybriden Darstellung erarbeitet. Die Ausflachung des Kontroll- Datenflusses erlaubt es, kontrollflussübergreifend datenunabhängige Operationsfolgen zu identifizieren und im Rahmen der verfügbaren Funktionseinheiten zeitgleich auszuführen. Dadurch kann eine deutliche Erhöhung des Parallelitätsgrades in der erzeugten Schaltung erreicht und die Ausführungszeit verkürzt werden. Neben der expliziten Ausnutzung kontroll- flussübergreifender Parallelität wird ebenfalls untersucht, inwieweit eine spekulative, parallele Ausführung alternativer Operationssequenzen zur weiteren Verbesserung der Syntheseergebnisse beitragen kann. Im Gegensatz zu den bisherigen Ansätzen erlaubt das vorliegende Syntheseverfahren auch eine Zustandszuteilung bei eingeschränkten Speicherkanälen und nutzt diese möglichst effizient zum Operandentransfer aus. Anhand quantitativer Untersuchungen der Synthesergebnisse für nichttriviale Algorithmen, wie z. B. dem ADPCM-Sprachcodec des ITU-G.723-Standards, kann gezeigt werden, dass durch eine Verhaltenssynthese auf der Basis flacher Kontroll-/Datenflussgraphen eine Verkürzung des maximalen Taktzyklenbedarfs zwischen 25% und 39% gegenüber den konventionellen High-Level-Syntheseverfahren erreicht werden kann. Dabei erzielen die vorgestellten Syntheseverfahren die erwähnten Verbesserungen insbesondere für Algorithmen, die einen Kontrollflussanteil von mehr als 30% aufweisen und sind somit für einfache Filterstrukturen weniger geeignet. Es ist zu beobachten, dass eine explizite Parallelisierung mehrerer Kontroll- flüsse auch zu merklich komplexeren Steuerwerken führt, welches in Anbetracht der heute erreichbaren Integrationsdichten jedoch tolerierbar erscheint.
Previous works concerned with the automatic construction of register transfer level descriptions from behavioral specifications focused primarily on solving central synthesis tasks - scheduling, allocation and binding of operations - both under resource and time constraints in minimum execution time. With the advent of complex, digital SoC designs, the aspect of limited resources for operand transfers - a circumstance related to the central memory architecture found in current system architecture motivated by economic aspects - need to be considered for successful application of the high-level synthesis flow in Hardware-/Software Codesign. Although numerous heuristics as well exact methods have been proposed to solve the NPhard high-level synthesis problem, the are usually restricted to the scope of a single basic block and not suitable for the synthesis of complex algorithmic problems featuring none trivial control flow behavior. For this reason, folded control-/dataflow graphs with petri-net like semanics have been chosen for an integral representation of control- and dataflow information in a single graph. The latter is the basis for a graph analysis and optimization algorithm introducing the notion of speculative operator execution into the scheduling process and thus increases the potential of increased system performance and improved resource usage.With respect to efficiently exploiting the inherent parallelism in an algorithmic problem, a method for the clustering of the specification petri net into concurrent operator subgraphs is presented. In the same context, long term data dependencies are analyzed with respect to their potential of creating optimized datapaths employing function unit feedback and reducing memory transfer cycles. As a result, operator subgraphs are transformed into highly specialized function units - so called macro operation blocks - also contributing to increased system performance and resource usage. In addition, a novel heuristic for simultaneous scheduling, binding and datapath construction under datapath constraints is proposed, implemented and evaluated in this work. The outlined algorithms are capable of constructing interconnect cost optimized datapaths suitable for central memory architectures with limited read and write port resources such as register file or central memory controller based ASPs. Applying computation time efficient look-ahead heuristics datapaths and controllers with a minimum of interconnect cost and propagation delay caused by multiplexers can be synthesized. In experiments performed on standard high-level bench marks as well as a number of speech coding algorithms the overall execution time was reduced by 25% to 33% as compared to conventional synthesis methods. However explicit parallelization and execution speedups can only be expected for algorithms with a minimum controlflow portion of at least 30% and usually calls for a dramatic increase in finite state automata complexity.
URI: urn:nbn:de:kobv:83-opus-7618
http://depositonce.tu-berlin.de/handle/11303/1157
http://dx.doi.org/10.14279/depositonce-860
Exam Date: 6-Feb-2004
Issue Date: 15-Mar-2004
Date Available: 15-Mar-2004
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Ausflachung
Digitale Systeme
Entwurfsautomatisierung
Register-Transfer-Strukturen
Verhaltenssynthese
Design Automation
Digital Systems
Flattening
High-Level-Synthesis
Register-Transfer-Level
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_17.pdf1.47 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.