Making cyclic circuits acyclic

ABSTRACT

Cyclic circuits that do not hold state or oscillate are often the most convenient representation for certain functions, such as arbiters, and can easily be produced inadvertently in high-level synthesis, yet are troublesome for most circuit analysis tools.This paper presents an algorithm that generates an acyclic circuit that computes the same function as a given cyclic circuit for those inputs where the cyclic circuit does not oscillate or hold state. The algorithm identifies all patterns on inputs and internal nodes that lead to acyclic evaluation orders for the cyclic circuit, which are represented as acyclic circuit fragments, then combines these to produce an acyclic circuit that can exhibit all of these behaviors.Experimental results suggest this potentially exponential algorithm is practical for small circuits and may be improved to handle larger circuits. This algorithm should make dealing with cyclic combinational circuits nearly as easy as dealing with their acyclic counterparts.

References

1. Gérard Berry. Esterel on hardware. Philosophical Transactions of the Royal Society of London. Series A, 339:87--103, April 1992. Issue 1652, Mechanized Reasoning and Hardware Design.
2. Gérard Berry. The constructive semantics of pure Esterel. Draft book, 1999.
3. Gérard Berry and Georges Gonthier. The Esterel synchronous programming language: Design, semantics, implementation. Science of Computer Programming, 19(2):87--152, November 1992.
4. Janusz A. Brzozowski and Carl-Johan H. Seger. Asynchronous Circuits. Springer-Verlag, 1995.
5. W. H. Kautz. The necessity of closed loops in minimal combinational circuits. IEEE Transactions on Computers, C-19(2):162--164, February 1970.
6. Sharad Malik. Analysis of cyclic combinational circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 13(7):950--956, July 1994.
7. Marc D. Riedel and Jeoshua Bruck. The synthesis of cyclic combinational circuits. In Proceedings of the 40th Design Automation Conference, Anaheim, California, jun 2003.
8. Ronald L. Rivest. The necessity of feedback in minimal monotone combinational circuits. IEEE Transactions on Computers, 26(6):606--607, 1977.
9. Thomas R. Shiple, Gérard Berry, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. Logical analysis of combinational cycles. Technical Report UCB/ERL M02/21, University of California, Berkeley, June 2002.
10. Thomas R. Shiple, Gérard Berry, and Hervé Touati. Constructive analysis of cyclic circuits. In Proceedings of the European Design and Test Conference, pages 328--333, Paris, France, March 1996.
11. Thomas R. Shiple, Vigyan Singhal, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. Analysis of combinational cycles in sequential circuits. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), volume~IV, pages 592--595, May 1996.
12. Thomas Robert Shiple. Formal Analysis of Synchronous Circuits. PhD thesis, University of California, Berkeley, October 1996. Memorandum UCB/ERL M96/76.
13. Leon Stok. False loops through resource sharing. In Proceedings of the IEEE/ACM International Conference on Computer Aided Design (ICCAD), pages 345--348, San Jose, California, November 1992.
14. Horia Toma. Analyse constructive et optimisation séquentielle des circuits générés à partir du langage synchrone réactif Esterel {Constructive Analysis and Sequential Optimization of Circuits Generated from the Synchronous Reactive Language Esterel}. PhD thesis, École des Mines de Paris, 1997.

Index Terms

• Hardware

  • Integrated circuits

    • Logic circuits