Refined single trunk tree

Abstract

We devised an efficient and accurate estimation of the rectilinear Steiner minimal tree (SMT), which is an essential building block for on-line and posteriori interconnect prediction. We proposed a new rectilinear Steiner tree generator, Refined Single Trunk Tree (RST-T). Compared with traditional minimal spanning tree based Steiner tree heuristics, RST-T has several advantages. 1. The algorithm runs very fast. Experiments show that RST-T algorithm runs 50 times faster than Prim's minimum spanning tree algorithm for 10-pin nets. 2. The RST-T provides excellent wire length estimation of the optimal solutions. For the nets of no more than 10 pins, the average wire length of RST-T is within 6 percent of the optimal solutions. Actually, for the nets with five or less pins, the wire length of RST-T is optimal. 3. The topology of RST-T remains stable when pin locations deviate. Experiments show that the topologies of routing trees produced by the proposed algorithm is much more stable than the minimum spanning tree and iterative 1-Steiner heuristics.