Timing-driven Steiner trees are (practically) free

Abstract

Traditionally, rectilinear Steiner minimum trees (RSMT) are widely used for routing estimation in design optimizations like floorplanning and physical synthesis. Since it optimizes wirelength, an RSMT may take a "non-direct" route to a sink, which may give the designer an unnecessarily pessimistic view of the delay to the sink.Previous works have addressed this issue through performance-driven constructions, minimum Steiner arborescence, and critical sink based Steiner constructions. Physical synthesis and routing flows have been reticent to adapt universal timing-driven Steiner constructions out of fear that they are too expensive (in terms of routing resource and capacitance). This paper studies several different performance-driven Steiner tree constructions in order to show which ones have superior performance.A key result is that they add at most 2%-4% extra capacitance, and are thus a promising avenue for today's increasingly aggressive performance-driven P&R flows.We demonstrate using a production P&R flow that timing-driven Steiner topologies can be easily embedded into an incremental routing subflow to obtain significantly improved timing (3.6% and 5.1% improvements in cycle time for two industry testcases) at practically no cost of wirelength or routability. Copyright 2006 ACM.