A Provably High-Probability White-Space Satisfaction Algorithm With Good Performance for Standard-Cell Detailed Placement

作者：Ren Huan^*; Dutt Shantanu

来源：IEEE Transactions on Very Large Scale Integration Systems, 2011, 19(7): 1291-1304.

DOI：10.1109/TVLSI.2010.2047876

• Discretized min-cost network flow
• full placement
• incremental placement
• probabilistic analysis
• timing and wirelength optimization
• white space constraint satisfaction

In this paper, we propose an effective white-space (i.e., row length) constraint satisfaction technique embedded in a network flow based detailed placer for standard cell designs that is suitable for both incremental as well as full detailed placement. The highlight of our method is a provable high-probability of obtaining a legal placement even under tight white space (WS) constraints. This high success probability of our method stems from our flexibility of allowing a well-controlled temporary WS constraint violation in the detailed placement process. The flexibility also helps improve the solution quality of the detailed placer, measured by the deterioration of the optimization metric from the global placement solution. We tested our WS constraint-satisfaction method controlled temporary violations (CTV) on two sets of benchmarks for both incremental and full placement applications, and for timing as well as wire length (WL) optimization problems. We obtained legal solutions for all circuits in reasonable times under a 3% WS constraint. For example, for a 210 k-cell circuit td-ibm18: 1) for the timing-driven incremental placement application, we obtain the final placement in 900 secs with a 35.2% delay reduction compared to an initial WL-optimized placement done by Dragon 2.23 and 2) for the full timing-driven placement problem, we obtain the final placement in less than 2.5 h with a timing improvement of 29.8% compared to the state-of-the-art WL-driven detailed placer of NTUplace3-LE. We also tested two internal methods, one that disallows any temporary WS violation, and another which moves cells from WS violated rows to non-full rows in a heuristic manner. The first method cannot legalize all benchmarks, and CTV is 41%-86% relatively better in delay and WL metrics than the two internal methods.

• 出版日期2011-7