Elasticity and Petri nets. (English) Zbl 1171.68568
Jensen, Kurt (ed.) et al., Transactions on Petri Nets and Other Models of Concurrency I. Berlin: Springer (ISBN 978-3-540-89286-1/pbk). Lecture Notes in Computer Science 5100. Journal Subline, 221-249 (2008).
Summary: Digital electronic systems typically use synchronous clocks and primarily assume fixed duration of their operations to simplify the design process. Time elastic systems can be constructed either by replacing the clock with communication handshakes (asynchronous version) or by augmenting the clock with a synchronous version of a handshake (synchronous version). Time elastic systems can tolerate static and dynamic changes in delays (asynchronous case) or latencies (synchronous case) of operations that can be used for modularity, ease of reuse and better power-delay trade-off. This paper describes methods for the modeling, performance analysis and optimization of elastic systems using Marked Graphs and their extensions capable of describing behavior with early evaluation. The paper uses synchronous elastic systems (aka latency-tolerant systems) for illustrating the use of Petri nets, however, most of the methods can be applied without changes (except changing the delay model associated with events of the system) to asynchronous elastic systems.
For the entire collection see [Zbl 1154.68308].
For the entire collection see [Zbl 1154.68308].
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
Software:
CPLEXReferences:
| [1] | Sutherland, I.E.: Micropipelines. Communications of the ACM 32(6), 720–738 (1989) · doi:10.1145/63526.63532 |
| [2] | Muller, D.E., Bartky, W.S.: A theory of asynchronous circuits. In: Proceedings of an International Symposium on the Theory of Switching, April 1959, pp. 204–243. Harvard University Press (1959) · Zbl 0171.37902 |
| [3] | Martin, A.J.: Compiling communicating processes into delay-insensitive VLSI circuits. Distributed Computing 1(4), 226–234 (1986) · Zbl 0643.94039 · doi:10.1007/BF01660034 |
| [4] | Sparsø, J., Furber, S. (eds.): Principles of Asynchronous Circuit Design: A Systems Perspective. Kluwer Academic Publishers, Dordrecht (2001) |
| [5] | Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic synthesis of asynchronous controllers and interfaces. Springer, Heidelberg (2002) · Zbl 1013.68273 · doi:10.1007/978-3-642-55989-1 |
| [6] | O’Leary, J., Brown, G.: Synchronous emulation of asynchronous circuits. IEEE Transactions on Computer-Aided Design 16(2), 205–209 (1997) · doi:10.1109/43.573835 |
| [7] | Peeters, A., van Berkel, K.: Synchronous handshake circuits. In: Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, pp. 86–95. IEEE Computer Society Press, Los Alamitos (2001) |
| [8] | Carloni, L.P., McMillan, K.L., Sangiovanni-Vincentelli, A.L.: Theory of latency-insensitive design. IEEE Transactions on Computer-Aided Design 20(9), 1059–1076 (2001) · doi:10.1109/43.945302 |
| [9] | Carloni, L.P., Sangiovanni-Vincentelli, A.L.: Coping with latency in SoC design. IEEE Micro, Special Issue on Systems on Chip 22(5), 12 (2002) |
| [10] | Jacobson, H.M., Kudva, P.N., Bose, P., Cook, P.W., Schuster, S.E., Mercer, E.G., Myers, C.J.: Synchronous interlocked pipelines. In: Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, pp. 3–12 (April 2002) · doi:10.1109/ASYNC.2002.1000291 |
| [11] | Cortadella, J., Kishinevsky, M., Grundmann, B.: Synthesis of synchronous elastic architectures. In: Proc. ACM/IEEE Design Automation Conference, pp. 657–662 (July 2006) · doi:10.1145/1146909.1147077 |
| [12] | Cortadella, J., Kishinevsky, M.: Synchronous elastic circuits with early evaluation and token counterflow. In: Proc. ACM/IEEE Design Automation Conference, pp. 416–419 (June 2007) · doi:10.1145/1278480.1278587 |
| [13] | Dennis, J.B.: Modular asynchronous control structures for a high performance processor. In: Project MAC Conf. on Concurrent Systems and Parallel Computation, pp. 55–80 (1970) |
| [14] | Dennis, J.B., Patil, S.S.: Speed-independent asynchronous circuits. In: Proc. Hawaii International Conf. System Sciences, pp. 55–58 (1971) |
| [15] | Misunas, D.: Petri nets and speed independent design. Communications of the ACM 16(8), 474–481 (1973) · doi:10.1145/355609.362318 |
| [16] | Linder, D.H., Harden, J.C.: Phased logic: supporting the synchronous design paradigm with delay-insensitive circuitry. IEEE Transactions on Computers 45(9), 1031–1044 (1996) · Zbl 1048.68968 · doi:10.1109/12.537126 |
| [17] | Cortadella, J., Kondratyev, A., Lavagno, L., Sotiriou, C.: Desynchronization: synthesis of asynchronous circuits from synchronous specifications. IEEE Transactions on Computer-Aided Design 25(10), 1904–1921 (2006) · doi:10.1109/TCAD.2005.860958 |
| [18] | Rosenblum, L.Y., Yakovlev, A.V.: Signal graphs: from self-timed to timed ones. In: Proceedings of International Workshop on Timed Petri Nets, Turin, Italy, July 1985, pp. 199–207. IEEE Computer Society Press, Los Alamitos (1985) |
| [19] | Yoeli, M.: Specification and verification of asynchronous circuits using marked graphs. In: Voss, K., Genrich, H.J., Rozenberg, G. (eds.) Concurrency and Nets, Advances in Petri Nets, pp. 605–622. Springer, Heidelberg (1987) · Zbl 0643.94042 |
| [20] | Yakovlev, A., Gomes, L., Lavagno, L. (eds.): Hardware Design And Petri Nets. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0933.68002 |
| [21] | Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, Chichester (1998) · Zbl 0970.90052 |
| [22] | CPLEX, http://www.ilog.com/products/cplex |
| [23] | Murata, T.: Petri Nets: properties, analysis and applications. Proceedings of the IEEE, 541–580 (April 1989) · doi:10.1109/5.24143 |
| [24] | Campos, J., Silva, M.: Structural techniques and performance bounds of stochastic Petri net models. In: Rozenberg, G. (ed.) APN 1992. LNCS, vol. 609. Springer, Heidelberg (1992) · doi:10.1007/3-540-55610-9_178 |
| [25] | Little, J.D.C.: A proof of the queueing formula L={\(\lambda\)} W. Operations Research 9, 383–387 (1961) · Zbl 0108.14803 · doi:10.1287/opre.9.3.383 |
| [26] | Ramamoorthy, C.V., Ho, G.S.: Performance evaluation of asynchronous concurrent systems using Petri nets. IEEE Trans. Software Eng. 6(5), 440–449 (1980) · Zbl 0444.68044 · doi:10.1109/TSE.1980.230492 |
| [27] | Karp, R.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23, 309–311 (1978) · Zbl 0386.05032 · doi:10.1016/0012-365X(78)90078-X |
| [28] | Dasdan, A., Irani, S.S., Gupta, R.K.: Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In: Proc. 36th Design Automation Conference, pp. 37–42 (1999) |
| [29] | Williams, T.E.: Performance of iterative computation in self-timed rings. Journal of VLSI Signal Processing 7(1/2), 17–31 (1994) · doi:10.1007/BF02108187 |
| [30] | Manohar, R., Martin, A.J.: Slack elasticity in concurrent computing. In: Jeuring, J. (ed.) MPC 1998. LNCS, vol. 1422, pp. 272–285. Springer, Heidelberg (1998) · doi:10.1007/BFb0054295 |
| [31] | Beerel, P.A., Kim, N.-H., Lines, A., Davies, M.: Slack matching asynchronous designs. In: Proc. of the 12th Int. Symp. on Asynchronous Circuits and Systems (2006) · doi:10.1109/ASYNC.2006.26 |
| [32] | Rodriquez-Beltran, J., Ramirez-Trevino, A.: Minimum initial marking in timed marked graphs. In: Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics (SMC 2000), vol. 4, pp. 3004–3008 (October 2000) · doi:10.1109/ICSMC.2000.884458 |
| [33] | Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979) · Zbl 0411.68039 |
| [34] | Lu, R., Koh, C.-K.: Performance optimization of latency insensitive systems through buffer queue sizing of communication channels. In: Proc. International Conf. Computer-Aided Design (ICCAD), pp. 227–231 (2003) |
| [35] | Lu, R., Koh, C.-K.: Performance analysis and efficient implementation of latency insensitive systems. ECE Technical Reports (March 2003) |
| [36] | Chelcea, T., Nowick, S.M.: Robust interfaces for mixed-timing systems. IEEE Trans. VLSI Syst. 12(8), 857–873 (2004) · doi:10.1109/TVLSI.2004.831476 |
| [37] | Dasdan, A., Gupta, R.K.: Faster maximum and minimum mean cycle algorithms for system performance analysis. IEEE Transactions on Computer-Aided Design 17(10), 889–899 (1998) · doi:10.1109/43.728912 |
| [38] | Carmona, J., Júlvez, J., Cortadella, J., Kishinevsky, M.: Performance-preserving clustering of elastic controllers. Technical Report LSI-08-7-R, Department of Software, Universitat Politècnica de Catalunya (2007) · Zbl 1242.68354 |
| [39] | Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms. McGraw-Hill Higher Education, New York (2001) · Zbl 1047.68161 |
| [40] | Júlvez, J., Cortadella, J., Kishinevsky, M.: Performance analysis of concurrent systems with early evaluation. In: Proc. International Conf. Computer-Aided Design (ICCAD) (November 2006) · Zbl 1200.93099 |
| [41] | Brej, C.F., Garside, J.D.: Early output logic using anti-tokens. In: Int. Workshop on Logic Synthesis, pp. 302–309 (May 2003) |
| [42] | Reese, R.B., Thornton, M.A., Traver, C., Hemmendinger, D.: Early evaluation for performance enhancement in phased logic. IEEE Transactions on Computer-Aided Design 24(4), 532–550 (2005) · doi:10.1109/TCAD.2005.844084 |
| [43] | 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(3), 189–233 (1996) · doi:10.1007/BF00122082 |
| [44] | Wolff, R.W.: Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs (1989) · Zbl 0701.60083 |
| [45] | Chiola, G., Anglano, C., Campos, J., Colom, J.M., Silva, M.: Operational analysis of timed Petri nets and application to the computation of performance bounds. In: Baccelli, F., Jean-Marie, A., Mitrani, I. (eds.) Quantitative Methods in Parallel Systems, pp. 161–174. Springer, Heidelberg (1995); Also appears in Procs. PNPM 1993 (1993) · Zbl 0845.68077 · doi:10.1007/978-3-642-79917-4_11 |
| [46] | Leiserson, C.E., Saxe, J.B.: Retiming synchronous circuitry. Algorithmica 6(1), 5–35 (1991) · Zbl 0708.94025 · doi:10.1007/BF01759032 |
| [47] | Bufistov, D., Cortadella, J., Kishinevsky, M., Sapatnekar, S.: A general model for performance optimization of sequential systems. In: Proc. International Conf. Computer-Aided Design (ICCAD), pp. 362–369 (November 2007) · doi:10.1109/ICCAD.2007.4397291 |
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.
