PLACEMENT METHOD AND NON-TRANSITORY COMPUTER READABLE STORAGE MEDIUM

Abstract

A placement method for integrated circuit design is provided. Each net is considered as a soft module. The net will receive a larger penalty if it covers more routing congested regions. Therefore, it is easier to move the nets away from routing congested regions. In addition, to relieve local congestion, a novel inflation method is proposed to expand the area of a cluster according to its internal connectivity intensity and routing congestion occupied by the cluster. Accordingly, it can get better routability and wirelength.

Claims

1. A placement method of integrated circuit design for a computer system, wherein a placement region is divided into a plurality of grids, a plurality of cells form a plurality of nets, each of the nets connects at least two of the cells, and the placement method comprises: taking the cells as a plurality of clusters, and merging the clusters in each of a plurality of levels from bottom to up; performing an initial placement; and disassembling the clusters in each of the levels from the up to the bottom and performing a first placement procedure comprising: setting a bounding box for each of the nets, wherein the bounding box covers at least one first grid of the grids; for each of the nets, calculating a routing congestion penalty according to an overlapping area between the bounding box and the at least one first grid and an overflow value of the at least one first grid; and establishing a first objective function according to the routing congestion penalties of the nets to determine locations of the clusters so that the first objective function outputs a first optimal value.

2. The placement method of claim 1, wherein merging the clusters comprises: generating a new cluster to contain a first cluster and a second cluster of the clusters; and summing up an internal connectivity intensity of the first cluster, an internal connectivity intensity of the second cluster, and a score between the first cluster and the second cluster to obtain an internal connectivity intensity of the new cluster, wherein the score is negatively related to a number of branches between first cluster and the second cluster.

3. The placement method of claim 2, wherein when the first cluster or the second cluster belongs to a lowest level of levels, the corresponding internal connectivity intensity is equal to 0, wherein the score is also negatively related to an area of the first cluster and an area of the second cluster.

4. The placement method of claim 3, wherein the first placement procedure further comprises: updating the overflow value of each of the grids; and for each of the clusters, obtaining a second grid of the grids that has a greatest overlapping area with the cluster, calculating an inflation ratio according to the overflow value of the second grid and the internal connectivity intensity of the cluster, and adjusting a size of the cluster according to the inflation ratio.

5. The placement method of claim 4, wherein the first placement procedure further comprises: when calculating the inflation ratio, multiplying the internal connectivity intensity of the corresponding cluster by a weight which is positively related to a current level of the levels.

6. The placement method of claim 5, wherein the inflation ratio is calculated by following equations: $$\begin{gathered} \begin{array}{cc}\gamma \left(c_i^l\right)=\min \left\{{\gamma }_{{\min }^{+}}\hat{o}\left(c_i^l\right)+\frac{l}{N_L}\times \hat{\eta }\left(c_i^l\right),{\gamma }_{\max }\right\} \\ \hat{o}\left(c_i^l\right)=\max \left\{\frac{o\left(c_i^l\right)-o_T}{o_{\max }},0\right\} \\ \hat{\eta }\left(c_i^l\right)=\max \left\{\frac{\eta \left(c_i^l\right)-{\eta }_T}{{\eta }_{\max }},0\right\}& \end{array} \end{gathered}$$ wherein l is the current level, c.sub.i.sup.l is an i.sup.th cluster in the current level, γ(c.sub.i.sup.l) is the inflation ratio of the cluster c.sub.i.sup.l, N.sub.L is a number of the levels, wherein γ.sub.min, γ.sub.max, o.sub.T and η.sub.T, are predetermined real values, wherein o(c.sub.i.sup.l) is the overflow value of the second grid corresponding to the cluster c.sub.i.sup.l, η(c.sub.i.sup.l) is the internal connectivity intensity of the cluster c.sub.i.sup.l, o.sub.max is a greatest overflow value among the grids, and η.sub.max is a greatest internal connectivity intensity among the clusters.

