Output-Determinacy and Asynchronous Circuit Synthesis

• Autorzy: Khomenko V. , Schaefer M. , Vogler W.
• Języki publikacji: EN

Abstrakty

EN

Signal Transition Graphs (STG) are a formalism for the description of asynchronous circuit behaviour. In this paper we propose (and justify) a formal semantics of non-deterministic STGs with dummies and OR-causality. For this, we introduce the concept of output-determinacy, which is a relaxation of determinism, and argue that it is reasonable and useful in the speed-independent context. We apply the developed theory to improve an STG decomposition algorithm used to tackle the state explosion problem during circuit synthesis, and present some experimental data for this improved algorithm and some benchmark examples.

Słowa kluczowe

EN

output-determinacy; decomposition; Signal Transition Graphs (STG); asynchronous circuits; OR-causality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 88, nr 4
• Strony: 541--579
• Opis fizyczny: bibliogr. 28 poz., tab., wykr.

Twórcy

autor

Khomenko V.

autor

Schaefer M.

autor

Vogler W.

• Institute of Computer Science University of Augsburg, Germany,

Bibliografia

• [1] C. André. Structural transformations giving B-equivalent PT-nets. In Pagnoni and Rozenberg, editors, Applications and Theory of Petri Nets, Informatik-Fachber. 66, 14-28. Springer, 1983.
• [2] G. Berthelot. Transformations and decompositions of nets. In W. Brauer et al., editors, Petri Nets: Central Models and Their Properties, Lect. Notes Comp. Sci. 254, 359-376. Springer, 1987.
• [3] K. v. Berkel. Handshake Circuits: an Asynchronous Architecture for VLSI Programming. International Series on Parallel Computation, 5, 1993.
• [4] Josep Carmona. StructuralMethods for the Synthesis ofWell-Formed Concurrent Specifications. PhD thesis, Universitat Polit`ecnica de Catalunya, 2003.
• [5] J. Carmona and J. Cortadella. ILP models for the synthesis of asynchronous control circuits. In Proc. of the IEEE/ACM International Conference on Computer Aided Design, pages 818-825, 2003.
• [6] J. Carmona and J. Cortadella. State Encoding of Large Asynchronous Controllers. In Proc. DAC'06, pages 939-944. IEEE Computer Society Press, 2006.
• [7] T.-A. Chu. Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications. PhD thesis, MIT, 1987.
• [8] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. PETRIFY: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers. IEICE Trans. Information and Systems, E80-D, 3:315-325, 1997.
• [9] J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. Logic Synthesis of Asynchronous Controllers and Interfaces. Springer, 2002.
• [10] D. Edwards and A. Bardsley. BALSA: an Asynchronous Hardware Synthesis Language. The Computer Journal, 45(1):12-18, 2002.
• [11] J. Ebergen. Arbiters: an exercise in specifying and decomposing asynchronously communicating components. Sci. of Computer Programming, 18:223-245, 1992.
• [12] J. Esparza. Decidability and complexity of Petri net problems- an introduction. In W. Reisig and G. Rozenberg, editors, Lectures on Petri Nets I: Basic Models, Lect. Notes Comp. Sci. 1491, pages 374-428. Springer-Verlag, 1998.
• [13] International Technology Roadmap for Semiconductors: Design, 2005. URL: www.itrs.net/Links/2005ITRS/Design2005.pdf.
• [14] V. Khomenko. Model Checking Based on Prefixes of Petri Net Unfoldings. PhD thesis, School of Computing Science, Newcastle University, 2003.
• [15] A. Kondratyev,M. Kishinevsky, and A. Taubin. Synthesis method in self-timed design. Decompositional approach. In IEEE Int. Conf. VLSI and CAD, pages 324-327, 1993.
• [16] M. Kishinevsky, A. Kondratyev, A. Taubin, and V. Varshavsky. Concurrent Hardware: The Theory and Practice of Self-Timed Design. JohnWiley & Sons Ltd., 1994.
• [17] V. Khomenko and M. Schaefer. Combining decomposition and unfolding for STG synthesis. In ICATPN '07: 28th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, pages 223-243, 2007.
• [18] S. Melzer. Verifikation Verteilter Systeme mit Linearer - und Constraint-Programmierung. PhD thesis, Technische Universität M¨unchen, Utz Verlag, 1998.
• [19] R. Milner. Communication and Concurrency. Prentice Hall, 1989.
• [20] T. Murata. Petri Nets: Properties, Analysis and Applications. Proc. of the IEEE, 77(4):541-580, 1989.
• [21] M. Schaefer. DESIJ - a tool for decomposition. Technical Report 2007-11, University of Augsburg, 2007. URL: http://www.informatik.uni-augsburg.de/de/forschung/reports/.
• [22] H. Saito, A. Kondratyev, J. Cortadella, L. Lavagno, and A. Yakovlev. What is the cost of delay insensitivity? In Proc. CAD'99, pages 316-323. IEEE Computer Society Press, 1999.
• [23] M. Schaefer and W. Vogler. Component refinement and CSC solving for STG decomposition. In Vladimiro Sassone, editor, FOSSACS 05, Lect. Notes Comp. Sci. 3441, pp. 348-363. Springer, 2005.
• [24] M. Schaefer,W. Vogler, R. Wollowski, and V. Khomenko. Strategies for optimised STG decomposition. In ACSD, pages 123-132, 2006.
• [25] M. Schaefer, W. Vogler, D. Wist, and R. Wollowski. Avoiding irreducible CSC conflicts by internal communication. Technical Report 2008-02, University of Augsburg, 2008. URL: http://www.Informatik.Uni-Augsburg.DE/skripts/techreports/.
• [26] W. Vogler and B. Kangsah. Improved decomposition of signal transition graphs. Fundamenta Informaticae, 76:161-197, 2006.
• [27] W. Vogler and R. Wollowski. Decomposition in asynchronous circuit design. In J. Cortadella et al., editors, Concurrency and Hardware Design, Lect. Notes Comp. Sci. 2549, 152 - 190. Springer, 2002.
• [28] A. Yakovlev,M. Kishinevsky,A. Kondratyev, L. Lavagno, andM. Pietkiewicz-Koutny. On themodels for asynchronous circuit behaviourwith OR causality. FormalMethods in System Design, 9:189-233, 1996.