03/10/2003 ------------------------------------------------------------ Version 2.0 Alpha Copyright (c) 1999,2003 by John P. Lillis, Milos Hrkic. The University of Illinois at Chicago. All rights reserved. ------------------------------------------------------------ This file contains descriptions of following programs: stree Performance driven Steiner router using S-Tree algorithm ptree Performance driven Steiner router using P-Tree algorithm sptree Performance driven Steiner router using SP-Tree algorithm -------------------------------------------------------------- program: stree overview: Takes as input a multi-pin net and a technology in which it is to be routed. The algorithm produces a family of Rectilinear Steiner topologies which exhibit a performance vs. cost tradeoff. usage: % stree -pins -src [ -o ] [ -tech ] [ -cap ] [ -rat ] [ -pol ] [ -blk ] [ -buf ] [ -bufblk ] [ -tree ] [ -part ] [ -scale ] [ -wcf ] [ -bcf ] [ -gridgap ] [ -a ] [ -memstat ] -------------------------------------------------------------- program: ptree overview: Takes as input a multi-pin net and a technology in which it is to be routed. The algorithm produces a family of Rectilinear Steiner topologies which exhibit a performance vs. cost tradeoff. usage: % ptree -pins -src [ -o ] [ -tech ] [ -cap ] [ -rat ] [ -pol ] [ -blk ] [ -buf ] [ -bufblk ] [ -scale ] [ -wcf ] [ -bcf ] [ -gridgap ] [ -a ] [ -wrap ] [ -memstat ] -------------------------------------------------------------- program: sptree overview: Takes as input a multi-pin net and a technology in which it is to be routed. The algorithm produces a family of Rectilinear Steiner topologies which exhibit a performance vs. cost tradeoff. usage: % sptree -pins -src [ -o ] [ -tech ] [ -cap ] [ -rat ] [ -pol ] [ -blk ] [ -buf ] [ -bufblk ] [ -part ] [ -scale ] [ -wcf ] [ -bcf ] [ -gridgap ] [ -a ] [ -memstat ] -------------------------------------------------------------- Command line parameters and file formats: (*) more detailed description of file formats and sample instances can be found at http://www.cs.uic.edu/~mhrkic/gsrc/gsrc.html -pins This is a required command line switch. The file specifies the pin names and locations. Also it specifies if the pin is input or output pin. An example file for a 6 pin net is as follows: NET net6 PIN P2 4700 7750 I PIN P3 2490 6730 I PIN P4 3200 1900 O PIN P8 5200 400 I PIN P9 7000 1800 I PIN P12 6211 6900 I END [ -src ] This is a required command line switch. It defines the signal source and for now its intrinsic delay in pico seconds and output resistance in ohms. For current implementation only one source is allowed. An example input file look like this: NET net6 PIN P4 50 300 END [ -o ] File name to output solution topologies. Default output is to the screen. Output file contains the following data for every solution # Input file: ../t2/net6.sitspins # Technology parameters: default # Driver technology parameters: ../t2/net6.src TOPOLOGY net6 1 # Capac[pF] Time[ps] Length[um] # 2.48040 -148.81241 14871.0 # Topology: # P3 P2 P12 + + P9 P8 + + P4 DRIVER P4 3200.00000 1900.00000 1 SINKS P3 2490.00000 6730.00000 1 P2 4700.00000 7750.00000 1 P12 6211.00000 6900.00000 1 P9 7000.00000 1800.00000 1 P8 5200.00000 400.00000 1 END STEINERS _S4 3200.00000 6730.00000 1 _S3 4700.00000 6730.00000 1 _S2 4700.00000 6900.00000 1 _S1 5200.00000 6900.00000 1 _S8 3200.00000 1800.00000 1 _S7 4700.00000 1800.00000 1 _S6 5200.00000 1800.00000 1 _S5 6211.00000 1800.00000 1 END EDGES P4 _S4 1.0 P4 _S8 1.0 _S4 P3 1.0 _S4 _S3 1.0 _S3 _S2 1.0 _S2 P2 1.0 _S2 _S1 1.0 _S1 P12 1.0 _S8 _S7 1.0 _S7 _S6 1.0 _S6 _S5 1.0 _S6 P8 1.0 _S5 P9 1.0 END END Comment: internal Steiner nodes names are in the form _S, so don't name your pins in the similar way. [ -tech ] This allows selection from a set of pre-defined technology types (unit res, cap, etc.). New technologies can be added by creating another tech file. Example of the tech_file follows: (line which begins with % is treated as a comment) % "LIC0p5S" % base width [microns] 0.5 % area wire capacitance at unit width per unit length [pF/micron] 0.0003 % fringe wire capacitance per unit length [pF/micron] 0.0 % wire resistance at unit width per unit length [Ohm/micron] 0.06 Note: At this moment values are order dependent. Default values are exactly those specified in the sample file. [ -cap ] This allows the user to specify the loads for the sinks of the net. Units are pF. If not specified, all sinks have default input cap of 0.05pF. Example input file: NET net6 PIN P2 0.07 PIN P3 0.1 PIN P8 0.05 PIN P9 0.11 PIN P12 0.06 END [ -rat ] This allows the user to specify the required-arrival times for the sinks of the net. Units are pico-seconds. If not specified, default required times are 0 ps. Example input file: NET net6 PIN P2 2100 PIN P3 3532 PIN P8 7356 PIN P9 5273 PIN P12 4364 END [ -pol ] Same idea as -rat switch; allows user to specify (possibly asymmetric) sink polarity (1 - inverted; 0 - noninverted). If not specified, all sinks have equal, noninverted, polarity. Example input file: NET net6 PIN P2 0 PIN P3 0 PIN P4 0 PIN P8 0 PIN P9 0 PIN P12 0 END [ -blk ] Specifies file that contains information about regions blocked for routing. Blockages are represented as rectangles by coordinates of their corner points (x1,y1,x2,y2). Units are the same as for pin locations. Example input file: ROUTBLOCK 3000 6000 5000 7500 0 ROUTBLOCK 4600 1000 6300 2000 0 [ -bufblk ] Specifies file that contains information about regions blocked for buffer insertion. Blockages are represented as rectangles by coordinates of their corner points (x1,y1,x2,y2). Units are the same as for pin locations. Example input file: BUFBLOCK 3000 6000 5000 7500 0 BUFBLOCK 4600 1000 6300 2000 0 [ -buf ] Specifies file that contains buffer library. Buffers are specified by 4 parameters given in a single line in this order: buffer input capacitance in pF, buffer intrinsic delay in ps, buffer output resistance in Ohms, inverter flag (1 if inverter, 0 if not). Example: 0.02 25 180 1 0.03 33 200 0 0.01 40 250 1 [ -tree ] Allows user to specify an abstract topology that the S-Tree will then embed. If not specified, the algorithm constructs one based on spanning tree, same tree that is used in P-Tree to construct sink permutation. Example input file: TOPOLOGY_TREE net6 1 P3 P2 P12 + + P9 P8 + + P4 END [ -part ] Same idea as -rat switch; allows user to partition sinks into two group which enables S-Tree to try 'stitching' operations. Right now only two partitions are considered (0 and 1). If not specified, the algorithm will come up with something on its own. Example input file: NET net6 PIN P2 0 PIN P3 0 PIN P4 0 PIN P8 0 PIN P9 0 PIN P12 0 END [ -scale ] This allows the user to specify a scaling coefficient for the elmore delay calculations. Default value is 1.0, but 0.69 is probably better since it tends to center elmore's error distribution. While the value of the scaling factor will not affect problem instances with identical required times (i.e., min-max src-to-sink delay), they can be affected significantly when there are varying required-times for the sinks -- i.e., different topologies will be produced because the algorithm can identify different critical branches depending on the scale. [ -wcf ] This allows user to specify wire cost. Currently wire cost is proportional to wire capacitance multiplied by this cost factor. To eliminate wire contribution to the cost, set this value to 0 (this will speed up program execution). Default value is 0.1. [ -bcf ] This allows user to specify buffer cost. Currently buffer cost is proportional to buffer input capacitance multiplied by this cost factor. Buffer contribution to the cost, must be greater than zero. Default value is 0.1. [ -gridgap ] Specifies the maximum allowed gap between the grid lines in the grid graph. If the gap is larger than this value, artificial grid lines will be inserted (in both horizontal and vertical direction). If not specified, it is ignored. Units are the same as for pin locations. [ -a ] Runs Area Only mode of the algorithm. Optimizes for area only, i.e. it gives the max-q solution among all min wire length solutions. [ -wrap ] Runs P-Tree algorithm in wraparound mode. This is equivalent to running the same algorithm n times (n is the number of sinks) where the permutation of the sinks is rotated by one each time. The runtime is increased only by a constant factor instead by n. [ -memstat ] After the computation it prints out some memory usage statistics. ------------------------------------------------------------------------ General Comments: Code is still in developing phase. All enclosed components should work without errors, but some parts could still be improved. Please report problems to mhrkic@cs.uic.edu