VLSI Cell Placement Techniques
NUMERICAL OPTIMIZATION TECHNIQUES:
In numerical optimization, techniques can be classified on the basis of equation solving and eigenvalue calculations. These techniques are computationally intensive deterministic. Such techniques are mainly used for macro blocks. The major problem encountered in using these techniques is that the placement is nonlinear. To overcome this obstacle, two different approaches can be used. One approach is to approximate the problem by linear method and then use linear programming, whereas the other approach focuses on using non-linear programming.
1 Eigenvalue Method:
This is an O(n2) algorithm. Hall [1970] has formulated the cell placement problem as a quadratic assignment problem and devised a novel method to solve it by using eigenvalues.
Consider a cost matrix cij, which represents the connection cost of elements of i and j and a distance matrix dkl representing the distance between locations k and l. Find a permutation function p, that maps elements i, j to locations k = p(i), l= p(j), such that the sum 𝛟 is minimized.
Given assignment problem can be solved as follow:
The permutation function p maps each cell to a slot. The wire length is given by the product of the connectivity and the distance between the slots to which the cells have been mapped. Thus, 𝜙 gives the total wire length for the circuit, which is to be minimized.
Let C be the connection matrix.
Let ci be the sum of all elements in the ith row of C.
D be the diagonal matrix such that,
D ij = 0, i≠ j,
Ci’ , i=j.
Let B be the matrix,
where, B= D — C
Further,
let X = [xl, x2, . . . . xn] be the row vector representing x coordinates
and YT = = [yl, y2, . . . . yn] be the row vector representing y coordinates
On the basis of given data, it can be proved that
These constraints are required specifically to avoid the trivial solution (of a quadratic equation) xi = 0 for all i.
Now α and β be the Lagrange Multipliers.
Lagrange Multipliers are used for minimization on forming the lagrangian as follow:
Now, on equating the first partial derivatives of L with respect to X and Y to zero, we get
Or
On separating the common term,
These equations yield a nontrivial solution if and only if α and β are eigenvalues of the matrix B, X and Y being the corresponding eigenvectors.
Pre-multiplying these equations by ,
respectively, and imposing the constraints , we get
Thus, in order to minimize the value of the objective function 𝜙, we must choose the smallest eigenvalues as a solution for α + β. The corresponding eigenvectors X and Y will give the x- and y-coordinates of all the modules.
If 0 — λ1 < λ2 < λ3 < . . . < λm are the distinct eigenvalues of B, then taking α = β = λ1 will give the minimum value. 𝜙 = O. x1 will be proportional to y1, all xi will be equal and all yi will be equal.
If it is desired that X not be proportional to Y (that is we require a two-dimensional solution with all modules not placed along a straight line), we must select different eigenvalues for α and β.
Further, if it is desired that not all Xi or all Yi, be equal, we should ignore λ1 = O.
Thus, a near optimal nontrivial solution is α = λ2, β = λ3. The components of the eigenvector associated with the second-smallest eigenvalue give the x-coordinates of all the modules, and the components of the eigenvector associated with the third smallest eigenvalue give the y-coordinates of all modules.
Analysis:
This is a 0(n2) algorithm. Weakness of this algorithm is that it does not take module size, shape, and routing channel width into account. It assumes that the modules are zero-area points. Therefore, it does not correspond very well to the module placement problem, where the modules must be placed at grid points or in rows. For large circuits, mapping the modules form this placement to grid points can be very difficult with many ties requiring arbitrary decisions. The wire length is often increased significantly while converting the result of this algorithm to a legal placement.
