Method and apparatus for producing sub-optimal routes for a net by generating fake configurations
AssigneeCadence Design Systems, Inc.
InventorsSteven Teig, Oscar Buset, Yang-Trung Lin
Life of this patent
Estimating the term…
Abstract
Some embodiments provide a method of producing sub-optimal routes for a net having a set of pins in a region of an integrated-circuit (“IC”) layout. In some embodiments, such a method is used for a router that partitions the region into a plurality of sub-regions. This method initially identifies a first set of sub-regions that contain the net's pins. It then obtains a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions. Each sub-region in the third set does not contain any pins of the net. For the second set of sub-regions, the method then identifies a first set of routes, where each route traverses the sub-regions in the second set.
Claims21
For a router that partitions a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, wherein a plurality of the sub-regions are on the boundary of the partitioned IC region and at least one sub-region is not on the boundary of the partitioned IC region, a method of producing a set of sub-optimal routes for a net having a set of pins in the region, the method comprising:
- a) identifying a first set of sub-regions that contain the net's pins;
- b) obtaining a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions, wherein each sub-region in the third set does not contain the net's pins, wherein at least one sub-region in the third set is not a sub-region on the boundary of the partitioned IC region;
- c) identifying a first set of routes for the second set of sub-regions, wherein the first-route set includes at least one route, and each route in the first-route set traverses the sub-regions in the second set.
For a router that partitions a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, a method of producing a set of sub-optimal routes for a net having a set of pins in the region, the method comprising:
- a) identifying a first set of sub-regions that contain the net's pins;
- b) obtaining a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions, wherein each sub-region in the third set does not contain the net's pins;
- c) identifying a first set of routes for the second set of sub-regions, wherein the first-route set includes at least one route, and each route in the first-route set traverses the sub-regions in the second set;
- d) computing a cost for at least one route in the first set of routes;
- e) obtaining a fourth set of sub-regions by adding a fifth set of sub-regions to the first set of sub-regions, wherein each sub-region in the fifth set does not contain the net's pins;
- f) identifying a second set of routes for the fourth set of sub-regions, wherein the second-route set includes at least one route, and each route in the second-route set traverses the sub-regions in the third set;
- g) computing a cost for at least one route in the second set of routes;
- h) selecting between routes in the first and second route sets based on the computed costs.
For a router that partitions a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, a method of producing a set of sub-optimal routes for a net having a set of pins in the region, the method comprising:
- a) identifying a first set of sub-regions that contain the net's pins, wherein the pins include actual and virtual pins;
- b) obtaining a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions, wherein each sub-region in the third set does not contain the net's pins;
- c) identifying a first set of routes for the second set of sub-regions, wherein the first-route set includes at least one route, and each route in the first-route set traverses the sub-regions in the second set.
For a router that partitions a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, wherein a plurality of the sub-regions are on the boundary of the partitioned IC region and at least one sub-region is not on the boundary of the partitioned IC region, a computer readable medium comprising a computer program having executable code, the computer program for producing a set of sub-optimal routes for a net having a set of pins in the region, the computer program comprising:
- a) a first set of instructions for identifying a first set of sub-regions that contain the net's pins;
- b) a second set of instructions for obtaining a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions, wherein each sub-region in the third set does not contain the net's pins, wherein at least one sub-region in the third set is not a sub-region on the boundary of the partitioned IC region;
- c) a third set of instructions for identifying a first set of routes for the second set of sub-regions, wherein the first-route set includes at least one route, and each route in the first-route set traverses the sub-regions in the second set.
For a router that partitions a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, a computer readable medium comprising a computer program having executable code, the computer program for producing a set of sub-optimal routes for a net having a set of pins in the region, the computer program comprising:
- a) a first set of instructions for identifying a first set of sub-regions that contain the net's pins;
- b) a second set of instructions for obtaining a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions, wherein each sub-region in the third set does not contain the net's pins;
- c) a third set of instructions for identifying a first set of routes for the second set of sub-regions, wherein the first-route set includes at least one route and each route in the first-route set traverses the sub-regions in the second set;
- d) a fourth set of instructions for computing a cost for at least one route in the first set of routes;
- e) a fifth set of instructions for obtaining a fourth set of sub-regions by adding a fifth set of sub-regions to the first set of sub-regions, wherein each sub-region in the fifth set does not contain the net's pins;
- f) a sixth set of instructions for identifying a second set of routes for the fourth set of sub-regions, wherein the second-route set includes at least one route, and each route in the second-route set traverses the sub-regions in the third set;
- g) a seventh set of instructions for computing a cost for at least one route in the second set of routes;
- h) an eighth set of instructions for selecting between routes in the first and second route sets based on the computed costs.
For a router that uses a set of partitioning lines to partition a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, a method of producing a set of sub-optimal routes for a net having a set of pins in the region, the method comprising:
- a) specifying an original pin configuration for the net, wherein the original configuration includes a pin value for each sub-region, and a sub-region's corresponding pin value is set in the configuration when the sub-region contains a pin of the net, and sub-region's corresponding pin value is not set in the configuration when the sub-region does not contain a pin of the net;
- b) generating a first fake pin configuration for the net by setting at least one of the unset pin values in the original pin configuration;
- and
- c) identifying a first set of routes for the first fake pin configuration, wherein each route traverses all the sub-regions that have their corresponding pin values set in the first fake pin configuration.
For a router that partitions a region of an integrated-circuit (“IC”) layout into a plurality of sub-regions, a computer readable medium comprising a computer program having executable code, the computer program for producing a set of sub-optimal routes for a net having a set of pins in the region, the computer program comprising:
- a) a first set of instructions for identifying a first set of sub-regions that contain the net's pins, wherein the pins include actual and virtual pins;
- b) a second set of instructions for obtaining a second set of sub-regions by adding a third set of sub-regions to the first set of sub-regions, wherein each sub-region in the third set does not contain the net's pins;
- c) a third set of instructions for identifying a first set of routes for the second set of sub-regions, wherein the first-route set includes at least one route, and each route in the first-route set traverses the sub-regions in the second set.
Dependencies are inferred from the claim text.