TY - THES A1 - Wist, Dominic T1 - Attacking complexity in logic synthesis of asynchronous circuits T1 - Komplexitätsbewältigung in der Logiksynthese asynchroner Schaltungen N2 - Most of the microelectronic circuits fabricated today are synchronous, i.e. they are driven by one or several clock signals. Synchronous circuit design faces several fundamental challenges such as high-speed clock distribution, integration of multiple cores operating at different clock rates, reduction of power consumption and dealing with voltage, temperature, manufacturing and runtime variations. Asynchronous or clockless design plays a key role in alleviating these challenges, however the design and test of asynchronous circuits is much more difficult in comparison to their synchronous counterparts. A driving force for a widespread use of asynchronous technology is the availability of mature EDA (Electronic Design Automation) tools which provide an entire automated design flow starting from an HDL (Hardware Description Language) specification yielding the final circuit layout. Even though there was much progress in developing such EDA tools for asynchronous circuit design during the last two decades, the maturity level as well as the acceptance of them is still not comparable with tools for synchronous circuit design. In particular, logic synthesis (which implies the application of Boolean minimisation techniques) for the entire system's control path can significantly improve the efficiency of the resulting asynchronous implementation, e.g. in terms of chip area and performance. However, logic synthesis, in particular for asynchronous circuits, suffers from complexity problems. Signal Transitions Graphs (STGs) are labelled Petri nets which are a widely used to specify the interface behaviour of speed independent (SI) circuits - a robust subclass of asynchronous circuits. STG decomposition is a promising approach to tackle complexity problems like state space explosion in logic synthesis of SI circuits. The (structural) decomposition of STGs is guided by a partition of the output signals and generates a usually much smaller component STG for each partition member, i.e. a component STG with a much smaller state space than the initial specification. However, decomposition can result in component STGs that in isolation have so-called irreducible CSC conflicts (i.e. these components are not SI synthesisable anymore) even if the specification has none of them. A new approach is presented to avoid such conflicts by introducing internal communication between the components. So far, STG decompositions are guided by the finest output partitions, i.e. one output per component. However, this might not yield optimal circuit implementations. Efficient heuristics are presented to determine coarser partitions leading to improved circuits in terms of chip area. For the new algorithms correctness proofs are given and their implementations are incorporated into the decomposition tool DESIJ. The presented techniques are successfully applied to some benchmarks - including 'real-life' specifications arising in the context of control resynthesis - which delivered promising results. N2 - Moderner Schaltungsentwurf fokussiert hauptsächlich synchrone Schaltungstechnik mit allen inhärenten Problemen. Asynchone (d.h. ungetaktete) Schaltungen zeichnen sich jedoch nicht nur durch das Fehlen der Taktversatzproblematik gegenüber ihren synchronen Pendents aus, sondern auch insbesondere durch geringeren Energieverbrauch, günstigere EMV-Eigenschaften, hohe Performance, Modularität und Robustheit gegenüber Schwankungen in der Spannungsversorgung, im Herstellungsprozess sowie Temperaturunterschieden. Diese Vorteile werden mit höherer Integration sowie höheren Taktraten signifikanter. Jedoch ist der Entwurf und auch der Test asynchroner Schaltungen erheblich schwieriger verglichen mit synchronen Schaltungen. Entwurfswerkzeuge zur Synthese asynchroner Schaltungen aus Hochsprachen-Spezifikationen sind zwar inzwischen verfügbar, sie sind jedoch noch nicht so ausgereift und bei weitem noch nicht so akzeptiert in der Industrie, wie ihre Äquivalente für den synchronen Schaltungsentwurf. Insbesondere fehlt es an Werkzeugunterstützung im Bereich der Logiksynthese komplexer Steuerungen („Controller“), welche kritisch für die Effizienz – z.B. in Bezug auf Chipfläche und Geschwindigkeit – der resultierenden Schaltungen oder Systeme ist. Zur Spezifikation von Steuerungen haben sich Signalflankengraphen („signal transition graphs“, STGs) bewährt, die auch als Entwurfseinstieg für eine Logiksynthese von SI-Schaltungen („speed independent“) verwendet werden. (SI-Schaltungen gelten als sehr robuste asynchrone Schaltungen.) Aus den STGs werden zwecks Logiksynthese Automaten abgeleitet werden, deren Zustandszahl aber oft prohibitiv groß werden kann. Durch sogenannte STG-Dekomposition wird die Logiksynthese einer komplexen Schaltung ermöglicht, was bislang aufgrund von Zustandsexplosion oft nicht möglich war. Dabei wird der Spezifikations-STG laut einer gegebenen Partition von Ausgangssignalen in viele kleinere Teilnetze dekomponiert, wobei zu jedem Partitionsblock ein Teilnetz – mit normalerweise signifikant kleinerem Zustandsraum im Vergleich zur Spezifikation – erzeugt wird. Zu jedem Teilnetz wird dann eine Teilschaltung (Komponente) mittels Logiksynthese generiert. Durch die Anwendung von STG-Dekomposition können jedoch Teilnetze erzeugt werden, die sogenannte irreduzible CSC-Konflikte aufweisen (d.h. zu diesen Teilnetzen kann keine SI-Schaltung erzeugt werden), obwohl die Spezifikation keine solchen Konflikte hatte. Diese Arbeit präsentiert einen neuen Ansatz, welcher die Entstehung solcher irreduziblen Konflikte vermeidet, und zwar durch die Einführung interner Kommunikation zwischen den (zu den Teilnetzen gehörenden) Schaltungskomponenten. Bisher werden STG-Dekompositionen total durchgeführt, d.h. pro resultierender Komponente wird ein Ausgangssignal erzeugt. Das führt gewöhnlich nicht zu optimalen Schaltungsimplementierungen. In dieser Arbeit werden Heuristiken zur Bestimmung gröberer Ausgabepartitionen (d.h. Partitionsblöcke mit mehreren Ausgangssignalen) vorgestellt, die zu kleineren Schaltungen führen. Die vorgestellten Algorithmen werden formal abgesichert und wurden in das bereits vorhandene Dekompositionswerkzeug DESIJ integriert. An praxisrelevanten Beispielen konnten die vorgestellten Verfahren erfolgreich erprobt werden. KW - Asynchrone Schaltung KW - Logiksynthese KW - Komplexitätsbewältigung KW - STG-Dekomposition KW - CSC KW - asynchronous circuit KW - logic synthesis KW - speed independence KW - STG decomposition KW - CSC Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-59706 ER - TY - JOUR A1 - Wist, Dominic A1 - Wollowski, Ralf A1 - Schaefer, Mark A1 - Vogler, Walter T1 - Avoiding irreducible CSC conflicts by internal communication N2 - Resynthesis of handshake specifications obtained e. g. from BALSA or TANGRAM with speed-independent logic synthesis from STGs is a promising approach. To deal with state-space explosion, we suggested STG decomposition; a problem is that decomposition can lead to irreducible CSC conflicts. Here, we present a new approach to solve such conflicts by introducing internal communication between the components. We give some first, very encouraging results for very large STGs concerning synthesis time and circuit area. Y1 - 2009 UR - http://iospress.metapress.com/content/300178/ U6 - https://doi.org/10.3233/Fi-2009-140 SN - 0169-2968 ER - TY - JOUR A1 - Wist, Dominic A1 - Schaefer, Mark A1 - Vogler, Walter A1 - Wollowski, Ralf T1 - Signal transition graph decomposition internal communication for speed independent circuit implementation JF - IET Computers and digital techniques N2 - Logic synthesis of speed independent circuits based on signal transition graph (STG) decomposition is a promising approach to tackle complexity problems like state-space explosion. Unfortunately, decomposition can result in components that in isolation have irreducible complete state coding conflicts. In earlier work, the authors showed how to resolve such conflicts by introducing internal communication between components, but only for very restricted specification structures. Here, they improve their former work by presenting algorithms for identifying delay transitions and inserting gyroscopes for specifications having a much more general structure. Thus, the authors are now able to synthesise controllers from real-life specifications. For all algorithms, they present correctness proofs and show their successful application to benchmarks, including very complex STGs arising in the context of control resynthesis. Y1 - 2011 U6 - https://doi.org/10.1049/iet-cdt.2010.0162 SN - 1751-8601 VL - 5 IS - 6 SP - 440 EP - 451 PB - Institution of Engineering and Technology CY - Hertford ER - TY - BOOK A1 - Wist, Dominic A1 - Wollowski, Ralf T1 - STG decomposition : avoiding irreducible CSC conflicts by internal communication N2 - Inhalt: 1 Introduction 2 Basic Definitions 3 Achieving SI Implementability by Internal Communication 4 Towards a Structural Method 5 Examples 6 Conclusions and Future Work T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 20 Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-32968 SN - 978-3-940793-02-7 ER - TY - BOOK A1 - Wist, Dominic A1 - Schaefer, Mark A1 - Vogler, Walter A1 - Wollowski, Ralf T1 - STG decomposition : internal communication for SI implementability N2 - STG decomposition is a promising approach to tackle the complexity problems arising in logic synthesis of speed independent circuits, a robust asynchronous (i.e. clockless) circuit type. Unfortunately, STG decomposition can result in components that in isolation have irreducible CSC conflicts. Generalising earlier work, it is shown how to resolve such conflicts by introducing internal communication between the components via structural techniques only. N2 - STG-Dekomposition ist ein bewährter Ansatz zur Bewältigung der Komplexitätsprobleme bei der Logiksynthese von SI (speed independent) Schaltungen – ein robuster asynchroner (d.h. ohne Taktsignal arbeitender digitaler) Schaltungstyp. Allerdings können dabei Komponenten mit irreduziblen CSC-Konflikten entstehen. Durch Verallgemeinerung früherer Arbeiten wird gezeigt, wie solche Konflikte durch Einführung interner Kommunikation zwischen den Komponenten gelöst werden können, und zwar ausschließlich durch Verwendung an der Graphenstruktur ansetzender Verfahren. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 32 KW - Asynchrone Schaltung KW - Petrinetz KW - Signalflankengraph (SFG oder STG) KW - STG-Dekomposition KW - speed independent KW - CSC KW - Controller-Resynthese KW - Asynchronous circuit KW - petri net KW - signal transition graph KW - STG decomposition KW - speed independent KW - CSC KW - control resynthesis Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-40786 SN - 978-3-86956-037-3 PB - Universitätsverlag Potsdam CY - Potsdam ER -