TY - GEN
T1 - Fast and robust quadratic placement combined with an exact linear net model
AU - Spindler, Peter
AU - Johannes, Frank M.
PY - 2006
Y1 - 2006
N2 - This paper presents a robust quadratic placement approach, which offers both high-quality placements and excellent computational efficiency. The additional force which distributes the modules on the chip in force-directed quadratic placement is separated into two forces: hold force and move force. Both of these forces are determined without any heuristics. Based on this novel systematic force implementation, we show that our iterative placement algorithm converges to an overlap-free placement. In addition, engineering change order (ECO) is efficiently supported by our placer. To handle the important trade-off between CPU time and placement quality, a deterministic quality control is presented. In addition, a new linear net model is proposed, which accurately models the half-perimeter wirelength (HPWL) in the quadratic cost function of quadratic placement. HPWL in general is a linear metric for netlength and represents an efficient and common estimation for routed wirelength. Compared with the classical clique net model, our linear net model reduces memory usage by 75%, CPU time by 23% and netlength by 8%, which is measured by the HPWL of all nets. Using the ISPD-2005 benchmark suite for comparison, our placer combined with the new linear net model has just 5.9% higher netlength but is 16× faster than A Place, which offers the best netlength in this benchmark. Compared to Capo, our placer has 9.2% lower netlength and is 5.4× faster. In the recent ISPD-2006 placement contest, in which quality is mainly determined by netlength and CPU time, our placer together with the new net model produced excellent results.
AB - This paper presents a robust quadratic placement approach, which offers both high-quality placements and excellent computational efficiency. The additional force which distributes the modules on the chip in force-directed quadratic placement is separated into two forces: hold force and move force. Both of these forces are determined without any heuristics. Based on this novel systematic force implementation, we show that our iterative placement algorithm converges to an overlap-free placement. In addition, engineering change order (ECO) is efficiently supported by our placer. To handle the important trade-off between CPU time and placement quality, a deterministic quality control is presented. In addition, a new linear net model is proposed, which accurately models the half-perimeter wirelength (HPWL) in the quadratic cost function of quadratic placement. HPWL in general is a linear metric for netlength and represents an efficient and common estimation for routed wirelength. Compared with the classical clique net model, our linear net model reduces memory usage by 75%, CPU time by 23% and netlength by 8%, which is measured by the HPWL of all nets. Using the ISPD-2005 benchmark suite for comparison, our placer combined with the new linear net model has just 5.9% higher netlength but is 16× faster than A Place, which offers the best netlength in this benchmark. Compared to Capo, our placer has 9.2% lower netlength and is 5.4× faster. In the recent ISPD-2006 placement contest, in which quality is mainly determined by netlength and CPU time, our placer together with the new net model produced excellent results.
UR - http://www.scopus.com/inward/record.url?scp=34547281987&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2006.320083
DO - 10.1109/ICCAD.2006.320083
M3 - Conference contribution
AN - SCOPUS:34547281987
SN - 1595933891
SN - 9781595933898
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 179
EP - 186
BT - Proceedings of the 2006 International Conference on Computer-Aided Design, ICCAD
T2 - 2006 International Conference on Computer-Aided Design, ICCAD
Y2 - 5 November 2006 through 9 November 2006
ER -