An Efficient Algorithm for the Analysis of Cyclic Circuits

Neiroukh, Osama; Edwards, Stephen A.; Song, Xiaoyu

Compiling high-level hardware languages can produce circuits containing combinational cycles that can never be sensitized. Such circuits do have well-defined functional behavior, but wreak havoc with most logic synthesis and timing tools, which assume acyclic combinational logic. As such, some sort of cycle-removal step is usually necessary for handling these circuits. We present an algorithm able to quickly and exactly characterize all combinational behavior of a cyclic circuit. It iteratively examines the boundary between gates whose outputs are and are not defined and works backward to find additional input patterns that make the circuit behave combinationally. It produces a minimal set of sets of assignments to inputs that together cover all combinational behavior. This can be used to restructure the circuit into an acyclic equivalent, report errors, or as an optimization aid. Experiments show our algorithm runs several orders of magnitude faster than existing ones on real-life cyclic circuits, making it useful in practice.



  • thumnail for neiroukh2006efficient.pdf neiroukh2006efficient.pdf application/pdf 91.3 KB Download File

Also Published In

IEEE Computer Society Annual Symposium on ISVLSI 06: proceedings: emerging VLSI technologies and architectures: 2-3 March 2006, Karlsruhe, German
IEEE Computer Society

More About This Work

Academic Units
Computer Science
Published Here
September 22, 2011