/****************************************************************************/
/*
  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.

NOTE, BUG and FIX:
 
   1. My VG Algorithm and Van Ginnken's 1990 Algorithm:

   The VG algorithm implemented in this software is slightly different from
   1990 ISCAS paper. In that paper, at every node, first merge two subbranches 
   solutions if this node degree > 2, then add a buffer at this node and propagate
   wire to the driving node. However, this flow has limit to add decoupling capacitance.
   Consider following example,
     u ------ v ------- v1
              |
              |
              |
              v2
   In VG 1990 algorithm, suppose wire (v, v2) and (v, v1) have nonzero resistance and capacitance.
   Then suppose we have got candidate lists for v2 and v1, N(v2) and N(v1) respectively.
   N(v2) and N(v1) includes the edge delay on e(v, v2) and e(v, v1).
   When the algorithm process to node v,  N(v2) and N(v1) are merged to 
   form N(v). Then if v is a buffer position, a buffer x are tried at this node and 
   there could be a new candidate generated. Insert the new candidate to N(v) and
   propagate through edge e(u, v), prune redundant solutions. Then new N(v) are formed.
   Note that, there is no buffer will be added at node v on e(v,v2),
   or on e(v, v1). The decoupling effect of buffer is ignored. To
   let the algorithm add the decoupling buffer, user need to
   add two dummy nodes on e(v, v2) and e(v,v1) with zero distance to node v.
   
   To automatically allow decoupling, in this program, i implemented VG in a little different way.
   Still use the above example, and suppose N(v2) and N(v1) are candidate lists
   including the edge delay on e(v,v2) and e(v,v1). My algorithm first try to add a buffer
   for N(v2) at node v with the direction driving v2, and insert it into N(v2). 
   Do the same process for N(v1). Then merge N(v2) and N(v1) to form N(v) and add the 
   wire delay on e(u, v). Then, the decoupling buffer are considered. 
   One problem of this implementation is there
   will be no buffer added at node v on edge e(u,v), if u is not a dummy node.
   User can add a dummy node on e(u,v) just before node v to force the algorithm consider 
   adding buffer there. 
  
   If there is three dummy nodes at each node with degree = 3, then VG (1990) and my
   implementation will give same result. Generally, without adding dummy nodes by user,
   my implentation tends to give better slack due to decoupling consideration. 
   The future version of this program will consider these 3 locations, buffer at v
   on edge (u,v), buffer at v on edge (v, v1), buffer at v on edge (v, v2), automatically even
   there are no dummy nodes at node v. 

   2. Muliple Layers and Vias:

   Mulitple layers and vias are not implemented for this version. 
   Currently there is only one unit resistance and capacitance. 
   Edge with nonzero resistance and zero capacitance is not allowed, such as via.
   (however, zero resistance and capacitance edge is allowed.) 
   It can be easy implemented with la field introduced in the paper and will be
   implemented in next version.
   
   3. Driver and Buffer Library Requirement: 
   
   The driver resistance must be equal or greater than one of 
   buffer resistance in buffer library for FBI algorithm. Van Ginnken's algorithm does not 
   have this limitation.  This limitation will be 
   released in next version.
   The Buffer Library must be sorted in decreasing driving resistance order.

   4. Tree Topology: 

   The source node should have degree 1. If the source node has 
   degree 2, it will generate wrong result. User can add a dummy
   node at source node that can have degree 2, and then connect the source 
   node to this node. 
   
   Every node can have maximum degree 3. User need to add dummy
   node to seperate node with degree greater than 3. 
   
   5. Buffer Position:

   In this version, buffer can be inserted at any node. If there is zero length wire,
   buffer will still be inserted.
   
   6. More segmenging points implies more speedup of FBI algorithm and gives better slack. 
   However, it may result overflow of stack and segmenting fault of program. In a 
   SUN SPAC machine of 450MHZ and 2G pc, segment coef under 50 for all sample nets are tested.
   
   7. Maximum buffer Library size is upgraded from 24 to 64. If you want to treat the case 
   with more than 64 buffer types, please contact the author. 

Version 1.1.   Mon Sep 6 14:42:26 CST 2004
