Patent
1998-03-05
1999-12-28
Teska, Kevin J.
39550005, 39550002, G06F 1716, G06F 1700, G06F 1500
Patent
active
060092521
ABSTRACT:
A layout versus schematic (LVS) comparison tool determines one-to-one equivalency between an integrated circuit schematic and an integrated circuit layout by performing operations to generate color symmetrizing matrices corresponding to respective child cells in the integrated circuit schematic. Here, the child cells are characterized as having a number of symmetrical configurations which at a port level are electrically equivalent. Operations are also performed to generate a first color symmetry vector for a child cell in the integrated circuit schematic and a second color symmetry vector for the corresponding child cell in the integrated circuit layout. A vector equivalency is also preferably determined by comparing a product of the color symmetrizing matrix and the first color symmetry vector against a product of the color symmetrizing matrix and the second color symmetry vector. Notwithstanding the presence of a vector equivalency, a possibility may still exist that with respect to the corresponding symmetric child cells in the schematic and layout, isomorphism between the schematic and layout is not present. To address this possibility, an operation is preferably performed to detect the absence of a spurious symmetry in the color symmetrizing matrix. If an absence is detected, the presence of the vector equivalency will unequivocally establish the one-to-one correspondence with respect to the child cells being analyzed. Thus, the need to perform a computationally expensive membership test to determine whether a selected permutation can be derived from valid symmetries, can be successfully eliminated. The preferred comparison tool also infers symmetries, where available, so that symmetries of a child cell may be propagated to a parent cell when the tool is evaluating a grandparent cell containing the parent cell.
REFERENCES:
patent: 5095454 (1992-03-01), Huang
patent: 5243538 (1993-09-01), Okuzawa et al.
patent: 5249133 (1993-09-01), Batra
patent: 5249134 (1993-09-01), Oka
patent: 5281558 (1994-01-01), Bamji et al.
patent: 5301318 (1994-04-01), Mittal
patent: 5349659 (1994-09-01), Do et al.
patent: 5455928 (1995-10-01), Herlitz
patent: 5461576 (1995-10-01), Tsay et al.
patent: 5463561 (1995-10-01), Razdan
patent: 5469366 (1995-11-01), Yang et al.
patent: 5475605 (1995-12-01), Lin
patent: 5475695 (1995-12-01), Caywood et al.
patent: 5490095 (1996-02-01), Shimada et al.
patent: 5497334 (1996-03-01), Russell et al.
patent: 5513313 (1996-04-01), Bruck
patent: 5528508 (1996-06-01), Russell et al.
patent: 5541849 (1996-07-01), Rostoker et al.
patent: 5548524 (1996-08-01), Hernandez et al.
patent: 5550750 (1996-08-01), Wolff
patent: 5555201 (1996-09-01), Dangelo
patent: 5559718 (1996-09-01), Baisuck et al.
patent: 5568396 (1996-10-01), Bamji et al.
patent: 5574388 (1996-11-01), Barbier et al.
patent: 5581474 (1996-12-01), Bamji et al.
patent: 5590049 (1996-12-01), Arora
patent: 5592392 (1997-01-01), Matheson et al.
patent: 5604680 (1997-02-01), Bamji et al.
patent: 5606698 (1997-02-01), Powell
patent: 5610832 (1997-03-01), Wikle et al.
patent: 5623419 (1997-04-01), Kundert
patent: 5625564 (1997-04-01), Rogoyski
patent: 5625565 (1997-04-01), Van Dyke
patent: 5634115 (1997-05-01), Fitzpatrick et al.
patent: 5636132 (1997-06-01), Kamdar
patent: 5648910 (1997-07-01), Ito
patent: 5649166 (1997-07-01), Saldanha et al.
patent: 5689432 (1997-11-01), Blaauw et al.
patent: 5691910 (1997-11-01), Thodiyil
patent: 5694481 (1997-12-01), Lam et al.
patent: 5801958 (1998-09-01), Dangelo et al.
patent: 5903469 (1999-05-01), Ho
Batra and Cooke "HCompare: A Hierarchical Netlist Comparison Program," 29th ACM/IEEE Design Automation Conference, Jun. 8-12, 1992, pp. 299-304.
Kim and Shim "Hierarchical LVS Based on Hierarchy Rebuilding," Proceedings of the ASP-DAC '98, Asia and South Pacific Design Automation Conference, Feb. 10-13, 1998, pp. 379-384.
Pelz and Roettcher "Circuit Comparison by Hierarchical Pattern Matching," 1991 IEEE International Conference on Computer-Aided Design, Nov. 11-14, 1991, pp. 290-293.
Ebeling "Geminill: A Second Generation Layout Validation Program," IEEE International Conference on Computer-Aided Design, Nov. 7-10, 1988, pp. 322-325.
Saber and Tekalp "Face Detection and Facial Feature Extraction Using Color, Shape and symmetry-Based Cost Functions," Proceedings of the 13th International Conference on Pattern Recognition, Aug. 25-29, 1996, pp. 654-658, vol. 3.
Abadir and Ferguson "An Improved Layout Verification Algorithm (LAVA)," Proceedings of the European Design Automation Conference, Mar. 12-15, 1990, pp. 391-395.
A.J. van Genderen and N.P. van der Meijs, Hierarchical Extraction of 3D Interconnect Capacitances in Large Regular VLSI Structures, Delft University of Technology, Department of Electrical Engineering, Mekelweg 4, 2628 CD Delft, The Netherlands.
Riedell et al., Dielectric Characterization of Printed Circuit Substrates, Conference Proceedings--IEEE Southeastcon '89, Proceedings, vol. 1 of 3, Apr. 9-12, 1989, Conference and Exhibit, pp. 102-106.
K.W. Chiang et al., Time-Efficient VLSI Artwork Analysis Algorithms in GOALIE2, IEEE Transactions on Computer-Aided Design, vol. 8 No. 6, Jun. 1989, pp. 640-648.
Riedell et al., Dielectric Characterization of Printed Circuit Board Substates, IEEE Transactions on Instrumentation and Measurement, vol. 39, No. 2, Apr. 1990, pp. 437-440.
K.P. Belkhale et al., Parallel Algorithms for VLSI Circuit Extraction, IEEE Transactions on Computer-Aided Design, vol. 10, No. 5, May 1991, pp. 604-618.
Basel et al., High Speed Digital System Simulation Using Frequency Dependent Transmission Line Network Modeling, IEEE MTT-S International Microwave Symposium Digest, vol. 3, 1991 IEEE, pp. 987-990.
Franzon et al., Tools to Aid in Wiring Rule Generation for High Speed Interconnects, Proceedings--Design Automation Conference, 29.sup.th ACM/IEEE Design Automation Conference, 1992 IEEE, pp. 466-471.
Deschacht et al., Post-Layout Timing Simulation of CMOS Circuits, IEEE, vol. 12, No. 8, Aug. 1993, pp. 1170-1177.
Basel et al., Hierarchical Simulation of High Speed Digital Interconnects using a Packaging Simulator, 1994 Proceedings, 44.sup.th Electronic Components & Tech. Conference, May 1-4, 1994, IEEE, pp. 81-87.
Ramachandran et al., Combined Topological and Functionality-Based Delay Estimation Using a Layout-Driven Approach for High-Level Applications, IEEE, vol. 13, No. 12, Dec., 1994, pp. 1450-1460.
Basel et al., Simulation of High Speed Interconnects Using a Convolution-Based Hierarchical Packaging Simulator, IEEE Transactions on Components, Packaging, and Manufacturing Technology, Part B, vol. 18, No. 1, Feb. 1995, pp. 74-82.
Onozawa et al., Post-Layout Optimization of Power and Timing for ECL LSIs, IEEE, Mar. 6-9, 1995, pp. 167-172.
Choudhury et al., Automatic Generation of Analytical Models for Interconnect Capacitances, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, No. 4, Apr. 1995, pp. 470-480.
Wang et al., Accurate Parasitic Resistance Extraction for Interconnection Analysis, Proceedings of the IEEE 1995 Custom Integrated Circuits Conference, May 1-4, 1995, 12.2.1-12.2.4, pp. 255-258.
J. Lipman, Submicron EDA to Help Tackle Tough Designs, EDN, Jun. 8, 1995, pp. 44-51.
S.E. Schulz, Timing Analysis Tools and Trends, Focus Report, Integrated System Design, Nov. 1995, pp. 50-57.
Basel, Accurate and Efficient Extraction of Interconnect Circuits for Full-Chip Timing Analysis, Wescon Conference Record 1995, Moscone Convention Center, San Francisco, CA, Nov. 7-9, 1995, pp. 118-123.
N.D. Arora et al., Modeling and Extraction of Interconnect Capacitances for Multilayer VLSI Circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 1, Jan. 1996, pp. 58-67.
Navabi et al., Modeling Strategy for Post Layout Verification, IEEE, pp. P5-7.1-P5-7.4.
IC Design Automation, An Electronics Journal; Feb. 1997, pp. 1-12.
Electronics Journal, IC Design Automation; Feb. 1998.
Avant! Corporation of Sunnyvale, California, Chapter 11 Netlist Comparison Commands, Section 11.2 Com
Avant! Corporation
Pruessner Marcel
Teska Kevin J.
LandOfFree
Methods, apparatus and computer program products for determining does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, apparatus and computer program products for determining, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, apparatus and computer program products for determining will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2388467