Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design

Abstract

In this paper, we present a very fast and accurate rectilinear Steiner minimal tree (RSMT) algorithm called FLUTE. The algorithm is an extension of the wirelength estimation approach by fast lookup table [1]. The main contribution of this paper is a new net breaking technique which is much better than the one in [1]. A scheme is also presented to allow users to control the tradeoff between accuracy and runtime.FLUTE is optimal for nets up to degree 9 and is still very accurate for nets up to degree 100. So it is particularly suitable for VLSI applications in which most nets have a degree 30 or less. We show experimentally that over 18 industrial circuits in the ISPD98 benchmark suite, FLUTE with default accuracy is more accurate than the Batched 1-Steiner heuristic and is almost as fast as a very efficient implementation of Prim's rectilinear minimum spanning tree (RMST) algorithm. By adjusting the accuracy parameter, the error can be further reduced with only a small increase in runtime (e.g., 2.7x error reduction with 2.2x runtime increase).