Estimation of wirelength reduction for lambda-geometry vs. manhattan placement and routing

Hongyu Chen, Chung-Kuan Cheng, Andrew B. Kahng, Ion I. Mandoiu, Qinke WangSLIP 2003 · DOI

TL;DR

This paper tackles the challenge of accurately estimating wirelength reduction when moving from traditional Manhattan routing to more flexible lambda-geometry routing in chip design. By considering how placement algorithms influence pin locations, the authors provide more realistic wirelength reduction estimates than previous studies, suggesting that the benefits of lambda-geometry routing are more nuanced than initially thought.

What Problem Does This Paper Address?

Modern integrated circuits (ICs) rely heavily on Manhattan routing, where wires can only run horizontally or vertically. While this simplifies routing, it often leads to longer wire lengths than theoretically possible, impacting performance, power consumption, and timing. Lambda-geometry routing offers a solution by allowing wires to run at specific angles (defined by $\lambda$), potentially reducing wire lengths. However, accurately quantifying these benefits is crucial for adoption. Previous studies often assumed random net placement, which doesn't reflect real-world scenarios where placement algorithms optimize for wirelength. This paper addresses this gap by providing more accurate wirelength reduction estimates that account for the impact of wirelength-driven placement on net pin locations, and by exploring the combined effect of lambda-geometry placement and routing.

Methods

The authors employ a two-pronged approach:

  1. Improved Analytical Estimation for Manhattan Placements: They refine existing analytical models to estimate wirelength reduction for lambda-geometry routing when nets are placed using Manhattan-aware algorithms. This involves considering specific net topologies (2, 3, and 4 pins) and how their pin locations are influenced by wirelength minimization in a Manhattan grid. They derive expected wirelengths by integrating over possible pin distributions, taking into account bounding box aspect ratios.
  2. Simulated Annealing for Lambda-Geometry Placement and Routing: To estimate the combined benefits of lambda-geometry placement and routing, they build a simplified placer using simulated annealing. This placer is driven by lambda-geometry wirelength estimation (using the Geosteiner algorithm) to optimize both cell placement and routing simultaneously. They then compare the total wirelength achieved by this lambda-geometry-aware approach against traditional Manhattan placement and routing.

Datasets

The paper uses netlists extracted from MCNC instances for evaluation of the simulated annealing placer. Specific instances mentioned include C2, BALU, and C7.

Key Insights and Ideas

  • Placement Matters: The most significant insight is that wirelength reduction estimates for lambda-geometry routing are considerably smaller when accounting for wirelength-driven Manhattan placement compared to assuming random net placement. This highlights that the benefits of new routing architectures are heavily dependent on corresponding placement strategies.
  • The "Virtuous Cycle": The paper introduces and analyzes the "virtuous cycle" effect. Reduced wirelength leads to smaller routing areas, which in turn can further reduce wirelength by bringing pins closer together. This effect can significantly amplify the benefits of lambda-geometry routing.
  • Hexagonal Cells for $\lambda=3$: For $\lambda=3$ routing, square cells are found to be suboptimal. The paper suggests that hexagonal cells, when used with a $\lambda=3$ placement strategy, lead to substantial wirelength improvements.

Key Results

  • Reduced Estimates: For nets with 2, 3, and 4 pins originating from Manhattan-driven placements, the expected wirelength reduction for lambda-geometry routing is smaller than previously reported for randomly placed nets. For example, Table 3 shows average wirelength reductions for k=2 nets from Manhattan placement ranging from 5.45% ($\lambda=3$) to 10.57% ($\lambda=4$), compared to higher values for random nets.
  • Combined Placement and Routing Benefits: The simulated annealing placer demonstrates significant wirelength improvements with lambda-geometry placement and routing. Table 4 shows average wirelength improvements for various instances ranging from 3.43% ($\lambda=2$ on C2) to 13.03% ($\lambda=4$ on PRIMARY1).
  • "Virtuous Cycle" Impact: The analysis suggests that the "virtuous cycle" effect can account for a substantial portion of the observed wirelength reduction, with estimates showing potential routing area reductions of 23-36% for $\lambda=3$ to $\lambda=\infty$ compared to Manhattan.

Limitations and Future Work

  • Interaction Between Nets: The authors acknowledge that their current models do not fully capture the complex interactions between multiple nets, which is crucial for accurate overall wirelength estimation in real designs.
  • Detailed Site Maps and Routing: The analysis of the "virtuous cycle" is based on simplified assumptions. Detailed site maps and actual routing results are needed to determine the true impact.
  • Efficient Optimizers and Estimators: Finding efficient optimizers and estimators for lambda-geometry wirelength remains an open research problem.
  • Future Work: The paper suggests exploring the interaction between nets and the detailed impact of the "virtuous cycle" in more complex scenarios. Developing better optimization and estimation tools for lambda-geometry wirelength is also highlighted as a future direction.

Summary updated

BibTeX
@inproceedings{chen2003estimation,
  author = {Hongyu Chen and Chung-Kuan Cheng and Andrew B. Kahng and Ion I. Mandoiu and Qinke Wang},
  title = {{Estimation of wirelength reduction for lambda-geometry vs. manhattan placement and routing}},
  booktitle = {SLIP},
  year = {2003},
  doi = {10.1145/639929.639944},
}
Figure