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 routabillity. We introduce I the notion of flexibility, a geometric property associated with Steiner trees; We show that the flexibility contribution of this of a Steiner tree is related to, its routability. The main 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 I throughout the region where those nets are routed.