Breuer’s Algorithms
partitioning for placement.
Breuer’s algorithms were among the first to use partitioning for placement. As the circuit is repeatedly partitioned along a given set of cut lines, they minimize the number of nets that are cut. Breuer has investigated two fundamental placement algorithms. Each of these algorithms necessitates a specific sequence of cut lines that divide the chip into parts, each of which contains only one slot. To be compatible with Breuer’s notation, the portions of the chip generated by the partitioning method are referred to as blocks in the following discussion. This is not to be confused with macro bricks.
Cut Oriented Min-Cut Placement Algorithm: Begin with the entire chip and a predefined collection of cut lines. Allow the first cut line to divide the chip into two parts. Also, split the circuit into two sub-circuits such that the net-cut is as minimal as possible. Partition all of the blocks intersected by the second cut line, and then partition the circuit accordingly. This process should be repeated for all cut lines. Figure 1a depicts this operation. This algorithm implements the previously mentioned sequential objective function. In reality, however, this algorithm does not always produce successful results due to two issues. Examine Figure 1. We must partition blocks A and B generated by c1 simultaneously while processing cut line C2. Second, if they can be partitioned sequentially, processing time would be saved due to a reduction in problem size. Furthermore, a conflict can occur if we attempt to bisect blocks A and B using the same cut line. If the modules of A that are to be put above C2 need a larger area than the corresponding elements of B, it is difficult to bisect A and B with the same cut line, and a less optimal partition must be accepted. To avoid each of these concerns, another algorithm is presented in which each block is partitioned with its own cut line.
Block-Oriented Min-Cut Placement Algorithm: In this algorithm, a cut line is chosen to split the chip into two regions. Then, for each region, we choose a separate cut line and partition the regions further. This process is replicated 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 for partitioning the chip can be chosen in any order. Breuer has given three sequences (Figure 3) that are ideally suited to three different styles of layout. There are the following:
(1) Quadrature Placement Procedure: The partitioning method in this algorithm is done breadth first, with alternate vertical and horizontal cuts. Figure 3a portrays this technique. A area is subdivided into two equal sub regions with each cut. Where there is a high routing density in the middle, this approach is appropriate. Congestion in the middle is minimized by first cutting through the center and minimizing the net-cut. This is currently the most common cut line sequence for min-cut algorithms.
(2)Bisection Placement Procedure: The chip is repeatedly bisected (divided into two equal sub regions) by horizontal cut lines in this process, until each sub region consists of one row. This process assigns each element to a row without tying it to a specific location. Then, each row is repeatedly bisected until each resulting sub region contains just one space, resulting in the placement of all movable modules (Figure 3b). This is a good technique for putting standard cells. It does not, however, guarantee that the actual net-cut per channel is kept to a minimum.
(3) Slice Bisection Procedure: Another method of positioning is to separate a suitable 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 each module is allocated to a row. The modules in each row are then allocated to columns by bisecting them with vertical cut lines (Figure 3c). When there is a high interconnect density at the periphery, this technique is best suited.
