Method and apparatus for computing placement costs by calculating bend values of connection graphs that model interconnect line topologies
First Claim
1. For a placer that places circuit modules in integrated-circuit (“
- IC”
) layouts, the placer using a set of partitioning lines, that define a plurality of slots, to partition an IC layout region into a plurality of sub-regions corresponding to said slots, a method of computing costs of placing circuit modules in an IC-layout region, the method comprising;
a) selecting a first group of said slots; and
b) calculating a number of bends in a set of one or more interconnect lines for connecting the first group of said slots.
2 Assignments
0 Petitions
Accused Products
Abstract
One embodiment of the invention is a recursive partitioning method that places circuit elements in an IC layout. This method initially defines a number of partitioning lines that divide an IC region into several sub-regions (also called slots). For a net in the region, the method then identifies the set of sub-regions (i.e., the set of slots) that contain the circuit elements (e.g., the pins or circuit modules) of that net. The set of sub-regions for the net represents the net'"'"'s configuration with respect to the defined partitioning lines. Next, the placement method identifies attribute or attributes of a connection graph that models the net'"'"'s configuration with respect to the partitioning lines. The connection graph for each net provides a topology of interconnect lines that connect the slots that contain the net'"'"'s circuit elements. According to some embodiments of the invention, the connection graph for each net can have edges that are completely or partially diagonal.
128 Citations
18 Claims
-
1. For a placer that places circuit modules in integrated-circuit (“
- IC”
) layouts, the placer using a set of partitioning lines, that define a plurality of slots, to partition an IC layout region into a plurality of sub-regions corresponding to said slots, a method of computing costs of placing circuit modules in an IC-layout region, the method comprising;a) selecting a first group of said slots; and
b) calculating a number of bends in a set of one or more interconnect lines for connecting the first group of said slots. - View Dependent Claims (2)
- IC”
-
3. For an electronic-design-automation placer that uses a set of partitioning lines, that define a plurality of slots, to partition an integrated-circuit (“
- IC”
) layout region into a plurality of sub-regions corresponding to said slots, a method of pre-computing placement costs, the method comprising;a) for each combination of said slots, identifying a connection graph that represents a topology of interconnect lines necessary for connecting the combination of said slots;
b) calculating a number of bends in each identified connection graph; and
c) storing the number of bends for each combination of slots in a storage structure. - View Dependent Claims (4, 5)
- IC”
-
6. For an electronic design automation (“
- EDA”
) application that performs placement operations, a method of computing costs for placing circuit elements within an integrated-circuit (“
IC”
) layout, the method comprising;a) defining a partitioning grid having a plurality of slots, said partitioning grid for partitioning a region of an IC layout into a plurality of sub-regions corresponding to said slots;
b) for each combination of said slots, identifying at least one connection graph that models a topology of interconnect lines for connecting the combination of said slots;
c) computing a length and number of bends in each of said connection graphs;
d) wherein when more than one connection graphs are identified for a particular combination of said slots, selecting the graph with the shortest length that has less than a first predetermined number of bends. - View Dependent Claims (7)
- EDA”
-
8. A method of placing a set of circuit modules in an integrated-circuit layout region, the method comprising:
-
a) partitioning the region into a plurality of sub-regions;
b) identifying a connection graph that connects the sub-regions that contain the set of circuit modules;
c) computing a placement cost based on a number of bends in the connection graph. - View Dependent Claims (9, 10, 11)
a) identifying a length of the connection graph;
b) computing the placement cost also based on the length of the connection graph.
-
-
12. A computer readable medium storing a computer program for placing a set of circuit modules in an integrated-circuit layout region, the computer program comprising sets of instructions for:
-
a) partitioning the region into a plurality of sub-regions;
b) identifying a connection graph that connects the sub-regions that contain the set of circuit modules;
c) computing a placement cost based on a number of bends in the connection graph. - View Dependent Claims (13, 14, 15)
a) identifying a length of the connection graph;
b) computing the placement cost also based on the length of the connection graph.
-
-
16. A method of placing a net in an integrated-circuit layout region, the method comprising:
-
a) identifying a connection graph for the net;
b) computing a placement cost based on a number of bends in the connection graph. - View Dependent Claims (17, 18)
-
Specification