Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2005-04-19
2005-04-19
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06883154
ABSTRACT:
Some embodiments provide an LP method that identifies route propagations. In some embodiments, this method is used by a router that hierarchically defines routes for nets within a region of a design layout. The router (1) partitions the region into a first set of sub-regions, and (2) for each particular net, identifies a route that traverses a set of the first-set sub-regions. In some embodiments, the invention's method partitions the first set of sub-regions into a second set of smaller sub-regions. It then identifies a plurality of propagation possibilities for propagating each route into the second set of smaller sub-regions of the first set sub-regions. The method next formulates a linear-programming (“LP”) problem based on the identified propagation possibilities. The method then solves the LP problem. In some embodiments, the formulated LP problem is an integer-linear-programming (“ILP”) problem, and solving the ILP problem returns integer solutions that specify one propagation permutation for each route in each first-set sub-region traversed by the route. In other embodiments, solving the LP problem returns real-numbered solutions. In some of these embodiments, the method converts the real-number solutions into integer solutions that specify one identified propagation permutation for each route in each first-set sub-region traversed by the route.
REFERENCES:
patent: 4593363 (1986-06-01), Burstein et al.
patent: 4615011 (1986-09-01), Linsker
patent: 4673966 (1987-06-01), Shimoyama
patent: 4782193 (1988-11-01), Linsker
patent: 4855929 (1989-08-01), Nakajima
patent: 5097422 (1992-03-01), Corbin, II et al.
patent: 5251147 (1993-10-01), Finnerty
patent: 5267176 (1993-11-01), Antreich et al.
patent: 5281151 (1994-01-01), Arima et al.
patent: 5360948 (1994-11-01), Thornberg
patent: 5375069 (1994-12-01), Satoh et al.
patent: 5532934 (1996-07-01), Rostoker
patent: 5566078 (1996-10-01), Ding et al.
patent: 5578840 (1996-11-01), Scepanovic et al.
patent: 5587923 (1996-12-01), Wang
patent: 5618744 (1997-04-01), Suzuki et al.
patent: 5633479 (1997-05-01), Hirano
patent: 5634093 (1997-05-01), Ashida et al.
patent: 5635736 (1997-06-01), Funaki et al.
patent: 5636125 (1997-06-01), Rostoker et al.
patent: 5637920 (1997-06-01), Loo
patent: 5640327 (1997-06-01), Ting
patent: 5650653 (1997-07-01), Rostoker et al.
patent: 5657242 (1997-08-01), Sekiyama et al.
patent: 5663891 (1997-09-01), Bamji et al.
patent: 5723908 (1998-03-01), Fuchida et al.
patent: 5742086 (1998-04-01), Rostoker et al.
patent: 5757089 (1998-05-01), Ishizuka
patent: 5757656 (1998-05-01), Hershberger et al.
patent: 5777360 (1998-07-01), Rostoker et al.
patent: 5784289 (1998-07-01), Wang
patent: 5798936 (1998-08-01), Cheng
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: 5859449 (1999-01-01), Kobayashi et al.
patent: 5889677 (1999-03-01), Yasuda et al.
patent: 5898597 (1999-04-01), Scepanovic et al.
patent: 5914887 (1999-06-01), Scepanovic et al.
patent: 5973376 (1999-10-01), Rostoker et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6035108 (2000-03-01), Kikuchi
patent: 6058254 (2000-05-01), Scepanovic et al.
patent: 6067409 (2000-05-01), Scepanovic et al.
patent: 6068662 (2000-05-01), Scepanovic et al.
patent: 6070108 (2000-05-01), Andreev et al.
patent: 6123736 (2000-09-01), Pavisic et al.
patent: 6128767 (2000-10-01), Chapman
patent: 6134702 (2000-10-01), Scepanovic et al.
patent: 6150193 (2000-11-01), Glenn
patent: 6155725 (2000-12-01), Scepanovic et al.
patent: 6175950 (2001-01-01), Scepanovic et al.
patent: 6209123 (2001-03-01), Maziasz et al.
patent: 6216252 (2001-04-01), Dangelo et al.
patent: 6219832 (2001-04-01), Buzbee
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: 6249902 (2001-06-01), Igusa et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6260179 (2001-07-01), Ohsawa et al.
patent: 6262487 (2001-07-01), Igarashi et al.
patent: 6289495 (2001-09-01), Raspopovic et al.
patent: 6295634 (2001-09-01), Matsumoto
patent: 6301686 (2001-10-01), Kikuchi et al.
patent: 6307256 (2001-10-01), Chiang et al.
patent: 6316838 (2001-11-01), Ozawa 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: 6378121 (2002-04-01), Hiraga
patent: 6385758 (2002-05-01), Kikuchi et al.
patent: 6401234 (2002-06-01), Alpert et al.
patent: 6405358 (2002-06-01), Nuber
patent: 6407434 (2002-06-01), Rostoker et al.
patent: 6412097 (2002-06-01), Kikuchi et al.
patent: 6412102 (2002-06-01), Andreev et al.
patent: 6415422 (2002-07-01), Mehrotra et al.
patent: 6436804 (2002-08-01), Igarashi et al.
patent: 6442743 (2002-08-01), Sarrafzadeh et al.
patent: 6446245 (2002-09-01), Xing et al.
patent: 6448591 (2002-09-01), Juengling
patent: 6463575 (2002-10-01), Takahashi
patent: 6473891 (2002-10-01), Shively
patent: 6480991 (2002-11-01), Cho et al.
patent: 6490713 (2002-12-01), Matsumoto
patent: 6516455 (2003-02-01), Teig et al.
patent: 6519751 (2003-02-01), Huang et al.
patent: 6543043 (2003-04-01), Wang et al.
patent: 6546540 (2003-04-01), Igarashi et al.
patent: 6557145 (2003-04-01), Boyle et al.
patent: 6567967 (2003-05-01), Greidinger et al.
patent: 20010003843 (2001-06-01), Scepanovic et al.
patent: 20010009031 (2001-07-01), Nitta et al.
patent: 20020069397 (2002-06-01), Teig et al.
patent: 20020073390 (2002-06-01), Teig et al.
patent: 20020100007 (2002-07-01), Teig et al.
patent: 20020124231 (2002-09-01), Teig et al.
patent: 20020133798 (2002-09-01), Teig et al.
patent: 20020147958 (2002-10-01), Teig et al.
patent: 20020157075 (2002-10-01), Teig et al.
patent: 20020166105 (2002-11-01), Teig et al.
patent: 20020170027 (2002-11-01), Teig et al.
patent: 20020174412 (2002-11-01), Teig et al.
patent: 20020182844 (2002-12-01), Igarashi et al.
patent: 20020199165 (2002-12-01), Teig et al.
patent: 20030005399 (2003-01-01), Igarashi et al.
patent: 20030018947 (2003-01-01), Teig et al.
patent: 20030023943 (2003-01-01), Teig et al.
patent: 20030025205 (2003-02-01), Shively
patent: 20030056187 (2003-03-01), Teig et al.
patent: 20030063568 (2003-04-01), Teig et al.
patent: 20030063614 (2003-04-01), Teig et al.
patent: 20030064559 (2003-04-01), Teig et al.
patent: 20030066042 (2003-04-01), Teig et al.
patent: 20030066043 (2003-04-01), Teig et al.
patent: 20030066044 (2003-04-01), Teig et al.
patent: 20030066045 (2003-04-01), Teig et al.
patent: 20030079193 (2003-04-01), Teig et al.
patent: 20030088841 (2003-05-01), Teig et al.
patent: 20030088844 (2003-05-01), Teig et al.
patent: 20030088845 (2003-05-01), Teig et al.
patent: 20030101428 (2003-05-01), Teig et al.
patent: 20030115566 (2003-06-01), Teig
patent: 20030121015 (2003-06-01), Teig et al.
patent: 64-15947 (1989-01-01), None
patent: H03-173471 (1991-07-01), None
patent: 04000677 (1992-01-01), None
patent: H05-102305 (1993-04-01), None
patent: H05-243379 (1993-09-01), None
patent: H07-86407 (1995-03-01), None
patent: H09-162279 (1997-06-01), None
patent: 411296560 (1999-10-01), None
patent: 2000-82743 (2000-03-01), None
Resolving horizontal constraints and minimizing net wire length for multi-layer channel routing Pal, R.K.; Datta, A.K.; Pal, S.P.; Pal, A.;TENCON '93. Proceedings. Computer, Communication, Control and Power Engineering.1993 IEEE Region 10 Conference.*
Hierarchical physical design system Schulz, U., CompEuro '89., ‘VLSI and Computer Peripherals. VLSI and Microelectronic Applications in Intelligent Peripherals and their Interconnection Networks’, Proceedings. , May 8-12, 1989.*
On the integration of partitioning and global routing for rectilinear placement problems Chingwei Yeh; Chi-Shong Wang; Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol.: 15 , Issue: 1 , Jan. 1996.*
Timing-driven hierarchical global routing with wire-sizin
Buset Oscar
Teig Steven
Cadence Design Systems Inc.
Liu Andrea
Siek Vuthe
Stattler Johansen & Adeli LLP
LandOfFree
LP method and apparatus for identifying route propagations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with LP method and apparatus for identifying route propagations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LP method and apparatus for identifying route propagations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3434895