Algorithm for Block Placement by Size Optimization

This approach selects the optimal block size and relative block placement repeatedly in order to eliminate wasted space and reduce total chip area. During the optimization process, channel widths are also taken into account.

The placement problem is reformulated as a linear programming problem, which this algorithm solves using the Simplex approach. . This approach is an extension of Kozawa et al[1984] .’s work, and it employs their Combined and Top Down Placement (CTOP) technique to arrange the blocks. This is combined with linear programming block resizing. Only use this approach if block sizes aren’t yet defined and macro blocks can be formed with a variety of aspect ratios.

The CTOP algorithm generates an initial placement as the first step. This method operates by combining two blocks to generate a hyper-block over and over until the entire chip is made up of one hyper-block. At each phase, blocks are paired to reduce wasted space and increase connectedness.

A combine tree is formed by repeatedly merging blocks, with the entire chip serving as the root node and the individual blocks serving as leaves. This tree is then explored from the top down, so that a good location for each hy — per-component block’s blocks may be determined. This shows how the blocks are arranged in relation to one another.

A Block Neighboring Graph is created using the relative location (BNG). The BNG represents each block as a node, and each segment of a routing channel between two blocks as an edge connecting the nodes. The linear programming approach for block size optimization is the next step. The linear programming approach for block size optimization is the next step.

The primary objective is to minimize the chip area. Wire length is considered indirectly through its effect on the chip area. There is a user-specified limit on the chip aspect ratio.