Analytical placement method and apparatus

• US 20060236291A1
• Filed: 03/06/2006
• Published: 10/19/2006
• Est. Priority Date: 09/06/2001
• Status: Active Grant

• Current Assignee: Andrew Siegel, Hussein Etawil, Steve Teig
• Original Assignee: Andrew Siegel, Hussein Etawil, Steve Teig
• Inventors: Teig, Steven, Etawil, Hussein, Siegel, Andrew
• Granted Patent: US 7,493,581 B2
• Time in Patent Office: Days
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Some embodiments provide an analytical placement method that considers diagonal wiring. This method formulates an objective function that accounts for the use of diagonal wiring during routing. Some embodiments use horizontal, vertical, and ±45° diagonal lines. For such a wiring model, some embodiments use the following objective function: $\mathrm{Function}=\sum _n\sum _{p\left(n\right)}{b}_{i,j}\left(\begin{array}{c}\frac{1}{\sqrt{2}}\left(\sqrt{\beta +{\left(x_i-x_j\right)}^2}+\sqrt{\beta +{\left(y_i-y_j\right)}^2}\right)+\\ \left(1-\frac{1}{\sqrt{2}}\right)\sqrt{\begin{array}{c}\beta +{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2-\\ \frac{2{\left(x_i-x_j\right)}^2{\left(y_i-y_j\right)}^2}{\sqrt{\beta +{\left(x_i-x_j\right)}^2{\left(y_i-y_j\right)}^2}}\end{array}}\end{array}\right)$
In this equation, n represents a net, p(n) represents a unique pair of pins i and j of the net n, x and y represent the x-, and y-coordinates of a particular pin, and b_i,j represents a weighting factor that biases the function based on the desired closeness of pins i and j.

Claims

1. An analytical placement method for identifying locations of circuit elements in a region of a layout, the method comprising:

a) formulating an objective function that accounts for diagonal wiring during routing;

b) solving the objective function to identify the locations of the circuit elements to be Placed, wherein the objective function is continuously differentiable along at least a portion of a domain over which the objective function is defined.

2. The method of claim 1, wherein formulating the objective function further comprises:

a) identifying at least one pair of pins in the layout that have to be connected;

b) specifying the distance between the pin pair based on a distance formula that accounts for diagonal wiring during routing.

3. The method of claim 2, wherein the circuit elements are circuit modules, each circuit module having a set of pins, the region having a set of nets, wherein each net specifies a set of pins that have to be connected, wherein formulating the objective function further comprises:

a) identifying pairs of pins in the layout that have to be connected;

b) specifying the distance between each pin pair based on a distance formula that accounts for diagonal wiring during routing;

c) specifying the objective function as an amalgamation of the specified distance formulas.

4. The method of claim 3, wherein identifying pairs of pins in the layout comprises identifying each possible pair of pins of each net in the set of nets.

5. The method of claim 2, wherein the distance formula is based on a wiring model that is used for routing.

6. The method of claim 5, wherein the wiring model is an octilinear model that specifies horizontal, vertical, and ±

45°

wiring, wherein the distance formula is;

$\left(\frac{1}{\sqrt{2}}<br><br>\left(\sqrt{\mathrm{\beta <br><br>}+{\left(x_i-x_j\right)}^2}+\sqrt{\mathrm{\beta <br><br>}+{\left(y_i-y_i\right)}^2}\right)+\left(1-\frac{1}{\sqrt{2}}\right)<br><br>\sqrt{\mathrm{\beta <br><br>}+{\left(x_i+x_j\right)}^2+{\left(y_i-y_j\right)}^2-\frac{2<br><br>{\left(x_i-x_j\right)}^2<br><br>{\left(y_i-y_j\right)}^2}{\sqrt{\mathrm{\beta <br><br>}+{\left(x_i-x_j\right)}^2<br><br>{\left(y_i-y_j\right)}^2}}}\right)$

wherein i and j represent the pins, x and y represent the x-, and y-coordinates of a particular pin, and β

represents a smoothing parameter.

7. The method of claim 5, wherein the wiring model is a hexagonal model that specifies three wiring directions each at 60°

to other directions, wherein the distance formula is;