7. The placement method of claim 6, further comprising: performing a second placement procedure before the first placement procedure, wherein the second placement procedure comprises: for each of the cluster, calculating a second inflation ratio of the cluster, and adjusting the size of the cluster according to the second inflation ratio; and establishing a second objective function to determine the locations of the clusters so that the second objective function outputs a second optimal value, wherein the second objective function does not contain the routing congestion penalties.

8. The placement method of claim 1, wherein the routing congestion penalty of each of the nets is calculated by a following equation: $C_i=\underset{g_{k\in G\cap B_i}}{.Math.}{\rho }_k\times {\pi }_k$ wherein C.sub.i is the routing congestion penalty of an i.sup.th net of the nets, B.sub.i is the bounding box of the i.sup.th net, G is a set formed by the grids, g.sub.k is the at least one first grid that is covered by the bounding box B.sub.i, wherein ρ.sub.k is a ratio of the overlapping area between the at least one first grid g.sub.k and the bounding box B.sub.i to an area of the bounding box B.sub.i, and π.sub.k is the overflow value of the at least one first grid g.sub.k.

9. A non-transitory computer readable storage media for storing a plurality of instructions, wherein the instructions are configured to be executed to perform the placement method of claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] The invention can be more fully understood by reading the following detailed description of the embodiment, with reference made to the accompanying drawings as follows.

[0017] FIG. 1 is a diagram illustrating routing congestions caused by different reasons.

[0018] FIG. 2 is a diagram illustrating cells and nets in accordance with an embodiment.

[0019] FIG. 3 is a flow chart of a placement method in accordance with an embodiment.

[0020] FIG. 4 is a diagram illustrating the procedures of the step 301 in accordance with an embodiment.

[0021] FIG. 5 is a diagram illustrating congestion map and layout in a high level and a low level in accordance with an embodiment.

[0022] FIG. 6 is a diagram illustrating the procedures of the step 303 in accordance with an embodiment.

[0023] FIG. 7 is a diagram illustrating nets and bounding boxes in accordance with an embodiment.

[0024] FIG. 8 is a diagram illustrating nets and congestions regions in accordance with an embodiment.

[0025] FIG. 9 is a diagram illustrating overlap between the bounding box and the grids in accordance with an embodiment.

DETAILED DESCRIPTION

[0026] Specific embodiments of the present invention are further described in detail below with reference to the accompanying drawings, however, the embodiments described are not intended to limit the present invention and it is not intended for the description of operation to limit the order of implementation. Moreover, any device with equivalent functions that is produced from a structure formed by a recombination of elements shall fall within the scope of the present invention. Additionally, the drawings are only illustrative and are not drawn to actual size.

[0027] The using of “first”, “second”, “third”, etc. in the specification should be understood for identifying units or data described by the same terminology, but are not referred to particular order or sequence.

[0028] FIG. 2 is a diagram illustrating cells and nets in accordance with an embodiment. Four cells 201-204 are illustrated in FIG. 2. The cells 201-204 form nets 211-214 which are configured to connect pins of the cells 201-204. Each net connects at least two cells. For example, the net 211 connects one input pin of the cell 201 and an output pin of the cell 202, and so on. The number of branches of a net is defined as the number of the connected pins. For example, the number of branches of the net 211 is two, and the number of branches of the net 214 is three. In the embodiment, the cells 201-204 are logic gates, but they may be flip flops or any other suitable circuits in other embodiments.

[0029] A placement method is provided for spreading the cells in a placement region. FIG. 3 is a flow chart of a placement method in accordance with an embodiment. Referring to FIG. 3, the provided placement method is based on multilevel framework that includes three steps 301-303. The step 301 is also referred to coarsening for taking all cells as clusters and merging the clusters in each level from bottom to up. In the step 302, an initial placement is performed. Any conventional approach such as quadratic placement may be adopted in the step 302. The step 303 is also referred to uncoarsening or refinement for disassembling the clusters in each level from up to bottom and determining the location of each cluster. Detail embodiments will be provided below.

