Near-Optimal Critical Sink Routing Tree Constructions

Report
Authors:Boese, K, Department of Computer ScienceUniversity of Virginia Kahng, A, Department of Computer ScienceUniversity of Virginia McCoy, B, Department of Computer ScienceUniversity of Virginia Robins, G, Department of Computer ScienceUniversity of Virginia
Abstract:

We present critical-sink routing tree (CSRT) constructions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and "Global Slack Removal" algorithms together modify traditional Steiner tree constructions to optimize signal delay at identified critical sinks. We further propose an iterative Elmore routing tree (ERT) construction which optimizes Elmore delay directly, as opposed to heuristically abstracting linear or Elmore delay as in previous approaches. Extensive timing simulations on industry IC and MCM interconnect parameters show that our methods yield trees that significantly improve (by averages of up to 67%) over minimum Steiner routings in terms of delays to identified critical sinks. ERTs also serve as generic high-performance routing trees when no critical sink is specified: for 8-sink nets in standard IC (MCM) technology, we improve average sink delay by 19% (62%) and maximum sink delay by 22% (52%) over the minimum Steiner routing. These approaches provide simple, basic advances over existing performance-driven routing tree constructions, including the recent works of [1, 9]. Our results are complemented by a detailed analysis of the accuracy and fidelity of the Elmore delay approximation; we also exactly assess the suboptimality of our heuristic tree constructions. In achieving the latter result, we develop a new characterization of Elmore-optimal routing trees, as well as a decomposition theorem for optimal Steiner trees, which are of independent interest.
Note: Abstract extracted from PDF file via OCR

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

Boese, K, A Kahng, B McCoy, and G Robins. "Near-Optimal Critical Sink Routing Tree Constructions." University of Virginia Dept. of Computer Science Tech Report (1993).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1993