Analysis of Static Data Flow Structures

• Autorzy: Sokolov, D. , Poliakov, I. , Yakovlev, A.
• Języki publikacji: EN

Abstrakty

EN

A token-based model for asynchronous data path, called static data flow structures (SDFS), is formally defined. Three token game semantics are introduced for this model, namely atomic token, spread token and counterflow. The SDFS semantics are analysed using a simple benchmark example; their advantages and drawbacks are highlighted. A combination of spread token and counterflow models, which employs the advantages of both, is presented. A technique is described for mapping the high-level SDFS token game semantics into the low level of underlying Petri nets (PNs). The PNs are employed as a back-end for verification of SDFS models. For analysis and comparison of SDFS semantics a software tool has been developed, which integrates all SDFS semantics into a consistent framework, implements their conversion into PNs and provides an interface to existing model checking tools.

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 88, nr 4
• Strony: 581-610
• Opis fizyczny: bibliogr. 31 poz., tab., wykr.

Twórcy

autor

Sokolov, D.

autor

Poliakov, I.

autor

Yakovlev, A.

• School of Electrical, Electronic and Computer Engineering, Merz Court Newcastle University, Newcastle upon Tyne, NE1 7RU, UK,

Bibliografia

• [1] Ampalam, M., Singh, M.: Counterflow pipelining: architectural support for preemption in asynchronous systems using anti-tokens, Proc. International Conference Computer-Aided Design (ICCAD), November 2006.
• [2] Bainbridge, J., Toms, W., Edwards, D., Furber, S.: Delay-insensitive, point-to-point interconnect using Mof-N codes, Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), IEEE Computer Society Press, May 2003.
• [3] Blunno, I., Lavagno, L.: Automated synthesis of micro-pipelines from behavioral Verilog HDL, Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), IEEE Computer Society Press, April 2000.
• [4] Blunno, I., Lavagno, L.: Designing an asynchronous microcontroller using Pipefitter, Proc. International Conference Computer Design (ICCD), 2002.
• [5] Brej, C.: Early output logic and anti-tokens, Ph.D. Thesis, Dept. of Computer Science, University of Manchester, 2005.
• [6] Brej, C., Garside, J.: Early output logic using anti-tokens, Proc. International Workshop on Logic Synthesis, ACM Press, May 2003.
• [7] Bystrov, A., Sokolov, D., Yakovlev, A.: Low-latency control structures with slack, Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), IEEE Computer Society Press, May 2003.
• [8] Chou, W.-C., Beerel, P. A., Yun, K. Y.: Average-case technology mapping of asynchronous burst-mode circuits, IEEE Transactions on Computer-Aided Design, 18(10), October 1999, 1418-1434.
• [9] Chu, T.-A.: Synthesis of self-timed VLSI circuits from graph-theoretic specifications, Ph.D. Thesis, MIT Laboratory for Computer Science, June 1987.
• [10] 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, E80-D(3),March 1997, 315-325.
• [11] Dindhuc, A., Rigaud, J.-B., Rezzag, A., Sirianni, A., Fragoso, J. L., Fesquet, L., Renaudin, M.: TIMA asynchronous synthesis tools, Communication to ACID Worshop, January 2002.
• [12] Fuhrer, R. M., Nowick, S. M., Theobald, M., Jha, N. K., Lin, B., Plana, L.: Minimalist: an environment for the synthesis, verification and testability of burst-mode asynchronous machines, Technical Report TR CUCS-020-99, Columbia University, July 1999.
• [13] Khomenko, V.: Model checking based on Petri net unfolding prefixes, Ph.D. Thesis, School of Computer Science, University of Newcastle upon Tyne, 2002.
• [14] Kishinevsky,M., Kondratyev, A., Taubin, A., Varshavsky, V.: Concurrent hardware: the theory and practice of self-timed design, Series in Parallel Computing,Wiley-Interscience, JohnWiley& Sons, Inc., 1994.
• [15] Kondratyev, A., Lwin, K.: Design of asynchronous circuits using synchronous CAD tools, IEEE Design & Test of Computers, 19(4), 2002, 107-117.
• [16] Linder, D. H., Harden, J. C.: Phased Logic: supporting the synchronous design paradigm with delayinsensitive circuitry, IEEE Transactions on Computers, 45, September 1996, 1031-1044.
• [17] Montanari, U., Rossi, F.: Contextual nets, Acta Informacia, 32(6), 1995, 545-596.
• [18] Petri, C. A.: Kommunikation mit automaten (Communicating with automata), Ph.D. Thesis, University of Bonn, 1962.
• [19] Poliakov, I., Sokolov, D., Mokhov, A.: Workcraft: a static data flow structure editing, visualisation and analysis tool, Proc. International Conference on Application and Theory of Petri Nets, June 2007.
• [20] Rosenblum, L., Yakovlev, A.: Signal graphs: from self-timed to timed ones, Proceedings of International Workshop on Timed Petri Nets, IEEE Computer Society Press, Torino, Italy, July 1985.
• [21] Shang, D., Burns, F., Koelmans, A., Yakovlev, A., Xia, F.: Asynchronous system synthesis based on direct mapping using VHDL and Petri nets, IEE Proceedings, Computers and Digital Techniques, 151(3), May 2004, 209-220.
• [22] Sokolov, D., Bystrov, A., Yakovlev, A.: Direct mapping of low-latency asynchronous controllers from STGs, IEEE Transactions on Computer-Aided Design, (To appear), 2006.
• [23] Sokolov, D., Murphy, J. P., Bystrov, A., Yakovlev, A.: Design and analysis of dual-rail circuits for security applications, IEEE Transactions on Computers, 54(4), April 2005, 449-460.
• [24] Sokolov, D., Poliakov, I., Yakovlev, A.: Asynchronous data path models, International Conference Application of Concurrency to System Design, July 2007.
• [25] Sparsø, J., Furber, S.: Principles of asynchronous circuit design: a system perspective, Kluwer Academic Publishers, 2001.
• [26] Sproull, R. F., Sutherland, I. E.,Molnar, C. E.: The counterflow pipeline processor architecture, IEEE Design & Test of Computers, 11(3), 1994, 48-59.
• [27] Toms, W.: Synthesis of quasi-delay-insensitive datapath circuits, Ph.D. Thesis, Dept. of Computer Science, University of Manchester, 2006.
• [28] Vogler, W., Wollowski, R.: Decomposition in asynchronous circuit design, in: Concurrency and Hardware Design (J. Cortadella, A. Yakovlev, G. Rozenberg, Eds.), vol. 2549 of Lecture Notes in Computer Science, Springer-Verlag, 2002, 152-190.
• [29] 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.
• [30] Yoneda, T., Onda, H., Myers, C. J.: Synthesis of speed independent circuits based on decomposition, Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC), IEEE Computer Society Press, April 2004.
• [31] Zhou, Y., Sokolov, D., Yakovlev, A.: Cost-aware synthesis of asynchronous circuit, Proc. International Conference Computer-Aided Design (ICCAD), November 2006.