High-Performance Routing Trees With Identified Critical Sinks

Authors:Boese, Kenneth, Department of Computer ScienceUniversity of Virginia Kahng, Andrew, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia

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

All rights reserved (no additional license for public reuse)
Source Citation:

Boese, Kenneth, Andrew Kahng, and Gabriel Robins. "High-Performance Routing Trees With Identified Critical Sinks." University of Virginia Dept. of Computer Science Tech Report (1992).

University of Virginia, Department of Computer Science
Published Date: