An efficient multilevel placement technique using hierarchical partitioning

Ratio cut hierarchical partitioning, which enables efficient multilevel simulated annealing, is applied to the row placement problem for large circuits. An overlapping moving window scheme is used to compensate for the effect of partitioning on the placement quality. Through the use of hierarchical partitioning, the asymptotic run time complexity of this algorithm grows linearly as the function of the circuit size. The system is called placement by ratio cut partitioning (PRC). The results from several benchmark tests are presented demonstrating PRC to be 2.49% on average better than TimberWolfSC Ver5.6. Furthermore, the run time for PRC is 18.3% on average less than that required for TimberWolfSC Ver5.6 for large test cases with more than 2000 cells. For a 100-K sea of gates test case, a 7.09% reduction in total wire length over TimberWolfSC Ver5.6 and a 51.7% saving in CPU time were achieved