Automating Synthesis of Asynchronous Communication Mechanisms

• Autorzy: Gorgônio K. , Xia F. , Yakovlev A.
• Języki publikacji: EN

Abstrakty

EN

Asynchronous data communication mechanisms (ACMs) have been extensively studied as data connectors between independently timed processes in digital systems. In previous work, systematic ACM synthesis methods have been proposed. In this paper, we advance this work by developing algorithms and software tools which automate most of the ACM synthesis process. Firstly, an interleaving specification is constructed in the form of a state graph, and secondly, a Petri net model of an "ACM-type" is derived using the theory of regions. The method is applied to a number of "standard" writing and reading policies of ACMs with shared memory and unidirectional control variables.

Słowa kluczowe

EN

asynchronous communication mechanisms; Petri net; concurrent and distributed systems; embedded system; hardware and software codesign; protocols; synthesis

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

Twórcy

autor

Gorgônio K.

autor

Xia F.

autor

Yakovlev A.

• Department of Software, Universitat Politécnica de Catalunya, Barcelona, Spain,

Bibliografia

• [1] ITRS 2005 Edition, http://www.itrs.net/Common/2005ITRS/Home2005.htm, 2005.
• [2] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers., IEICE Transactions on Information and Systems, (3), March 1997, 315-325.
• [3] Cortadella, J., Kishinevsky,M., Lavagno, L., Yakovlev, A.: Deriving Petri nets from finite transition systems, IEEE Transactions on Computers, 47(8), August 1998, 859-882, ISSN 0018-9340.
• [4] Fassino, J.-P.: THINK : vers une architecture de systèmes flexibles, Ph.D. Thesis, école Nationale Supérieure des Télécommunications, December 2001.
• [5] Jones, G., Goldsmith, M.: Programming in Occam 2, Prentice Hall International, 1988.
• [6] Kelly IV, C., Ekanayake, V., Manohar, R.: SNAP: A Sensor-Network Asynchronous Processor, Proceedings of the 9th International Symposium on Asynchronous Circuits and Systems, IEEE Computer Society, 2003, ISBN 0-7695-1898-2.
• [7] Kleeman, L., Cantoni, A.: On the Unavoidability of Metastable Behavior in Digital Systems., IEEE Transactions on Computers, 36(1), 1987, 109-112.
• [8] Lamport, L.: On Interprocess Communication - Part I: Basic Formalism, Distributed Computing, 1(2), 1986, 77-85.
• [9] Lamport, L.: On Interprocess Communication - Part II: Algorithms, Distributed Computing, 1(2), 1986, 86-101.
• [10] Lin, B.: Software Synthesis of Process-Based Concurrent Programs, 35th ACM/IEEE Design Automation Conference, June 1998.
• [11] Marino, L. R.: General Theory of Metastable Operation, IEEE Transactions on Computers, 30(2), 1981, 107-115.
• [12] Muller, D. E., Bartky, W. S.: "A Theory of Asynchronous Circuits, "Proceedings of an International Symposium on the Theory of Switching, "Harvard University Press, April 1959.
• [13] Murata, T.: Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, 77(4), April 1989, 541-580.
• [14] Nielsen, M., Rozenberg, G., Thiagarajan, P. S.: Elementary transition systems, Theoretical Computer Science, 96(1), 1992, 3-33, ISSN 0304-3975.
• [15] Peterson, J. L.: Petri Net Theory and Modeling of Systems, Prentice Hall, 1981.
• [16] Seitz, C. L.: System Timing, in: Introduction to VLSI Systems (C. Mead, L. Conway, Eds.), chapter 7, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1980.
• [17] Sgroi, M., Lavagno, L., Watanabe, Y., Sangiovanni-Vincentelli, A.: Synthesis of Embedded Software Using Free-Choice Petri Nets, 36th ACM/IEEE Design Automation Conference, June 1999.
• [18] Simpson, H. R.: Methodological and notational conventions in DORIS real-time networks, February 1994, Dynamics Division, BAe.
• [19] Simpson, H. R.: Protocols for Process Interaction, IEE Proceedings on Computers and Digital Techniques, 150(3),May 2003, 157-182.
• [20] Simpson, H. R., Campbell, E.: Real-time network architecture: principles and practice, Proc. AINT'2000, Asynchronous Interfaces: Tools, Techniques and Implementations, TU Delft, The Netherlands, July 2000.
• [21] Xia, F., Clark, I.: Algorithms for Signal and Message Asynchronous Communication Mechanisms and their Analysis, Fundamenta Informaticae, 50(2), April 2002, 205-222.
• [22] Xia, F., Hao, F., Clark, I., Yakovlev,A., Chester, E. G.: Buffered Asynchronous Communication Mechanisms, Fundamenta Informaticae, 70(1,2),March 2006, 155-170.
• [23] Xia, F., Yakovlev, A., Clark, I. G., Shang, D.: Data Communication in Systems with Heterogeneous Timing, IEEE Micro, 22(6), 2002, 58-69.
• [24] Xia, F., Yakovlev, A., Shang, D., Bystrov, A., Koelmans, A., Kinniment, D. J.: Asynchronous Communication Mechanisms Using Self-Timed Circuits, ASYNC '00: Proceedings of the 6th International Symposium on Advanced Research in Asynchronous Circuits and Systems, IEEE Computer Society, Washington, DC, USA, 2000, ISBN 0-7695-0586-4.
• [25] Yakovlev, A., Kinniment, D., Xia, F., Koelmans, A.: A FIFO buffer with non-blocking interface, TCVLSI Technical Bulletin, Fall 1998, 11-14.
• [26] Yakovlev, A., Xia, F.: Towards Synthesis of Asynchronous Communication Algorithms, in: Synthesis and Control of Discrete Event Systems. Part I: Decentralized Systems & Control (B. Caillaud, P. Darondean, L. Lavagno, X. Xie, Eds.), Kluwer Academic Publishers, Boston, January 2002, ISBN 0-7923-7639-0, 53-75.
• [27] Yakovlev, A., Xia, F., Shang, D.: Synthesis and Implementation of a Signal-Type Asynchronous Data Communication Mechanism, ASYNC '01: Proceedings of the 7th International Symposium on Asynchronous Circuits and Systems, IEEE Computer Society, 2001, ISBN 0-7695-1034-5.