Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-12-22
2002-10-29
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06473885
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to techniques for converting representations of digital circuits, such as logic diagrams or schematics, into layouts for circuit implementation, and more specifically to the identification of logic input equivalences for controlling and optimizing circuit area and circuit delays during the layout process.
2. Description of the Prior Art
Many very sophisticated logic synthesis and layout tools have been developed for producing circuit layouts from circuit and logic diagrams. One recent article, “Effective Coupling between Logic Synthesis and Layout Tools for Synthesis of Area and Speed-Efficient Circuits”, Chandrasekhar, McCharles and Wallace, published in VLSI DESIGN, 1997, Vol. 5, No. 2, pp. 125-140, co-authored by the inventor hereof, proposes coupling between logic synthesis and layout tools to improve post-layout circuit implementation.
As noted in that article, many circuits produced by synthesis or other methods contain internal nodes at the outputs of logic gates that implement the same logic function and are therefore logically equivalent. Such nodes are considered output equivalent and techniques are provided for exploiting output equivalents during the layout of digital circuits. Similarly, input equivalence is demonstrated in logic circuits in which the output of an output gate does not change even if the circuit configuration is changed by interchanging the drivers connected to input gates feeding that output gate, as shown in
FIG. 8
of that article.
Although techniques are provided for working with output equivalence, what are needed are techniques for identifying and exploiting input equivalences in the synthesis and layout of digital logic circuits.
SUMMARY OF THE INVENTION
The present invention provides improved techniques for identifying input equivalence in digital circuits for use, for example, in swapping pins in order to modify circuit layout. These techniques include the steps of decomposing the circuit into one or more regions, then decomposing the logic function of each region into a directed graph of logic functions, and using the directed graph, identifying pin swap groups and swapping pins as desired for final layout or configuration.
In one embodiment, the present invention decomposes the circuit into fanout free regions (FFRs), and the logic function of each fanout free region is decomposed by generating quasi canonical models for the cells of the circuit. Then, a swap structure is created using these models to form the directed graph, to facilitate identification of input equivalences. The present invention proceeds by looking for extensible symmetric logic functions (such as AND, OR and XOR functions) within and between gates in a logic circuit. Such functions are grown backwards as long as they can continue to be extended and then analyzed to identify input equivalences to identify permutable pins.
In another embodiment, the circuit is decomposed into coalesced regions, where each member of a group of coalesced regions has at most fan out to only one other region. The decomposition of the logic functions of the coalesced regions are accomplished by constructing binary decision diagrams (BDD) for outputs of these regions, and then using the corresponding BDD to construct a ds-prime decomposition for each of the logic function, forming the directed graph. These BDDs are then used to associate nets in the original circuit with the arcs of the directed graph, and compared to identify input equivalences.
The present invention may be conveniently implemented in a computer by coding appropriate software on computer coded media or by any other conventional means of programming a computer. The required software may be written by a person of ordinary skill in the art of developing programs for analyzing digital circuits for layout and similar operations.
These and other features and advantages of this invention will become further apparent from the detailed description and accompanying figures that follow. In the figures and description, numerals indicate the various features of the invention, like numerals referring to like features throughout both the drawings and the description.
REFERENCES:
patent: 5436849 (1995-07-01), Drumm
patent: 5610829 (1997-03-01), Trimberger
patent: 5752000 (1998-05-01), McGeer et al.
patent: 6023566 (2000-02-01), Belkhale et al.
patent: 6086626 (2000-07-01), Jain et al.
patent: 6212669 (2001-04-01), Jain
patent: 6360352 (2002-03-01), Wallace
O. Choy et al., Test Generation with Dynamic Probe Points in High Observability Testing Environment, IEEE Transactions on Computers, vol. 45, Issue 1, pp. 88-96, Jan. 1996.*
J. Cong et al., An Improved Graph-Based FPGA Technology Mapping Algorithm for Delay Optimization, IEEE 1992 International Conference on VLSI in Computers and Processors, pp. 154-158, Apr. 1992.*
D. Wallace, High-Level Delay Estimation for Technology-Independent Logic Equations, 1990 IEEE Conference on Computer Aided Design, pp. 188-191, Nov. 1990.*
A. Prabhu, LOGOPT—A Multi-Level Logic Synthesis and Optimization System, 1989 IEEE Custom Integrated Circuits Conference, pp. 4.1/1-4.1/4, May 1989.*
A Nagoya et al., Multi-Level Logic Optimization for Large Scale ASICs, 1990 IEEE International Conference on Computer Aided Design, pp. 564-567, Nov. 1990.*
K. -H. Tsai, R. Thompson, J. Rajski, M. Marek-Sadowska, Mentor Graphics Corporation, Wilsonville, OR USA, STAR-ATPG: A High Speed Test Pattern Generator For Large Scan Designs, Dept. of E.C.E., University of California, Santa Barbara, CA., USA.
Valeria Bertacco & Maurizio Damiani, “Boolean Function Representation Based on Disjoint-Support Decompositions”, ICCD96, Oct. 1996, pp. 27-32, IEEE Computer Society Press, Los Alamitos, CA, USA.
Valeria Bertacco & Maurizio Damiani, “The Disjunctive Decomposition of Logic Functions”, ICCD97, Nov. 1997, pp. 78-82, IEEE Computer Society, Los Alamitos, CA, USA.
S-C. Chang, K-T. Cheng, N-S. Woo & M. Marek-Sadowska, “Layout Driven Logic Synthesis for FPGAs”, DAC94, Jun. 1994, pp. 308-313.
P. Chong, Y. Jiang, S. Khatri, S. Sinha & R. Brayton, “Don't Care Wires in Logical/Physical Design”, International Workshop on Logic Synthesis (IWLSOO), Nov. 1, 1999, pp. 1-9.
Luis Entrena & Kwang-Ting Cheng, “Sequential Logic Optimization By Redundancy Addition And Removal”, ICCAD93, Nov. 1993, pp. 310-315, IEEE Computer Society Press, Los Alamitos, CA, USA.
Hans T. Heineken & Wojciech Maly, “Interconnect Yield Model for Manufacturability Prediction in Synthesis of Standard Cell Based Designs”, ICCAD96, Nov. 1996, pp. 368-373, IEEE Computer Society Press, Los Alamitos, CA, USA.
Yusuke Matsunaga, “An Exact and Efficient Algorithm for Disjunctive Decomposition”, SASIMI98, Oct. 1998, pp. 44-50.
Dirk Moller, Janett Mohnke & Michael Weber, “Detection of Symmetry of Boolean Functions Represented by ROBDDs”, ICCAD93, Nov. 1993, pp. 680-684, IEEE Computer Society Press, Los Alamitos, CA, USA.
Mandalagiri S. Chandrasekhar, Robert H. McCharles and David E. Wallace, “Effective Coupling between Logic Synthesis and Layout Tools for Synthesis of Area and Speed-Efficient Circuits”, VLSI Design, 1997, vol. 5, No. 2, pp. 125-140.
D. Brasen, T. Schaefer, A. Ginetti, S. Chu, Compass Design Automation, “Post-Placement Buffer Reoptimization”, 1992 IEEE, pp. 156-161.
Blakely , Sokoloff, Taylor & Zafman LLP
Mentor Graphics Corporation
Siek Vuthe
Thompson A. M.
LandOfFree
Digital circuit layout techniques using circuit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital circuit layout techniques using circuit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital circuit layout techniques using circuit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2995013