[0030] FIG. 4 is a diagram illustrating the procedures of the step 301 in accordance with an embodiment. In step 401, a Design Hierarchy Tree (DHT) is established by the reference of Lin, Jai-Ming, Szu-Ting Li, and Yi-Ting Wang. “Routability-driven Mixed-size Placement Prototyping Approach Considering Design Hierarchy and Indirect Connectivity Between Macros.” Proceedings of the 56th Annual Design Automation Conference 2019. Let c.sub.i.sup.l denotes a cluster in a level l which is initialized as zero. In the level 0, each cell is taken as a cluster c.sub.i.sup.0.

[0031] In the step 402, two clusters c.sub.j.sup.l and c.sub.k.sup.l are selected with a largest score S(c.sub.j.sup.l, c.sub.k.sup.l) between the cluster c.sub.j.sup.l and the cluster c.sub.k.sup.l, and a new cluster c.sub.i.sup.l is generated to contain the cluster c.sub.j.sup.l and the cluster c.sub.k.sup.l. The score is calculated by the following Equation 1.

[00003]$\begin{array}{cc}S\left(c_j^l,c_k^l\right)=e^{\frac{-\left(A_j^l+A_k^l\right)}{\mu \times A_{avg}}}\times \underset{e_m\in E_{j,k}}{.Math.}\frac{1}{d\left(e_m\right)-1}& \left[\mathrm{Equation}1\right]\end{array}$

[0032] A.sub.j.sup.l denotes the area of the cluster c.sub.j.sup.l. A.sub.k.sup.l denotes the area of the cluster c.sub.k.sup.l. A.sub.avg denotes the average area of all clusters. μ is a predetermined real number (e.g. determined by the user). E.sub.j,k denotes a set of the nets connecting the cluster c.sub.j.sup.l and the cluster c.sub.k.sup.l. e.sub.m denotes one of the nets connecting the cluster c.sub.j.sup.l and the cluster c.sub.k.sup.l. d(e.sub.m) denotes the number of branches of the net e.sub.m. Larger score S(c.sub.j.sup.l, c.sub.k.sup.l) represents that the clusters c.sub.j.sup.l, c.sub.k.sup.l have smaller areas and stronger connectivity intensity (i.e. the second term on the right side of the equal sign in Equation 1). In the embodiment, the score S(c.sub.j.sup.l, c.sub.k.sup.l) is negatively related to the areas of the clusters c.sub.j.sup.l, c.sub.k.sup.l. In particular, the score S(c.sub.j.sup.l, c.sub.k.sup.l) is negatively related to the number of branches d(e.sub.m) because fewer branches of a net represents the corresponding two clusters connects with the each other with fewer routes (i.e. stronger connectivity intensity). In contrast, if the number of branches is large, it means the corresponding two clusters can be connected by multiple routes and therefore the connectivity intensity is relatively weak.

[0033] In step 403, an internal connectivity intensity (ICI) of the new cluster is calculated by the following Equation 2.

η(c.sub.i.sup.l)=S(c.sub.j.sup.l,c.sub.k.sup.l)+η(c.sub.j.sup.l)+η(c.sub.k.sup.l)  [Equation 2]

[0034] η(c.sub.i.sup.l) denotes the internal connectivity intensity of the new cluster cil. η(c.sub.j.sup.l) denotes the internal connectivity intensity of the cluster c.sub.j.sup.l. η(c.sub.k.sup.l) denotes the internal connectivity intensity of the cluster c.sub.k.sup.l. In other words, the internal connectivity intensity of the new cluster is calculated by summing up the internal connectivity intensity of the cluster C.sub.j.sup.l, the internal connectivity intensity of the cluster c.sub.k.sup.l, and the score S(c.sub.j.sup.l, c.sub.k.sup.l) between these two clusters. When a cluster belongs to the lowest level (i.e. l=0), the internal connectivity intensity of this cluster is equal to zero, and that is η(c.sub.i.sup.0)=0. Note that larger score S(c.sub.j.sup.l, c.sub.k.sup.l) results in a larger internal connectivity intensity η(c.sub.i.sup.l).

