A floorplanning algorithm using rectangular Voronoi diagram and force-directed block shaping

The authors propose a novel floorplanning algorithm which handles a mixture of fixed-shaped and variable-shaped blocks in a chip having a chip aspect ratio within a given range. This algorithm consists of two stages. In the first stage, overlapped blocks in the initial placement obtained using FDR (force directed relaxation) are spread out uniformly over the whole chip area using the ratioed rectangular Voronoi diagram such that each block finds enough space without significant overlap with its neighboring blocks. In the second stage, each block is reshaped or moved by the independent move of each block edge according to the attractive force and repulsive force exerted on it due to the overlap and the dead space, respectively. Experimental results were obtained on the ami33 benchmark circuit with varying conditions on the aspect ratio of blocks and chip. Significant improvement of the chip utilization factor has been obtained compared to previous work.<>