Apparatus for wire routing of VLSI

• US 5,245,550 A
• Filed: 01/15/1992
• Issued: 09/14/1993
• Est. Priority Date: 01/25/1991
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Miki, Yoshio, Takamine, Yoshio, Suzuki, Kei
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/820,995
• Time in Patent Office: 608 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 395/800
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A wiring route is determined between terminals on an integrated circuit on the basis of information concerning the terminals and areas of the integrated circuit through which a wire can be routed. A mesh memory holds information of mesh points of a wiring area partitioned in a mesh-like pattern. A wavefront memory holds information concerning mesh points constituting the leads of searching point arrays. An expansion point extracting unit selects a source point from the mesh points for a succeeding search from the leading mesh points on the basis of costs. Addresses and costs for mesh points neighboring the source point are calculated. A searching point register holds information concerning the mesh points obtained through the calculation. A determination is made of whether or not the mesh points placed in the searching point register can be searched, and if so they are written to the mesh memory. Duplicate information stored in the searching point register is eliminated. It is then determined whether or not the mesh points corresponding to the terminals to be wired are contained in the searching point register. If so, the wiring route is determined and the process concluded.

Claims

1. A wire routing apparatus for searching a wiring path in an integrated circuit on the basis of information concerning an area of said integrated circuit through which a wire can extend and information concerning terminals to be wired together, comprising:

first storage means for holding first searching point information inclusive of wire passage flags indicating permissibility of passing of the wire through mesh points in a routing area of said integrated circuit which is partitioned in a mesh-like pattern, search-done flags indicating that search has already been performed and tracing directions;

second storage means for holding second searching point information inclusive of addresses of said first storage means for first searching point, tracing directions and costs involved in wire routing;

expansion point extracting means for selecting from said first mesh points a second mesh point which constitutes a source point for a succeeding search on the basis of the costs in said second searching point information;

neighbor address calculating means for calculating addresses of said first storage means for third mesh points neighboring said second mesh point;

cost calculating means for arithmetically determining costs for said third mesh points on the basis of said second searching point information concerning said second mesh point and said second searching point information concerning said third mesh points;

third storage means for holding said second searching point information concerning said third mesh points as obtained through said neighbor address calculating means and said cost calculating means;

searching point write-out means for reading out content of said first storage means indicated by said second searching point information stored in said third storage means to make a determination as to whether or not said third mesh points can be searched and write out content of said third storage means to said first storage means when said third mesh points can be searched;

duplicate trace eliminating means for comparing content of said first storage means indicated by said second searching point information stored in said third storage means with content of said third storage means to thereby eliminate from said third storage means the second searching point information having the content in duplicate with that of said first storage means;

valid data selecting means for determining whether or not a mesh point corresponding to the terminal to be wired is included in the content of said third storage means and writing out the content of said third storage means to said second storage means unless the mesh point corresponding to the terminal to be wired is contained; and

control means for designating a starting point and a target point for the searching which correspond to two terminals to be wired to said second storage means and said valid data selecting means.

2. A wire routing apparatus according to claim 1, wherein said neighbor address calculating means assigns one-dimensionally addresses to memory units of said first storage means and calculates the addresses of said first storage means corresponding to said third mesh points as increment values of address of said second mesh point.

3. A wire routing apparatus according to claim 1, wherein said cost calculating means calculates increment of the cost of said third mesh points on the basis of tracing directions of said second mesh point and said third mesh points.

4. A wire routing apparatus according to claim 1, wherein said expansion point extracting means selects the mesh point for which the cost is lowest from said second storage means.

5. A wire routing apparatus according to claim 1, wherein when a plurality of mesh points corresponding to a plurality of terminals to be wired are included in the content of said third storage means, said valid data selecting means writes out the content of said third storage means to said second storage means until search processing for said plural terminals to be wired has been completed.

6. A wire routing method carried out by a vector computer including a plurality of vector registers, a pipeline arithmetic unit and a main memory, comprising steps of:

a) holding in a mesh memory array of said main memory first searching point information inclusive of wire passage flags indicating permissibility of passing of a wire through mesh points in a routing area divided in a mesh-like pattern, a search-over flag indicating that search has already been performed and tracing direction;

b) holding in a wavefront array second searching point information inclusive of addresses of said first storage means for first mesh points constituting leading ones of mesh point arrays, the tracing direction and costs involved in wire routing;

c) selecting from said first mesh points a second mesh point which constitutes a source point for a succeeding search on the basis of said cost information;

d) calculating addresses of said first storage means for third mesh points neighboring said second mesh point;

e) calculating costs for said third mesh points on the basis of said second searching point information concerning said second mesh point and said second searching point information concerning said third mesh points;

f) holding in a searching point array said second searching point information concerning said third mesh points as obtained in said steps d) and e);

g) reading out content of said mesh memory array indicated by said second searching point information stored in said searching point array to make a determination as to whether or not said third mesh points can be searched and write out content of said searching point array to said mesh memory array when said third mesh points can be searched;

h) comparing content of said mesh memory array indicated by said second searching point information stored in said searching point array with content of said searching point array to thereby eliminate from said searching point array the second searching point information having the content duplicative with that of said mesh memory array;

i) determining whether or not a mesh point corresponding to a terminal to be wired is included in the content of said searching point array and writing out the content of said searching point array to said wavefront array unless the mesh point corresponding to the terminal to be wired is contained; and

j) repeating said steps a) to i) by designating newly a starting point and a target point for the searching which correspond to two terminals to be wired, respectively.