×

Step persistence in the design of GALS systems. (English) Zbl 1381.68200

Colom, José-Manuel (ed.) et al., Application and theory of Petri nets and concurrency. 34th international conference, PETRI NETS 2013, Milan, Italy, June 24–28, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38696-1/pbk). Lecture Notes in Computer Science 7927, 190-209 (2013).
Summary: 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 one 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. Here we introduce a notion of persistent steps and discuss their basic properties. We then introduce a formal definition of a bundle and propose an algorithm to prune the behaviour of a system, so that only bundle 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.
For the entire collection see [Zbl 1266.68010].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Barylska, K.; Ochmański, E., Levels of persistency in place/transition nets, Fundamenta Informaticae, 93, 33-43 (2009) · Zbl 1191.68429
[2] Barylska, K.; Mikulski, Ł.; Ochmański, E., On persistent reachability in Petri nets, Information and Computation, 223, 67-77 (2013) · Zbl 1293.68200 · doi:10.1016/j.ic.2012.11.004
[3] Best, E.; Darondeau, P.; van Hee, K. M.; Valk, R., Decomposition theorems for bounded persistent Petri nets, Applications and Theory of Petri Nets, 33-51 (2008), Heidelberg: Springer, Heidelberg · Zbl 1143.68473 · doi:10.1007/978-3-540-68746-7_7
[4] Best, E.; Darondeau, P.; Lilius, J.; Penczek, W., Separability in persistent Petri nets, Applications and Theory of Petri Nets, 246-266 (2010), Heidelberg: Springer, Heidelberg · Zbl 1233.68161 · doi:10.1007/978-3-642-13675-7_15
[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, vol. 8. Springer (2002) · Zbl 1013.68273
[7] Dasgupta, S.; Yakovlev, A., Desynchronisation technique using Petri nets, Electronic Notes in Theoretical Computer Science, 245, 51-67 (2009) · doi:10.1016/j.entcs.2009.07.028
[8] Davis, A., Nowick, S.M.: An introduction to asynchronous circuit design. The Encyclopedia of Computer Science and Technology (1997)
[9] Gurkaynak, F., Oetiker, S., Kaeslin, H., Felber, N., Fichtner, W.: GALS at ETH Zurich: Success or failure? In: Proceedings of the 12th IEEE International Symposium on Asynchronous Circuits and Systems (2006)
[10] Iyer, A., Marculescu, D.: Power and performance evaluation of globally asynchronous locally synchronous processors. In: 29th International Symposium on Computer Architecture, pp. 158-168. IEEE Computer Society (2002)
[11] Keller, R.; Tse-Yun, F., A fundamental theorem of asynchronous parallel computation, Parallel Processing, 102-112 (1975), Heidelberg: Springer, Heidelberg · Zbl 0301.68063 · doi:10.1007/3-540-07135-0_113
[12] Koutny, M.; Mikulski, Ł.; Pietkiewicz-Koutny, M.; Colom, J.-M.; Desel, J., A taxonomy of persistent and nonviolent steps, PETRI NETS 2013, 210-229 (2013), Heidelberg: Springer, Heidelberg · Zbl 1381.68208
[13] Landweber, L. H.; Robertson, E. L., Properties of conflict-free and persistent Petri nets, JACM, 25, 352-364 (1978) · Zbl 0384.68062 · doi:10.1145/322077.322079
[14] Muller, D.E., Bartky, W.S.: A theory of asynchronous circuits. In: Proceedings of an International Symposium on the Theory of Switching, pp. 204-243. Harvard University Press (1959) · Zbl 0171.37902
[15] Myers, C.: Asynchronous circuit design. Wiley (2004)
[16] Sparso, J., Furber, S.: Principles of asynchronous circuit design: a systems perspective. Kluwer Academic Publishers (2001)
[17] 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, 115-134 (2009) · doi:10.1016/j.entcs.2009.07.032
[18] Yakovlev, A., Designing self-timed systems, VLSI System Design, VI, 70-90 (1985)
[19] Yakovlev, A.; Koelmans, A.; Semenov, A.; Kinniment, D., Modelling, analysis and synthesis of asynchronous control circuits using Petri nets, Integration, the VLSI Journal, 21, 143-170 (1996) · Zbl 0875.68972 · doi:10.1016/S0167-9260(96)00010-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.