ECE 741: Sequential Machines

Homework #5 - Spring 2003Assignment

Write a Python script to compare actual and optimal net lengths for the design you routed in Homework #3. Actual length will be determined by summing the lengths of route-segments, while optimal length will be the minimum Steiner-Tree cost, as computed by the steiner program.

Tutorial

The following is a brief tutorial with example files to give you a starting point in writing your script.

1. Importing the Design
   
   • Run the command dirSetup.py run/oa. This will create a directory with a cds.lib file that gives paths to technology and standard-cell libraries.
   • Copy the file counter.def into this directory. You can create a DEF file for your own design by using Route -> Export -> DEF in First Encounter.
   • Run the following command in the run/oa directory:
     def2oa -def counter.def -lib mylib -cell counter -view autoLayout -tech TSMC025_deep
     This will create the new library and import the design to the cellname and viewname specified. It will also update the cds.lib file.
2. Basic Python Scripts
   Various example Python scripts have been provided. You may download them from this page or copy them from the examples/oa directory in the course workspace.
   • Copy the file listinst.py into the run/oa directory and run the command python listinst.py. This script simply lists all of the instances in the design, organized by the cell-master or Instance Header. Note that to make this script work with your design, you will need to change only one line to match the library, cell, and view names you used when you imported your own DEF file. Everything but the last 4 lines of this script can be identical in every OpenAccess Python script that you write.
   • Copy the file listterm.py and run the command python listterm.py. This script prints out all of the terminals in the design, followed by the pins associated with each terminal. Remember that a terminal is a logical connection to a cell, while a pin is a physical connection. There may be more than one pin for each terminal. Run this script once for the counter design, and then modify the line to see the effect when running it on the inv_4 standard cell. Note that there are several pins for some terminals, and that some have different centers. We will have to pick a terminal randomly. This will create some ambiguity in our steiner tree estimates, but it can't be helped.
3. Finding the location of instanceTerminals
   Copy the file listnetendpoints.py and run it. This script cycles through all of the nets, printing the locations of terminals and instanceTerminals for each net. Note that a net can have more than one terminal, which might create more ambiguity in our Steiner-tree estimates, although our design only has one terminal per net, so we're Ok. Each terminal and instanceTerminal has a figure assocated with it. This figure is the shape of the pin. This script gets the bounding box for that figure and prints out its center. If you're having trouble running the script, you can look at the endpoints.out file, which is what I get when I run it. The last confusing things to note here are the lines that read "print str(long(point.x()))...". The x() method of the oaPoint class returns an oaInt4 object rather than a standard python long integer. If you try to print this out, you will get an "L" following the number, which will confuse the steiner program. Here we typecast the oaInt4 as a long integer (which is also 4 bytes) and then use the str() routine to convert it to a string with no "L" suffix.
4. Finding the minimum steiner tree
   To determing the minimum steiner tree cost, we will use the Khang-Robbins 1-steiner heuristic, which was popularized in the steiner program that we use here.
   • First, run the command steiner to see how the program works. Enter 1 for the mode (random pointset), 100 for the number of points, 5 for the number of iterations, and 100000 for the grid size. Any grid-size will do, but 2^17 is the largest number that it will handle. Lastly, enter 0 as the random number seed and press return five times to see a graphical representation of each pointset and its corresponding steiner tree. The small points are the original points, while the large points are the "steiner-points". The terminal screen will show several numbers for each pointset, including #SP (number of steiner points), ST_cost (steiner-tree cost), and MST_cost (minimum spanning tree cost, which is the cost without creating steiner points... this number should be greater than or equal to the steiner-tree cost).
   • Next, run steiner again for a specific case. Enter 2 for the mode (read in pointset), 4 for the number of points, 1 for the gridsize (since this value is used only for the graphical output, we don't care about it for this case), and then enter the following values:
     1 2
     2 4
     4 1
     5 3
     The program will report the minimum steiner tree for this specific case. We will use this program in this mode to compute our steiner-tree costs.
   • Copy the file steiner.py and run it. This script takes a list of endpoints and runs the steiner program to determine the steiner-tree cost. It uses the os.popen2 function to run the program and "open pipes" to stdin and stdout. It then writes to stdin and reads from stdout. This is not a very fast way to do things, but it's very easy to code, and should be fast enough for the small designs for this assignment.
5. Finding the actual wire-lengths
   Copy the file listnetwirelengths.py and run it. This script cycles through the nets in the design and the routes associates with each net. Each route has a number of route elements associated with it. These route elements can be either segments or vias. For segments, the endpoints are given along with the metal layer. We will ignore the metal layer, since it doesn't affect the wire-length so much. We will also ignore the vias. You may examine my wirelengths.out file, if you get stuck.
6. You will now need to create your own script called "netdiff.py" to print out the steiner-tree cost and total wire-length for every net in the counter design. Your final output should match the file netdiff.out perfectly. If you're having trouble, the you may want to print out the net name on each line (although the script you turn in should not print the net names). You may use the file netdiff_names.out for debugging purposes. This file contains the steiner cost, actual cost, error (steiner minus actual) and the net object (which includes the net name).
7. Creating a histogram of the estimation error
   Although not required for this assignment, you may use the netdiff.out file generated with the matlab script nethist.m to create a histogram of the estimation error.
   • Copy nethist.m into your directory.
   • Type "add matlab" to add matlab to your path.
   • Run matlab with the command matlab &
   • In the matlab windown, run the command nethist. This script reads in the entire file into a single vectory, which then needs to be split up again into a steiner vector and an actual vector. The error is then calculated, and a histogram is generated with 100 bins. You should see a plot like the following:
     
   • Note that there are two nets with a large, positive error. If you look in the netdiff_names.out file, you will note that these are the supply and ground nets, which aren't actually routed yet and for which steiner-tree estimates are very inaccurate. You can remove these nets and run nethist again to see the following results:
     The netdiff.out file here has removed these nets.
   • Note now that some nets have a positive error, but the error should always be negative (since the steiner-tree estimate should be the minimum length possible). How can this be? Some of this error is due to the fact that there are multiple pins, and we're choosing one at random, but there is also another problem. By examination of the first net in the endpoints.out and wirelengths.out files, you may note that not all pins have been connected! This means that we need the design to pass LVS to get more accuracy in our estimate.

Submission

You should turn in a .tar.gz archive containing the following files:

1. Your own netdiff.py script. It must generate the netdiff.out file exactly when used on the counter design to get full credit. Partial credit will be given if it gets close.
2. A DEF file for your own routed design from Homework #3.
3. A netdiff.out file corresponding to your own DEF file.