Preferred direction Steiner trees

Interconnect optimization for VLSI circuits has received wide at-tention. To model routing surfaces, multiple circuit layers are fre-quently abstracted as a single rectilinear plane, ignoring via costs, layer dependent routing costs, and congestion impact for routing in a particular direction. In this paper, we consider preferred di-rection multi-layer routing, which more closely models practical applications. We adapt a well known rectilinear planar Steiner tree heuristic, resulting in a new method to construct low cost Steiner trees under a realistic model. Our implementation is fast and effec-tive, obtaining reductions in tree cost of 11 % to 37 % on average for random problems. Our results include a proof that the performance bound of Mini-mum Spanning Tree cost to Steiner Minimal Tree cost under this model is 2:1 (in contrast to 1.5:1 for planar problems). We adapt the Hanan grid to this model, and show that a Steiner tree which would be optimal under a planar formulation is suboptimal for the multi-layer preferred direction model. 1