Persistent and Nonviolent Steps and the Design of GALS Systems

• Autorzy: Fernandes J. , Koutny M. , Mikulski Ł , Pietkiewicz-Koutny M. , Sokolov D. , Yakovlev A.

Identyfikatory

DOI

10.3233/FI-2015-1173

• Języki publikacji: EN

Abstrakty

EN

A concurrent system is persistent if throughout its operation no activity which became enabled can subsequently be prevented from being executed by any other activity. This is often a highly desirable (or even necessary) property; in particular, if the system is to be implemented in hardware. Over the past 40 years, persistence has been investigated and applied in practical implementations assuming that each activity is a single atomic action which can be represented, for example, by a single transition of a Petri net. In this paper we investigate the behaviour of GALS (Globally Asynchronous Locally Synchronous) systems in the context of VLSI circuits. The specification of a system is given in the form of a Petri net. Our aim is to re-design the system to optimise signal management, by grouping together concurrent events. Looking at the concurrent reachability graph of the given Petri net, we are interested in discovering events that appear in ‘bundles’, so that they all can be executed in a single clock tick. The best candidates for bundles are sets of events that appear and re-appear over and over again in the same configurations, forming ‘persistent’ sets of events. Persistence was considered so far only in the context of sequential semantics. In this paper, we move to the realm of step based execution and consider not only steps which are persistent and cannot be disabled by other steps, but also steps which are nonviolent and cannot disable other steps. We then introduce a formal definition of a bundle and propose an algorithm to prune the behaviour of a system, so that only bundled steps remain. The pruned reachability graph represents the behaviour of a re-engineered system, which in turn can be implemented in a new Petri net using the standard techniques of net synthesis. The proposed algorithm prunes reachability graphs of persistent and safe nets leaving bundles that represent maximally concurrent steps.

Słowa kluczowe

EN

asynchronous circuit; synchronous circuit; GALS system; persistence; nonviolence; step transition system; step semantics; Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 1
• Strony: 143--170
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Fernandes J.

• School of Electrical & Electronic Eng. Newcastle University Newcastle upon Tyne, NE1 7RU, U.K.

autor

Koutny M.

• School of Electrical & Electronic Eng. Newcastle University Newcastle upon Tyne, NE1 7RU, U.K.

autor

Mikulski Ł

• Faculty of Mathematics and Computer Science Nicolaus Copernicus University Toru´n, Chopina 12/18, Poland

autor

Pietkiewicz-Koutny M.

• School of Electrical & Electronic Eng. Newcastle University Newcastle upon Tyne, NE1 7RU, U.K.

autor

Sokolov D.

• School of Electrical & Electronic Eng. Newcastle University Newcastle upon Tyne, NE1 7RU, U.K.

autor

Yakovlev A.

• School of Electrical & Electronic Eng. Newcastle University Newcastle upon Tyne, NE1 7RU, U.K.

Bibliografia

• [1] Barylska, K., Ochmański, E.: Levels of persistency in place/transition nets. Fundamenta Informaticae 93 (2009) 33–43.
• [2] Barylska, K., Mikulski, Ł., Ochmański, E.: On persistent reachability in Petri nets. Information and Computation 223 (2013) 67–77.
• [3] Best, E., Darondeau, Ph.: Decomposition theorem for bounded persistent Petri nets. ICATPN’08, Lecture Notes in Computer Science 5062, Springer (2008) 33–51.
• [4] Best, E., Darondeau, Ph.: Separability in persistent Petri nets. ICATPN’10, Lecture Notes in Computer Science 6128 (2010) 246–266.
• [5] Chapiro, D.M.: Globally-asynchronous locally-synchronous systems. PhD Thesis, Stanford University (1984).
• [6] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic synthesis for asynchronous controllers and interfaces. Springer Series in Advanced Microelectronics 8, Springer-Verlag (2002).
• [7] Dasgupta, S., Potop-Butucaru, D., Caillaud, B., Yakovlev, A.: Moving from weakly endochronous systems to delay-insensitive circuits. Electronic Notes in Theoretical Computer Science 146 (2006) 81–103
• [8] Dasgupta, S., Yakovlev, A.: Desynchronisation technique using Petri nets. Electronic Notes in Theoretical Computer Science 245 (2009) 51–67.
• [9] Davis, A., Nowick, S.M.: An introduction to asynchronous circuit design. The Encyclopedia of Computer Science and Technology (1997).
• [10] Fernandes, J., Koutny, M., Pietkiewicz-Koutny, M., Sokolov, D., Yakovlev, A.: Step persistence in the design of GALS systems. ICATPN’13, Lecture Notes in Computer Science 7927, Springer (2013) 190–209.
• [11] Gurkaynak, F., Oetiker, S., Kaeslin, H., Felber, N., Fichtner, W.: GALS at ETH Zurich: Success or failure? Proc. of the 12th IEEE International Symposium on Asynchronous Circuits and Systems (2006).
• [12] Iyer, A., Marculescu, D.: Power and performance evaluation of globally asynchronous locally synchronous processors. 29th International Symposium on Computer Architecture, IEEE Computer Society (2002) 158–168.
• [13] Keller, R.: A fundamental theorem of asynchronous parallel computation. Lecture Notes in Computer Science 24 (1975) 102–112.
• [14] Koutny, M., Mikulski, Ł., Pietkiewicz-Koutny, M.: A taxonomy of persistent and nonviolent steps. ICATPN’13, Lecture Notes in Computer Science 7927, Springer (2013) 210-229.
• [15] Król, T., Krstić, M., Fan, X., Grass, E.: Modeling and reducing EMI in GALS and synchronous systems. PATMOS’09, Lecture Notes in Computer Science 5953, Springer (2009) 146–155.
• [16] Landweber, L.H., Robertson, E.L.: Properties of conflict-free and persistent Petri nets. JACM 25 (1978) 352–364.
• [17] Muller, D.E., Bartky, W.S.: A theory of asynchronous circuits. Proceedings of an International Symposium on the Theory of Switching, Harvard University Press (1959) 204-243.
• [18] Myers, C.: Asynchronous circuit design. Wiley (2004).
• [19] Sparso, J., Furber, S.: Principles of asynchronous circuit design: a systems perspective. Kluwer Academic Publishers (2001).
• [20] Stevens, K.S., Gebhardt, D., You, J., Xu, Y., Vij, V., Das, S., Desai, K.: The future of formal methods and GALS design. Electronic Notes in Theoretical Computer Science 245 (2009) 115–134.
• [21] Yakovlev, A.: Designing self-timed systems. VLSI SYSTEM DESIGN VI (1985) 70–90.
• [22] Yakovlev, A., Koelmans, A., Semenov, A., Kinniment, D.: Modelling, analysis and synthesis of asynchronous control circuits using Petri nets. INTEGRATION, the VLSI Journal 21 (1996) 143–170.