Improved Decomposition of Signal Transition Graphs

• Autorzy: Vogler W. , Kangsah B.
• Języki publikacji: EN

Abstrakty

EN

Signal Transition Graphs (STGs) are a version of Petri nets for the specification of asynchronous circuit behaviour. It has been suggested to decompose such a specification as a first step; this leads to a modular implementation, which can support circuit synthesis by possibly avoiding state explosion or allowing the use of library elements. In a previous paper, the original method was extended and shown to be much more generally applicable than known before. But further extensions are necessary, and some are presented in this paper. In particular, to avoid dynamic auto-conflicts, the previous paper insisted on avoiding structural auto-conflicts, which is too restrictive; as a main contribution, we show how to work with the latter type of auto-conflicts. This extension makes it necessary to restructure presentation and correctness proof of the decomposition algorithm.

Słowa kluczowe

EN

COncurrent SYstem; Petri net; asynchronous circuitis; Signal Transition Graphs (STGs); decomposition; modular implementation; state explosion

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 1
• Strony: 161--197
• Opis fizyczny: bibliogr. 24 poz., wykr.

Twórcy

autor

Vogler W.

autor

Kangsah B.

• Institut für Informatik, Universität Augsburg, D-86135, Augsburg, Germany,

Bibliografia

• [1] André, C.: Structural transformations giving B-equivalent PT-nets, Applications and Theory of Petri Nets (Pagnoni, Rozenberg, Eds.), Informatik-Fachber. 66, 14-28. Springer, 1983.
• [2] Beister, J., Eckstein, G.,Wollowski, R.: CASCADE: a tool kernel supporting a comprehensive designmethod for asynchronous controllers, Applications and Theory of Petri Nets 2000 (M. Nielsen, Ed.), Lect. Notes Comp. Sci. 1825, 445-454. Springer, 2000.
• [3] Berthelot, G.: Transformations and decompositions of nets, Petri Nets: Central Models and Their Properties (W. Brauer, et al., Eds.), Lect. Notes Comp. Sci. 254, 359-376. Springer, 1987.
• [4] Carmona, J., Cortadella, J.: ILP models for the synthesis of asynchronous control circuits, Proc. of the IEEE/ACM International Conference on Computer Aided Design, 2003.
• [5] Chu, T.-A.: On the models for designing VLSI asynchronous digital systems, Integration: the VLSI Journal, 4, 1986, 99-113.
• [6] Chu, T.-A.: Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications, Ph.D. Thesis, MIT, 1987.
• [7] Chu, T.-A.: Synthesis of self-timed VLSI circuits from Graph-Theoretic Specifications, IEEE Int. Conf. Computer Design ICCD '87, 1987.
• [8] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers, IEICE Trans. Information and Systems, E80-D, 3, 1997, 315-325.
• [9] Ebergen, J.: Arbiters: an exercise in specifying and decomposing asynchronously communicating components, Sci. of Computer Programming, 18, 1992, 223-245.
• [10] Kondratyev, A., Kishinevsky, M., Taubin, A.: Synthesis Method in self-timed design. Decompositional approach, IEEE Int. Conf. VLSI and CAD, 1993.
• [11] Lynch, N.: Distributed Algorithms, Morgan Kaufmann Publishers, San Francisco, 1996.
• [12] Peterson, J.: Petri Net Theory, Prentice-Hall, 1981.
• [13] Reisig, W.: Petri Nets, EATCS Monographs on Theoretical Computer Science 4, Springer, 1985.
• [14] Rosenblum, L., Yakovlev, A.: Signal graphs: from self-timed to timed ones, Proc. Int. Work. Timed Petri Nets, Torino, Italy, 1985.
• [15] Schaefer, M., Vogler, W.: Component Refinement and CSC Solving for STG Decomposition, FOSSACS 05, Lect. Notes Comp. Sci. 3441, 348 -363. Springer, 2005.
• [16] Schaefer, M., Vogler, W., Wollowski, R., Khomenko, V.: Strategies for Optimised STG Decomposition, Accepted for ACSD 06.
• [17] Segala, R.: Quiescence, fairness, testing, and the notion of implementation, CONCUR 93 (E. Best, Ed.), Lect. Notes Comp. Sci. 715, 324-338. Springer, 1993.
• [18] Vanbekbergen, C., Ykman-Couvreur, C., Lin, B., de Man, H.: A generalized signal transition graph model for specification of complex interfaces, European Design and Test Conf., IEEE, 1994.
• [19] Vogler, W., Wollowski, R.: Decomposition in Asynchronous Circuit Design, Concurrency and Hardware Design (J. Cortadella, et al., Eds.), Lect. Notes Comp. Sci. 2549, 152 - 190. Springer, 2002.
• [20] Wendt, S.: Using Petri nets in the design process for interacting asynchronous sequential circuits, Proc. IFAC-Symp. on Discrete Systems, Vol.2, Dresden, 130-138. 1977.
• [21] Wollowski, R.: Entwurfsorientierte Petrinetz-Modellierung des Schnittstellen-Sollverhaltens asynchroner Schaltwerksverb¨unde, Ph.D. Thesis, Uni. Kaiserslautern, FB Elektrotechnik, 1997.
• [22] Wollowski, R., Beister, J.: Comprehensive Causal Specification of Asynchronous Controller and Arbiter Behaviour, Hardware Design and Petri Nets (A. Yakovlev, L. Gomes, L. Lavagno, Eds.), Kluwer Academic Publishers, 2000.
• [23] Yakovlev, A., Kishinevsky, M., Kondratyev, A., Lavagno, L., Pietkiewicz-Koutny, M.: On the models for asynchronous circuit behaviour with or causality, Formal Methods in System Design, 9, 1996, 189-233.
• [24] Yoneda, T., Onda, H.,Myers, C.: Synthesis of Speed Independent Circuits Based on Decomposition, ASYNC 2004, IEEE, 2004.