VLSI Cell Placement Techniques
PROUD: Placement by Block Gauss-Seidel Optimization
The module placement problem involves placing a set of modules (standard cells, gate arrays, sea-of-gates) on a VLSI chip, given a netlist that specifies the connectivity between the modules. The objective is to minimize the total wire-length between the modules. In this blog, we try to solve such placement problems using PROUD algorithm.
PROUD uses the quadratic placement formulation , how- ever, instead of determining the eigenvalues and eigenvectors of a large matrix, the concept of resistive network optimization is used. The PROUD algorithm is especially suitable for extremely large designs having tens of thousands of gates and produces placement qualities comparable to those obtained by simulated annealing but in runtimes that are orders of magnitude faster.
PROUD is a hierarchical algorithm. It has two major components: global placement by solving a system of equations, and partitioning based on the result of placement.
Global placement is based on two assumptions,
1. All modules are point modules and
2. All nets are two-pin nets.
Thus multi-pin nets are expanded into two-pin net cliques. The weight of each edge of an r-terminal net is set to 2=r.
Let matrix C = (cij);
where cii = 0 and
cij be the number of nets connecting module i and module j.
Let (xi, yj ) represent the location of module i, and x̅ and ȳ represent the n-dimensional vectors which specify the coordinates of the n modules.
The objective is to minimize the sum of the squared wire lengths
D : be the diagonal matrix.
B = D — C, then
Based on a resistive network analogy, the minimization of the term ~xT B~x can be achieved by solving
In this way, the chip area is partitioned into two equal-sized sub-blocks with roughly equal number of modules in each sub-block. Then the new blocks will placed by global placement. The loop of global placement and partitioning is executed a few times to make the placement more accurate. This number is called the block Gauss-Seidel number. In the next level of the hierarchy, the coordinate is switched to y. This process continues until each block contains at most one module.
