Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-12-22
2002-11-05
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06477688
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains to the fields of integrated circuit (IC) design. More particularly, this invention relates to electronic design automation (EDA) tools employed to assist placement and routing of an IC design.
2. Background
Logic equivalence identifies classes of permutable pins (or nets) with an IC design. In application Ser. No. 09/118,225, digital circuit layout techniques including in particular techniques for identifying logic equivalency in an IC design were disclosed. In application Ser. No. 09/470,540, additional techniques for identifying logic equivalency in an IC design were disclosed.
Such pins (or nets) may be swapped without impacting the logic of the IC design. In particular once identified these pins (or net) may be swapped to reduce wire length, improve circuit timing or reduce routing congestion, when placing and routing an IC design. Thus, an improved machine implemetable place and route technique that leverages on the identified logic equivalents, when placing and routing an IC design is desired.
SUMMARY OF THE INVENTION
At least one EDA tool is provided with first and second plurality of programming instructions. The first plurality of programming instructions are designed to determine equivalent logic in an IC design, and the second plurality of programming instructions are designed to place and route the IC design. The place and route operation includes performance of at least one place and route operation selected from a group of place and route operations consisting of choosing coupling assignments for nets and logically equivalent input pins of the IC design, and choosing coupling assignments for logically equivalent output pins and loads of the IC design.
In one embodiment, coupling assignments are chosen to minimize total wire length of an IC design. The coupling assignment selection problem is formulated as a bi-partite matching problem, more specifically, a weighted matching problem. Manhattan distances are employed in weight assignments, and penalty costs are added for congested areas. In one embodiment, coupling assignments are chosen to minimize selected total delay times. The coupling assignment selection problem is also formulated as a bi-partite matching problem, more specifically, a max-min matching problem. Slack times are determined in accordance with arrival and required times.
REFERENCES:
patent: 5618744 (1997-04-01), Suzuki et al.
patent: 5808899 (1998-09-01), Scepanovic et al.
patent: 6272668 (2001-08-01), Teene
patent: 6282693 (2001-08-01), Naylor et al.
patent: 6289490 (2001-09-01), Boyd et al.
Doom et al. (“Identifying high-level components in combinational circuits”, Proceedings of the 8th Great Lakes Symposium on VLSI, Feb. 19, 1998, pp. 313-318).*
Takeya et al. (“A generator for high-density macrocells with hierarchical structure”, Proceedings of the IEEE 1989 Custom Integrated Circuits Conference, May 15, 1989, pp. 23.5/1-23.5/4).*
Tsay (“An exact zero-skew clock routing algorithm”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, No. 2, pp. 242-249).*
Ghosh et al. (“Synthesis of wiring signature-invariant equivalence class circuit mutants and applications to benchmarking”, Proceedings of Design, Automation and Test in Europe, Feb. 23, 1998, pp. 656-663).*
Hassoun et al. (“Regularity extraction via clan-based structural circuit decomposition”, IEEE/ACM International Conference on Computer-Aided Design, Nov. 7, 1999, pp. 414-418).*
NB8909290 (“Method to Improve Chip Wiring”, IBM Technical Disclosure Bulletin, vol. 32, No. 4B, Sep. 1989, pp. 290-293 (6 pages)).*
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.
K. H. Tsai, et al., “A High Speed Test Pattern Generator for Large Scan Designs,” ITC International Test Conference, Paper 382, IEEE, 1999, pp. 1021-1030.
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, Jan. 1997.
D. Brasen, T. Schaefer, A. Ginetti, S. Chu, Compass Design Automation, “Post-Placement Buffer Reoptimization”, 1992 IEEE, pp. 156-161, Jun. 1992.
Blakely , Sokoloff, Taylor & Zafman LLP
Kik Phallaka
Siek Vuthe
LandOfFree
Logic equivalence leveraged placement and routing of an IC... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Logic equivalence leveraged placement and routing of an IC..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic equivalence leveraged placement and routing of an IC... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2955044