VLSI Cell Placement Techniques

PLACEMENT BY PARTITIONING

Placement by partitioning is a type of placement algorithm that involves repeatedly dividing a given circuit into densely connected sub circuits in order to reduce the number of nets cut by the partition. Also, the available chip area is partitioned alternately in the horizontal and vertical direction with each partitioning of the circuit(Fig.1.).

Fig.1.The chip area is alternately partitioned in vertical and horizontal directions

Each sub circuit is assigned to one of the chip’s partitions. If this process is carried out until there is only one module in each sub circuit, then each module will have been mapped to a unique position on the chip.

Most partitioning algorithms, or Min-cut algorithms, use some modified form of partitioning heuristics from Kernighan-Lin and Fiduccia-Matthey, as well as Schweikert and Kernighan.

The algorithm for partitioning Kernighan-Lin is as follows. Start with a random initial partition that splits the module set into two separate A and B sets. Assess the net cut (the number of nets connecting modules in A to modules in B and are therefore cut by the partition).Find the reduction g in the net cut obtained by swapping a and b for all pairs (a, b), where a belongs to A and b belongs to B (moving a to set B and b to A). The interchange gain is denoted by the letter g. If g > 0, the interchange is advantageous. Choose the module pair with the highest gain g1 (a1, b1). Find the new maximum gain g2 for a pairwise interchange by removing al and b1 from A and B. ( a2, b2).Keep this process going until A and B are empty. Find a value of k to maximize the total gain

and exchange the corresponding module pairs (a1, b1)…., (ak, bk). This process should be repeated until G>0 and k>0.

Figure 3shows an example of partitioning-based placement. The circuit to be laid and the desired pad locations are shown in Figure 2. As shown in Figure 3, this circuit is partitioned several times. The number of nets intersected by the cut line is reduced at each step, and the sub circuits are assigned horizontally or vertically partitioned chip areas.

Fig.2.Input: Netlist

Fig. 3. Min-cut partitioning of the circuit in Figure 2

The resulting placement Figure 4 yields a total wire length of 43 (for chain connections).

Fig.4. checkboard model