C. N. Sze and Jiang Hu(Texas A&M University)
|
|
Charles Alpert(IBM Austin Research
Laboratory);
C. N. Sze and Jiang Hu(Texas A&M University) |
| 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:
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.
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:
| contains all the information about the net, which includes pins locations, properties of source and sink nodes, etc. | |
| contains all the information about the buffer library, which is used by the final step: van Ginnekin style buffer insertion. |
|
|
|
|