A Novel Macro Placement Approach based on Simulated Evolution Algorithm

Abstract

This paper proposes a novel approach to handle the macro placement problem, which integrates the simulated evolution algorithm and corner stitching data structure. Unlike the simulated annealing based algorithm which has to pack each macro to a contour in its representation, a macro can be placed at any empty region according to the corner stitching. Hence, even when a chip contains several preplaced macros which do not abut to boundaries, it can be easily handled by our approach. Moreover, we further apply an efficient and effective simulated evolution algorithm to refine a placement. To avoid standard cells being placed at a small region or being pushed away from related macros in the cell placement stage, our macro placement method also preserves placement areas for standard cells by expanding macros according to the design hierarchy. The experimental results show that our approach obtains better results than CP-tree and a commercial tool in term of wirelength and routability. More importantly, our methodology can complete a large test case in 6 minutes that CP-tree fails to get a result in one day, and their runtime is 659 times longer than ours even when large test cases are ignored.