Abstract
Legalization is one of the most critical steps in modern placement tool designs. Since several objectives like wirelength, routability, or temperature are already optimized in global placement stage. The objective of legalization is not only to align the cells overlap-free to the rows, but also to preserve the solution of global placement, i.e., the displacement of cells needs to be minimized. Furthermore, modern chip designs often consist of many preplaced blocks, such as analog blocks, memory blocks, and/or I/O buffers, which are fi ed in the chip and cannot overlap with other blocks. These preplaced blocks, i.e., obstacles, impose more constraints on the legalization problem. A legalization algorithm without considering obstacles may significantl induce increasing cell displacement or inferior solutions. In this paper, we present OAL, an obstacle-aware legalization with displacement minimization. The main contributions of our work are: (1) an exact linear wirelength model to minimize total displacement precisely; (2) an obstacleaware cell insertion technique to handle the relative order problem for advanced displacement minimization. Compared with the state-of-a-art Tetris [7] and Abacus [17] algorithms, experimental results show that our legalizer obtains very high-quality results on legalized NTUplace3 [5] global placements on ISPD 2005 and 2006 placement contest benchmarks and 5 industrial benchmarks. ©2009 IEEE.