Synthesis of Asynchronous Hardware from Petri Nets

1. Allan, A., et al.: 2001 Technology Roadmap for Semiconductors. Computer, 42–53 (January 2002)

   Google Scholar 

2. van Berkel, K.: Handshake Circuits: an Asynchronous Architecture for VLSI Programming. International Series on Parallel Computation, vol. 5. Cambridge University Press, Cambridge (1993)

   MATH  Google Scholar 

3. Best, E., Grahlmann, B.: PEP – more than a Petri Net Tool. In: Margaria, T., Steffen, B. (eds.) TACAS 1996. LNCS, vol. 1055, pp. 397–401. Springer, Heidelberg (1996)

   Google Scholar 

4. Blunno, I., Lavagno, L.: Automated synthesis of micro-pipelines from behavioral Verilog HDL. In: Proc. of IEEE Symp. on Adv. Res. in Async. Cir. and Syst (ASYNC 2000), pp. 84–92. IEEE CS Press, Los Alamitos (2000)

   Chapter  Google Scholar 

5. Brayton, R., Hachtel, G., McMullen, C., Sangiovanni-Vincentelli, A.: Logic Minimisation Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Dordrecht (1984)

   Google Scholar 

6. Bystrov, A., Yakovlev, A.: Asynchronous Circuit Synthesis by Direct Mapping: Interfacing to Environment. In: Proc. ASYNC 2002, Manchester (April 2002)

   Google Scholar 

7. Carmona, J., Cortadella, J.: Input/Output Compatibility of Reactive Systems. In: Aagaard, M.D., O’Leary, J.W. (eds.) FMCAD 2002. LNCS, vol. 2517. Springer, Heidelberg (2002)

   Chapter  Google Scholar 

8. Carmona, J., Cortadella, J.: ILP Models for the Synthesis of Asynchronous Control Circuits. In: Proc. International Conf. Computer-Aided Design (ICCAD), San Jose, California, USA (November 2003)

   Google Scholar 

9. Carmona, J., Cortadella, J., Pastor, E.: A structural encoding technique for the synthesis of asynchronous circuits. Fundamenta Informaticae, 135–154 (April 2001)

   Google Scholar 

10. Carrion, C., Yakovlev, A.: Design and Evaluation of Two Asynchronous Token Ring Adapters. Tech. Rep. CS-TR-562, School of Comp. Sci., Univ. of Newcastle (1996)

    Google Scholar 

11. Chapiro, D.M.: Globally-Asynchronous Locally-Synchronous Systems. PhD thesis, Stanford University (October 1984)

    Google Scholar 

12. Chelcea, T., Bardsley, A., Edwards, D., Nowick, S.M.: A burst-mode oriented back-end for the Balsa synthesis system. In: Proc. of Design, Automation and Test in Europe (DATE 2002), pp. 330–337. IEEE CS Press, Los Alamitos (2002)

    Chapter  Google Scholar 

13. Chu, T.-A., Leung, C.K.C., Wanuga, T.S.: A design methodology for concurrent VLSI systems. In: Proc. International Conf. Computer Design (ICCD), pp. 407–410. IEEE Computer Society Press, Los Alamitos (1985)

    Google Scholar 

14. Chu, T. -A.: Synthesis of Self-Timed VLSI Circuits from Graph-Theoretic Specifications. PhD Thesis, MIT/LCS/TR-393 (1987)

    Google Scholar 

15. Cortadella, J., Kishinevsky, M., Burns, S.M., Stevens, K.S., Kondratyev, A., Lavagno, L., Taubin, A., Yakovlev, A.: Lazy Transition Systems and Asynhronous Circuit Synthesis with Relative Timing Assumptions. IEEE Trans. of CAD 21(2), 109–130 (2002)

    Google Scholar 

16. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: A Region-Based Theory for State Assignment in Speed-Independent Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 16(8), 793–812 (1997)

    Article  Google Scholar 

17. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Automatic Handshake Expansion and Reshuffling Using Concurrency Reduction. In: Proc. of HWPN 1998, pp. 86–110 (1998)

    Google Scholar 

18. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic Synthesis of Asynchronous Controllers and Interfaces. Springer, Heidelberg (2002)

    Google Scholar 

19. Dally, W.J., Poulton, J.W.: Digital Systems Engineering. Cambridge University Press, Cambridge (1998)

    MATH  Google Scholar 

20. David, R.: Modular design of asynchronous circuits defined by graphs. IEEE Transactions on Computers 26(8), 727–737 (1977)

    Article  MATH  Google Scholar 

21. Desel, J., Esparza, J.: Reachability in cyclic extended free-choice systems. TCS, vol. 114. Elsevier Science Publishers B.V, Amsterdam (1993)

    Google Scholar 

