MARCO GSRC Calibrating Achievable Design: Bookshelf

C-tree : Buffered Steiner Trees for Difficult Instances

Work in progress: last updated Oct 19 2003

(see other slots)

Charles Alpert(IBM Austin Research Laboratory);
C. N. Sze and Jiang Hu(Texas A&M University)

Contents

I. Introduction
II. The Algorithm
III. I/O Data Formats
IV.Sample Instances
V. C-tree Executable
VI. References

I. Introduction

This entry is about the problem of single interconnection steiner tree construction with buffer insertion. We focus on the ``difficult instances'' [1] which are characterized by a large number of sinks, large variation in sink criticalities nonuniform sink distribution, and varying polarity requirements.
In this page, you can find the details of our C-tree implementation, the executables, our data format for a single interconnection tree description and a set of test-case files which is based on some difficult nets from industry.

Important Notes: International Business Machines Corporation (IBM) holds the patent (#6591411) of the C-tree techniques. Please refer to the patent page.

II. The Algorithm

The C-tree algorithm is briefly introduced here. If you need more information about the algorithm, please see [1].
C-tree algorithm consists of two main parts:
Sink clustering
It clusters the sinks with similar characteristics such as criticality, polarity, and distance from source pin.
We use the K-center heuristic for sink clustering, which aims to minimize the maximum cluster radius (distance to the cluster center). Here, the distance function is a linear combination of the spatial, temporal and polarity distance which is shown in the following.

In the equation, the sum first two terms are less than or equal to 1, and they are weighed by a parameter ``\beta''. The last term itself is a value which is either one (when two sinks are of difference polarity) or zero (when their polarity are the same) which represents the importance of putting two sinks with the same polarity in the same cluster.
sDist() is just the Manhattan distance between the two sinks and ``Diameter of net'' is the maximum sDist() between every pair of sinks in the net.

crit() is a value showing the criticality difference of two sinks. AS() is a good indicator of the criticality of a sink and the equations are shown as follows.

Note that in the equation of crit(), we use a parameter ``\alpha'' to control that how much amount of sinks will be treated as critical and all other non-critical sinks would have a similar value of crit().

In the K-center heuristic, first we need to find the total number of cluster seeds, K. This is can be controlled by a parameter ``D'' -- we keep adding a new seed which is furthest from all other old seeds until the minimum distance from the new seed to all other old seeds is less than or equal to D.

Two-level timing driven Steiner tree construction
It constructs a Steiner tree for each sink cluster and then a top-level timing driven Steiner tree is built such that each cluster is considered as a sink in the top-level.
The timing driven Steiner tree is constructed by the Prim-Dijkstra tradeoff method [2]. The algorithm trades off between the minimum spanning tree and the shortest path tree via a parameter c. However, c is not a parameter in our implementation since we try c=0,0.25,0.5,0.75,1.0 and pick the best one according to the maximum slack of the trees.


III. I/O Data Formats

Input file format

C-tree implementation takes these types of files as input:
  • Pin information (.net)
 contains all the information about the net, which includes pins locations, properties of source and sink nodes, etc.
  • Buffer Library (.lib)
 contains all the information about the buffer library, which is used by the final step: van Ginnekin style buffer insertion.
We generates our testcase according to some industry data. However, some changes have been made in order to make each net a "more difficult" instance for buffered Steiner tree. Here, we explain the fields in the testcase files.
  • Net
 Name of the net
  • UnitCap
 Wire capacitance per unit length (unit: Ohm/nm)
  • UnitRes
 Wire resistance per unit length (unit: fF/nm)
  • Number Sinks
 Total number of sink pins for the net
  • Source
Source pin id (the id of source pin is usually set to 0)
It is also a tag indicates that all information following this line is related to the source pin.
  • Sink
Sink pin id
It is also a tag indicates that all information following this line is related to the sink pin with the name shown after the tag.
  • Location (x, y)
 x and y can be any integer which shows the x- and y- coordinates of the physical pin location. (unit: 10^-6 m)
  • Resistance
Driver resistance at the source pin (unit: 10^3 Ohm)
  • Arr
 Arrival time for the signal at source pin (unit: 10^3 ps)
  • Capacitance
Load capacitance at a sink pin (unit: 10^3 fF)
  • Req
Required arrival time for the signal at a sink pin (unit: 10^3 ps)
  • Polarity
The polarity of a sink pin (0: same as source pin; 1: opposite of the source pin)

Sample input file

Buffer library format

  • buffer i c d r
 each line shows all the information of one buffer type. "i" is the buffer id; "c" is the buffer load capacitance (in fF); "d" is the intrinsic delay (in ps); "r" is the buffer resistance (in Ohm).

Sample buffer library file

Output format

The output of our C-tree implementation consists of the physical location of the source, sinks and Steiner nodes as well as the connection information.
  • wire_res_per_unit_length
 Wire capacitance per unit length (unit: Ohm/10^(-6)m)
  • wire_cap_per_unit_length
 Wire resistance per unit length (unit: fF/10^(-6)m)
  • driver x y
 the location of source node; x and y can be any integer which shows the x- and y- coordinates of the physical location. (unit: 10^-6 m)
  • number_of_sinks
 Total number of sink pins for the net
  • sink i x y a b
the location of the i-th sink node; x and y can be any integer which shows the x- and y- coordinates of the physical location. (unit: 10^-6 m);
a : the Load capacitance at the sink pin
b : Required arrival time at the sink pin
  • number_of_steiner_nodes
 Total number of steiner nodes
  • steiner i x y
the location of the steiner node with the node id i; x and y can be any integer which shows the x- and y- coordinates of the physical location. (unit: 10^-6 m);
  • edge i j
there exists a connection from node i to node j

Sample output file

Verbose mode

You can use the "-v" option to turn on the Verbose mode. The following information would be useful to understand the operations of C-tree.
  • Buffer information:
followed by the buffer insertion results.
  • id[id1],x[bx],y[by],buffer([t])-> [id2]
Each line describes the exact buffer location ([bx],[by]) and other information. The buffer is added just after the node [id1] on the connection from [id1] to [id2] with the buffer type [t].
  • Slack
minimum slack of the whole net achieved by C-tree (You can show the slack before and after the final buffer insertion step.)
  • User time/System time
CPU time used for C-tree implementation


IV. Sample Instances

Sample data file in zipped format
Sample data files for our C-tree implementation, which follows the data format described in last section.


V. C-tree Executable

README of the C-tree executable (Click)
It shows the usage of the C-tree implementation
C-tree binary (Version 1.0)
ctree.tar.gz (Sparc Solaris 2.7, gcc version 2.95.3 20010315 dynamically linked)
ctree.tar.gz (Sparc Solaris 2.7, gcc version 2.95.3 20010315 statically linked)
The full version C-tree package: it contains the executable, readme, documentations and sample data files


VI. References

[1] C. J. Alpert, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, A. J. Sullivan, P. Villarrubia, ``Buffered Steiner trees for difficult instances'', IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 21 Issue: 1 , January 2002, pp. 3-14
[2] C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, D. Karger, ``Prim-Dijkstra tradeoffs for improved performance-driven routing tree design'', IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 14 Issue: 7 , July 1995 , pp. 890-896


alpert@us.ibm.com, cnsze@ee.tamu.edu, jianghu@ee.tamu.edu