Decomposition of signal transition graphs for the synthesis of asynchronous circuits

• Applicants: Professor Dr. Walter Vogler; Dr.-Ing. Ralf Wollowski
• Subject Area: Electronic Semiconductors, Components and Circuits, Integrated Systems, Sensor Technology, Theoretical Electrical Engineering
• Term: from 2000 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5290343

• Final Report Year: 2010

Final Report Abstract

Asynchrone Schaltungen haben im Gegensatz zu ihren weiter verbreiteten synchronen Pendants kein Taktsignal. Als Konsequenz ergeben sich viele potentielle Vorzüge wie geringerer Energieverbrauch, günstigere EMV-Eigenschaften, hohe Geschwindigkeit, Robustheit gegenüber Spannungs-, Temperatur- und Verzögerungsschwankungen sowie fertigungsprozess-bedingter Variationen. Insbesondere treten keine Taktversatzprobleme auf, welche den synchronen Entwurf – aufgrund weiterhin steigender Chip-Komplexität – zunehmend erschweren. Deswegen erwartet die “International Technology Roadmap on Semiconductors” auch ein rapides Wachstum bei den Schaltungskomponenten, die über asynchrone Handshake-Protokolle kommunizieren. Allerdings sind asynchrone Schaltungen weitaus schwieriger zu entwerfen als synchrone. Zur breiten industriellen Anwendung asynchroner Technik fehlen bislang vor allem die ausgereiften Entwurfsalgorithmen und -werkzeuge, die eine durchgängig automatische Generierung konkurrenzfähiger Schaltungen ermöglichen. Das Projekt hat einen Beitrag zur Verbesserung von Werkzeugen geleistet, die eine – im synchronen Bereich grundsätzlich Anwendung findende - Logiksynthese des Steuerungsteils von Schaltungen ermöglichen. Zur Spezifikation asynchroner Steuerungen haben sich signalflanken-interpretierte Petrinetze (signal transition graphs, STGs), bewährt. Die Logiksynthese einer asynchronen Schaltung aus einem Spezifikations-STG erfordert die Konstruktion des Erreichbarkeitsgraphen bzw. des State Graph. Die dabei auftretende Zustandsexplosion setzt diesem Vorgehen enge Grenzen. Daher wurde vorgeschlagen, die Spezifikation in STG-Komponenten zu zerlegen, die zusammen das Verhalten der Spezifikation implementieren. Dieses Dekompositionsverfahren wurde im Projekt - stark verallgemeinert und formal als korrekt bewiesen, - in verschiedener Hinsicht effizienzsteigernd für einen breiteren Einsatz verbessert sowie - effizient implementiert und getestet (Tool DesiJ). Besondere Aufmerksamkeit verdienen Verfahrensverbesserungen mit dem Ziel, die Schaltkreis-Realisierung mit dem derzeit wichtigsten Syntheseverfahren, dem sog. SI-Verfahren, zu ermöglichen. Die hierzu nötige Auflösung bzw. Vermeidung sog. CSC-Konflikte konnte für eine Vielzahl der praktisch auftretenden Fälle erreicht werden. Diese DesiJ-Version bildet auch eine Grundlage, auf der nun erstmals die Flexibilität des Dekompositionsverfahrens bei der Partitionsbildung ausgelotet werden kann bzgl. der Auswirkungen auf die Schaltungsqualität (Fläche, Energieverbrauch, Performance). Erfolgversprechendste Anwendungsmöglichkeit von DesiJ scheint momentan die Integration von DesiJ in den Designflow des industrienahen Balsa-Entwurfssystems zu sein, um dort im Rahmen einer Resynthese die Optimierung des Control-Teils zu ermöglichen.

Publications

• Canonical Prefixes of Petri Net Unfoldings. In CAV 2002: 14th Computer-Aided Verification. Springer, Lect. Notes Comput. Sci. 2404 (2002) 582 – 595
  V. Khomenko, M. Koutny, W. Vogler
  
• Decomposition in asynchronous circuit design. In FSTTCS 2002: 22nd Foundations of Software Technology and Theoretical Computer Science, Springer, Lect. Notes Comput. Sci. 2556 (2002) 336 – 347
  W. Vogler, R. Wollowski
  
• Decomposition in asynchronous circuit design. In: Concurrency and Hardware Design. Springer, Lect. Notes Comput. Sci. 2549, 152 – 190 (2002) 152 – 190
  W. Vogler, R. Wollowski
  
• Decomposition in Asynchronous Circuit Design. Uni. Augsburg, Inst. f. Informatik, Report Nr. 2002-5, 2002
  W. Vogler, R. Wollowski
  
• Canonical Prefixes of Petri Net Unfoldings. Acta Informatica 40 (2003) 95 – 118
  V. Khomenko, M. Koutny, W. Vogler
  
