Decomposing specifications with concurrent outputs to resolve state coding conflicts in asynchronous logic synthesis

ABSTRACT

Synthesis of asynchronous logic using the tool Petrify requires a state graph with a complete state coding. It is common for specifications to exhibit concurrent outputs, but Petrify is sometimes unable to resolve the state coding conflicts that arise as a result, and hence cannot synthesise a circuit. A pair of decomposition heuristics (expressed in the language of Delay-Insensitive Sequential Processes) are given that helps one to obtain a synthesisable specification. The second heuristic has been successfully applied to a set of nine benchmarks to obtain significant reductions both in area and in synthesis time, compared with synthesis performed on the original specifications.

References

1. J. Carmona, J. Cortadella, and E. Pastor. A Structural Encoding Technique for the Synthesis of Asynchronous Circuits. Fundamenta Informaticae, 34:1--23, 2002.
2. T.-A. Chu. Synthesis of Self-timed VLSI Circuits from Graph-theoretic Specifications. PhD thesis, Department of Electrical Engineering and Computer Science, June 1987. MIT/LCS/TR-393.
3. J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, and A. Yakovlev. Petrify: A Tool for Manipulating Concurrent Specifications and Synthesis of Asynchronous Controllers. IEICE Transactions on Information and Systems, 3(E80-D):315--325, 1997.
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 of Integrated Circuits and Systems, 16(8):793--812, August 1997.
5. C. A. R. Hoare. Communicating Sequential Processes. Prentice-Hall International Series in Computer Science, 1985.
6. M. B. Josephs and D. P. Furey. A Programming Approach to the Design of Asynchronous Logic Blocks. In J. Cortadella, A. Yakovlev, and G. Rozenberg, editors, Concurrency and Hardware Design Advances in Petri-Nets, LNCS, volume 2549, pages 34--60. Springer Verlag, 2002.
7. M. B. Josephs and J. T. Udding. An Overview of D-I Algebra. System Sciences, 1993, IEEE Proc. of the Twenty-Sixth Hawaii International Conference, 1:329--338, January 1993.
8. A. Madalinski, A. Bystrov, V. Khomenko, and A. Yakovlev. Visualisation and Resolution of Encoding Conflicts in Asynchronous Circuit Design. IEEE Proc. on Computers and Digital Techniques, 150(5):285--293, September 2003.
9. R. Manohar. An Analysis of Reshuffled Handshaking Expansions. Proc. of the Seventh International Symposium on Advanced Research in Asynchronous Circuits and Systems, pages 184--193, March 2001.
10. S. M. Nowick, K. Y. Yun, and D. L. Dill. Practical Asynchronous Controller Design. International Conference on Computer Design, ICCD, pages 341--345, October 1992.
11. W. Vogler and R. Wollowski. Decomposition in Asynchronous Circuit Design. In J. Cortadella, A. Yakovlev, and G. Rozenberg, editors, Concurrency and Hardware Design Advances in Petri-Nets, LNCS, volume 2549, pages 152--190. Springer Verlag, 2002.
12. K. Y. Yun and D. L. Dill. Automatic Synthesis of 3D Asynchronous Controllers. International Conference on Computer-Aided Design, ICCAD, pages 576--580, November 1992.
13. K. Y. Yun and D. L. Dill. A High-Performance Asynchronous SCSI Controller. International Conference on Computer Design, ICCD, pages 44--49, October 1995.

Index Terms

• Hardware

  • Electronic design automation

    • Hardware description languages and compilation

    • High-level and register-transfer level synthesis