[0035] In step 404, it is determined whether to stop merging. In some embodiments, it is determined whether to stop merging based on the number of the cluster because this number is getting smaller. For example, it is determined if an inequality N.sub.i/N′.sub.l>α holds where N.sub.l denotes the initial number of the clusters in the level l, N′.sub.l denotes the current number of the clusters, and a denotes a predetermined real number (e.g. 1.7). If the inequality equation holds, then the merging stops to perform step 408, otherwise the merging continues (step 405 is performed).

[0036] In the step 405, it is determined if there is suitable clusters to be merged. Based on the algorithm of the design hierarchy tree, only the clusters in the same layer are selected. If the result of the step 405 is “No”, then the design hierarchy tree is amended in the step 406, and step 407 is performed to process a new layer in the design hierarchy tree. The detail of the steps 405 to 407 may be referred to the reference of the Design Hierarchy Tree mentioned above.

[0037] In the step 408, it is determined whether to stop establishing new levels. In some embodiments, this is also based on the number of the clusters. For example, it is determined if the inequality N′.sub.lβ holds where denotes a predetermined real number (e.g. β=0.05×N.sub.0). If the inequality holds, then the procedure ends, otherwise step 409 is performed to process the next higher level (i.e. l=l+1).

[0038] In the embodiments, the clusters are merged based on the Design Hierarchy Tree algorithm, but the clusters may be merged based on any other suitable algorithm as long as the internal connectivity intensity of each cluster is calculated in each level. In other words, another calculation of the score different from the Equation 1 may be adopted when merging the clusters. In addition, the score of merging the clusters may be different from that of calculating the internal connectivity intensity. It is in the spirit of the disclosure as long as the score S(c.sub.j.sup.l, c.sub.k.sup.l) is positively related to the connectivity intensity between these two clusters and negatively related to the number of branches of the nets when calculating the internal connectivity intensity. People in the art should be able to devise another score S(c.sub.j.sup.l, c.sub.k.sup.l) based on the disclosure.

[0039] Next, refinement is performed. In some conventional approaches, inflation technology is used to increase a size of a cell so that the cell may be removed from a congested region to avoid local routing congestion. However, this approach relies on the congestion map which is composed of overflow values of grids of the placement region. However, the congestion map in high levels may not be accurate. FIG. 5 is a diagram illustrating congestion maps and layout in a high level and a low level in accordance with an embodiment. Referring to FIG. 5, a placement region 510 shows layout result in the high level, and a congestion map 520 is also calculated in the high level. A placement region 530 is the layout result in the low level, and a congestion map 540 is calculated in the low level. It is shown in FIG. 5 that there is a significant difference between the congestion map 520 and the congestion map 540 because the congestion inside the clusters is unknown. In the embodiment, the inflation is performed according to the congestion map in addition to the internal connectivity intensities of the clusters to reduce local routing congestion.

[0040] FIG. 6 is a diagram illustrating the procedures of the step 303 in accordance with an embodiment. In step 601, the congestion map is updated.

[0041] The congestion map includes overflow values of all the grids. The overflow value of a grid is defined as a routing number that the grid needs minus a routing number that the grid provides. The larger the overflow value is, the more the grid is congested. The overflow value of each grid is updated based on the current layout. People in the art should be able to appreciate the congestion map, and therefore the detail thereof is not described herein.

[0042] In step 602, the clusters in the current level l are disassembled. In step 603, an inflation ratio of each cluster is calculated according to the congestion map and its internal connectivity intensity. To be specific, the inflation ratio may be calculated based on the following Equations 3-5.

