A wire-length minimization algorithm for single-layer layouts

The authors consider a Steiner tree S interconnecting a set N of terminals. The minimizing length of S can be shown to be equivalent to the traditional (NP-hard) Steiner tree problem. An exact polynomial-time algorithm for minimizing the length of S when operations on S are limited is presented. These operations are called topology preserving transformations (TPTs). Based on the notion of TPT, an exact algorithm for minimizing the total length of a single-layer layout involving a set of multi-terminal nets and a collection of obstacles is proposed. The algorithm has been used to find a minimum length single-layer layout. The algorithm was also applied to find a Steiner tree interconnecting a net N of terminals. The idea is to find a minimum spanning tree T of N. Then, generate K Steiner trees by randomly flipping edges of T to both its upper- and lower-L-shaped configurations. Then, a topology preserving transformation is applied to each Steiner tree. The best of them is selected as the final Steiner tree. On the average, 9.4% improvement over the MST length has been reported.<>