High-Level-Synthese aus flachen Kontroll-/Datenflussgraphen

Abstract

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.

Abstract

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.