[00004]$\begin{array}{cc}\gamma \left(c_i^l\right)=\min \left\{{\gamma }_{{\min }^{+}}\hat{o}\left(c_i^l\right)+\frac{l}{N_L}\times \hat{\eta }\left(c_i^l\right),{\gamma }_{\max }\right\}& \left[\mathrm{Equation}3\right]\end{array}$$\begin{array}{cc}\hat{o}\left(c_i^l\right)=\max \left\{\frac{o\left(c_i^l\right)-o_T}{o_{\max }},0\right\}& \left[\mathrm{Equation}4\right]\end{array}$$\begin{array}{cc}\hat{\eta }\left(c_i^l\right)=\max \left\{\frac{\eta \left(c_i^l\right)-{\eta }_T}{{\eta }_{\max }},0\right\}& \left[\mathrm{Equation}5\right]\end{array}$

[0043] γ(c.sub.i.sup.l) denotes the inflation ratio of the cluster c.sub.i.sup.l. Since the cluster c.sub.i.sup.l may overlap with multiple grids, the grid g having greatest overlapping area with the cluster c.sub.i.sup.l is considered. o(c.sub.i.sup.l) denotes the overflow value of the grid g. ô(c.sub.i.sup.l) denotes a normalized overflow value. o.sub.max denotes the greatest overflow value among all the grids. η(c.sub.i.sup.l) denotes the internal connectivity intensity of the cluster c.sub.i.sup.l. {circumflex over (η)}(c.sub.i.sup.l) denotes a normalized internal connectivity intensity. η.sub.max denotes the greatest internal connectivity intensity among all the clusters. o.sub.T, η.sub.T,γ.sub.min, and γ.sub.max are predetermined real numbers (e.g. determined by the user). N.sub.L denotes the number of all the levels. In some embodiments, the inflation ratio is limited in the range from 1 to 2, and therefore γ.sub.min=1, and γ.sub.max=2. In some embodiment, η.sub.T, is twice the average of the internal connectivity intensities of all clusters in the current level l.

[0044] Note that l/N.sub.L in the Equation 3 is a weight which is positively related to the current level l. The current level l is decreased during refinement, and therefore the weight is decreased from 1 of the highest level to 0 of the lowest level (each cluster only contains one cell in the lowest level). The weight l/N.sub.L is decreased because there exists more internal connectivity intensity in a cluster in a higher level. However, the overflow values in the high level are less accurate. On the contrary, there exists less internal connectivity intensity in a cluster in a lower level with more accurate overflow values. After the inflation ratio γ(c.sub.i.sup.l) is calculated, the size of the cluster c.sub.i.sup.l (i.e. the area the cluster c.sub.i.sup.l occupies in the placement region) is adjusted according to the inflation ratio.

[0045] In step 604, a wirelength-driven distribution is performed. In detail, an objective function is established to determine locations of the clusters so that the objective function outputs an optimal value. The objective function is written in the following Equation 6.

[00005]$\begin{array}{cc}\min {\lambda }_{1}W\left(x,y\right)+{\lambda }_2\underset{b}{.Math.}{\left(U_b\left(x,y\right)-M_b\right)}^2& \left[\mathrm{Equation}6\right]\end{array}$

[0046] In the embodiments, the placement region is divided into multiple bins. The size of the bins may be larger, equal, or smaller than that of the grids. W(x, y) denotes a total length of the wires. U.sub.b(x,y) denotes the total area of the cells in the bin b. M.sub.b denotes the maximum allowable area of the cells in the bin b. λ.sub.l and λ.sub.2 are user-specified real numbers. The Equation 6 may be referred to the reference of Chen, Tung-Chieh, et al. “NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints.” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27.7 (2008): 1228-1240, and the detail thereof is not described herein.

