State encoding of large asynchronous controllers

ABSTRACT

A novel method to solve the state encoding problem in Signal Transition Graphs is presented. It is based on the structural theory of Petri nets and can be applied to large specifications with hundreds of signals. This new method opens the door to incorporate logic synthesis in the design flow of large control circuits obtained from high-level specifications. The experimental results validate the quality of the encoded circuits and show the significant improvements that can be obtained by the synthesis of large controllers.

REFERENCES

• 1: Kees van Berkel, Handshake circuits: an asynchronous architecture for VLSI programming, Cambridge University Press, New York, NY, 1993
• 2: Josep Carmona , Jordi Cortadella, ILP Models for the Synthesis of Asynchronous Control Circuits, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.818, November 09-13, 2003 [doi>10.1109/ICCAD.2003.82]
• 3: T. Chelcea , S. Nowick , A. Bardsley , D. Edwards, A Burst-Mode Oriented Back-End for the Balsa Synthesis System, Proceedings of the conference on Design, automation and test in Europe, p.330, March 04-08, 2002
• 4: J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. A region-based theory for state assignment in speed-independent circuits. IEEE Transactions on Computer-Aided Design, 16(8):793--812, Aug. 1997.
• 5: J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. Logic Synthesis of Asynchronous Controllers and Interfaces. Springer-Verlag, 2002.
• 6: Jörg Desel , Javier Esparza, Reachability in cyclic extended free-choice systems, Theoretical Computer Science, v.114 n.1, p.93-118, June 14 1993
• 7: D. Edwards and A. Bardsley. Balsa: An asynchronous hardware synthesis language. The Computer Journal, 45(1):12--18, 2002.
• 8: Robert M. Fuhrer , Bill Lin , Steven M. Nowick, Symbolic hazard-free minimization and encoding of asynchronous finite state machines, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.604-611, November 05-09, 1995, San Jose, California, United States
• 9: F. García-Vallés and J. M. Colom. Structural analysis of signal transition graphs. In D. H. I. B. Farwer and M. Stehr, editors, Proceedings of the Workshop Petri Nets in System Engineering (PNSE'97). Modelling, Verification and Validation, pages 123--134, 1997.
• 10: Victor Khomenko , Maciej Koutny , Alex Yakovlev, Detecting State Coding Conflicts in STG Unfoldings Using SAT, Proceedings of the Third International Conference on Application of Concurrency to System Design, p.51, June 18-20, 2003
• 11: K.-J. Lin, J.-W. Kuo, and C.-S. Lin. Direct synthesis of hazard-free asynchronous circuits from STGs based on lock relation and MG-decomposition approach. In Proc. European Design and Test Conference, pages 178--183. IEEE Computer Society Press, 1994.
• 12: T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541--574, Apr. 1989.
• 13: E. Pastor and J. Cortadella. An efficient unique state coding algorithm for signal transition graphs. In Proc. International Conf. Computer Design (ICCD), pages 174--177, Oct. 1993.
• 14: Manuel Silva , Enrique Teruel , José Manuel Colom, Linear Algebraic and Linear Programming Techniques for the Analysis of Place or Transition Net Systems, Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, the volumes are based on the Advanced Course on Petri Nets, p.309-373, September 01, 1996
• 15: P. Vanbekbergen. Synthesis of Asynchronous Control Circuits from Graph-Theoretic Specifications. PhD thesis, Catholic University of Leuven, Sept. 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
asynchronous circuits, petri nets, state encoding