US 6,609,237 B1 · Routing path finding method for automated routing/designing process and computer-readable storage medium having stored thereon routing path finding program

Abstract

In an automatic routing/designing process of an LSI using a maze algorithm, multiple sub-regions, formed by getting a grid column partitioned by a component placed in a routing region, are extracted. And grid point availability, representing the number of grid points available for routing, is obtained for each of these sub-regions. Also, if there is any open net, then the component is vertically moved upward by one grid unit, for example, to make the net routable. If the grid point availability of a sub-region, used for routing another net, has become negative as a result of the movement of the component, then the net is rerouted to pass other sub-regions. Accordingly, even if a height constraint, for example, has been imposed on the routing region, all of the nets can be routed successfully with the constraint satisfied without increasing the number of grid points in the column direction. As a result, the number of open nets can be minimized and all of the nets are much more likely to be routed successfully.

Claims7

Dependent claims

A method for finding a routing path during an automated routing/designing process of an LSI by applying a maze algorithm to a routing region partitioned into multiple grid points arranged in columns and rows, a routing path cost being calculated by adding a cost every time one of the grid points is passed responsive to a request that terminals of a component, placed in the routing region, be interconnected, the method comprising the steps of:

a) extracting multiple sub-regions from each said column or row in the routing region, the sub-regions being formed by getting the column or row partitioned by the component and a routing forbidden region;
b) obtaining a parameter for each said sub-region, which has been extracted in the step a), based on the number of nets that can pass the sub-region and the number of nets already routed in the sub-region;
c) calculating, using the parameter obtained in the step b), the cost to be added every time one of the grid points is passed;
d) moving the component such that available ones of the sub-regions are arranged in line if there is any open net between any pair of the terminals to be interconnected;
and
e) recalculating the routing path cost by performing the steps b) and c) after the step d) has been performed.

3 more elements

A computer-readable storage medium having stored thereon a routing path finding program, the program being used to find a routing path during an automated routing/designing process of an LSI by applying a maze algorithm to a routing region partitioned into multiple grid points arranged in columns and rows, a routing path cost being calculated by adding a cost every time one of the grid points is passed responsive to a request that terminals of a component, placed in the routing region, be interconnected, the program comprising the steps of:

a) extracting multiple sub-regions from each said column or row in the routing region, the sub-regions being formed by getting the column or row partitioned by the component and a routing forbidden region;
b) obtaining a parameter for each said sub-region, which has been extracted in the step a), based on the number of nets that can pass the sub-region and the number of nets already routed in the sub-region;
c) calculating, using the parameter obtained in the step b), the cost to be added every time one of the grid points is passed;
d) moving the component such that available ones of the sub-regions are arranged in line if there is, any open net between any pair of the terminals to be interconnected;
and
e) recalculating the routing path cost by performing the steps b) and c) after the step d) has been performed.

3 more elements

Dependencies are inferred from the claim text.

Routing path finding method for automated routing/designing process and computer-readable storage medium having stored thereon routing path finding program

Life of this patent

Routing path finding method for automated routing/designing process and computer-readable storage medium having stored thereon routing path finding program

Life of this patent

Abstract

Claims7