Preferred direction Steiner trees

Interconnect optimization for VLSI circuits has received wide attention. To model routing surfaces, multiple circuit layers are frequently 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 direction 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 effective, obtaining reductions in tree cost of 11% to 37% on average for random problems. Our results include a proof that the performance bound of Minimum 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.