I. INTRODUCTION

The floorplanning procedure is to place blocks by using the connection information among the blocks while trying to optimize the wirelength, area utilization, critical path delays, and routing congestions. At the same time, each block should be placed at a legal location without illegal overlaps. During the past few years, several works have been reported for floorplanning optimization. Recently 3D floorplanning techniques are introduced^[1,2]. Typical floorplanning methods based on simulated annealing techniques include fixed outline^[3] and BSG^[4]. Recently, analytical placement methods such as mPL6^[5] and APlace3^[6] have shown the best performance, for example, in ISPD 2005/2006 placement contests.

An analytical method consists of three stages: global placement, legalization, and post processing. Typically, global placement determines the location of blocks while minimizing the total wirelength and trying to optimize the timing and routability. After global placement, the results may contain macro/cell overlaps, and the macros/cells may not be aligned to the rows. The target of legalization is removing all the overlaps between the macros/cells, and putting all the macros/cells on the rows or columns in the placement area while maintaining the relative positions with minimal displacement. We can obviously find that the overlaps remaining after the global placement directly affect the legalization process and thus the quality of the final solution. Like most analysis methods, mPL6^[5] and APlace3^[6] regard global placement as a constrained nonlinear optimization problem: They divide the placement area into uniform bins, and seek to minimize the total wirelength under the constraint that the total module area density in every bin is less than or equal to the target density of the bin.

In conventional analytical methods^[5,6], the overlaps of the macros/cells are reduced by increasing the global overlap penalty factor in a cost function while iteratively minimizing the cost function using a conjugate gradient method. However, this single global penalty factor may not be effective, since the overlaps in each bin can vary significantly depending on the connectivity of the macros/cells. In this paper, we describe a new adaptive density control method in which the overlaps in each bin are analyzed, and the density of each bin is adaptively determined so that the overlaps can effectively be reduced. Experimental results show that the overlaps before legalization step can be reduced by 90.8 to 98.6% on average when compared to those of the conventional single global penalty factor methods.

In Section II, the overall floorplanning algorithm is described. The new adaptive density control method is explained in detail, in Section III, followed by the description of the experimental results in Section IV. Finally, conclusions are summarized in Section V.

II. OVERALL FLOORPLANNING ALGORITHM

Analytical method is widely used for large scale circuit placement owing to good performance^[5,6]. The circuit netlist can be formulated as a hypergraph H={V, E}, where the vertex set, V={v1,v2,…,vn}, represents the set of all macros/cells and the edge set, E={e1, e2,…, en}, represents the set of nets. Analytical placement adopts its own objective function such as that shown in (1) and (2).

where $W L(\vec{x}, \vec{y})$ is the total wirelength, $\mu$ is the density penalty factor, $P_{d_{i j}}(\vec{x}, \vec{y})$ is the penalty function to penalize the density violations, $d_{i j}(\vec{x}, \vec{y})$ denotes the density of a bin(i, j), and TD denotes the target density of the bin. Analytical placement allows overlap among the macros/cells and spreads macros/cells by increasing the density penalty factor $\mu$. In the case of the quadratic cost, all the nets are divided into two port nets, and a quadratic wirelength cost model is used. It can find the block position efficiently by using the first order derivative (gradient) of the cost function.

Analytical placement has an advantage in dealing with mixed size circuits. However, it has a disadvantage when there are blocks which should be placed in a restricted area, especially when the available area is highly non-convex. Analytical placement continuously moves blocks with finite resolution and allows overlaps between blocks. Therefore, an analytical method needs a legalization step. The legalization step is to remove all the overlaps between the macros and cells and to put all the macros and cells in the legal placement area. To minimize the disruption of the optimized positions of macros/cells during legalization, the amount of overlaps should be minimized during the global analytical placement.

III. NEW EFFECTIVE ADAPTIVE DENSITY CONTROL FOR OVERLAP REDUCTION

In analytical placement, macros/cells are moved by using their gradients. When two macros/cells are connected by a net, then attractive force is produced due to the connection, and repulsive force is produced due to the overlap penalty term. When the attractive and repulsive force form an equilibrium, the gradient becomes zero until the penalty weight is increased. In conventional analytical method, one global penalty weight is used. We developed a new method in which the cell density for each bin is adaptively adjusted by using the local congestion.

Eqs. ((3), (4)) show the objective function of our analytical method. In our new method, the density daij for each bin (i,j) is adaptively adjusted for effective removal of overlaps

where $P_{d_{i j}}(\vec{x}, \vec{y})$ is the density penalty function to penalize the density violations. Now we explain how the adaptive density for each bin is computed.

IV. EXPERIMENTAL RESULTS

