Recursive partitioning placement method and apparatus
First Claim
1. For an electronic design automation application, a partitioning method of placing circuit modules in a region of an integrated circuit (“
- IC”
) layout, wherein said IC layout includes nets and a plurality of circuit elements, each net representing interconnections between a set of circuit elements in the IC layout, the method comprising;
a) defining a plurality of partitioning lines that divide the IC region into several sub-regions;
b) identifying the set of sub-regions containing the circuit elements of a net, said set of sub-regions representing the net'"'"'s configuration with respect to the defined partitioning lines;
wherein a connection graph models the net'"'"'s configuration with respect to the defined partitioning lines;
said connection graph having an edge that is completely or partially diagonal; and
c) identifying an attribute of the connection graph.
1 Assignment
0 Petitions
Accused Products
Abstract
One embodiment of the invention is a recursive partitioning method that places circuit elements in a 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.
-
Citations
27 Claims
-
1. For an electronic design automation application, a partitioning method of placing circuit modules in a region of an integrated circuit (“
- IC”
) layout, wherein said IC layout includes nets and a plurality of circuit elements, each net representing interconnections between a set of circuit elements in the IC layout, the method comprising;a) defining a plurality of partitioning lines that divide the IC region into several sub-regions;
b) identifying the set of sub-regions containing the circuit elements of a net, said set of sub-regions representing the net'"'"'s configuration with respect to the defined partitioning lines;
wherein a connection graph models the net'"'"'s configuration with respect to the defined partitioning lines;
said connection graph having an edge that is completely or partially diagonal; and
c) identifying an attribute of the connection graph. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
a) constructing the connection graph after identifying the set of sub-regions containing the net'"'"'s circuit elements;
b) measuring the attribute of the constructed connection graph.
- IC”
-
8. The method of claim 1 wherein a data structure stores attributes of all connection graphs that model all potential net configurations with respect to the partitioning lines, wherein identifying the attribute of the connection graphs comprises retrieving said attribute from the data structure.
-
9. The method of claim 8 wherein retrieving said attribute comprises retrieving the attribute by using the identified set of sub-regions.
-
10. The method of claim 1 further comprising calculating the cost of a placement layout within the region from the identified connection-graph attribute.
-
11. The method of claim 1 further comprising:
-
a) changing the position of a circuit element of the net from one sub-region to another;
b) identify a new set of sub-regions that contain the circuit elements of the net, said new set of sub-regions representing the net'"'"'s new configuration with respect to the defined partitioning lines;
wherein a new connection graph models the net'"'"'s configuration with respect to the defined partitioning lines;
said new connection graph having an edge that is completely or partially diagonal;
c) identifying an attribute of the new connection graph.
-
-
12. The method of claim 1 further comprising:
-
a) for each particular net that has a circuit element in said region, identifying the set of sub-regions containing the circuit elements of the particular net, said set of sub-regions representing the particular net'"'"'s configuration with respect to the defined partitioning lines;
wherein a connection graph models the particular net'"'"'s configuration with respect to the defined partitioning lines;
identifying an attribute of the connection graph;
wherein some of the connection graphs have an edge that is completely or partially diagonal;
b) calculating a cost of an initial placement configuration within the region by using the identified attributes.
-
-
13. The method of claim 12 further comprising modifying the placement configuration in the IC regions to optimize the placement cost.
-
14. The method of claim 13 further comprising:
-
a) after optimizing the placement configuration within the region, defining a second plurality of partitioning lines that divide one of said sub-regions into smaller sub-regions;
b) for each particular net that has a circuit element in said divided sub-region, identifying the set of smaller sub-regions containing the circuit elements of the particular net, said set of smaller sub-regions representing the particular net'"'"'s configuration with respect to the second partitioning lines;
wherein a connection graph models the particular net'"'"'s configuration with respect to the second partitioning lines;
identifying an attribute of the connection graph;
wherein some of the connection graphs have an edge that is completely or partially diagonal;
b) calculating a cost of an initial placement configuration within the divided sub-region by using the identified attributes.
-
-
15. The method of claim 1, wherein the region is the entire IC layout.
-
16. The method of claim 1, wherein the region is a portion of the IC layout.
-
17. The method of claim 1, wherein the partitioning lines are intersecting lines that define a partitioning grid.
-
18. The method of claim 1, wherein the intersecting partitioning lines are N horizontal and M vertical lines that divide the IC region into (N+1)(M+1) sub-regions, where N and M can equal any integer.
-
19. For an electronic design automation (“
- EDA”
) application that performs a placement process, a method of pre-computing costs of placements of circuit modules in regions of integrated circuit (“
IC”
) layouts, the method comprising;a) defining a partitioning grid with N number of slots, said partitioning grid for partitioning a region of an IC layout into N sub-regions during the placement process of the EDA application;
b) for each particular grouping of slots of said grid, constructing a connection graph that models the topology of interconnect lines needed to connect said particular group of slots;
c) computing an attribute of each of the constructed connection graphs;
d) storing said attribute in a data structure. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27)
a) for each particular grouping of slots of said grid, constructing, based on a second wiring model, a connection graph that models the topology of interconnect lines needed to connect said particular group of slots;
b) computing an attribute of each of the connection graphs that are constructed based on the second wiring model; and
c) storing said attribute in a data structure.
- EDA”
-
27. The method of claim 26 wherein the first wiring model is the octagonal wiring model, and the second wiring model is the hexagonal wiring model.
Specification