[0047] In step 605, it is determined if spreading is enough. If the result of the step 605 is “yes”, step 606 is performed, otherwise the step 604 is performed. In some embodiments, an overflow area of each bin is calculated. The overflow area is defined as the total area of the cells (e.g. clusters) in the bin minus the area of the bin. The less the overflow area is, the less the bin is congested. The total overflow area of all bins is divided by the total area of all movable clusters to obtain an overflow area ratio. If the overflow area ratio is less than a threshold (e.g. 0), then it is determined that the spreading is enough.

[0048] In the step 606, the overflow value of each grid is updated. In step 607, for each cluster, an inflation ratio is calculated according to the overflow value of the grid and the internal connectivity intensity of the corresponding clusters, and a size of the cluster is adjusted according to the inflation ratio. The step 607 may be referred to the step 603, and therefore the detail is not repeated herein.

[0049] In step 608, a routability-driven distribution is performed. The global routing congestion cannot be solved when only considering the wirelength. In the embodiment, each net is considered as a movable soft bounding box. FIG. 7 is a diagram illustrating nets and bounding boxes in accordance with an embodiment. Referring to FIG. 7, a net 710 connects pins 721-724, and a bounding box 730 is a minimum rectangle to cover all the pins 721-724. In the embodiment, a penalty is given to the region that each net occupies. When the bounding box 730 covers larger or more congested regions, the corresponding net receives larger penalty. The shape and the location of the bounding box 730 will change to move the net to a low congested region. FIG. 8 is a diagram illustrating nets and congested regions in accordance with an embodiment. Referring to FIG. 8, a scenario 810 illustrates a layout based on a conventional approach. The scenario 810 includes three congested regions 821-823 and three nets 831-833. In the embodiment, the shape and location of the nets can change, and accordingly as shown in a scenario 820, the shapes of the nets 831-833 change, and the nets 831-833 are moved to low congested regions.

[0050] To be specific, let n.sub.i denotes the i.sup.th net. B.sub.i denotes the bounding box corresponding to the net n.sub.i. Given a placement, a routing congestion penalty of the net n.sub.i is calculated as the following Equation 7.

[00006]$\begin{array}{cc}{C}_i=\underset{g_k\in G\cap B_i}{.Math.}{\rho }_k\times {\pi }_k& \left[\mathrm{Equation}7\right]\end{array}$

[0051] C.sub.i denotes the routing congestion penalty of the net n.sub.i. G denotes a set including all the grids. g.sub.k denotes the grid covered by the bounding box B.sub.i. π.sub.k denotes the overflow value of the grid g.sub.k. ρ.sub.k denotes a ratio of an overlapping area between the grid g.sub.k and the bounding box B.sub.i to the area of the bounding box B.sub.i. For example, FIG. 9 is a diagram illustrating overlap between the bounding box and the grids in accordance with an embodiment. Referring to FIG. 9, four grids 901-904 are shown in which the overflow value of the grid 901 is equal to 1.41, the overflow value of the grid 902 is equal to 1.02, the overflow value of the grid 903 is equal to 0.9, and the overflow value of the grid 904 is equal to 0.89. The bounding box 910 is overlapped with the grids 901-904 in which 15% of the area of the bounding box 910 is overlapped with the grid 901, 22% of the area of the bounding box 910 is overlapped with grid 902, 28% of the area of the bounding box 910 is overlapped with the grid 903, and 35% of the area of the bounding box 910 is overlapped with the grid 904. Therefore, the routing congestion penalty of the net n.sub.i corresponding to the bounding box 910 is calculated as 0.15×1.41+0.22×1.02+0.28×0.9+0.35×0.89=0.9994. When the net n.sub.i covers more congested regions, it receives larger penalty. In other words, the routing congestion penalty servers as routability. The larger the routing congestion penalty is, the lower the routability is. In order to present the Equation 7 by the coordinates of cells, we transform the Equation 7 into the following Equation 8.

