TL;DR
This paper introduces RippleDP, a novel detailed placement algorithm that optimizes wire-length while strictly adhering to cell density targets and limiting cell displacement from their global placement positions. By introducing a "Legalized Cell Move" framework and a two-stage approach (Global Move and Local Move), RippleDP significantly improves upon existing methods, achieving better wire-length reduction without compromising global placement quality.
What Problem Does This Paper Address?
Modern integrated circuit (IC) design involves a multi-stage placement process: global placement, legalization, and detailed placement. While global placement aims to minimize overall objectives like wire-length, legalization and detailed placement are crucial for resolving cell overlaps and further optimizing the design. A key challenge in detailed placement is that aggressive local optimizations can inadvertently disrupt the global placement solution, potentially impacting other critical metrics like timing and routability. Furthermore, maintaining specific cell density across the chip is becoming increasingly important for performance and power efficiency. Existing detailed placers often struggle to balance these competing objectives, particularly when trying to minimize wire-length while respecting constraints on how much cells can move from their initial positions and maintaining target density. This paper addresses this gap by proposing a detailed placement algorithm that explicitly incorporates both cell displacement constraints and target cell density as primary objectives.
Methods
The proposed algorithm, RippleDP, employs a two-stage approach:
- Global Move: This stage partitions the placement region into rectangular bins. For each cell, it identifies candidate bins that minimize a "scaled wire-length" (sHPWL) objective, which combines wire-length with a penalty for exceeding target cell density. Crucially, this move is constrained by the maximum allowable displacement from the cell's original global placement position. A novel "Legalized Cell Move" framework is introduced to ensure that intermediate solutions remain legal (no overlaps) throughout the process, preventing the need for a separate, potentially disruptive, legalization step.
- Local Move: This stage further refines the placement by performing local adjustments. It consists of three sub-steps:
- Vertical Move: Cells are moved vertically to nearby rows to reduce sHPWL, while still respecting displacement constraints.
- Local Reordering: The order of a few consecutive cells within a row is adjusted to minimize sHPWL.
- Compaction: Cells are moved to their optimal positions within their row, maintaining their order, while strictly adhering to displacement and density constraints. This stage extends existing compaction algorithms to handle these new constraints.
The "Legalized Cell Move" is a core innovation, ensuring that any cell movement is checked for its "legalizability" and that the legalization impact (sum of cell displacements) is kept within affordable limits. This prevents large, disruptive shifts that could violate global placement objectives.
Datasets
The experiments were conducted using large-scale benchmarks from the ICCAD 2013 detailed placement contest. These benchmarks include detailed information about cells, nets, target densities, and initial global placement solutions.
Key Insights and Ideas
- Legalized Cell Move is Crucial: The paper highlights that a separate legalization step after detailed placement can be detrimental. By integrating legalization directly into cell moves, the algorithm maintains solution quality and avoids disruptions.
- Displacement Constraint is Key for Preserving Global Placement: Explicitly limiting cell displacement is essential for ensuring that detailed placement optimizations don't undo the work of global placement, especially concerning objectives like timing and routability.
- Scaled Wire-Length (sHPWL) Effectively Balances Objectives: The sHPWL metric, which penalizes density overflow, provides a unified objective that guides the placer towards solutions that are both wire-length efficient and density-aware.
- Two-Stage Approach for Efficiency and Quality: The separation into Global Move (bin-level allocation) and Local Move (fine-tuning) allows for efficient exploration of the solution space while progressively refining the placement.
Key Results
RippleDP demonstrated significant improvements over existing methods:
- Wire-Length Reduction: The algorithm achieved an average wire-length reduction of 6.27% (HPWL) and 13.38% (sHPWL) under a tight maximum displacement constraint, and 9.49% (HPWL) and 16.41% (sHPWL) under a relaxed constraint.
- Density Improvement: The algorithm effectively reduced placement density overflow to nearly zero.
- Constraint Satisfaction: The displacement constraint was strictly satisfied, a notable achievement compared to modified versions of existing placers that struggled to meet these requirements.
- Competitive Runtime: The algorithm achieved these improvements with reasonable runtimes, comparable to or better than existing detailed placers.
Limitations and Future Work
- Violation of Displacement Constraint in Modified FastPlace-DP: The paper notes that even a modified FastPlace-DP struggled to strictly satisfy displacement constraints, indicating the difficulty of integrating such constraints into existing frameworks.
- Future Work: The authors suggest that their approach can be extended to incorporate other objectives like routability and timing, further enhancing its applicability to modern complex placement problems. The "Legalized Cell Move" framework is presented as a flexible foundation for such extensions.
Summary updated