GSRC   Bookshelf

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

Chris Chu

Work in progress.
Last updated:  Jun. 20, 2007

Contents

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

FLUTE is a very fast and accurate technique originally designed for wirelength estimation. It is later extended to also perform 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. 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.

III. Source Code

The newest FLUTE version 2.5 gives much better tradeoff between error and runtime than previous versions. This .tgz file contains the FLUTE source code in C and lookup-table:   flute-2.5.tgz

This package 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.
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
IV. Literature

[1] Chris C. N. 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, 2007.
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.eng.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.