Incremental Layer Assignment for Timing Optimization

Derong Liu, Bei Yu, Salim Chowdhury, David Z. PanACM Trans. Design Autom. Electr. Syst 2017 · DOI

TL;DR

This paper introduces a novel framework for optimizing the timing of critical paths in integrated circuit designs by intelligently assigning network segments to different metal layers. Their approach uses a combination of integer linear programming (ILP), semidefinite programming (SDP) relaxation, and a novel self-adaptive partitioning strategy to efficiently find optimal layer assignments, leading to reduced critical path delays and improved overall circuit performance.

What Problem Does This Paper Address?

As integrated circuit technology nodes shrink, interconnect delays become a dominant factor in overall circuit timing. Global routing, a crucial step in chip design, determines how these interconnects are laid out. A key part of global routing is "layer assignment," where segments of a net are assigned to different metal layers. Different metal layers have varying properties (e.g., width, resistance, capacitance), making some layers more suitable for timing-critical nets. However, previous methods often focused on minimizing via counts or total net delays, neglecting the critical paths within each net, which can lead to unaddressed timing violations. This paper tackles the challenge of optimizing layer assignment specifically for these critical timing paths to minimize potential timing issues.

Methods

The authors propose a multi-stage approach:

  • Integer Linear Programming (ILP) Formulation: They first formulate the problem of optimizing critical path timing as an ILP. This provides a precise mathematical model but can be computationally expensive for large designs.
  • Self-Adaptive Quadruple Partitioning: To address the scalability issues of ILP, they introduce a novel partitioning technique. This method divides the design into smaller, manageable regions, ensuring each region has a similar number of critical segments. This allows for parallel processing and reduces the overall problem size.
  • Semidefinite Programming (SDP) Relaxation: The ILP formulation is then relaxed into an SDP problem. SDP is a more general optimization technique that can handle a wider range of problems and often provides a good approximation to the ILP solution, significantly speeding up computation.
  • Sequential Mapping Algorithm: Since SDP provides continuous solutions, a sequential mapping algorithm is used to convert these continuous assignments into discrete integer layer assignments, ensuring edge capacity constraints are met.
  • Concurrent Matching Algorithm: To further improve solution quality, a concurrent matching approach is employed. This generates multiple candidate assignments for each division and selects the best one, considering both internal via violations and external costs with neighboring divisions.
  • Post Delay Optimization: Finally, a greedy post-optimization step is applied to further reduce any remaining timing violations by intelligently reassigning segments on noncritical paths to free up resources for critical nets.

Datasets

The authors evaluated their framework on the ISPD 2008 global routing benchmarks. These benchmarks are standard in the field for testing routing algorithms.

Key Insights and Ideas

  • Focus on Critical Paths: The paper highlights the importance of directly optimizing critical paths within nets, rather than just total net delays, for achieving better timing closure.
  • SDP as an Efficient Relaxation: Using SDP relaxation is shown to be a powerful technique for speeding up the layer assignment process while maintaining solution quality comparable to ILP.
  • Self-Adaptive Partitioning for Scalability: The proposed self-adaptive partitioning is crucial for making the SDP approach scalable to large industrial designs by balancing workload across parallel threads.
  • Post-Optimization for Fine-Tuning: The greedy post-delay optimization step effectively addresses remaining timing violations by strategically reallocating resources, demonstrating the benefit of a multi-stage optimization approach.

Key Results

  • Timing Improvement: The proposed SDP-based method reduced average critical path timing by 11% and maximum critical path timing by 4% compared to TILA [Yu et al. 2015a].
  • Runtime Speedup: The SDP approach achieved significant speedups compared to the ILP formulation, with runtimes increasing proportionally to the critical ratio, indicating good scalability.
  • Delay Violation Reduction: The post-delay optimization stage successfully reduced timing violations by 28% on average.
  • Via Violations: The method showed a slight penalty of 2% in via violations compared to TILA but maintained similar via counts.

Limitations and Future Work

  • Via Violations: The paper acknowledges a slight increase in via violations, which is attributed to the focus on timing optimization.
  • Future Work: The authors plan to extend their work to consider timing paths consisting of multiple nets and cells, and to coordinate layer assignments of segments from different paths more holistically, including the impact of transition vias. They also suggest exploring the integration of the concurrent matching algorithm earlier in the flow for potentially better results.

Summary updated

BibTeX
@article{liu2017incremental,
  author = {Derong Liu and Bei Yu and Salim Chowdhury and David Z. Pan},
  title = {{Incremental Layer Assignment for Timing Optimization}},
  journal = {ACM Trans. Design Autom. Electr. Syst.},
  year = {2017},
  doi = {10.1145/3083727},
}
Figure