Cost-Distance Steiner Trees for Timing-Constrained Global Routing
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929745064624128 |
|---|---|
| author | Held, Stephan Perner, Edgar |
| author_facet | Held, Stephan Perner, Edgar |
| contents | The cost-distance Steiner tree problem seeks a Steiner tree that minimizes the total congestion cost plus the weighted sum of source-sink delays. This problem arises as a subroutine in timing-constrained global routing with a linear delay model, used before buffer insertion. Here, the congestion cost and the delay of an edge are essentially uncorrelated, unlike in most other algorithms for timing-driven Steiner trees.
We present a fast algorithm for the cost-distance Steiner tree problem. Its running time is $\mathcal{O}(t(n \log n + m))$, where $t$, $n$, and $m$ are the numbers of terminals, vertices, and edges in the global routing graph. We also prove that our algorithm guarantees an approximation factor of $\mathcal{O}(\log t)$. This matches the best-known approximation factor for this problem, but with a much faster running time.
To account for increased capacitance and delays after buffering caused by bifurcations, we incorporate a delay penalty for each bifurcation without compromising the running time or approximation factor.
In our experimental results, we show that our algorithm outperforms previous methods that first compute a Steiner topology, e.g. based on shallow-light Steiner trees or the Prim-Dijkstra algorithm, and then embed this into the global routing graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_04419 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cost-Distance Steiner Trees for Timing-Constrained Global Routing Held, Stephan Perner, Edgar Data Structures and Algorithms The cost-distance Steiner tree problem seeks a Steiner tree that minimizes the total congestion cost plus the weighted sum of source-sink delays. This problem arises as a subroutine in timing-constrained global routing with a linear delay model, used before buffer insertion. Here, the congestion cost and the delay of an edge are essentially uncorrelated, unlike in most other algorithms for timing-driven Steiner trees. We present a fast algorithm for the cost-distance Steiner tree problem. Its running time is $\mathcal{O}(t(n \log n + m))$, where $t$, $n$, and $m$ are the numbers of terminals, vertices, and edges in the global routing graph. We also prove that our algorithm guarantees an approximation factor of $\mathcal{O}(\log t)$. This matches the best-known approximation factor for this problem, but with a much faster running time. To account for increased capacitance and delays after buffering caused by bifurcations, we incorporate a delay penalty for each bifurcation without compromising the running time or approximation factor. In our experimental results, we show that our algorithm outperforms previous methods that first compute a Steiner topology, e.g. based on shallow-light Steiner trees or the Prim-Dijkstra algorithm, and then embed this into the global routing graph. |
| title | Cost-Distance Steiner Trees for Timing-Constrained Global Routing |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.04419 |