Proceedings of the 40th Design Automation Conference 2003 (Design Automation Conference//Proceedings)
Publisher: Ieee
Published: August 2003
Language: eng
Format: Paperback
Number of pages: 832
ISBN-13: 9781581136883
Subjects: Computer aided design (CAD); Data Modeling & Design; Data Processing - Optical Data Processing; Internet - Web Site Design; Computers; Computer Books: General
Description: 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.