2005 · 99 citations · 14 references
EngineeringComputer EngineeringElectrical EngineeringAlgorithmsMicroelectronicsVlsi DesignAlgorithm AnalysisVery-large-scale Integration LayoutAccuracyError ReductionMinimum Spanning Tree AlgorithmsSteiner Tree ProblemVlsi Implementation
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).
14
The ISPD98 circuit benchmark suite
Charles J. Alpert · 1998 · 344 citations
Jiří Soukup · Proceedings of the IEEE · 1981 · 211 citations
Engineering, Computer Engineering, Electrical Engineering +16