$\left(\frac{1}{2}<br><br>\sqrt{\mathrm{\beta <br><br>}+{\left(x_i-x_j\right)}^2}+\frac{\sqrt{3}}{2}<br><br>\left(\sqrt{\mathrm{\beta <br><br>}+{\left(y_i-y_i\right)}^2}\right)+\frac{1}{2}<br><br>\sqrt{\mathrm{\beta <br><br>}+{\left(x_i+x_j\right)}^2+\frac{1}{3}<br><br>{\left(y_i-y_j\right)}^2-\frac{2<br><br>{\left(x_i-x_j\right)}^2<br><br>{\left(y_i-y_j\right)}^2}{\sqrt{3<br><br>\left(\mathrm{\beta <br><br>}+{\left(x_i-x_j\right)}^2<br><br>{\left(y_i-y_j\right)}^2\right)}}}\right)$

wherein i and j represent the pins, x and y represent the x-, and y-coordinates of a particular pin, and β

represents a smoothing parameter.

8. The method of claim 5, wherein the wiring model is a model that specifies four wiring directions, three of which are at 60°

to one another and a fourth is at 90°

to one of other three directions, wherein the distance formula is;

$\left(\frac{3}{2}<br><br>\left(1-\frac{1}{\sqrt{3}}\right)<br><br>\sqrt{\mathrm{\beta <br><br>}+{\left(x_i-x_j\right)}^2}+\frac{1}{2}<br><br>\left(1+\frac{1}{\sqrt{3}}\right)<br><br>\left(\sqrt{\mathrm{\beta <br><br>}+{\left(y_i-y_i\right)}^2}\right)+\frac{\sqrt{3}-1}{2}<br><br>\sqrt{\mathrm{\beta <br><br>}+{\left(x_i+x_j\right)}^2+\frac{1}{3}<br><br>{\left(y_i-y_j\right)}^2-\frac{2<br><br>{\left(x_i-x_j\right)}^2<br><br>{\left(y_i-y_j\right)}^2}{\sqrt{3<br><br>\left(\mathrm{\beta <br><br>}+{\left(x_i-x_j\right)}^2<br><br>{\left(y_i-y_j\right)}^2\right)}}}\right)$

wherein i and j represent the pins, x and y represent the x-, and y-coordinates of a particular pin, and β

represents a smoothing parameter.

9. The method of claim 1, wherein the objective function is a first objective function, the method further comprising:

partitioning a region into a set of sub-regions;

specifying placement constraints based on the sub-regions;

finding a solution to a second objective function that satisfies the constraints, wherein the second objective function accounts for diagonal wiring during routing.

10. The method of claim 9, wherein the first and second objective functions are identical.

11. The method of claim 9, wherein the objective functions include a smoothing parameter, wherein the objective functions have different smoothing parameters.

12. The method of claim 9, wherein partitioning the region comprises partitioning the region into four sub-regions.

13. The method of claim 9, wherein specifying placement constraints comprises requiring each circuit element to be within a particular sub-region.

14. The method of claim 13, wherein specifying placement constraints further comprises requiring average x- and y-coordinates of the circuit elements in a sub-region to be within a particular range of a center of the sub-region.

15. The method of claim 13, wherein specifying placement constraints further comprises requiring average x- and y-coordinates of the circuit elements in a sub-region to be a center of the sub-region.

16. A computer readable medium that stores a computer program for an analytical placement method for identifying locations of circuit elements in a region of a layout, the program comprising instructions for:

a) formulating an objective function that accounts for diagonal wiring during routing; and

b) solving the objective function to identify the locations of the circuit elements to be placed, wherein the objective function is continuously differentiable along at least a portion of a domain over which the objective function is defined.

17. The computer readable medium of claim 16, wherein the instructions for formulating the objective function further comprises instructions for:

a) identifying at least one pair of pins in the layout that have to be connected;

b) specifying the distance between the pin pair based on a distance formula that accounts for diagonal wiring during routing.

18. The computer readable medium of claim 17, wherein the distance formula is based on a wiring model that is used for routing.

19. The computer readable medium of claim 16, wherein the objective function is a first objective function, the computer program further comprising instructions for:

partitioning a region into a set of sub-regions;

specifying placement constraints based on the sub-regions;

finding a solution to a second objective function that satisfies the constraints, wherein the second objective function accounts for diagonal wiring during routing.

20. The computer readable medium of claim 19, wherein the instructions for specifying placement constraints comprises instructions for requiring each circuit element to be within a particular sub-region.

21. The computer readable medium of claim 20, wherein the instructions for specifying placement constraints further comprises instructions for requiring average x- and y-coordinates of the circuit elements in a sub-region to be within a particular range of a center of the sub-region.

22. The computer readable medium of claim 20, wherein the instructions for specifying placement constraints further comprises instructions for requiring average x- and y-coordinates of the circuit elements in a sub-region to be a center of the sub-region.