Fidelity and Near-Optimality of Elmore-Based Routing Constructions

We address the efficient construction of interconnection trees with nearoptimal delay properties. Our study begins from first principles: we consider the accuracy and fidelity of easily-computed delay models (specifically, Elmore delay) with respect to the delay values computed from detailed simulation of underlying physical phenomena (e.g., SPICE simulator output). Our studies show that minimization of Elmore delay is a high-accuracy, high-ffdelity interconnect objective within a range of IC interconnect technologies. We propose an efficient law delay tree (LDT) heuristic which uses a greedy construction to minimize maximum sink delay for a given (monotone) delay function. For comparison purposes, we also generate optimal routing trees (ORTs) under Elmore delay using exhaustive search with branch-and-bound pruning. Experimental results show that the LDT heuristic approximates ORTs very accurately: for nets with up to seven pins, LDT trees have on average a maximum sink delay within 2% of optimum. Moreover, compared with traditional minimum spanning tree constructions, the LDT achieves average reductions in delay of up to 35% depending on the net size and technology parameters.
Note: Abstract extracted from PDF file via OCR

Boese, K, A Kahng, B McCoy, and G Robins. "Fidelity and Near-Optimality of Elmore-Based Routing Constructions." University of Virginia Dept. of Computer Science Tech Report (1993).