NEAR-OPTIMAL CRITICAL SINK ROUTING TREE CONSTRUCTIONS

We present critical-sink routing tree (CSRT) constructions which explo it available critical-path information to yield high-performance routi ng trees, Our CS-Steiner and ''global slack removal'' algorithms toget her modify traditional Steiner tree constructions to optimize signal d elay at identified critical sinks, We further propose an iterative Elm ore routing tree (ERT) construction which optimizes Elmore delay direc tly, as opposed to heuristically abstracting linear or Elmore delay as in previous approaches. Extensive timing simulations on industry IC a nd 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, ERT's also s erve as generic high-performance routing trees when no critical sink i s specified: for 8-sink nets in standard IC (MCM) technology, we impro ve average sink delay by 19% (62%) and maximum sink delay by 22% (52%) over the minimum Steiner routing, These approaches provide simple, ba sic advances over existing performance-driven routing tree constructio ns, Our results are complemented by a detailed analysis of the accurac y and fidelity of the Elmore delay approximation; we also exactly asse ss the suboptimality of our heuristic tree constructions, In achieving the latter result, we develop a new characterization of Elmore-optima l routing trees, as well as a decomposition theorem for optimal Steine r trees, which are of independent interest.