Method and apparatus for pre-computing placement costs
Some embodiments of the invention provide a method that pre-computes costs of placing circuit modules in regions of circuit layouts. The method defines a set of partitioning lines for partitioning the region into a plurality of sub-regions during a placement operation. For each set of potential sub-regions, the method identifies a connection graph that traverses the set of potential sub-regions. Some of the connection graphs have edges that are at least partially diagonal. The method then identifies an attribute of each identified connection graph. For each set of potential sub-regions, the method then stores the identified attribute of the connection graph that is identified for the set.
1. A method of pre-computing costs of placing circuit modules in regions of circuit layouts, the method comprising:
a) defining a set of partitioning lines for partitioning the region into a plurality of sub-regions during a placement operation;
b) for each set of sub-regions, identifying a connection graph that traverses the set of sub-regions, wherein some of the connection graphs have edges that are at least partially diagonal;
c) identifying an attribute of each identified connection graph;
d) for each set of sub-regions, storing the attribute of the connection graph identified for the set, wherein said attribute is for use during a placement operation to compute costs of placing circuit modules in regions of circuit layouts.
2. The method of claim 1 , wherein the connection graph for each set of sub-regions is the shortest graph that traverses the set of sub-regions.
3. The method of claim 2 , wherein each connection graph is a Steiner tree.
4. The method of claim 1 , wherein the attribute is the length the method further comprising:
for each connection graph, identifying a bend-value;
for each set of potential sub-regions, storing the bend value of the connection graph identified for the set.
5. The method of claim 4 , wherein the bend-value of a graph specifies the number of diagonal bends of the graph.
6. The method of claim 1 , wherein the partitioning lines form a partitioning grid.
7. The method of claim 1 , wherein the partitioning lines are horizontal and vertical lines.
8. For a placer that partitions a region of a circuit layout into a plurality of sub-regions, a method of computing placement costs, the method comprising:
a) for a set of sub-regions, identifying a connection graph that connects the set of sub-regions, wherein the connection graph has at least one edge that is at least partially diagonal;
b) identifying a placement cost from an attribute of the connection graph;
c) storing the placement cost for the set of sub-regions, wherein said placement cost is for use during a placement operation to compute costs of placing circuit modules in regions of circuit layouts.
9. The method of claim 8 , wherein the attribute is the length of the connection graph, and the placement cost equals the length of the connection graph.
10. The method of claim 9 , wherein the length of the connection graph provides an estimate of the necessary wirelength for routing a net that has circuit elements in the set of sub-regions.
11. The method of claim 8 , wherein the attribute is a bend value.
12. The method of claim 11 , wherein the bend-value of a graph specifies the number of diagonal bends of the graph.
13. The method of claim 8 further comprising:
for each set of sub-regions,
(i) identifying a connection graph that connects the set of sub-regions;
(ii) identifying a placement cost from an attribute of the connection graph;
(iii) storing the placement cost for the set of sub-regions;
wherein some connection graphs have at least one edge that is at least partially diagonal.
14. The method of claim 13 , wherein the attributes are the lengths of the connection graphs, and the placement costs are the lengths of the connection graphs.
15. The method of claim 14 , wherein each connection graph is a Steiner tree.