[00007]$\begin{array}{cc}{C}_i\left(x,y\right)=\underset{g_k\in G}{.Math.}\Phi \left(B_i,g_k\right)& \left[\mathrm{Equation}8\right]\end{array}$

[0052] Φ(B.sub.i, g.sub.k) denotes the penalty contributed by any grid g.sub.k. Φ(B.sub.i, g.sub.k) can be calculated as the following Equation 9.

[00008]$\begin{array}{cc}\Phi \left(B_i,g_k\right)=\frac{P_x\left(B_i,g_k\right)\times P_y\left(B_i,g_k\right)}{{.Math.}_{g_k\in G}{P}_x\left(B_i,g_k\right)\times P_y\left(B_i,g_k\right)}\times {\pi }_k& \left[\mathrm{Equation}9\right]\end{array}$

[0053] P.sub.x(B.sub.i, g.sub.k) denotes the width of the overlapping are between the bounding box B.sub.i and the grid g.sub.k. P.sub.y(B.sub.i, g.sub.k) denotes the height of the overlapping are between the bounding box B.sub.i and the grid g.sub.k. Since P.sub.x(B.sub.i, g.sub.k) and P.sub.y(B.sub.i,g.sub.k) cannot be differentiated, they are replaced by {circumflex over (P)}.sub.x(B.sub.i, g.sub.k) and {circumflex over (P)}.sub.y(B.sub.i, g.sub.k) according to the bell-shaped potential function as the following Equation 10 and 11. Without loss of generality, only {circumflex over (P)}.sub.x(B.sub.i,g.sub.k) is illustrated. {circumflex over (P)}.sub.y(B.sub.i,g.sub.k) can be done similarly.

