FLUTE: Fast Lookup Table Based Technique for RSMT Construction and
Work in progress.
Last updated: Feb. 28, 2011
FLUTE is a very fast and accurate technique for rectilinear Steiner
minimal tree (RSMT) construction. There is a user-defined parameter to
control the tradeoff between accuracy and runtime. FLUTE is optimal and
extremely fast for nets up to degree 9. For higher degree nets, it is
still very fast and accurate. Latest implementation can generate accurate
RSMT for nets with millions of pins in minutes. As it handles low degree
nets particularly well, it is most 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 (0.075% vs. 0.086%)
and is almost as fast as
a very efficient
implementation of Prim's rectilinear minimum spanning tree (RMST)
algorithm (7% slower).
By adjusting the accuracy parameter, the error can be further reduced
with only a small increase in runtime (e.g., 3.1x error reduction
with 2.0x runtime increase).
II. Experimental Results
We perform all experiments in a 3.4-GHz Intel Pentium 4 machine. We compare
the following six algorithms on nets from industrial circuits:
an efficient O(n2) implementation of Prim’s algorithm
- RST-T: Refined Single Trunk Tree [SLIP-02, p.85-89]
- SPAN: the spanning graph based RSMT algorithm [ISPD-03, p.152-157]
batched greedy triple contraction algorithm [ASPDAC-03, p.827-833]
the near-optimal Batched Iterated 1-Steiner heuristic [TCAD-94,
- FLUTE with default accuracy A = 3
The exact RSMT software GeoSteiner
3.1 is used to generate the optimal solutions. Source codes of SPAN and RST-T
are obtained from the authors. 18 IBM circuits based on
benchmark suite are used. There are totally 1.57 million nets in the 18
circuits. The placement is generated by
The results are summarized in the following four tables.
Percentage error in wirelength.
Runtime comparison. The overall runtimes in the last
row are normalized with respect to FLUTE runtime.
Remark: The results above are based on FLUTE version 2.5. For nets
with up to tens of pins (i.e., industrial circuits), the latest version
3.1 obtains very similar results to version 2.5 (a bit more accurate but
a bit slower). For nets with more than 100 pins, version 3.1 can achieve
much better accuracy than version 2.5 in a similar runtime. For example,
for a 1-million-pin net, the wirelength of the RSMT by FLUTE 3.1 is
10.96% shorter than RMST. The runtime is only 531 seconds on a 1.8-GHz Pentium
4 laptop with 256 MB memory. In comparison, BGA can only get 10.72%
improvement in twice longer runtime.
Breakdown of the wirelength estimation
according to degree for all 1.57 million nets.
Wirelength error and runtime of FLUTE with
accuracy A for all 1.57 million nets. The row in bold is the default.
III. Source Code
The latest version FLUTE 3.1 is based on the ideas from the TCAD-2008
paper for low-degree nets and the VLSIDAT-2008 paper for high-degree
nets. As a result, for nets with up to tens of pins, it performs
similarly to version 2.5 (which is based on the TCAD-2008 paper). For
high-degree nets, its scalability is significantly improved.
This package flute-3.1.tgz
contains the following files:
flute.c -- The rectilinear Steiner minimal tree and wirelength
estimation algorithm described in the ICCAD 04 and ISPD 05
papers with some improvements described in TCAD 07 paper.
flute.h -- The interface to use flute.
flute_mst.c -- The net breaking and merging techniques described in the
VLSIDAT 08 paper.
dist.[ch], dl.[ch], err.[ch], heap.[ch], mst2.[ch], neighbors.[ch],
global.h -- Utility functions used by flute_mst.c.
POWV9.dat -- The lookup-table of optimal POWVs up to degree 9.
POST9.dat -- The lookup-table for optimal Steiner tree up to degree 9.
(Note that it is formerly called PORT9.dat.)
flute-net.c -- A program to evaluate the wirelength of a net. It takes
input from stdin as a list of points.
rand-pts.c -- A program to generate a list of random points.
flute-ckt.c -- A program to find FLUTE and half-perimeter wirelength of a
circuit in bookshelf format.
bookshelf_IO.[ch] -- Functions for flute-ckt.c to read bookshelf files.
memAlloc.[ch] -- Functions for flute-ckt.c to allocate memory.
ibm01/ibm01.* -- ibm01 bookshelf files that can be read by flute-ckt.c
license.txt -- License agreement.
Here is a Java version ported by Stefan Mücke:
Flute.java. It is based on FLUTE 2.5.
The Java API is the same as the C API.
 Chris Chu.
FLUTE: Fast Lookup Table Based Wirelength Estimation Technique.
In Proc. International Conference on Computer Aided Design, pages 696-701, 2004.
 Chris Chu and Yiu-Chung Wong.
Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design.
In Proc. International Symposium on Physical Design, pages 28-35, 2005.
 Chris Chu and Yiu-Chung Wong.
FLUTE: Fast Lookup Table Based Rectilinear Steiner
Minimal Tree Algorithm for VLSI Design.
In IEEE Transactions on Computer-Aided Design,
vol. 27, no. 1, pages 70-83,
 Yiu-Chung Wong and Chris Chu.
A Scalable and Accurate Rectilinear Steiner Minimal Tree Algorithm.
In Proc. International Symposium on VLSI Design, Automation and
READ THIS LICENSE AGREEMENT CAREFULLY BEFORE USING THIS PRODUCT. BY USING
THIS PRODUCT YOU INDICATE YOUR ACCEPTANCE OF THE TERMS OF THE FOLLOWING
AGREEMENT. THESE TERMS APPLY TO YOU AND ANY SUBSEQUENT LICENSEE OF THIS
License Agreement for FLUTE
Copyright (c) 2004 by Dr. Chris C. N. Chu
All rights reserved
ATTRIBUTION ASSURANCE LICENSE (adapted from the original BSD license)
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the conditions below are
met. These conditions require a modest attribution to Dr. Chris C. N. Chu
THIS FREE SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR OR ANY CONTRIBUTOR BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, EFFECTS OF UNAUTHORIZED OR MALICIOUS
NETWORK ACCESS; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- Redistributions of the source code, with or without modification (the
"Code"), must be accompanied by any documentation and, each time
the resulting executable program or a program dependent thereon is
launched, a prominent display (e.g., splash screen or banner text) of
the Author's attribution information, which includes:
(a) Dr. Chris C. N. Chu ("AUTHOR"),
(b) Iowa State University ("PROFESSIONAL IDENTIFICATION"), and
(c) http://home.engineering.iastate.edu/~cnchu/ ("URL").
- Users who intend to use the Code for commercial purposes will notify
Author prior to such commercial use.
- Neither the name nor any trademark of the Author may be used to
endorse or promote products derived from this software without
specific prior written permission.
- Users are entirely responsible, to the exclusion of the Author and any
other persons, for compliance with (1) regulations set by owners or
administrators of employed equipment, (2) licensing terms of any other
software, and (3) local, national, and international regulations
regarding use, including those regarding import, export, and use of