Overview

The objective of this assignment is to evaluate and display the performance of your routing algorithm from homework 1.  In this assignment, wires and vias have associated costs which correspond to a delay metric, and your algorithms should be made to optimize the cost of the circuit.  The distribution of net costs will be displayed in a histogram to provide insight into the working of your algorithm.  Extra credit will be given to routing algorithm which performs best on this task.

Note: You can work in pairs on this assignment.  Here is a list of student solutions for homework 1.

Due November 21, 1997.

Optimizing Costs

The costs that we are concerned with are delay in the circuit.  The delay model that we have in this assignment is  oversimplified for your convenience.  Wires will have a cost/unit length depending on which layer they are located on.  Vias will have a cost/instance.   In practice, numerous tricks are played to overcome resistance in long wires or vias, is quadratic for long wires and is also significant in vias, but in practice there are a number of ways to subvert this.

These costs should be specified by the user (via a dialog box), and should have the following defaults:

Layer 0: 1 cost/unit length
Layer 1: 1 cost/unit length
Via: 5 cost/instance
Your algorithm should have two modes:
1. Optimize for average cost of all nets
2. Optimize for maximum cost of all nets (try to minimize this value)

The histogram which displays your results should have two axes.  The X axis should be net costs, the Y axis should be number of nets which have that particular cost.
 

Test Files

Here are a number of new dot files representing challenging channels to route.  It has not been decided which circuits will be required for the homework.

channel.zip

Many thanks to Dr. Hiroshi Murata of UC Berkeley and Professor Atsushi Takahashi of Tokyo Institute of Science and Technology for providing these examples.

Turnin Materials

Your turnin should consist of the following items:
• An applet which demonstrates your algorithm.  This will be run remotely and should perform reasonably well.
• A short description of the algorithms and data structures you implemented.  In particular, how did you modify your algorithm from homework 1 to optimize the cost?
• A short textual analysis of your algorithm's performance.  What does the distribution you've plotted mean about the algorithm?
Please make an HTML page which links all of these items, and send the URL link in an e-mail message to michaels@eecs.berkeley.edu with the subject "ee244 hw1 turnin".