22. Edwards, D., Bardsley, A.: Balsa: An asynchronous hardware synthesis language. The Computer Journal 45(1), 12–18 (2002)

    Article  MATH  Google Scholar 

23. Esparza, J.: Decidability and Complexity of Petri Net Problems – an Introduction. In: Reisig, W., Rozenberg, G. (eds.) APN 1998. LNCS, vol. 1491, pp. 374–428. Springer, Heidelberg (1998)

    Google Scholar 

24. Esparza, J.: A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs. In: Proc. of the 3rd Int. Conf. Applications of Concurrency to System Design (ACSD 2003), June 2003, pp. 61–70. IEEE CS Press, Los Alamitos (2003)

    Chapter  Google Scholar 

25. Esparza, J., Römer, S., Vogler, W.: An Improvement of McMillan’s Unfolding Algorithm. FMSD 20(3), 285–310 (2002)

    MATH  Google Scholar 

26. Ferguson, D., Hagedorn, M.: The Application of NULL Convention Logic to Microcontroller/Microconverter Product. In: Second ACiD-WG Workshop, Munich (2002), http://www.scism.sbu.ac.uk/ccsv/ACiD-WG/Workshop2FP5/Programme/

27. Furber, S.: Industrial take-up of asynchronous design, Keynote talk at the Second ACiD-WG Workshop, Munich (2002), http://www.scism.sbu.ac.uk/ccsv/ACiD-WG/Workshop2FP5/Programme/

28. Furber, S.B., Efthymiou, A., Singh, M.: A Power-Efficient Duplex Communication System. In: Proc. of AINT 2000, pp. 145–150. TU Delft, The Netherlands (2000)

    Google Scholar 

29. García Vallés, F., Colom, J.M.: Structural analysis of signal transition graphs. In: Holdt In, D., Farwer, B., Stehr, M.O. (eds.) Proceedings of the Workshop Petri Nets in System Engineering (PNSE 1997), Modelling, Verification and Validation, Hamburg, Germany, September 25–26, pp. 123–134 (1997), Published as report n 205 of the Computer Science Department of the University of Hamburg

    Google Scholar 

30. Heljanko, K.: Using Logic Programs with Stable Model Semantics to Solve Deadlock and Reachability Problems for 1-Safe Petri Nets. Fundamentae Informaticae 37(3), 247–268 (1999)

    MATH  MathSciNet  Google Scholar 

31. Heljanko, K., Khomenko, V., Koutny, M.: Parallelization of the Petri Net Unfolding Algorithm. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol. 2280, pp. 371–385. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

32. Hollaar, L.A.: Direct implementation of asynchronous control units. IEEE Transactions on Computers C-31(12), 1133–1141 (1982)

    Article  Google Scholar 

33. Kapoor, H.K., Josephs, M.B., Furey, D.P.: Verification and Implementation of Delay-Insensitive Processes in Restrictive Environments. In: Proc. of ICACSD 2004. IEEE Comp. Soc. Press, Los Alamitos (2004) (to appear)

    Google Scholar 

34. Kapoor, H.K., Josephs, M.B.: Automatically decomposing specifications with concurrent outputs to resolve state coding conflicts in asynchronous logic synthesis. In: Proc. of DAC 2004 (2004) (to appear)

    Google Scholar 

35. Khomenko, V., Koutny, M.: LP Deadlock Checking Using Partial Order Dependencies. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 410–425. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

36. Khomenko, V., Koutny, M.: Towards An Efficient Algorithm for Unfolding Petri Nets. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 366–380. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

37. Khomenko, V., Koutny, M., Vogler, V.: Canonical Prefixes of Petri Net Unfoldings. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 582–595. Springer, Heidelberg (2002); Full version: Acta Informatica 40(2), 95-118 (2003)

    Chapter  Google Scholar 

38. Khomenko, V., Koutny, M., Yakovlev, A.: Detecting State Coding Conflicts in STGs Using Integer Programming. In: Proc. of DATE 2002, pp. 338–345. IEEE Comp. Soc. Press, Los Alamitos (2002)

    Google Scholar 

39. Khomenko, V., Koutny, M., Yakovlev, A.: Detecting State Coding Conflicts in STG Unfoldings Using SAT. In: Proc. of ICACSD 2003, pp. 51–60. IEEE Comp. Soc. Press, Los Alamitos (2003); Full version: to appear in Special Issue on Best Papers from ICACSD 2003. Fundamenta Informaticae

    Google Scholar 

40. Khomenko, V., Koutny, M., Yakovlev, A.: Logic Synthesis Avoiding State Space Explosion. In: Proc. of ICACSD 2004, IEEE Comp. Soc. Press, Los Alamitos (2004), http://homepages.cs.ncl.ac.uk/victor.khomenko/home.formal/papers/papers.html ; Full version: Tech. Rep. CS-TR-813, School of Comp. Science, Univ. of Newcastle (to appear)

    Google Scholar 

