PLACEMENT BY PARTITIONING
Cut Oriented Min-Cut Placement Algorithm: Begin by cutting a series of cut lines around the entire chip. Allow the chip to be partitioned into two blocks using the first cut line. Additionally, divide the circuit into two sub-circuits to reduce the net cut. Partition all of the blocks intersected by the second cut line, and then partition the circuit in the same way. Carry on in this manner with all cut lines. Figure 1 depicts this procedure. This algorithm implements the above-mentioned sequential objective function. In reality, however, this algorithm does not always produce satisfactory results due to two issues. Think about Figure 1. We must partition blocks A and B generated by c1 simultaneously while processing cut line C2.
This algorithm implements the above-mentioned sequential objective function. In reality, however, this algorithm does not always produce satisfactory results due to two issues. Take a look at Figure 1. We must partition blocks A and B generated by c1 simultaneously while processing cut line C2. First, by reducing the problem size, if there is a way to partition them sequentially, computation time will be saved. Furthermore, attempting to bisect blocks A and B using the same cut line can result in a conflict. If the modules of A that will be put above C2 need a larger area than the corresponding elements in B, then bisecting A and B with the same cut line will be impractical, and a less optimal partition will have to be accepted. Another algorithm is proposed to avoid each of these issues, in which each block is partitioned using a separate cut line.
Block-Oriented Min-Cut Placement Algorithm: We choose a cut line to divide the chip into two regions in this algorithm. Then, for each region, we choose a separate cut line and partition the regions further. This procedure is repeated until each block has just one slot.
As shown in Figure 2, different regions may have different cut lines. Since we are not making standardized cuts around the entire chip, we are no longer minimizing the sequential objective feature.
The cut lines used to partition the chip can be chosen in any order. Breuer has given three sequences (Figure 3) that are best suited to three different layout styles. The following are some of them:
(1) Quadrature Placement Procedure: The partitioning procedure is carried out breadth-first, with alternate vertical and horizontal cuts in this algorithm. Figure 3shows how this mechanism works. A region is divided into two equal subregions with each cut. Where there is a high routing density in the middle, this approach is appropriate. The congestion in the middle is minimized by first cutting through the center and minimizing the net cut.
This is the most famous cut line sequence for min-cut algorithms right now.
(2) Bisection Placement Procedure: The chip is bisected (divided into two equal subregions) by horizontal cut lines until each subregion consists of one row in this process. Each element is assigned to a row in this method, but its location is not fixed. Then each row is bisected again and again until each subregion has just one space, and all movable modules have been put (Figure 4). This is a good technique for placing standard cells. It does not, however, ensure that the actual net-cut per channel is kept to a minimum.
(3) Slice Bisection Procedure: Another method for module placement is to separate a reasonable number of modules from the rest of the circuit and allocate them to a row (slicing) by horizontal cut lines. This procedure is repeated until all of the modules have been allocated to a row. The modules in each row are then bisected and allocated to columns using vertical cut lines (Figure 5). When there is a high interconnect density at the periphery, this technique is best.
