Creating and exploiting flexibility in rectilinear Steiner trees

The global routing problem decomposes the large, complex routing problem into a set of more manageable subproblems. The high correlation between the output of the global router and the detailed router enables the designer to efficiently use the global route to refine the design quickly before running the full detailed route. Hence, routability of the global routing solution is the key factor. The routability of the circuit depends on the congestion of the routing. In this paper, we study Steiner trees in terms of routability. We introduce the notion of flexibility, a geometric property associated with Steiner trees. We show that the flexibility of a Steiner tree is related to its routability. The main contribution of this paper is an algorithm which takes a stable Steiner tree as an input and maps it to a more flexible Steiner tree. Any existing Steiner tree algorithm can be used for the initial construction of the Steiner tree. Experiments with a global router on a subset of nets show that routing congestion is improved by approximately 20% locally throughout the region where those nets are routed.