2006 Articles
An Efficient Algorithm for the Analysis of Cyclic Circuits
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.
Subjects
Files
-
neiroukh2006efficient.pdf application/pdf 91.3 KB Download File
Also Published In
- Title
- IEEE Computer Society Annual Symposium on ISVLSI 06: proceedings: emerging VLSI technologies and architectures: 2-3 March 2006, Karlsruhe, German
- Publisher
- IEEE Computer Society
- DOI
- https://doi.org/10.1109/ISVLSI.2006.18
More About This Work
- Academic Units
- Computer Science
- Published Here
- September 22, 2011