Delay-related secondary objectives for rectilinear Steiner minimum trees
✍ Scribed by Sven Peyer; Martin Zachariasen; David Grove Jørgensen
- Publisher
- Elsevier Science
- Year
- 2004
- Tongue
- English
- Weight
- 759 KB
- Volume
- 136
- Category
- Article
- ISSN
- 0166-218X
No coin nor oath required. For personal study only.
✦ Synopsis
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 ÿnding 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.