FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design

In this paper, we present a very fast and accurate rectilinear Steiner minimal tree (RSMT) algorithm called fast lookup table estimation (FLUTE). FLUTE is based on a precomputed lookup table to make RSMT construction very fast and very accurate for low-degreeThe degree of a net is the number of pins...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2008-01, Vol.27 (1), p.70-83
Main Authors: Chu, C., Yiu-Chung Wong
Format: Article
Language:English
Subjects:
Accuracy
Algorithm design and analysis
Algorithms
Delay estimation
Design engineering
Integrated circuit interconnections
Integrated circuits
Interconnect optimization
Iterative algorithms
Lookup tables
rectilinear Steiner minimal tree (RSMT) algorithm
Routing
Runtime
Space exploration
Steiner trees
Studies
Table lookup
Tables (data)
Trees
Very large scale integration
wirelength estimation
wirelength minimization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a very fast and accurate rectilinear Steiner minimal tree (RSMT) algorithm called fast lookup table estimation (FLUTE). FLUTE is based on a precomputed lookup table to make RSMT construction very fast and very accurate for low-degreeThe degree of a net is the number of pins in the net. nets. For high-degree nets, a net-breaking technique is proposed to reduce the net size until the table can be used. A scheme is also presented to allow users to control the tradeoff between accuracy and runtime. FLUTE is optimal for low-degree nets (up to degree 9 in our current implementation) and is still very accurate for nets up to degree 100. Therefore, it is particularly suitable for very large scale integration applications in which most nets have a degree of 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 algorithm.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2007.907068