Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-04-08
2004-07-13
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06763512
ABSTRACT:
BACKGROUND
1. Technical Field
This relates to the design and manufacture of very large scale integrated (“VLSI”) circuits and, more particularly, to a method for routing connections between component tiles of a VLSI circuit suitable for use in conjunction with the design and manufacture of VLSI circuits.
2. Description of the Relevant Art
A VLSI circuit is typically composed of a plurality of generally horizontal layers, each layer having a plurality of generally rectangular shaped components positioned thereon. VLSI circuit designers commonly refer to these generally rectangular shaped components as “component tiles” and to the rectangular shaped open spaces that surround the component tiles as “space tiles.” Component tiles that are to be connected on a VLSI circuit are said to form a “net”, while any component tile not connected to a particular net is considered to be an obstruction to that net. Two tiles are said to be “adjacent” if they touch along their edges and “overlapping” if there is even a single point located within the interior of both tiles. A set of tiles positioned within a routing area is said to be “maximal” if no two tiles are either overlapping or adjacent on their left or right edges.
One step in the design of a VLSI circuit is to select the wire paths that extend through the space tiles to connect the electrically equivalent component tiles that form nets. A current technique used to determine these paths utilizes a tile expansion algorithm. More specifically, clear space around the component tiles forming a net is fractured into maximal space tiles. Adjoining ones of these maximal space tiles are used to define the most efficient tile path between two components. The path of the actual connection between the components, known as the wire path, is then defined as the route through the space tile path from the center of the component source tile to the center of the component destination tile.
The aforementioned technique for selecting the wire paths for a VLSI circuit design suffers from two drawbacks, both of which may add to the cost of VLSI circuits manufactured in accordance with the design. First, if defined in accordance with the above-described manner, a tile path is not necessarily the optimal tile path through the clear space. Second, since the width of a tile path is typically much larger than the width of a wire path, multiple wire paths may exist through a given tile path. If the wire path located within the tile path is arbitrarily selected, the selected wire path is not necessarily the most efficient wire path potentially located within the tile path.
SUMMARY
Disclosed herein is a method and associated apparatus for the design and manufacture of VLSI circuit which incorporates therein a method for routing connections between component tiles of the VLSI circuit being designed. In accordance with the disclosed method, maximal component tile and maximal space tile lists are constructed and, from the constructed lists, the maximal component and maximal space tiles are positioned on the routing area(s). Optimal tile path and minimum cost wire path between pins that are CTs to be connected are determined and, utilizing the determined wire path, a VLSI circuit design is generated. The minimum cost path from a starting tile S to a destination tile T is determined by creating a priority queue and a search tree ST with the starting tile S as its root. While the priority queue is not empty, a low cost tile E neighboring the starting tile S is popped and, if a tile path to destination tile T is found, the cost of the tile path is evaluated and saved as the minimum cost point path. Otherwise, for each tile F neighboring the tile E, the search tree is expanded and, for a tile path having an estimated cost greater than the current cost, the search path is pruned. Otherwise, the search is expanded by adding the tile F (with corresponding minimum cost CE)) to the priority queue Q and inserting the tile F into the search tree as a child node of the tile E.
REFERENCES:
patent: 4484292 (1984-11-01), Hong et al.
patent: 5787010 (1998-07-01), Schaefer et al.
patent: 5818730 (1998-10-01), Young
patent: 5822214 (1998-10-01), Rostoker et al.
patent: 5856927 (1999-01-01), Greidinger et al.
patent: 6002857 (1999-12-01), Ramachandran
patent: 6071315 (2000-06-01), Ramamurthi et al.
patent: 6209123 (2001-03-01), Maziasz et al.
patent: 6223332 (2001-04-01), Scepanovic et al.
patent: 6324673 (2001-11-01), Luo et al.
patent: 6446239 (2002-09-01), Markosian et al.
patent: 6467074 (2002-10-01), Katsioulas et al.
patent: 6567967 (2003-05-01), Greidinger et al.
patent: 6642556 (2003-11-01), Ulrey
patent: 6665852 (2003-12-01), Xing et al.
patent: 2002/0104061 (2002-08-01), Xing et al.
Tsai et al., “An H-V Alternating Router”, IEEE Transacations on Computer-Aided Design of Integrated Circuits and Systems, Vo 11, No. 8, Aug. 1992, pp. 976-991.*
Frezza et al., “SPAR: A Schematic Place and Route System”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 7, Jul. 1993, pp. 956-973.*
Lee et al., “A Gridless Area Router for Multichip Module Design”, 42nd Midwest Symposium on Circuits and Systems, Aug. 8, 1999, Vol. 1, pp. 206-209.*
Sarrafzadeh et al., “Single-Layer Global Routing”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 13, No. 1, Jan. 1994, pp. 38-47.*
Chow et al., “The Design of a SRAM-Based Field-Programmable Gate Array—Part II: Circuit Design and Layout”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 7, No. 3, Sep. 1999, pp. 321-330.*
Leijten-Nowak et al., “Architecture and Implementation of an Embedded Reconfigurable Logic Core in CMOS 0.13/spl mu/m”, 15th Annual IEEE International ASIC/SOC Conference, Sep. 25, 2002, pp. 3-7.*
Yen et al., “Strategies for Mapping Lee's Maze Routing Algorithm onto Parallel Architectures”, 1993 Proceedings of Seventh International Parallel Processing Symposium, Apr. 13, 1993, pp. 672-679.*
NB82123853, “Connecting Three Points While Minimizing Cost”, IBM Technical Disclosure Bulletin, Vol. 25, No. 7B, pp. 3853-3858 (7 pages).*
Xing et al.; U.S. patent Ser. No. 10/109,116; Filed Mar. 28, 2002.
Xing et al.; U.S. patent Ser No. 10/109,125; Filed Mar. 28, 2002.
Kik Phallaka
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Smith Matthew
Sun Microsystems Inc.
LandOfFree
Detailed method for routing connections using tile expansion... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detailed method for routing connections using tile expansion..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detailed method for routing connections using tile expansion... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3214341