We implemented our adaptive density control algorithm in the C++ language on a 3.4 GHz Intel Xeon CPU with 64 GB memory. We used the GSRC hard benchmark to illustrate the performance of our algorithm. The information of the GSRC-hard benchmark is shown in Table 1.

We used an analytical method and the conjugate gradient method to solve the unconstrained optimization problem. For this experiment, we implemented a legalization procedure based on [7]^[7]. When the total

overlap area is less than 35% of total macro/cell area, we apply adaptive density control (shown in Algorithm 1 and 2). The threshold value 35% was experimentally chosen. If this value is too small, the adaptive density control starts too early, when the placement information is not yet accurate, wasting CPU time. When this value is too large, the adaptive density control starts too late and may cause less optimized final results. For the n30 circuit in the GSRC-hard benchmark, the amount of overlaps each global placement iteration without and with our adaptive density control feature is shown in Fig. 3. From the result, one can see that the amount of overlap is reduced very effectively and efficiently with adaptive density control. In the current implementation, $\rho$ = 0.00049 and $\sigma$ = 0.1 are used, since optimal average half-parameter wirelength (HPWL) can be obtained with three values ( $\mu$, $\rho$, $\sigma$ ). These parameters are optimized based on experiments and $\mu$ increased from 1, $\rho$ = 0.00049 and $\sigma$ = 0.1 are used.

Table 2 shows the results of the GSRC-hard benchmark without and with our adaptive density control feature. The area for floorplanning is fixed for all circuits by 800x800 in Table 2. We also do the experiment by changing the floorplanning area constraint. The area constraint refers to the ratio of the floorplanning area to the sum of the macro/cell area. The experimental results of the different area constraints (140% and 120%) without and with our adaptive density control are shown in Table 3 and Table 4. To the best of our knowledge, there is no previous report which shows effective overlap reduction techniques. Therefore, we compare the results without and with the adaptive density control feature to evaluate the performance. The overlap amount is an area and the displacement is a distance.

From Table 2-Table 4, one can see that the overlap before legalization can be reduced by 90.8 to 98.6% on average. The Max displacement (Total displacement) after legalization can also be reduced by 62.0 to 88.3% (44.0 to 85.1%) on average, respectively, when compared to those of the conventional single global penalty function method. The HPWL cost after legalization can also be reduced by 1.5 to 2.0 %. With adaptive density control, the CPU time takes longer (154 to 283%), however, the reduction of the overlaps after analytical placement is significant, and thus the displacement of macros/cells can also be significantly reduced during legalization.

A fixed area of 800x800 is used in Table 2. Therefore, area margin is large for small circuits and margin is small for big circuits. The area constraint 100% means that the area is tight and there is no room to move cells. When area constraints are 120% and 140% of total cell area, there are 20% and 40% margins in area and thus further optimization can be achieved. In Table 2, the overlap amount of some circuits (n30c, n50, n50b, n50c, n200c) are increased. In cases of 120% and 140%, large cells cannot be easily moved since the area margin is not big (only 20% or 40%). On the other hand, the large size cells within the fixed size of 800x800 can move easily even if the proposed method is applied because there are many empty spaces within the boundary. Therefore, the cells spread outward quickly in the fixed area with large margin. At the end, the cells are attracted toward the center to reduce the total wierlength, resulting in slight overlaps, and therefore, the results can be worse in some cases in the fixed area case with large margin.

Table 5 shows GSRC-hard Benchmark Results using the Parquet-4, A-FP and new ADC analytical methods with area constraint (115%). Our method produced 32% and 14% better results in HPWL when compared to a Parquet-4^[3] and a A-FP^[8].

Table 6 shows the detailed routing results of the GSRChard benchmark for conventional and new ADC analytical methods. To compare the final results after detailed routing, we performed the detailed routing using Synopsys design compiler using 0.18 μm library. Since lef/def data of GSRC benchmarks are not given, we transformed placement results into lef/def format to perform detailed routing. Our method produced 1.5% to 2.0% better final results in wirelength when compared to a conventional analytical method as shown in Table 6(for area constraints of 140% and 120%). This means that our proposal method can improve the final wirelength of the design.

V. CONCLUSIONS

The overlaps remaining after the global placement directly affect the complexity of legalization and the quality of the final floorplaning solution. Most of the conventional analytical methods just control a single global penalty factor while iteratively minimizing the cost function to reduce the overlaps. We have developed an effective adaptive density control method in which the density of each bin is adaptively controlled to reduce the overlaps among the macros/cells while minimizing the total wirelength or other cost function in the global placement stage. The experimental results show that overlaps can be greatly reduced during analytical placement and thus the displacement required during legalization can also be significantly reduced. The final results after detailed routing can also be improved by using the proposed adaptive density control technique.