TY - JOUR

T1 - Delay-related secondary objective for rectilinear Steiner trees

AU - Peyer, Sven

AU - Zachariasen, Martin

AU - Jørgensen, David Grove

PY - 2004

Y1 - 2004

N2 - The rectilinear Steiner tree problem in the plane is to construct a minimum-length tree interconnecting a set of points (called terminals) consisting of horizontal and vertical line segments only. Rectilinear Steiner minimum trees (RSMTs) can today be computed quickly for realistic instances occurring in VLSI design. However, interconnect signal delays are becoming increasingly important in modern chip designs. Therefore, the length of paths or direct delay measures should be taken into account when constructing rectilinear Steiner trees. We consider the problem of finding an RSMT that — as a secondary objective — minimizes a signal delay related objective. Given a source (one of the terminals) we give some structural properties of RSMTs for which the weighted sum of path lengths from the source to the other terminals is minimized. Also, we present exact and heuristic algorithms for constructing RSMTs with weighted sum of path lengths or Elmore delays secondary objectives. Computational results for industrial designs are presented.

AB - The rectilinear Steiner tree problem in the plane is to construct a minimum-length tree interconnecting a set of points (called terminals) consisting of horizontal and vertical line segments only. Rectilinear Steiner minimum trees (RSMTs) can today be computed quickly for realistic instances occurring in VLSI design. However, interconnect signal delays are becoming increasingly important in modern chip designs. Therefore, the length of paths or direct delay measures should be taken into account when constructing rectilinear Steiner trees. We consider the problem of finding an RSMT that — as a secondary objective — minimizes a signal delay related objective. Given a source (one of the terminals) we give some structural properties of RSMTs for which the weighted sum of path lengths from the source to the other terminals is minimized. Also, we present exact and heuristic algorithms for constructing RSMTs with weighted sum of path lengths or Elmore delays secondary objectives. Computational results for industrial designs are presented.

KW - Rectilinear Steiner trees

KW - VLSI design

KW - Secondary objectives

M3 - Journal article

SN - 0166-218X

SP - 271

EP - 298

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -