Flexibility in Rectilinear Steiner Minimal Tree

The flexibility of RSMT strongly affects the distortion ability of a structure of RSMT, becoming one of the key factors affecting the convergence of integrated circuits routing.The flexibility of RSMT is studied in this paper from three aspects, including the shape of a tree edge, inherent distortion of a structure of RSMT, and topological transformation, and a new model reflecting the structural distortion ability of RSMT is proposed.A congestion-driven flexibility exploiting algorithm is proposed to solve the flexibility "bottleneck" problem.Firstly, the flexibility of a tree edge is defined according with the shortest-length routing possibility.Secondly, the flexibility of RSMT is defined considering the combination of all tree edges' flexibility in a structure of RSMT and topological transformation.Experiments show that congestion-driven flexibility exploiting algorithm can generate a routing tree with less congestion using the model.Also, the routing tree generated by the algorithm is applied into Fast Route 4.1, resulting a reduction of 14% in the runtime of global routing.