Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-07-17
2002-03-19
Smith, Matthew (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06360352
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 synthesized by automatic logic 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 fanout-free regions (FFRs), generating quasi-canonical models to create a swap structure, identifying pin swap groups and swapping pins as desired for final layout or configuration.
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.
The present invention 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.
In a first aspect, the present invention provides a method of analyzing a digital circuit to identify input equivalences by decomposing the digital circuit into one or more regions having a first set of specified characteristics, creating a modified circuit structure from the decomposed regions, and identifying pin swap groups within the modified circuit structure.
In another aspect, the present invention provides a method of analyzing a digital circuit to identify input equivalences by decomposing the digital circuit into one or more fanout-free regions, creating a quasi-canonical circuit structure from the fanout-free regions, and identifying pin swap groups within the circuit structure.
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: 5349659 (1994-09-01), Do et al.
patent: 5448497 (1995-09-01), Ashar et al.
patent: 5524082 (1996-06-01), Horstmann et al.
patent: 5526276 (1996-06-01), Cox et al.
patent: 5774369 (1998-06-01), Horstmann et al.
patent: 6023566 (2000-02-01), Belkhale et al.
patent: 6212669 (2001-04-01), Jain
H. Selvaraj et al., Decomposition Strategies and Their Performance in FPGA Technology Mapping, Eleventh International Conference on VLSI Design, pp. 388-393, Jan. 1998.*
V. Bertacco et al., Boolean Function Representation Based on Disjoint-Support Decompositions, 1996 IEEE International Conference on Computer Design, pp. 27-32, Oct. 1996.*
M.S. Chandrasekhar et al., Application of Term Rewriting Techniques to Hardware Design Verification, 24th ACM/IEEE Conference Proceedings on Design Automation Conference, pp. 277-282, Jun. 1987.*
M.A. Perkowski et al., Fast Minimization of Mixed-Polarity AND/XOR Canonical Networks, IEEE 1992 Conference on Computer Design, pp. 33-36, Oct. 1992.*
J. Cong et al., Exploiting Signal Flow and Logic Dependency in Standard Cell Placement, 1995 Design Automation conference, pp. 399-404, Aug. 1995.*
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.
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 Logical 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.
Blakely , Sokoloff, Taylor & Zafman LLP
Smith Matthew
Thompson A. M.
LandOfFree
Digital circuit layout techniques 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital circuit layout techniques will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2819414