TY - GEN
T1 - Abacus
T2 - 2008 ACM International Symposium on Physical Design, ISPD 2008
AU - Spindler, Peter
AU - Schlichtmann, Ulf
AU - Johannes, Frank M.
PY - 2008
Y1 - 2008
N2 - Standard cell circuits consist of millions of standard cells, which have to be aligned overlap-free to the rows of the chip. Placement of these circuits is done in consecutive steps. First, a global placement is obtained by roughly spreading the cells on the chip, while considering all relevant objectives like wirelength, and routability. After that, the global placement is legalized, i.e., the cell overlap is removed, and the cells are aligned to the rows. To preserve the result of global placement, cells should be moved as little as possible during legalization. This paper presents "Abacus", which is a fast approach to legalize standard cell circuits with minimal movement. The approach is based on sorting the cells according to their position first, and legalizing the cells one at a time then. Legalizing one cell is done by moving the cell from row to row until the optimal place with the lowest movement is found. Whenever a cell is moved to a row, the cells already aligned to the row are placed by dynamic programming to minimize their total movement. Therefore, our approach Abacus moves already legalized cells during legalization. In contrast to this, Tetris [1], which uses a similar legalization technique, does not move already legalized cells. Consequently, the average movement is about 30% lower in Abacus than in Tetris. On the other hand, the CPU time of the whole placement process is increased by only 7% with our legalization approach. Applying Abacus to routability-driven placement results in 1% improvement in routed wirelength.
AB - Standard cell circuits consist of millions of standard cells, which have to be aligned overlap-free to the rows of the chip. Placement of these circuits is done in consecutive steps. First, a global placement is obtained by roughly spreading the cells on the chip, while considering all relevant objectives like wirelength, and routability. After that, the global placement is legalized, i.e., the cell overlap is removed, and the cells are aligned to the rows. To preserve the result of global placement, cells should be moved as little as possible during legalization. This paper presents "Abacus", which is a fast approach to legalize standard cell circuits with minimal movement. The approach is based on sorting the cells according to their position first, and legalizing the cells one at a time then. Legalizing one cell is done by moving the cell from row to row until the optimal place with the lowest movement is found. Whenever a cell is moved to a row, the cells already aligned to the row are placed by dynamic programming to minimize their total movement. Therefore, our approach Abacus moves already legalized cells during legalization. In contrast to this, Tetris [1], which uses a similar legalization technique, does not move already legalized cells. Consequently, the average movement is about 30% lower in Abacus than in Tetris. On the other hand, the CPU time of the whole placement process is increased by only 7% with our legalization approach. Applying Abacus to routability-driven placement results in 1% improvement in routed wirelength.
KW - Dynamic programming
KW - Legalization
KW - Minimal movement
KW - Standard cell circuits
UR - http://www.scopus.com/inward/record.url?scp=43349095254&partnerID=8YFLogxK
U2 - 10.1145/1353629.1353640
DO - 10.1145/1353629.1353640
M3 - Conference contribution
AN - SCOPUS:43349095254
SN - 9781605580487
T3 - Proceedings of the International Symposium on Physical Design
SP - 47
EP - 53
BT - ISPD'08 - Proceedings of the 2008 ACM International Symposium on Physical Design
Y2 - 13 April 2008 through 16 April 2008
ER -