On breakable cyclic definitions

ABSTRACT

In the course of hardware system design or real-time process control, high-level specifications may contain simultaneous definitions of concurrent modules whose information flow forms cyclic dependencies without the separation of state-holding elements. The temporal behavior of these cyclic definitions may be meant to be combinational rather than sequential. Most prior approaches to analyzing cyclic combinational circuits were built upon the formulation of ternary-valued simulation at the circuit level. This work shows the limitation of this formulation and investigates, at the functional level, the most general condition where cyclic definitions are semantically combinational. It turns out that the prior formulation is a special case of our treatment. Our result admits strictly more flexible high-level specifications. Furthermore, it allows a higher-level analysis of combinationality, and, thus, no costly synthesis of a high-level description into a circuit netlist before combinationality analysis can be performed. With our formulation, when the target is software implementations, combinational cycles need not be broken as long as the execution of the underlying system obeys a sequencing execution rule. For hardware implementations, combinational cycles are broken and replaced with acyclic equivalents at the functional level to avoid malfunctioning in the final physical realization.

REFERENCES

• 1: Gérard Berry, The foundations of Esterel, Proof, language, and interaction: essays in honour of Robin Milner, MIT Press, Cambridge, MA, 2000
• 2: [2] G. Berry. The constructive semantics of pure Esterel. Draft book, 1999.
• 3: [3] R. Bryant. Boolean analysis of MOS circuits. IEEE Trans. Computer-Aided Design, pages 634-649, July 1987.
• 4: [4] J. Brzozowski and C.-J. Seger. Asynchronous Circuits. Springer-Verlag, 1995.
• 5: Stephen A. Edwards, Making cyclic circuits acyclic, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775874]
• 6: Stephen A. Edwards , Edward A. Lee, The semantics and execution of a synchronous block-diagram language, Science of Computer Programming, v.48 n.1, p.21-42, July 2003
• 7: [7] G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, vol. 20, pages 151-174, 1998.
• 8: Nicolas Halbwachs, Synchronous Programming of Reactive Systems, Kluwer Academic Publishers, Norwell, MA, 1992
• 9: [9] N. Halbwachs and F. Maraninchi. On the symbolic analysis of combinational loops in circuits and synchronous programs. In Proc. Euromicro, 1995.
• 10: Neil Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing, v.17 n.5, p.935-938, October 1988 [doi>10.1137/0217058]
• 11: [11] N. Jones. Space-bounded reducibility among combinatorial problems. Journal of Computer and System Sciences, vol. 11, pages 68-85, 1975.
• 12: [12] R. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85-104, Plenum Press, 1972.
• 13: [13] W. Kautz. The necessity of closed circuit loops in minimal combinational circuits. IEEE Trans. on Computers, pages 162-164, 1970.
• 14: Bill Lin , A. Richard Newton, Implicit Manipulation of Equivalence Classes Using Binary Decision Diagrams, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.81-85, October 14-16, 1991
• 15: [15] S. Malik. Analysis of cyclic combinational circuits. IEEE Trans. on Computer-Aided Design, vol. 13, no. 7, pages 950-956, July 1994.
• 16: Kedar S. Namjoshi , Robert P. Kurshan, Efficient Analysis of Cyclic Definitions, Proceedings of the 11th International Conference on Computer Aided Verification, p.394-405, July 06-10, 1999
• 17: Marc D. Riedel , Jehoshua Bruck, The synthesis of cyclic combinational circuits, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775875]
• 18: [18] M. Riedel and J. Bruck. Cyclic combinational circuits: analysis for synthesis. In Proc. Int'l Workshop on Logic and Synthesis, pages 105-112, 2003.
• 19: [19] W. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, vol. 4, pages 177-192, 1970.
• 20: Thomas Robert Shiple , Alberto Sangiovanni-Vincentelli, Formal analysis of synchronous circuits, University of California, Berkeley, 1996
• 21: Thomas R. Shiple , Gerard Berry , Herve Touati, Constructive Analysis of Cyclic Circuits, Proceedings of the 1996 European conference on Design and Test, p.328, March 11-14, 1996
• 22: Leon Stok, False loops through resource sharing, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.345-348, November 1992, Santa Clara, California, United States