GSRC   Bookshelf

FLUTE: Fast Lookup Table Based Technique for RSMT Construction and Wirelength Estimation

Chris Chu

Work in progress.
Last updated:  Feb. 28, 2011

Contents

I.  Introduction 
II.  Experimental Results 
III.  Source Code
IV. Literature
V. License
I. Introduction

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:

  1. RMST: an efficient O(n2) implementation of Prim’s algorithm
  2. RST-T: Refined Single Trunk Tree [SLIP-02, p.85-89]
  3. SPAN: the spanning graph based RSMT algorithm [ISPD-03, p.152-157]
  4. BGA: the batched greedy triple contraction algorithm [ASPDAC-03, p.827-833]
  5. BI1S: the near-optimal Batched Iterated 1-Steiner heuristic [TCAD-94, p.1351-1365]
  6. 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 ISPD98 benchmark suite are used. There are totally 1.57 million nets in the 18 circuits. The placement is generated by FastPlace. 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.



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.

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.

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.
ChangeLog.txt
Makefile
Readme

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.

IV. Literature

[1] Chris Chu. FLUTE: Fast Lookup Table Based Wirelength Estimation Technique. In Proc. International Conference on Computer Aided Design, pages 696-701, 2004.
[2] 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.
[3] 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, January 2008.
[4] Yiu-Chung Wong and Chris Chu. A Scalable and Accurate Rectilinear Steiner Minimal Tree Algorithm. In Proc. International Symposium on VLSI Design, Automation and Test, 2008.

V. License

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 PRODUCT.

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 (the "Author").

  1. 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").
  2. Users who intend to use the Code for commercial purposes will notify Author prior to such commercial use.
  3. 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.
  4. 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 encryption software.
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.