Title :
Relaxed partitioning balance constraints in top-down placement
Author :
Caldwell, Andrew E. ; Kahng, Andrew B. ; Markov, Igor L.
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
Abstract :
Recent work of Simon and Teng (1997) observes that the recursive bisection (i.e., bipartitioning with equal partition target areas, and minimum possible allowed deviation from targets) heuristic for k-way minimum-cut graph partitioning can have unbounded error, but that relaxing the balance constraints in each call to the bipartitioning engine can result in k-way net cuts within a small (O(logk)) factor of optimal. Motivated by this result, we experimentally determine whether relaxing the traditional exact bisection constraint in a top-down partitioning-based placement tool can improve the resulting cutsizes, and hence total wirelength, of the placement solution. We find that this simple change reduces total wirelength by up to several percent, with no change in placement uniformity and under 10% runtime penalty. Finally, we observe that the stability (predictability) of the placement process appears unimpaired by this modification: both wirelength stability, and stability of Rent parameter based wirelength and wireability estimates, appear to be preserved
Keywords :
VLSI; circuit layout CAD; integrated circuit layout; Rent parameter based wireability estimate; Rent parameter based wirelength estimate; cutsizes; k-way minimum-cut graph partitioning; partitioning balance constraints relaxation; partitioning-based placement tool; placement process stability; recursive bisection heuristic; top-down placement; wirelength stability; Computer errors; Computer science; Constraint theory; Engines; Packaging; Runtime; Stability; Timing; Very large scale integration; Wiring;
Conference_Titel :
ASIC Conference 1998. Proceedings. Eleventh Annual IEEE International
Conference_Location :
Rochester, NY
Print_ISBN :
0-7803-4980-6
DOI :
10.1109/ASIC.1998.722911