2025-05-07

Steiner Trees Minimizing Elmore Delay

On chips, a single source signal needs to be transmitted to several destinations. For instance, consider a clock signal. It leaves a single source, and must be routed to each components such as D Latches. Determining this routing is similar to the Steiner tree problem.

Given an undirected graph and a set of vertices, the Steiner tree problem requires finding the tree of minimum weight containing all terminals. We call non-terminal vertices Steiner points. As an example, below is the minimum Steiner tree for four points with two Steiner points, $S_1$ and $S_2$.

In chip design, we are interested in the rectilinear Steiner minimum tree problem (RSMT), where we replace the Euclidean distance with taxicab distance. That is, given $n$ points in the plane, we wish to interconnect them by a shortest network consisting of vertical and horizontal line segments. In 1966, Hanan showed that the solution to RSMT can be found by restricting the grid constructed by drawing vertical and horizontal lines through each vertex, known as the Hanan grid.

However, there are often constraints on the signal delay between source and each sink. As a result, the shortest Steiner tree may not be possible. We can measure the delay using the Elmore delay model:

$$ED(s,t):=r_s{C}_s+\sum _{(v,w)\in E(Y_{[s,t]})}r\Vert v-w{\Vert }_1\left(\frac{c}{2}\Vert v-w{\Vert }_1+C_w\right)$$

where $Y_{[}s,v]$ is a path from $s$ to $v$ in a rectilinear Steiner tree $Y$ and

$$C_v:=\sum _{(x,y):v\in V(Y_{[s,x]})}c\Vert x-y{\Vert }_1+\sum _{t\in T:v\in V(Y_{[s,t]})}{c}_t.$$

Problem Formulation

Given

• a source vertex $s\in {\mathbb{R}}^2$
• a finite set of sinks $T\subset {\mathbb{R}}^2$
• a delay adder $a_t\in \mathbb{R}$ for all $t\in T$
• a source resistance $r_s>0$
• a sink capacitance $c_t>0$ for all $t\in T$
• the capacitance $c>0$ and $r>0$ for a wire per unit length

We seek a rectilinear Steiner tree $Y$ for $\{s\}\cup T$ rooted at $s$ such that

$$\underset{t\in T}{\max }(a_t+ED(s,t))$$

is minimal.

This problem is NP-hard. For $|T|\le 3$ the problem can be solved in constant time. However, it has been demonstrated that in some instances the optimal solutions are not part of the Hanan grid.

Extensions to Problem

• A chip likely has blockages that need to be routed around. The above problem formulation assumes there is not objects in the way of the optimal solution. In most cases, the blockages are small and can be neglected in the solution.
• While the above problem ensures that signals do not arrive too late, some signals (such as a clock) must not arrive too early as well. We can handle this by modifying our objective function to combine latency (maximum delay) and skew (maximum difference of delays):

$$(1+\alpha )\underset{t\in T}{\max }(a_t+ED(s,t))-\underset{t\in T}{\min }(a_t+ED(s,t)).$$

Relevant Publications

A High Efficient and Scalable Obstacle-Avoiding VLSI Global Routing Flow

Introduces a scalable and fast obstacle-based rectilinear Steiner minimal tree algorithm.

Link: https://arxiv.org/abs/2503.07268

The Rectilinear Steiner Forest Arboresceance problem

Provides simple exact exponential time algorithm for a class of RSMT.

Link: https://arxiv.org/abs/2210.04576

The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers

Original paper introducing Elmore delay model.

Link: https://pubs.aip.org/aip/jap/article-abstract/19/1/55/159107/The-Transient-Response-of-Damped-Linear-Networks?redirectedFrom=fulltext