User Manual
TRIO – UCLA Interconnect Optimization Package
Project Director: Prof. Jason Cong
Authors: Lei He, Cheng-Kok Koh and David Z. Pan
Copyright © 1993-1998 the Regents of University of California
Overview
The UCLA TRIO package is developed at UCLA VLSI CAD LAB. It includes
optimization engines to perform routing-tree construction, buffer
(repeater) insertion, device sizing, and wire sizing and spacing. The
manual includes the following:
Formulations and Algorithms
Technical References
Usage and Examples
Input Formats
For interests to use the package, please send email to
cong@cs.ucla.edu. For comments on the manual, please send email to
helei@cs.ucla.edu.
Formulations and Algorithms
The TRIO package includes the following optimization engines:
wiresize: wire sizing optimization
siss: single-net interconnect sizing and spacing considering
coupling capacitance from its neighboring nets
giss: global interconnect sizing and spacing considering coupling
capacitance for multiple nets
sbws: simultaneous buffer and wire sizing
stis1: simultaneous transistor and wire sizing using table-based
model for device delay
stis2: simultaneous transistor sizing, and wire sizing and spacing
using table-based models for device delay and coupling
capacitance for multiple nets
bisws: buffer insertion, sizing and wire sizing
batree: wiresized buffered A-Tree
There are two type models for device delay and interconnect
capacitance. One is called the simple model based on the following
formulas: the device delay is given by Intrinsic_delay +
Output_resistance / Size * C_load, where Output_resistance is the
output resistance for a unit-size device; the interconnect capacitance
is given by (Unit_area_capacitance * width +
Unit_fringe_capacitance)*Length. In the simple model, Intrinsic_delay,
Output_resistance, Unit_area_capacitance and Unit_fringe_capacitance
are constants.
The other type of model is the table-based model. The table-based
interconnect capacitance model considers area, fringe and coupling
capacitance as functions of wire width and spacing [4]. The table-based
device delay model treats device delay as a function of input waveform
slope, device size and output load.
There are two types of device sizing formulations. One is the
continuous gate sizing formulation, where the driver/buffer is
characterized by one size under the assumption that the ratio between
p- and n-transistors within a driver/buffer are fixed. All engines
support the gate sizing formulation. In addition to the gate sizing
formulation, stis1 and stis2 also supports transistor sizing
formulation, i.e., the size of each transistor is assigned
independently.
Algorithms in TRIO can be classified into two categories: local-
refinement based approach and bottom-up based approach.
Engine wiresize, sbws, stis1 and stis2 use local-refinement based
approach.
Wiresizing optimization was proposed in [8] using local refinement (LR)
operation. Engine wiresize implements bundled local refinement (BLR)
[1] operation that may be 100x faster than the LR operation. It uses
the simple model for the interconnect capacitance.
Simultaneous buffer and wire sizing for a single net was proposed in
[7] using alternated wire sizing and device sizing procedures, where
wire sizing is based on the BLR operation and device sizing is based on
closed-form formula. Engine SBWS implements iterative LR and BLR
operations (LR for devices and BLR for wires). It uses the simple model
for both device delay and interconnect capacitance.
Simultaneous transistor and interconnect sizing was proposed in [2,3]
for multiple nets. Engine stis1 is different from stis2 that stis1 does
not consider the coupling capacitance between multiple nets.
Consequently, stis1 uses the simple model for interconnect capacitance,
whereas stis2 used the table-based model for interconnect capacitance.
Both use LR operation to compute device sizing under the simple model,
or extended local refinement (ELR) [3] to compute device sizing under
the table-based model. The wire sizing is computed by the LR operation
in stis1, and by the ELR operation in stis2.
Engine giss, bis and batree are based on the bottom-up approach. The
simple models for device delay and interconnect capacitance are used,
except that giss uses the table-based model for interconnect
capacitance.
ToDo: please add some comments on giss, bis and batree
Technical References
The following are publications concerning TRIO algorithms. All except
[9] were developed in UCLA CAD group.
[1] J. Cong and L. He, "Optimal Wiresizing for Interconnects with
Multiple Sources,'' ACM Trans. on Design Automation of Electronic
Systems, 1(3),pp. 478-511, October 1996.
[2] J. Cong and L. He, "An Efficient Approach to Simultaneous
Transistor and Interconnect Sizing", ACM/IEEE Int'l Conf. on Computer-
Aided Design, Dec.,1996, pp. 181-186.
[3] J. Cong and L. He, "Theory and Algorithm of Local Refinement Based
Optimization with Application to Device and Interconnect Sizing", Proc.
Int'l Symp. on Physical Design, 1998.
[4] J. Cong, L. He, A. B. Kahng, D. Noice, N. Shirali and S. H.-C. Yen,
"Analysis and Justification of a Simple, Practical 2 1/2-D Capacitance
Extraction Methodology", ACM/IEEE Design Automation Conference, 1997,
pp. 627-632.
[5] J. Cong, L. He, C.K. Koh and Z. Pan, ”Global Interconnect Sizing
and Spacing with Consideration of Coupling Capacitance", ACM/IEEE Int'l
Conf. on Computer-Aided Design, Dec. 1997, pp. 628-633.
[6] J. Cong and C.-K. Koh, ``Simultaneous Driver and Wire Sizing for
Performance and Power Optimization,'' IEEE Trans. on Very Large Scale
Integration (VLSI) Systems}, 2(4), December 1994, pp. 408-423.
[7] J. Cong, C.-K. Koh, and K.-S. Leung, ``Simultaneous Buffer and
Wire Sizing for Performance and Power Optimization,'' Proc. Int'l Symp.
on Low Power Electronics and Design, August 1996, pp. 271--276.
[8] J. Cong and K. S. Leung, ``Optimal wiresizing under the distributed
Elmore delay model,'' IEEE Trans. on Computer-Aided Design of
Integrated Circuits and Systems, vol. 14, pp. 321--336, Mar. 1995.
[9] J. Lillis, C. K. Cheng, and T. T. Y. Lin, ``Optimal wire sizing and
buffer insertion for low power and a generalized delay model,'' in
Proc. Int. Conf. on Computer Aided Design, pp. 138--143, Nov. 1995.
[10] T. Okamoto and J. Cong, ``Buffered Steiner tree construction with
wire sizing for interconnect layout optimization,'' in Proc. Int. Conf.
on Computer Aided Design, pp. 44--49, Nov. 1996.
Usage and Examples
User Interface and Scripts
Flows and examples
GUI
User Interface
TRIO can be run in the interactive or batch mode. To run it in the
interactive mode, issue the following command at the UNIX system
prompt:
% trio
The following program head appears:
***********************************************************
* *
* TRIO *
* UCLA Interconnect Optimization Package *
* Version 1.0 *
* *
* Copyright (c) 1993-1998 Regents of UC *
* *
* Director: Prof. Jason Cong *
* Developers: Lei He, Cheng-Kok Koh and David Z. Pan *
* *
* VLSI CAD Group *
* Department of Computer Science *
* UCLA *
* *
***********************************************************
Trio>
At the prompt Trio>, the user can type in any command/script. For
example, command help gives the list of all available commands. After a
command, TRIO gives the times for the command and the total memory
space used for far in the following format:
[user_time system_time memory_space] (e.g., [0:00.03u 0:00.02s 32k])
The package is invoked in the batch mode by issuing the following at
the UNIX system prompt:
%trio script_file
where script_file is the name for a file containing a list of TRIO
commands.
Scripts
Terms command and script are exchangeable in the manual. However,
script tends to be a list of commands. TRIO has the following types of
commands:
Readin commands
Setting commands
Optimization commands
Writeout commands
Inquiry commands
Miscellaneous commands
Readin commands
include the following:
rdnetspec file
readin a file for timing specification for the netlist
readcap_table file
readin a file for the interconnect capacitance table
readdev_table file
readin a file for the device delay table
readdev_spec file
readin a file for the device library specification (device delay
table can be part of the file)
readint_spec file
readin a file for the interconnect library specification
(interconnect capacitance table can be part of the file)
readgdf file
readin a file for the netlist (pre- or post- routing) in GDIF
format
Formats of these files are defined in Input Formats, where dimensions
are always in unit of 0.01um.
Setting commands
include the following:
setdev_width cell_name min_width:max_width!increment_width
e.g., setdev_width INV1 20:80!20 sets the size choices for cell
INV1 as 20, 40, 60, 80
setint_width layer_name min_width:max_width!increment_width
e.g., setint_width MET2 20:80!20 sets the size choices for wire
in layer MET2 as 20, 40, 60, 80
setint_cap layer_name width space1 space2
e.g., by using setint_cap MET2 20 30 30, for the simple model,
the Unit_area_capacitance for layer MET2 is same as that for a
MET2 wire at width 20 and with both nearest neighboring wires at
spacing 30
setdev_delay cell_name input_slope size output_load
e.g., setdev_delay INV1 1e-10 30 2e-14 makes the simple model for
cell INV1 use values (Output_resistance and etc.) same as those
at input_slope 1e-10s, size 30 and output_load 2e-12F.
setmax_edge
ToDo
setmin_grid min_grid
e.g., setmin_grid 100 sets the minimal wire segment used in the
BLR operation [1] is 100.
setopt_mode
ToDo
Optimization commands
batree netname
Build wire-sized buffered A-tree using dynamic programming.
bisws
Simultaneous buffer insertion, sizing and wire sizing.
siss [-dp] [-s] –net netname
Single-net interconnect sizing and spacing with consideration of
coupling capacitance from its neighboring nets.
-lr local refinement based approach (default)
-dp dynamic programming based approach
-a asymmetric wiresizing (default)
-s symmetric wiresizing
giss [-s]
Global interconnect sizing and spacing(giss) with consideration
of coupling capacitance for multiple nets, using LR based
approach followed by DP. It has the following options:
-a asymmetric wiresizing (default)
-s symmetric wiresizing
sbws
Single-net simultaneous buffer and wire sizing. It can also be
performed by stis1 without any option
stis1 [–s#] [-t]
stis2 [-s#] [-t]
stis2 considers the coupling capacitance between multiple nets,
stis1 does not. The default setting for both is to compute one
size for a gate under the simple model for device delay. Option
-s1 computes one size for a gate, and -s2 computes two sizes for
a gate. Option –t uses the table-base model for device delay.
wiresize
Single-source wire sizing. It can also be performed by stis1
without any option
Writeout commands
Writegdf file
Writeout a file in GDIF format. The file can be shown by GUI.
Writespice file
Writeout a file in HSPICE format for simulation.
Inquiry commands
Miscellaneous commands
run file
invoke a sequence of commands in the file
help
list all available commands
quit
quit TRIO
!unix_command
run a unix_command without quit from TRIO
Flows and Examples
Flow
Example of tree construction, buffer insertion, and sizing
Example of global wire sizing and spacing
Flow
In general, commands should be invoked in the following order: first,
read in device and interconnect specification; secondly, read in
netlist for optimization where the netlist can be pre- or post-routing;
thirdly, set optimization parameters like size choices, optimization
mode (e.g., objective to minimize delay or power), and simple model or
table-based model; finally, carry out optimization and write out
optimization results and HSPICE netlist for simulation.
Example of tree construction, buffer insertion, and sizing
Example of global wire sizing and spacing
GUI
Input Forms
Interconnect library specification
Device library specification
Netlist specification (GDIF format)
Timing specification
Interconnect library specification
This file specifies the layer stack. An example is given in the
following:
hpcmos26.tech.line
********************
#### Process Parameters extracted from
#### MOSIS PARAMETRIC TEST RESULTS
#### RUN: N65Z VENDOR: HP-NID
#### TECHNOLOGY: SCN08H FEATURE SIZE: 0.8 microns
#### COMMENTS: Hewlett Packard CMOS26G.
#### @(#)hpcmos26.tech 1.1 8/7/96
#### VALUES ARE PER 0.1UM
Number_of_layer = 4
# POLY
Layer_number = POLY
Sheet_resistance = 2.0
Unit_area_capacitance = 88e-20
Unit_fringe_capacitance = 176e-19
Number_of_width = 11
Widths = 10 12 14 16 18 20 22 24 26 28 30
# MET3
Layer_number = MET3
Sheet_resistance = 0.05
Unit_area_capacitance = 27e-20
Unit_fringe_capacitance = 54e-19
Number_of_width = 1
Widths = 32:40!2
.
.
.
# via parasitics
Number_of_via = 3
# MPOLY
Via_number = MPOLY
Bottom_layer = POLY
Top_layer = MET1
Via_resistance = 0.48
Via_capacitance = 0
# M1M2
Via_number = M1M2
Bottom_layer = MET1
Top_layer = MET2
Via_resistance = 0.47
Via_capacitance = 0
Via_number = M2M3
Bottom_layer = MET2
Top_layer = MET3
Via_resistance = 0.47
Via_capacitance = 0
# capacitance table
cap_table = cap.LEF
*********************
The order of this file is important. It always start with the layer
specification, followed by via specification. The layer includes poly-
silicon as well the metal layers. Recall that we assume 1 unit
corresponds to 0.01um. All values that we specify for the parasitics
of the routing layer are per unit of 0.01um.
Lines that start with "#" are comments. Empty lines are skipped.
The following line specifies that there are four layers in this
technology
Number_of_layer = 4
The following few line specifies metal layer MET3:
# MET3
Layer_number = MET3
Sheet_resistance = 0.05
Unit_area_capacitance = 27e-20
Unit_fringe_capacitance = 54e-19
Number_of_width = 1
Widths = 32:40!2
MET3 is commented since the name of the routing layer is not important.
1. Layer_number (string) specifies MET3
2. Sheet_resistance (double) is the resistance of a square of MET3.
3. Unit_area_capacitance (double) is the area capacitance per unit
area
4. Unit_fringer_capacitance (double) is the fringing capacitance per
unit length
5. Number_of_width (integer) specifies the number of wire widths in
the next line starting with "Widths"
6. Widths (list of integers) list all the widths.
min_width:max_width!increment_width
Line widths = 32:40!2 is equivalent to listing the widths
Number_of_width = 5
Widths = 32 34 36 38 40
max_width and increment_width are optional as the above example
illustrates. max_width is min_width if it is missing, and
increment_width is 1 if it is missing.
Note that only Layer_number and Sheet_resistance are required for a
layer. The rest are optional, and may be set later on, or be overwitted
by commands setint_cap, setint_width.
After all the layer specifications, the following line specifies that
there are three type of vias in this technology (normally
Number_of_layer - 1)
Number_of_via = 3
The following lines defines the type of via M1M2 connecting layer MET1
to MET2
# M1M2
Via_number = M1M2
Bottom_layer = MET1
Top_layer = MET2
Via_resistance = 0.47
Via_capacitance = 0
1. Via_number (string) is the name of via.
2. Bottom_layer (integer) is the lower layer, which is MET1
3. Top_layer (integer) is the upper layer, which MET2
4. Via_resistance (double) is the via resistance.
5. Via_capacitance (integer) specifies the via capacitance (F). Note
that the unit is not in fF, but in F.
cap_table = cap.LEF
This line specifies that the interconnect capacitance table is given in
file cap.LEF. It is also optional in the sense that command
readcap_table can be invoked as an alternative.
Device library specification
#### Process Parameters extracted from
#### MOSIS PARAMETRIC TEST RESULTS
#### RUN: N65Z VENDOR: HP-NID
#### TECHNOLOGY: SCN08H FEATURE SIZE: 0.8 microns
#### COMMENTS: Hewlett Packard CMOS26G.
#### @(#)hpcmos26.tech 1.1 8/7/96
#### VALUES ARE PER 0.1UM
Number_of_buffer = 1
Buffer_name = INV1
Size = 10:150!10
Gate_capacitance = 15.0e-15
Output_resistance = 100
Output_capacitance = 0
Intrinsic_delay = 100e-12
input_cap_p = 1.887e-16
input_cap_n = 3.4418e-16
output_cap_p = 0.0
output_cap_n = 0.0
rdp = 18287
rdn = 11023
size = 100
coutn = 1.890030e-14
coutp = 6.245200e-15
cinn = 2.799930e-14
cinp = 1.065660e-14
sin = 5.000e-11 1.000e-10 2.000e-10 3.000e-10
cload = 2.251e-13 4.251e-13 8.251e-13 1.625e-12 3.225e-12
rdn = table
1.220e+04 1.337e+04 1.918e+04 2.021e+04
7.578e+03 9.719e+03 1.250e+04 1.488e+04
8.114e+03 8.665e+03 1.025e+04 1.168e+04
8.135e+03 8.170e+03 8.707e+03 9.458e+03
8.124e+03 8.137e+03 8.251e+03 8.572e+03
rdp = table
1.471e+04 1.714e+04 2.455e+04 2.604e+04
1.614e+04 1.992e+04 1.882e+04 2.073e+04
1.709e+04 1.694e+04 1.729e+04 1.813e+04
1.718e+04 1.715e+04 1.710e+04 1.720e+04
1.720e+04 1.719e+04 1.715e+04 1.712e+04
size = 400
coutn = 7.570600e-14
coutp = 2.498080e-14
cinn = 1.119976e-13
cinp = 4.245270e-14
sin = 5.000e-11 1.000e-10 2.000e-10 3.000e-10
cload = 5.007e-13 9.007e-13 1.701e-12 3.301e-12 4.901e-12
rdn = table
1.156e+04 1.744e+04 1.555e+04 3.039e+04
1.220e+04 1.336e+04 1.915e+04 2.015e+04
7.554e+03 9.688e+03 1.247e+04 1.487e+04
8.463e+03 8.812e+03 1.042e+04 1.214e+04
7.725e+03 8.480e+03 1.001e+04 1.118e+04
rdp = table
1.820e+04 1.997e+04 2.703e+04 3.215e+04
1.609e+04 1.959e+04 2.456e+04 2.605e+04
1.734e+04 1.742e+04 1.879e+04 2.070e+04
1.703e+04 1.678e+04 1.744e+04 1.849e+04
1.707e+04 1.702e+04 1.706e+04 1.767e+04
*********************
Number_of_buffer = 1
specifies that there is only one type of buffer in the library.
The following line specify buffer INV1
Buffer_name = INV1
Size = 10:150!10
Buffer_name (string) specifies the name of buffer in the library size
(integer:integer!integer) list all the sizes as in layer information.
The following few lines specify buffer INV1 for gate sizing formulation
under step-model.
Gate_capacitance = 15.0e-15
Output_resistance = 100
Output_capacitance = 0
Intrinsic_delay = 100e-12
Gate_capacitance (double) is the gate capacitance of a unit size buffer
Output_resistance (double) is the resistance of a unit size buffer
Output_capacitance (double) is the output capacitance of a unit size
buffer
Intrinsic_delay (double) specifies the intrinsic delay of buffer
The following few lines specify buffer INV1 for transistor sizing
formulation under the simple model.
input_cap_p = 1.887e-16
input_cap_n = 3.4418e-16
output_cap_p = 0.0
output_cap_n = 0.0
rdp = 18287
rdn = 11023
input_cap_p (double) is the input capacitance of a unit size p-
transistor
input_cap_n (double) is the input capacitance of a unit size n-
transistor
output_cap_p (double) is the output capacitance of a unit size p-
transistor
output_cap_n (double) is the output capacitance of a unit size n-
transistor
rdp (double) is the resistance of a unit size p-transistor
rdn (double) is the resistance of a unit size n-transistor
The following few lines specify table for buffer INV1 for transistor
sizing formulation under the table-based model.
size = 100
cinp = 1.065660e-14
cinn = 2.799930e-14
coutp = 6.245200e-15
coutn = 1.890030e-14
sin = 5.000e-11 1.000e-10 2.000e-10 3.000e-10
cload = 2.251e-13 4.251e-13 8.251e-13 1.625e-12 3.225e-12
rdn = table
1.220e+04 1.337e+04 1.918e+04 2.021e+04
7.578e+03 9.719e+03 1.250e+04 1.488e+04
8.114e+03 8.665e+03 1.025e+04 1.168e+04
8.135e+03 8.170e+03 8.707e+03 9.458e+03
8.124e+03 8.137e+03 8.251e+03 8.572e+03
rdp = table
1.471e+04 1.714e+04 2.455e+04 2.604e+04
1.614e+04 1.992e+04 1.882e+04 2.073e+04
1.709e+04 1.694e+04 1.729e+04 1.813e+04
1.718e+04 1.715e+04 1.710e+04 1.720e+04
1.720e+04 1.719e+04 1.715e+04 1.712e+04
size (int) is the size for both p- and n- transistors under measurement
cinp (double) is the input capacitance of the p-transistor
cinn (double) is the input capacitance of the n-transistor
coutp (double) is the output capacitance of the p-transistor
coutn (double) is the output capacitance of the n-transistor
sin (double) is the input slope for p- and n- transistors
cload (double) is the output load for p- and n- transistors
rdp (= table) contains output resistance values for p-transistor, each
row for an output load, each column for an input slope
rdn (= table) contains output resistance values for n-transistor, each
row for an output load, each column for an input slope
In order to use table-based model, at lease two sizes, two input-slopes
and two output loads are needed.
The sizing formulation under the table-based model using these values
defined by cinn (double), coutn (double) and rdn (=table).
Netlist specification (GDIF format)
For further information and format, please refer to the GDIF. The nets
may only have pin locations or may be already given paths.
Timing Specification
There are two ways for timing specifications:
(1) Default timing specification
trio> rdnetspec // Use default timing specification,
from default.spec
The default.spec will not specify timing spec for each source/sink;
instead, it will read in a simple default timing spec for all
sink/source
####### default.spec ########
SOURCE 2384
SINK 12
CRITICALITY 1
RATIME 0
########## End of default.spec ###########
Where every source node will have driver resistance of 2384 ohm, every
sink node will have loading capacitance of 12fF, criticality of 1 and
required arrival time (RATIME) of 0.
(2) Read in timing specification from a file
trio> rdnetspec filename // Read timing from specific file
A sample timing specification file is as follows:
#######################################################################
##
### Format. There are three possible specification formats.
###
### (1) SOURCE x1 y1 layer1 Driver_res input_slope
###
### (2) SINK x1 y1 layer1 Loading_Cap slope_req noisemargin
### for source-independent specification.
###
### (3) SOURCESINK x1 y1 layer1 x2 y2 layer2 ratime criticality
### for source-dependent specification.
###
### where x, y are in 1/100 micron units
### layer is the layer name
### Driver_res is the driver resistance in ohm
### slope is the required waveform slope, in second.
### Loading_cap is the loading capacitance in fF
### noisemargin is a double
### ratime is the required arrival time, in second.
### criticality is the weight
#######################################################################
##
SOURCE 0 0 MET2 119 1e-9
SINK 100000 -100000 MET2 12 1e-9 10
SINK 100000 100000 MET2 12 10 10
SOURCESINK 0 0 MET2 100000 -100000 MET2 0.0 1.0
SOURCESINK 0 0 MET2 100000 100000 MET2 0.0 2.0
SOURCE 0 300 MET2 119 1e-9
SINK 80000 300 MET2 12 10 1
SOURCESINK 0 300 MET2 80000 300 MET2 0 1.0
############## End of timing spec file
#######################################