[00009]$\begin{array}{cc}{\hat{P}}_x\left(B_i,g_k\right)=\{\text{⁠}\begin{array}{c}1-a{d}_x^{2}0\le d_x\le w_{B_i}/2+w_{g_k}\\ {b\left(d_x-w_{B_i}/2-2w_{g_k}\right)}^2,w_{B_i}/2+w_{g_k}\le d_x\le w_{B_i}/2+w_{g_k}\\ 0,w_{B_i}/2+2w_{g_k}\le d_x\end{array}& \left[\mathrm{Equation}10\right]\end{array}$$\begin{array}{cc}a=4/\left(w_{B_i}+2w_{g_k}\right)\left(w_{B_i}+4w_{g_k}\right)b=2/w_{g_k}\left(w_{B_i}+4w_{g_k}\right)& \left[\mathrm{Equation}11\right]\end{array}$

[0054] d.sub.x denotes the distance between the center of the bounding box B.sub.i and the center of the grid g.sub.k in the x-axis. w.sub.Bi denotes the width of the bounding box B.sub.i. w.sub.gk denotes the width of the grid g.sub.k. To compute the distance d.sub.x, we have to get the center coordinate of the bounding box B.sub.i, which is denoted by (x.sub.Bi, γ.sub.Bi). x.sub.Bi is computed by the following Equation 12, and the width w.sub.Bi is computed by the following Equation 13.

[00010]$\begin{array}{cc}{x}_{B_i}=\frac{\underset{v_k\in n_i}{\max }{x}_k+\underset{v_k\in n_i}{\min }{x}_k}{2}& \left[\mathrm{Equation}12\right]\end{array}$$\begin{array}{cc}{w}_{B_i}=\underset{v_k\in n_i}{\max }{x}_k-\underset{v_k\in n_i}{\min }{x}_k& \left[\mathrm{Equation}13\right]\end{array}$

[0055] v.sub.k denotes a cell of the net n.sub.i. x.sub.k denotes the x-coordinate of the center of the cell v.sub.k. Because the function max.sub.ck∈nix.sub.k and min.sub.ck∈nix.sub.k are not differentiable, we apply the log-sum-exp function to compute the value.

[0056] According to the aforementioned disclosure, the objective function established in the step 608 is written in the following Equation 14.

[00011]$\begin{array}{cc}\min {\lambda }_{1}W\left(x,y\right)+{\lambda }_2\underset{b}{.Math.}{\left(U_b\left(x,y\right)-M_b\right)}^2+{\lambda }_{3}C\left(x,y\right)& \left[\mathrm{Equation}14\right]\end{array}$

[0057] The difference between the Equation 14 and the Equation 6 is routing congestion penalty C(x,y) which is defined in the following Equation 15.

[00012]$\begin{array}{cc}C\left(x,y\right)=\underset{n_i\in \Psi }{.Math.}{C}_i\left(x,y\right)& \left[\mathrm{Equation}15\right]\end{array}$

[0058] Ψ denotes a list (i.e. set) including all the nets. In some embodiments, λ.sub.1 and λ.sub.2 are set according to the following Equations 16 and 17. λ.sub.3 is a predetermined real number (e.g. determined by the user) such as 1 in some embodiments.

[00013]$\begin{array}{cc}{\lambda }_1=\frac{.Math..Math.\partial C\left(x,y\right).Math.}{.Math..Math.\partial W\left(x,y\right).Math.}& \left[\mathrm{Equation}16\right]\end{array}$$\begin{array}{cc}{\lambda }_2=\frac{.Math..Math.\partial C\left(x,y\right).Math.}{.Math..Math.\partial U_b\left(x,y\right).Math.}& \left[\mathrm{Equation}17\right]\end{array}$

[0059] In some embodiments, to make the cells evenly distributed over the placement region, λ.sub.1 and λ.sub.3 are fixed, and λ.sub.2 is increased (e.g. double) every iteration. In some embodiments, the Equation 14 may be solved for computing the coordinates x and y of every cluster by a conjugate gradient (CG) approach so that the objective function output an optimal value (e.g. minimum in the embodiment), but how the Equation 14 is solved is not limited in the disclosure.

[0060] In step 609, it is determined if the current level is the lowest level, then then procedure ends if the result is “yes”, otherwise step 610 is performed to process the next lower level (i.e. l=l−1).

[0061] The steps 603-605 may be collectively referred to a second placement procedure 620, and the steps 606-608 may be collectively referred to a first placement procedure 630. The objective function of the step 608 includes the routing congestion penalty C(x,y), but the objective function of the step 604 does not include the routing congestion penalty. This is because the clusters are located nearby in the initial stage and thus the routing congestion penalty cannot be considered. The wirelength-driven distribution is performed first to spread the clusters in the initial stage. The disclosure is not limited to the flow chart of FIG. 6, any suitable objective function may be adopted in the step 604 or the second placement procedure 620 may be omitted. In addition, the disclosure is not limited to the objective function of Equation 14, other objective functions may be adopted as long as it includes the routing congestion penalty C(x, y).

[0062] From another aspect, a non-transitory computer readable storage media is provided. The media may be a random access memory, a read-only memory, a flash memory, floppy disks, hard disks, CD-ROMs, pen drives, tapes, databases accessible via the Internet for storing instructions which are configured to be executed to perform the placement method.

[0063] The characteristics of the disclosure at least include: 1) We target on global and local routing congestion and use different strategies to resolve the problems in the multilevel framework; 2) We propose a congestion-aware net penalty model to reduce global congestion; 3) We propose a novel inflation technique by considering the internal connectivity intensity of a cluster as well as the congestion value occupied by the cluster to alleviate local congestion.

[0064] Although the present invention has been described in considerable detail with reference to certain embodiments thereof, other embodiments are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the embodiments contained herein. It will be apparent to those skilled in the art that various modifications and variations can be made to the structure of the present invention without departing from the scope or spirit of the invention. In view of the foregoing, it is intended that the present invention cover modifications and variations of this invention provided they fall within the scope of the following claims.