• DESI: a Tool for Decomposing Signal Transition Graphs. Proc. 3rd ACiD-WG Workshop (organized by the Working Group on Asynchronous Circuit Design as part of the European Commission's Framework Programme FP5 Microelectronics), Crete, January 2003
  B. Kangsah, R. Wollowski, W. Vogler, J. Beister
  
• Component Refinement and CSC Solving for STG Decomposition. Uni. Augsburg, Inst. f. Informatik, Report Nr. 2004-13, 2004
  Mark Schäfer, W. Vogler
  
• Determinate STG-Decomposition of Marked Graphs. Uni. Augsburg, Inst. f. Informatik, Report Nr. 2004-12, 2004
  Mark Schäfer, W. Vogler
  
• Improved Decomposition of Signal Transition Graphs. Uni. Augsburg, Inst. f. Informatik, Report Nr. 2004-8, 2004
  W. Vogler, Ben Kangsah
  
• Component refinement and CSC solving for STG decomposition. In FOSSACS 2005: 8th Foundations of Software Science and Computational Structures. Springer, Lect. Notes Comput. Sci. 3441 (2005) 348 – 363
  M. Schaefer, W. Vogler
  
• Determinate STG Decomposition of Marked Graphs. In ATPN'05: 26th Applications and Theory of Petri Nets Lect. Notes Comput. Sci. 3441 (2005) 365-384
  M. Schaefer, W. Vogler, P. Jancar
  
• Improved decomposition of signal transition graphs. In ACSD 2005: 5th Application of Concurrency to System Design. IEEE (2005) 244 – 253
  W. Vogler, B. Kangsah
  
• Merged processes – a new condensed representation of Petri net behaviour. In CONCUR 2005: 16th Concurrency Theory. Springer, Lect. Notes Comput. Sci. 3653 (2005) 338 – 352
  V. Khomenko, A. Kondratyev, M. Koutny, W. Vogler
  
• Strategies for optimised STG decomposition. ACSD'06: 6th Application of Concurrency to System Design, IEEE (2006) 123 – 132
  M. Schaefer, W. Vogler, R. Wollowski, V. Khomenko
  
• CSC-Aware STG Decomposition. 18th UK Asynchronous Forum, Newcastle, 2006
  Mark Schäfer
  
• Merged processes – a new condensed representation of Petri net behaviour. Acta Informatica 43 (2006) 307 – 330
  V. Khomenko, A. Kondratyev, M. Koutny, W. Vogler
  
• Avoiding irreducible CSC conflicts in component STGs. 19th UK Asynchronous Forum, Imperial College London, 2007
  D. Wist, R. Wollowski
  
• Combining Decomposition and Unfolding for STG Synthesis. In ATPN'07: 28th Applications and Theory of Petri Nets Lect. Notes Comput. Sci. 4546 (2007) 223 – 243
  Victor Khomenko, Mark Schaefer
  
• Component refinement and CSC solving for STG decomposition. Theoretical Computer Science 388(2007) 243-246
  M. Schaefer, W. Vogler
  
• DesiJ - a tool for STG decomposition. Technical Report 2007-11, Institute of Computer Science, University of Augsburg, 2007
  M. Schaefer
  
• DesiJ: A Tool for STG Decomposition - Downloads and Usage Examples
  Mark Schaefer
  
• Improved decomposition of signal transition graphs. Fundamenta Informaticae 78 (2007) 161 – 197
  W. Vogler, B. Kangsah
  
• Output-Determinacy and Asynchronous Circuit Synthesis. In ACSD 2007: 7th Application of Concurrency to System Design: IEEE (2007) 137 – 146
  V. Khomenko, M. Schaefer, W. Vogler
  
• Output-Determinacy and Asynchronous Circuit Synthesis. Uni. Augsburg, Inst. f. Informatik, Report Nr. 2007-02, 2007
  Victor Khomenko, Mark Schaefer, W. Vogler
  
• STG Decomposition: Avoiding Irreducible CSC Conflicts by Internal Communication. Technische Berichte des Hasso-Plattner-Instituts, Heft 20 (2007), ISBN 978-3-940793-02-7
  D. Wist, R. Wollowski
  
• Advanced STG-Decomposition. Dissertation, Uni. Augsburg, 2008
  Mark Schäfer
  
• Avoiding irreducible CSC conflicts by internal communication. ACSD'08: 8th Application of Concurrency to System Design, IEEE (2008) 3-12
  M. Schaefer, W. Vogler, D. Wist, R. Wollowski
  
• Avoiding irreducible CSC conflicts by internal communication. Fundamenta Informaticae Volume 95, Number 1, IOS Press (2009) 1–29
  D. Wist, R. Wollowski, M. Schaefer, W. Vogler
  
• Avoiding Irreducible CSC Conflicts by Internal Communication. Uni. Augsburg, Inst. f. Informatik, Report Nr. 2008-02, 2008
  M. Schaefer, W. Vogler, D. Wist and R. Wollowski
  
• Output-Determinacy and Asynchronous Circuit Synthesis. Fundamenta Informaticae 88 (2008) 541 – 579
  V. Khomenko, M. Schaefer, W. Vogler
  
• DESIJ – enabling decompositionbased synthesis of complex asynchronous controllers (Tool Paper). ACSD'09: 9th Application of Concurrency to System Design, IEEE (2009) 186-190
  M. Schaefer, D. Wist, R. Wollowski
  
• STG Decomposition Strategies in Combination with Unfolding. Acta Informatica 46, Number 6, Springer (2009) 433 – 474
  V. Khomenko, M. Schaefer, W. Vogler, R. Wollowski
  
• STG Decomposition: Internal Communication for SI Implementability. ACSD'10: 10th Application of Concurrency to System Design. IEEE (2010)
  D. Wist, M. Schaefer, W. Vogler, R. Wollowski
  
• STG Decomposition: Internal Communication for SI Implementability. Technische Berichte des Hasso- Plattner-Instituts, Heft 32 (2010), ISBN 978-3-86956-037-3, ISSN 1613-5652
  D. Wist, M. Schaefer, W. Vogler, R. Wollowski