41. Kinniment, D.J., Gao, B., Yakovlev, A., Xia, F.: Towards asynchronous A-D conversion. In: Proc. of ASYNC 2000, pp. 206–215. IEEE Comp. Soc. Press, Los Alamitos (2000)

    Google Scholar 

42. Kishinevsky, M., Kondratyev, A., Taubin, A., Varshavsky, V.: Concurrent Hardware: The Theory and Practice of Self-Timed Design. Series in Parallel Computing. John Wiley & Sons, Chichester (1994)

    MATH  Google Scholar 

43. Kondratyev, A., Lwin, K.: Design of asynchronous circuits using synchronous CAD tools. IEEE Design and Test of Computers 19(4), 107–117 (2002)

    Article  Google Scholar 

44. Low, K.S., Yakovlev, A.: Token Ring Arbiters: an Exercise in Asynchronous Logic Design with Petri Nets. Tech. Rep. CS-TR-537, School of Comp. Sci., Univ. of Newcastle (1995)

    Google Scholar 

45. Madalinski, A., Bystrov, A., Khomenko, V., Yakovlev, A.: Visualisation and Resolution of Coding Conflicts in Asynchronous Circuit Design. In: Proc. of DATE 2003, pp. 926–931. IEEE Comp. Soc. Press, Los Alamitos (2003); Full version: Special Issue on Best Papers from DATE 2003. IEE Proceedings: Computers & Digital Techniques vol. 150(5), pp. 285–293 (2003)

    Google Scholar 

46. McMillan, K.L.: Using Unfoldings to Avoid State Explosion Problem in the Verification of Asynchronous Circuits. In: Probst, D.K., von Bochmann, G. (eds.) CAV 1992. LNCS, vol. 663, pp. 164–174. Springer, Heidelberg (1992)

    Google Scholar 

47. De Micheli, G.: Synthesis and Optimisation of Digital Circuits. McGraw-Hill, New York (1994)

    Google Scholar 

48. Moskewicz, S., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an Efficient SAT Solver. In: Proc. of DAC 2001, pp. 530–535. ASME Technical Publishing (2001)

    Google Scholar 

49. Murata, T.: Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, 541–580 (April 1989)

    Google Scholar 

50. Pastor, E., Cortadella, J., Kondratyev, A., Roig, O.: Structural methods for the synthesis of speed-independent circuits. IEEE Transactions on Computer-Aided Design 17(11), 1108–1129 (1998)

    Article  Google Scholar 

51. Patil, S.S., Dennis, J.B.: The description and realization of digital systems. In: Proceedings of the IEEE COMPCON, pp. 223–226 (1972)

    Google Scholar 

52. Peña, M.A., Cortadella, J.: Combining process algebras and Petri nets for the specification and synthesis of asynchronous circuits. In: Proc. of IEEE Symp. on Adv. Res. in Async. Cir. and Syst (ASYNC 1996), pp. 222–232. IEEE CS Press, Los Alamitos (1996)

    Google Scholar 

53. Petri, C.A.: Kommunikation mit Automaten. PhD thesis, Bonn, Institut für Instrumentelle Mathematik (1962) (technical report Schriften des IIM Nr. 3)

    Google Scholar 

54. Riocreux, P.: Private communication. UK Asynchronous Forum (2002)

    Google Scholar 

55. Rosenblum, L.Y., Yakovlev, A.V.: Signal graphs: from self-timed to timed ones. In: Proceedings of International Workshop on Timed Petri Nets, Torino, Italy, July 1985, pp. 199–207. IEEE Computer Society Press, Los Alamitos (1985)

    Google Scholar 

56. Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, Chichester (1998)

    MATH  Google Scholar 

57. Semenov, A.: Verification and Synthesis of Asynchronous Control Circuits Using Petri Net Unfolding. PhD Thesis, University of Newcastle upon Tyne (1997)

    Google Scholar 

58. Shang, D., Xia, F., Yakovlev, A.: Asynchronous Circuit Synthesis via Direct Translation. In: Proc. Int. Symp. on Cir. and Syst. (ISCAS 2002), Scottsdale, Arizona (May 2002)

    Google Scholar 

59. Silva, M., Teruel, E., Colom, J.M.: Linear algebraic and linear programming techniques for the analysis of place/transition net systems. In: Reisig, W., Rozenberg, G. (eds.) APN 1998. LNCS, vol. 1491, pp. 309–373. Springer, Heidelberg (1998)

    Google Scholar 

