An Overlap Removal Algorithm for Macrocell Placement in VLSI Layouts

An efficient overlap removal algorithm in the context of macrocell placement is presented in this paper. The algorithm works on a novel augmented constraint graph and removes overlap in the presence of fixed location, spacing and boundary constraints imposed on macro cells. We propose a modified parallel plane shadowing sweep algorithm for creation of constraint graph and an augmentation scheme to handle constraints effectively. The spatial relations that exist among the macro cells in an overlapping placement are retained in the overlap free placement. A peripheral placement of macro cells is made feasible by utilizing the information in the constraint graph to compact the macro cells towards the periphery in conjunction with the legalization of the macro cells. Experimental results obtained with and without compaction on randomly generated testcases based on GSRC floorplanning benchmarks are presented. The runtime of the algorithm has been shown to scale linearly with increasing number of blocks