Floorplanning of VLSI by Mixed-Variable Optimization

Given a collection of rectangular modules $V=\{v_{1},v_{2},\ldots,v_{n}\}$ and a set of edges (networks) $E=\{e_{1},e_{2},\ldots,e_{m}\}$, the VLSI floorplanning problem tries to minimize the total wirelength and the floorplan area by placing modules in approximate positions. Denote the center coordinates of module $v_{i}$ be $(x_{i},y_{i})$, and its orientation is represented by $r_{i}$. A floorplan of VLSI is represented by the combination of vectors $\bm{x}$, $\bm{y}$ and $\bm{r}$, where $\bm{x}=(x_{1},x_{2},\dots,x_{n})$, $\bm{y}=(y_{1},y_{2},\dots,y_{n})$, $\bm{r}=(r_{1},r_{2},\dots,r_{n})$. Subject to the constraint of placing non-overlaping modules with a fixed outline, the floorplanning problem is formulated as

where $W(\bm{x},\bm{y})$ is the total wirelength, $D(\bm{x},\bm{y},\bm{r})$ is the sum of overlapping area, and $B(\bm{x},\bm{y},\bm{r})$ is the sum of width beyond the fixed outline. By the Lagrange multiplier method, it can be transformed into an unconstrained optimization model

where $\alpha$, $\lambda$, and $\mu$ are parameters to be confirmed. Here, the square root of $D(\bm{x},\bm{y},\bm{r})$ is adopted to ensure that all indexes to be minimized are of the same dimension.

Zhu et al.[13] proposed to solving the non-smooth continuous optimization model of the global placement by the conjugate sub-gradient algorithm (CSA). With an initial solution $\bm{u}_{0}$, the pseudo code of CSA is presented in Algorithm 1. Because the CSA is not necessarily gradient-descendant, the step size has a significant influence on its convergence performance. The step size is determined by the norm of the conjugate directions together with the control parameter $s_{k}$, which is updated as $s_{k}=qs_{k-1}$. As an initial study, we set $q=0.997$ in this paper. The termination-condition 1 is satisfied if $k$ is greater than a given budget $k_{max}$ or several consecutive iterations fails to get a better solution.

Besides the coordinate vectors $\bm{x}$ and $\bm{y}$, the floorplan is also confirmed by the orientation vectors $\bm{r}$. The orientation of modules is confirmed by clockwise rotation, and we set $r_{i}=j$ if the rotation angle is $\theta_{i}=j\pi/2$, $j=0,1,2,3$, $i=1,\dots,n$. The, optimization of the orientation vectors contributes to a combinatorial optimization problem.

The estimation of distribution algorithm (EDA) is a kind of metaheuristics that can address the combinatorial optimization problem well, but its balance between global exploration and local exploitation is a challenging issue [14]. Xu et al. [15] proposed for the graph coloring problem a distribution evolutionary algorithm based on a population of probability model (DEA-PPM), where a novel probability model and the associated orthogonal search are introduced to achieve well convergence performance on large-scale combinatorial problems.

The core idea of DEA-PPM for floorplanning is to simulate the probability distribution of orientations by constructing a probability matrix

where $\vec{q}_{j}$ representing the probability that module $j$ satisfies

Then, the random initialization of $\bm{q}$ generates a distribution matrix

The implementation of DEA-PPM is based on distributed population $\bm{Q}(t)=(\bm{q}^{[1]},\dots,\bm{q}^{[np]})$ and solution population $\bm{P}(t)=(\bm{p}^{[1]},\dots,\bm{p}^{[np]})$, which are employed here for the probability distributions and instantiations of orientation, respectively. Global convergence of DEA-PPM is achieved by an orthogonal search on $\bm{Q}(t)$, and the local exploitation are implemented in both the distribution space and the solution space.

In this paper, the fixed-outline floorplanning algorithm based on CSA and DEA-PPM (FFA-CD) is proposed to solve the problem of fixed-outline floorplanning, where the DEA-PPM is employed to optimize the orientations of the modules and the CSA is used to optimize the corresponding coordinates of the modules.

