Kappen describes an algorithm for cell placement in standard-cell or sea-of-gates VLSI design styles. The placement problem is modeled as a quadratic assignment problem whose solution is generated by a technique based on recursive partitioning. It improves a method proposed by Kuh et al. [1–3].
The introduction mentions some existing placement methods using recursive partitioning and includes good references. Next, an exact formulation of the quadratic assignment problem is given.
Section 3 deals with recursive partitioning. The author uses bipartitioning of the grid; the sizes of the subgrids created should be roughly equal. The cell assignment to the subgrids is found by solving an optimization problem: a quadratic cost function is to be minimized under an additional requirement of balance for the cell positions. Therefore the method needs no constraints on the number and position of border cells, unlike Kuh’s method, and exceeds it. The solution of the constraint optimization problem is the solution of a system of n+1 linear equations with n+1 unknowns (where n is the number of cells to be placed). Using sparse matrix methods, the author shows that the time complexity for the whole method is O(n log2 n).
Numerical results compare the algorithm with eigenvector and simulated annealing techniques. The paper presents interesting research results for scientists who are interested in circuit layout algorithms. It is written well, and its length is just right.
