The synthesis of cyclic combinational circuits

ABSTRACT

Digital circuits are called combinational if they are memoryless: they have outputs that depend only on the current values of the inputs. Combinational circuits are generally thought of as acyclic (i.e., feed-forward) structures. And yet, cyclic circuits can be combinational. Cycles sometimes occur in designs synthesized from high-level descriptions. Feedback in such cases is carefully contrived, typically occurring when functional units are connected in a cyclic topology. Although the premise of cycles in combinational circuits has been accepted, and analysis techniques have been proposed, no one has attempted the synthesis of circuits with feedback at the logic level.We propose a general methodology for the synthesis of multilevel combinational circuits with cyclic topologies. Our approach is to introduce feedback in the substitution / minimization phase, optimizing a multilevel network description for area. In trials with benchmark circuits, many were optimized significantly, with improvements of up to 30% in the area. superior to acyclic.We argue the case for radically rethinking the concept of "combinational" in circuit design: we should no longer think of combinational logic as acyclic in theory or in practice, since nearly all combinational circuits are best designed with cycles.

REFERENCES

• 1: Benchmarks from the 1993 Int'l Workshop on Logic Synthesis, available at http://www.cbl.ncsu.edu/.
• 2: Benchmarks from "Logic Minimization Algorithms for VLSI Synthesis," by R. K. Brayton et al., available at ftp://ic.eecs.berkeley.edu/.
• 3: R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli, "Multilevel Logic Synthesis," Proceedings of the IEEE, Vol. 78, No. 2, pp. 264--300, 1990.
• 4: J. A. Brzozowski and C.-J. H. 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: D. A. Huffman, "Combinational Circuits with Feedback," Recent Developments in Switching Theory, A. Mukhopadhyay, ed., pp. 27--55, 1971.
• 7: W. H. Kautz, "The Necessity of Closed Circuit Loops in Minimal Combinational Circuits," IEEE Trans. Comp., Vol. C-19, pp. 162--166, 1970.
• 8: S. Malik, "Analysis of Cyclic Combinational Circuits," IEEE Trans. Computer-Aided Design, Vol. 13, No. 7, pp. 950--956, 1994.
• 9: A. Raghunathan, P. Ashar, and S. Malik, "Test Generation for Cyclic Combinational Circuits," IEEE Trans. Computer-Aided Design, Vol. 14, No. 11, pp. 1408--1414, 1995.
• 10: M. Riedel and J. Bruck, "Cyclic Combinational Circuits: Analysis for Synthesis," Int'l Workshop Logic and Synthesis, 2003.
• 11: R. L. Rivest, "The Necessity of Feedback in Minimal Monotone Combinational Circuits," IEEE Trans. Comp., Vol. C-26, No. 6, pp. 606--607, 1977.
• 12: E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton and A. Sangiovanni-Vincentelli, "SIS: A System For Sequential Circuit Synthesis," Tech. Rep., UCB/ERL M92/41, Electronics Research Lab, University of California, Berkeley, 1992.
• 13: Thomas Robert Shiple , Alberto Sangiovanni-Vincentelli, Formal analysis of synchronous circuits, 1996
• 14: T. R. Shiple, V. Singhal, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, "Analysis of Combinational Cycles in Sequential Circuits," IEEE Int'l Symp. Circuits and Systems, Vol. 4, pp. 592--595, 1996.
• 15: T. R. Shiple, G. Berry, and H. Touati, "Constructive Analysis of Cyclic Circuits,"
• 16: R. A. Short, "A Theory of Relations Between Sequential and Combinational Realizations of Switching Functions," Stanford Electronics Laboratories, Tech. Rep. 098-1, pp. 33--34, 102--114, 1960.
• 17: A. Srinivasan and S. Malik, "Practical Analysis of Cyclic Combinational Circuits," IEEE Custom Integrated Circuits Conf., pp. 381--384, 1996.
• 18: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

General Terms:
Algorithms, Design

Keywords:
combinational logic, cycles, feedback, logic synthesis