Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2006-05-16
2006-05-16
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
07047512
ABSTRACT:
Some embodiments of the invention provide a method of specifying a cost function that represents the estimated distance between an external state and a set of states in a multi-state space that represents a region of a design layout. The method identifies a polygon that encloses the set of states. It then identifies vectors to project from the vertices of the polygon. Based on the projected vectors, the method identifies a set of distances that includes the distance between the polygon and each point in a set of points in the external state. The method then uses the identified set of distance to specify the cost function.
REFERENCES:
patent: 4777606 (1988-10-01), Fournier
patent: 5224057 (1993-06-01), Igarashi et al.
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5663891 (1997-09-01), Bamji et al.
patent: 5717600 (1998-02-01), Ishizuka
patent: 5757089 (1998-05-01), Ishizuka
patent: 5757656 (1998-05-01), Hershberger et al.
patent: 5811863 (1998-09-01), Rostoker et al.
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5856927 (1999-01-01), Greidinger et al.
patent: 5877091 (1999-03-01), Kawakami
patent: 5880969 (1999-03-01), Hama et al.
patent: 5889329 (1999-03-01), Rostoker et al.
patent: 5889677 (1999-03-01), Yasuda et al.
patent: 5898597 (1999-04-01), Scepanovic et al.
patent: 5973376 (1999-10-01), Rostoker et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6006024 (1999-12-01), Guruswamy et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
patent: 6110222 (2000-08-01), Minami et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6154873 (2000-11-01), Takahashi
patent: 6154874 (2000-11-01), Scepanovic et al.
patent: 6175950 (2001-01-01), Scepanovic et al.
patent: 6209123 (2001-03-01), Maziasz et al.
patent: 6219823 (2001-04-01), Hama et al.
patent: 6226560 (2001-05-01), Hama et al.
patent: 6230306 (2001-05-01), Raspopovic et al.
patent: 6247167 (2001-06-01), Raspopovic et al.
patent: 6247853 (2001-06-01), Papadopoulou et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6262487 (2001-07-01), Igarashi et al.
patent: 6286128 (2001-09-01), Pileggi et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6292929 (2001-09-01), Scepanovic et al.
patent: 6324674 (2001-11-01), Andreev et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6327693 (2001-12-01), Cheng et al.
patent: 6327694 (2001-12-01), Kanazawa
patent: 6330707 (2001-12-01), Shinomiya et al.
patent: 6349403 (2002-02-01), Dutta et al.
patent: 6407434 (2002-06-01), Rostoker et al.
patent: 6412102 (2002-06-01), Andreev et al.
patent: 6415427 (2002-07-01), Nitta et al.
patent: 6434730 (2002-08-01), Ito et al.
patent: 6436804 (2002-08-01), Igarashi et al.
patent: 6442745 (2002-08-01), Arunachalam et al.
patent: 6490713 (2002-08-01), Matsumoto et al.
patent: 6505331 (2003-01-01), Bracha et al.
patent: 6601227 (2003-07-01), Trimberger
patent: 6609237 (2003-08-01), Hamawaki et al.
patent: 6645842 (2003-11-01), Igarashi et al.
patent: 6656644 (2003-12-01), Hasegawa et al.
patent: 6665852 (2003-12-01), Xing et al.
patent: 2001/0003843 (2001-06-01), Scepanovic et al.
patent: 2001/0038612 (2001-11-01), Vaughn et al.
patent: 2002/0043988 (2002-04-01), Or-Bach et al.
patent: 2002/0100009 (2002-07-01), Xing et al.
patent: 2002/0104061 (2002-08-01), Xing et al.
patent: 2002/0107711 (2002-08-01), Xing et al.
patent: 2002/0182844 (2002-12-01), Igarashi et al.
patent: 2003/0005399 (2003-01-01), Igarashi et al.
patent: 2003/0009737 (2003-01-01), Xing
patent: 2003/0014725 (2003-01-01), Sato et al.
patent: 2003/0025205 (2003-02-01), Shively
patent: 2003/0121017 (2003-06-01), Andreev et al.
patent: 2003/0188281 (2003-10-01), Xing
patent: 2004/0044979 (2004-03-01), Aji et al.
patent: 2004/0088670 (2004-05-01), Stevens et al.
patent: 02-262354 (1990-10-01), None
patent: 11-296560 (1999-10-01), None
Xing et al., “Shotest Path Search Using Tiles and Piecewise Linear Cost Propagation,” IEEE, Feb. 2002, pp. 145-158.
Reeves et al., “A Distributed Algorithm for Delay-Constrained Unicast Routing,” IEEE, Apr. 2000, pp. 239-250.
Jun Dong Cho, “Wiring Space and Length Estimation in Two-Dimensional Arrays,” IEEE, May 2000, pp. 612-615.
Lai et al., “GMNF-DVMRP: A Modified Version of Distance Vector Multicast Routing Protocol,” IEEE, 1997, pp. 65-68.
Chen et al., “Distance Vector Routing Protocols for Networks with Unidirectional Link,” IEEE, 2001, pp. 473-478.
Zaumen et al., “Steady-State Response of Shortest-Path Routing Algorithms*,” IEEE, 1992, pp. 323-332.
NB8911253 (TDB-ACC-NO), IBM Technical Disclosure Bulletin, Nov. 1989, pp. 253-264.
Chen, H.F. et al., A Faster Algorithm for Rubber-Band Equivalent Transformation for Planar VLSI Layouts, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 2, Feb. 1996, pp. 217-227.
Dayan, T. et al., Layer Assignment for Rubber Band Routing, UCSC-CRI-93-04, Jan. 20, 1993.
Dayan, T., Rubber-Band Based Topological Router, A Dissertation, UC Santa Cruz, Jun. 1997.
Hama, T. et al., Curvilinear Detailed Routing Algorithm and its Extension to Wire-Spreading and Wire-Fattening.
Hama, T. et al., Topological Routing Path Search Algorithm with Incremental Routability Test, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 2, Feb. 1999, pp. 142-150.
Kobayashi, K. et al., A New Interactive Analog Layout Methodology based on Rubber-Band Routing, UCSC-CRL-96-12, Jun. 13, 1996.
Lim, A. et al, A Fast Algorithm To Test Planar Topological Routability, Technical Report 94-012, pp. 1-16.
Lu, Y., Dynamic Constrained Delaunay Triangulation and Application to Multichip Module Layout, A Thesis for Master of Science, UC Santa Cruz, Dec. 1991.
Maley, F.M., Testing Homotopic Routability Under Polygonal Wiring Rules, Algorithmica 1996, 15:1-16.
Morton, P. B. et al., An Efficient Sequential Quadratic Programming Formulation of Optimal Wire Spacing for Cross-Talk Noise Avoidance Routing, UCSC-CRL-99-05, Mar. 10, 1999.
Staepelaere, D. et al., Geometric Transformations for a Rubber-Band Sketch, A Thesis for a Master of Science in Computer Engineering, UCSC, Sep. 1992.
Staepelaere, D. et al., Surf: A Rubber-Band Routing System for Multichip Modules, pp. 18-26, 1993.
Su, J. et al., Post-Route Optimization for Improved Yield Using Rubber-Band Wiring Model, 1997 International Conference on Computer-Aided Design, pp. 700-706, Nov. 1997.
Wei-Ming Dai, W. et al., Routability of a Rubber-Band Sketch. 28thACM-IEEE Design Automation Conference, 1991. pp. 45-65.
Xing, Z. et al., A Minimum Cost Path Search Algorithm Through Tile Obstacles, slide presentation.
Xing, Z. et al., Shortest Path Search Using Tiles and Piecewise Linear Cost Propagation, IEEE, 2002, pp. 145-158.
Xu, A More Efficient Distance Vector Routing Algorithm, UCSC-CRL-96-18, Mar. 1997.
Yu, M.-F. et al., Fast and Incremental Routability Check of a Topological Routing Using a Cut-Based Encoding, UCSC-CRL-97-07, Apr. 14, 1997.
Yu, M.-F. et al, Interchangeable Pin Routing with Application to Package Layout, UCSC-CRL-96-10, Apr. 25, 1996.
Yu, M.-F. et al., Pin Assignment and Routing on a Single-Layer Pin Grid Array, UCSC-CRL-95-15, Feb. 24, 1995.
Yu, M.-F. et al., Planar Interchangeable 2-Terminal Routing, UCSC-CRL-95-49, Oct. 19, 1995.
Yu, M.-F. et al., Single-Layer Fanout Routing and Routability Analysis for Ball Grid Arrays, UCSC-CRL-95-18, Apr. 25, 1995.
Ahuja, R. et al., Faster Algorithms for the Shortest Path Problem, Journal of the Association for Computing Machinery, vol. 37, No. 2, Apr. 1990, pp. 213-223.
Bagga, J. et al., Internal, External, and Mixed Visibility Edges of Polygons.
Berger, B. et al., Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing, Journal of the Association for Computing Machinery, pp. 500-542, Mar. 1995.
Chen et al., Optimal Algorithms for Bubble Sort Based Non-Manhattan Channel Routing, May 1994, Computer-Aided Design of Integrated Circuits and Systems, I
Caldwell Andrew
Teig Steven
Cadence Design Systems Inc.
Stattler Johansen & Adeli LLP
LandOfFree
Method and apparatus for specifying a cost function that... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for specifying a cost function that..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for specifying a cost function that... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3575282