/****************************************************************************/
/*
  Released Software: Fast Buffer Insertion for Interconnect Optimization
                     Version 1.1: Sept. 2004

  Author:  Zhuo Li                       -- zhuoli@ee.tamu.edu 
  Author:  Weiping Shi                   -- wshi@ee.tamu.edu

                        All Rights Reserved

Description: 
  This software contain codes for the buffer insertion to maximize
  the slack at the source. 
  Two algorithms are included: Van Ginneken's O(n^2) time algorithm, 
  Lillis, Cheng and Lin O(B^2n^2) time algorithm. 
  and Shi and Li's fast buffer insertion (FBI) algorithm.
  For more detailed description about the two algorithms, see
  
  "Buffer placement in distributed RC-tree network for minimal
   Elmore delay," by L. P. P. P. van Ginneken, International Symposium 
   on Circuits and Systems , pp. 865-868, 1990.

   "Optimal wire sizing and buffer insertion for low power and a generalized delay model,"
   by J. Lllis, C.K. Cheng and T.-T. Y. Lin, IEEE J. Solid-State Circuits,
   vol. 31(3), pp. 437-447, 1996.
   
   "An O(nlogn) time algorithm for optimal buffer insertion",
   by Weiping Shi and Zhuo Li, Proc. of 40th Design Automation Conference
   (DAC), 2003, pp. 580-585.  

   "A Fast Algorithm for Optimal Buffer Insertion",
   by Weiping Shi and Zhuo Li, IEEE Transaction on Computer-Aided Design of 
   Integrated Circuits and Systems, to appear.
*/
/****************************************************************************/

 
 
The programs are available on "as is" basis. They are not guaranteed
to be free of bugs, and the authors assume no responsibility for any
potential problems.

The programs are designed to run under Sparc Solaris 2.7 or above.

PACKAGE 
   FBI:    dynamically linked binary file
   FBI_st: statically linked binary file
   routing_tree.m:   MATLAB program to read the output tree and buffer information
SYNOPSIS
	buffer_insert -f netfile -b libraryfile [-t] [-o] [-d]

OPTIONS
    -f netfile
	topology file filename. 

    -b libraryfile
        Buffer Library filename.

    -t
	Print the time and memory used by the buffer insertion algorithm. 

    -o
	Print nonredundent solutions before the source,  detail memory usage.

    -d
	Print debugging information.

INPUT FORMAT
   Use the format described in sample.net to build a tree.
   Use the format described in sample.lib to build the technology file.
   Wire Segmenting coef: Define how many segments are divided for each orignal edge

   Van Ginnken (1) or FBI Algorithm (2): 
    1: Van Ginnken O(n^2) and Lillis O(B^2n^2) Algorithm
    2: FBI Algorithm 

   
OUTPUT 
   1. The slack after buffer insertion and total number of buffres added are printed.
   1. The buffer location information is stored in file with netfile.buf extension name. 
   2. The net file after segmenting is stored in file netfile.finalnet. 
   3. Use routing_tree.m (written in MATLAB) to read the netfile.buf and .finalnet to display the tree
      and buffer information


SAMPLE 
   Eight sample net topology files are included: p1.net, p2.net, r1.net, 
   r2.net, r3.net, r4.net, r5.net, long_line.net. 
   p1, p2, r1, r2, r3, r4, and r5 are generated by constructing routing trees with
   an algorithm similar to A-tree algorithm on clock net benchmarks 
   from IBM benchmarks (from R.S. Tsay) and MCNC benchmarks (from DAC90 paper by Jackson et al.).
   The details can be found at http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/BST/
   or paper 
   "On the Bounded-Skew Clock and Steiner Routing Problems", 
   by D. J.-H. Huang, A. B. Kahng, and C.-W. A. Tsao, 
   Proc. 32nd ACM/IEEE Design Automation Conf., 1995, pp. 508-513. 
   
   long_line are a two-pin net randomly generated. 
   
   Two buffer library sample files are included: buffer.lib and buffer5.lib.

