Item Details

High-Performance Routing Trees With Identified Critical Sinks

Boese, Kenneth; Kahng, Andrew; Robins, Gabriel
Boese, Kenneth
Kahng, Andrew
Robins, Gabriel
We present critical-sink routing tree (CSRT) constructions which yield high-performance routing trees by exploiting the critical-path information that may be available during timing-driven layout. Motivated by analysis of the Elmore delay formula, we propose the CS-Steiner class of heuristics and a "Global Slack Removal" algorithm; these modify traditional Steiner tree constructions to optimize signal delay at identified critical sinks. Extensive timing simulations, using industry IC and MCM technology parameters and a fast simulator based on a 2-pole distributed RCL delay approximation [29], show that this simple approach affords very significant improvements over existing "performance-driven" routing tree constructions. Next, we observe that all existing routing tree objectives (e.g., minimum-cost Steiner [16] or bounded-radius are heuristic abstractions of the linear or Elmore delay models. We therefore propose a new class of efficient Elmore routing tree (ERT) constructions, which iteratively add tree edges that are optimal in terms of Elmore delay. For the CSRT problem, this direct optimization of Elmore delay yields trees that significantly improve (by averages of up to 69%) upon minimum Steiner routings in terms of delays to identified critical sinks. Moreover, ERTs serve as generic high-performance routing trees when no critical sink is specified: for 8-sink nets in 0.81.: CMOS IC technology, we improve average sink delay by 10% and maximum delay by 13% over the minimum Steiner routing. For a typical MCM technology, the corresponding improvements are 42% and 22%. The ERT approach represents a basic advance over existing performance-driven routing tree constructions, including such recent works as [1] [4] [5]- Note: Abstract extracted from PDF file via OCR
University of Virginia, Department of Computer Science, 1992
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online