60. Sparsø, J., Furber, S. (eds.): Principles of Asynchronous Circuit Design: A Systems Perspective. Kluwer Academic Publishers, Dordrecht (2001)

    Google Scholar 

61. Sokolov, D., Bystrov, A., Yakovlev, A.: STG optimisation in the direct mapping of asynchronous circuits. In: Proc. Design and Test in Europe (DATE), March 2003, pp. 932–937 (2003)

    Google Scholar 

62. Starodoubtsev, N., Bystrov, S., Goncharov, M., Klotchkov, I., Smirnov, A.: Towards Synthesis of Monotonic Circuits from STGs. In: Proc. of 2ndd Int. Conf. Applications of Concurrency to System Design (ACSD 2001), June 2001, pp. 179–180. IEEE CS Press, Los Alamitos (2001)

    Chapter  Google Scholar 

63. Starodoubtsev, N., Bystrov, S., Yakovlev, A.: Monotonic circuits with complete acknowledgement. In: Proc. of ASYNC 2003, Vancouver, pp. 98–108. IEEE CS Press, Los Alamitos (2003)

    Google Scholar 

64. Sutherland, I.E.: Micropipelines. Communications of the ACM 32(6), 720–738 (1989)

    Article  Google Scholar 

65. Valmari, A.: A stubborn attack on state explosion. Formal Methods in System Design 1(4), 297–322 (1992)

    Article  MATH  Google Scholar 

66. Vanbekbergen, P.: Synthesis of Asynchronous Control Circuits from Graph-Theoretic Specifications. PhD thesis, Catholic University of Leuven (1993)

    Google Scholar 

67. Vanbekbergen, P., Catthoor, F., Goossens, G., De Man, H.: Optimised Synthesis of Asynchronous Control Circuits form Graph-Theoretic Specifications. In: Proc. of ICCAD 1990, pp. 184–187. IEEE Comp. Soc. Press, Los Alamitos (1990)

    Google Scholar 

68. Varshavsky, V.I., Marakhovsky, V.B.: Asynchronous control device design by net model behavior simulation. In: Billington, J., Reisig, W. (eds.) ICATPN 1996. LNCS, vol. 1091, pp. 497–515. Springer, Heidelberg (1996)

    Google Scholar 

69. Varshavsky, V.I. (ed.): Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems. KluwerAcademic Publishers, Dordrecht (1990)

    MATH  Google Scholar 

70. Villiger, T., Kslin, H., Grkaynak, F.K., Oetiker, S., Fichtner, W.: Self-timed ring for globally-asynchronous locally-synchronous systems. In: Proc. International Symposium on Advanced Research in Asynchronous Circuits and Systems, May 2003, pp. 141–150. IEEE Computer Society Press, Los Alamitos (2003)

    Google Scholar 

71. Vogler, W., Wollowski, R.: Decomposition in asynchronous circuit design. In: Cortadella, J., Yakovlev, A., Rozenberg, G. (eds.) Concurrency and Hardware Design. LNCS, vol. 2549, pp. 152–190. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

72. Yakovlev, A.: Designing Control Logic for Counterflow Pipeline Processor Using Petri nets. FMSD 12(1), 39–71 (1998)

    MathSciNet  Google Scholar 

73. Yakovlev, A., Furber, S., Krenz, R.: Design, Analysis and Implementation of a Self-timed Duplex Communication System, CS-TR-761, Dept. Computing Science, Univ. of Newcastle upon Tyne (March 2002), http://www.cs.ncl.ac.uk/people/alex.yakovlev/home.informal/some_papers/duplex-TR.ps

74. Yakovlev, A., Koelmans, A.: Petri nets and Digital Hardware Design Lectures on Petri Nets II: Applications. In: Reisig, W., Rozenberg, G. (eds.) APN 1998. LNCS, vol. 1492, pp. 154–236. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

75. Yakovlev, A., Petrov, A.: Petri Nets and Asynchronous Bus Controller Design. In: Proc. of ICATPN 1990, pp. 244–262 (1990)

    Google Scholar 

76. Yakovlev, A., Varshavsky, V., Marakhovsky, V., Semenov, A.: Designing an asynchronous pipeline token ring interface. In: Proc. of 2nd Working Conference on Asynchronous Design Methdologies, London, May 1995, pp. 32–41. IEEE Comp. Society Press, N.Y (1995)

    Chapter  Google Scholar 

77. Yoneda, T., Myers, C.: Synthesis of Speed Independent Circuits based on Decomposition. In: Proceedings of ASYNC 2004, Heraklion, Greece, April 2004. IEEE CS Press, Los Alamitos (2004)

    Google Scholar 

78. Zhang, L., Malik, S.: The Quest for Efficient Boolean Satisfiability Solvers. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 17–36. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

Download references