The framework of FFA-CD is presented in Algorithm 2. It starts with initialization of the distribution and solution populations $\bm{Q}(0)$ and $\bm{P}(0)$, where $\bm{P}(0)$ consists of orientation combinations of modules. Meanwhile, the corresponding population $\bm{X}$ and $\bm{Y}$ of module coordinate is initialized by Latin hypercube sampling [16]. Combining the orientation and coordinates of modules, we get the best coordinate vectors $\bm{x}^{*}$ and $\bm{y}^{*}$, as well as the corresponding orientation vector $\bm{r}^{*}$. Then, the while loop of DEA-PPM is implemented to update $\bm{Q}(t)$ and $\bm{P}(t)$, where the CSA is deployed in UpdateXY to get the best module coordinate.

In order to better explore the distribution space, DEA-PPM carries out orthogonal exploration for individuals in $\bm{Q}(t)$. Algorithm 3 gives the flow of orthogonal exploration, which aims to change $m$ worst individuals in $\bm{Q}$ by orthogonal transformation performed on $c$ columns of a distribution matrix. Here, $m$ is a random integer in $[1,np/2]$ and $c$ is a random integer in $[1,n/10]$.

In Algorithm 4, the intermediate distribution population $\bm{Q}^{\prime}(t)$ is further updated to get $\bm{Q}(t)$. Given $\bm{q}^{[i]}\in\bm{Q}^{\prime}(t)$, it is updated using $\bm{v}^{\prime[i]}$ and $\bm{v}^{[i]}$, two orientation combinations selected from $\bm{P}^{\prime}$ and $\bm{P}$, respectively. Columns of $\bm{q}^{[i]}$ are updated using either a exploitation strategy or a disturbance strategy presented as follows.

The floorplan is represented by the orientation vector $\bm{r}$ and the coordinate vectors $\bm{x}$ and $\bm{y}$. In FFA-CD, the evolution of orientation vectors is implemented by iteration of solution population $\bm{P}(t)$, and the corresponding coordinate vectors are optimized by the function UpdateXY.

We first test the performance of FFA-CD on the fixed-outline cases. It is compared with the well-known open source layout planner Parquet-4.5 [17], where the floorplan is represented by the B*-tree and the simulated annealing algorithm to solve the combinatorial optimization model of floorplanning.

According to the given aspect ratio $R$, the width $W^{*}$ and height $H^{*}$ of the fixed contour are calculated as [18]

where $A$ is the summed area of all modules, and $\gamma$ is the white rate defined in (20). The experiment set the white rate as $\gamma=15\%$, the aspect ratio R as 1, 1.5, 2, and the population number as 5. For different aspect ratios, each experiment was independently run 10 times, and the results were shown in Table 1.

Numerical results demonstrate that FFA-CD outperforms Parquet-4.5 on cases with more than 50 modules, but runs a bit slow for some of the small cases, which is attributed to the compact floorplan of Parquet-4.5. The combinatorial floorplan implemented by Parquet-4.5 could lead to smaller HPWL and shorter runtime, but its performance would degrade significantly while the problem size increases. The iteration mechanism based on CSA ensures that FFA-CD can explore the floorplan space more efficiently. At the same time, DEA-PPM is introduced to explore the rotation strategy, which increases the flexibility of the floorplan and greatly improves the success rate of small-scale problems. Consequently, the success rate of FF-CD was better than or equal to Parquet-4.5 for all cases. Meanwhile, better results on wirelength and tuntime is obtained in several different aspect ratios for the larger-scale cases (n50-n100).

For layout planning problems without fixed contour constraints, FA-GSS is used to optimize the wirelength and area. The proposed FA-GSS is compared with Parquet-4.5 and the Hybrid Simulated Annealing Algorithm (HSA) [19], where the population size is set as 5, and we get $\epsilon=0.2\%$. Due to the different magnitude of wirelength and area, the cost function to minimized for the floorplanning problem without fixed outline is taken as

where $W_{{min}}$ and $S_{{min}}$ are the minimum values of $W$ and $A$, respectively.

The results in Table 1 show that all examples obtain better wirelength and shorter time when the aspect ratio is 1. So, we take $R=1$ in FA-GSS for all test cases. For benchmarks in GSRC, the average $Cost$, and runtime (CPU) of ten independent runs are collected in Table 2.

The experimental results show that FA-GSS outperforms both Parquet-4.5 and HAS except for the n30 case. Although FA-GSS runs a bit slower than Parquet-4.5 when they are tested by the n30 case, FA-GSS has the smallest rate of increase in run time as the module size increases. This means that FA-GSS is expected to achieve excellent results on larger circuits.