VLSI Cell Placement Techniques
Resistive Network Optimization
The method has the feature which includes fixed modules in the formulation. The overall algorithm comprises the four subprograms: optimization, scaling, relaxation, partitioning and assignment. The method is efficient because it takes advantage of net-list sparsity .Thus the method is particularly useful in standard-cell and gate-array designs.
1. Optimization
The power dissipation in the resistive network is
The network equations are:
The solution to the optimization problem of minimizing P , is given by the well-known Kuhn-Tucker conditions:
where,
It is seen that that first term i.e., Eq(2)has no constraint on slots. The second term of Eq.(2) can be viewed as a correction term which attempts to put the solution on slots. Thus we have a linear resistive network with both voltage and current sources.
2. Scaling
The result of the optimization with linear constraint leads to solutions which have modules concentrated at the center of gravity of all movable modules. The linear constraint dictates the mean position of the modules. The only forces which attempt to scatter the modules are the fixed modules at the boundary. Therefore, in order to be able to partition the modules, scaling is introduced to redistribute the modules at the expense of increasing the power dissipation. The result of scaling gives an improvement from the result of optimization as far as module location is concerned but at the expense of increasing power dissipation.
3. Relaxation
Before partitioning and assigning of modules to slots, relaxation is to be performed. The method calls for repeated use of scaling and optimization over subregions to be specified by designers.
For this, we propose to choose subregions in the following way:
First we start from one end of the region, then the other end and, finally, the middle. After the initial optimization over the entire region, three such steps of scaling and optimization over subregions are carried out. The result tends to settle down and is ready for partitioning.
4. Partitioning and Assignment
After Relaxation, we next partition the region into two. The ratio of the left subregion to the right subregion is |m/2|/|m/2| where |k| denotes the largest integer which is smaller than k. We do scaling once more for the left subregion and for the right subregion. As before, in scaling for a subregion we keep those modules outside fixed. The result of this gives two partitioned subregions together with their associated modules. We next start over again on each subregion, i.e., perform optimization, relaxation, partitioning and scaling independently.
