Switchbox Algorithm

Overview

A vector pinnums contains the number of unrouted pins remaining for each net (i.e. at the beginning of the algorithm pinnums[1] = 4, since net 1 has 4 pins to be routed). Another array pinlist contains the locations of these pins with respect to the board array.

Each pass of the algorithm proceeds as follows. A pin of net n at position (x1,y1) is selected to route (this is done sequentially - first a pin from net 1 is routed, then a pin from net 2, and so on). Using a maze searching technique, the closest point belonging to net n on the board, (x2,y2), is located. Clearly this will find another pin at the beginning of the algorithm, but if two pins from n have already been routed, anywhere along the wire between them is acceptable as an output from the maze search. Now we consider the problem of routing the pin at (x1,y1) towards (x2,y2). We treat this as another search problem. Note that (x2,y2) is merely used to direct the search - the final position we route may well be a different one, but (x2,y2) is a good direction in which to aim.

We start investigating a path beginning at (x1,y1). Our initial direction is necessarily chosen to be perpendicular to the face of the switchbox upon which we are starting. Our search is rule based, employing simple heuristics to decide when to turn left and right, and bad moves are recorded so that they are never repeated. A path will continue in a straight line as long as doing so brings it closer to (x2,y2) or it is blocked by a via from another net. In that sense the search is similar to line based search, although many rules are incorporated to prevent paths which may prove injurious to the routing of different nets later.

The operation of the procedure to route (x1,y1) to (x2,y2) is explained in the following pseudocode:

routeab
initialize direction;
move(direction);
while(not routed){
   if (any adjacent position = valid end position)
      move in the appropriate direction;
      insert a via if appropriate;
      routed = true;
   else if (no move is possible)
      mark the board so this position is never reached again;
      move backwards;
   else if (a straight move is forced)                                                       (1)
      move forwards;
   else if (a straight move is possible and constitutes a 'good' move)        (2)
      move forwards;
   else if (a right move is possible and constitutes a 'good' move)            (2)
      insert a via;
      move right;
   else if (a left move is possible and constitutes a 'good' move)              (2)
      insert a via;
      move left;
   else {
       if (a forward move is possible) move forward;
       else if (a right move is possible) move right;
       else if (a left move is possible) move left;
   }
}

Note the points in the above algorithm:

1. 1: A straight move is forced if, in turning, the resultant via would result in blocking another pin's entry into the board.
2. 2: A 'good' move is regarded simply as a move which brings the path closer to the solution. This simple definition proved sufficient to route the example given.

Data Structures

• board:    This is an array which represents the relevant information about which moves are tabu during the routing of a pin. Each position in the array maps trivially to a position in the switchbox. It is initialized before each pin is routed. Values in the array denote the positions of vias from other routed nets, positions where only horizontal wiring is allowed (i.e. where a net has already been routed vertically) and positions where only vertical wiring is allowed. Locations which correspond to prerouted wires of the same net as the current pin are given special marking as they correspond to valid end-points of the pin-routing procedure.
• pinlist:    This contains a list of all the pins to be routed, which is updated dynamically each time the pin-routing procedure is called.
• paths[]:  This is an array of linked lists, each linked list representing the wiring of either a pin to another pin or a pin to its corresponding net. Each list node in the linked list corresponds to a position on the board, and is declared as follows:
public class listnode{
    int xpos, ypos;   // where on the circuit is it
    boolean up;       // up layer or down layer
    boolean block;   // does it block (is it a via)
    int net;              // what net does it correspond to
    listnode link;      // next node on the list
}

Conclusion and Evaluation

A short description of your experience with implementing the algorithm, programming in Java, etc...:
The homework assignment was, I felt, very long and I don't think this was as clear to the TA as it proved to be for the students afterwards. Not knowing Java before was, of course, a hindrance, and I really feel a class devoted to the TA discussing (a) Java fundamentals, and (b) the graph package we were supposed to use as our framework would have saved everyone a great deal of time. Having said this I certainly learned quite a bit of Java, but my code is sub-optimal - for the most part I tried to treat Java as though it were C, thereby missing out on the advantageous features which Java supports.

Second assignment:
The second assignment should be less lengthy, I feel. What I would like to implement is an on-line router wherein the user may specify an arbitrary pin configuration in a switchbox of arbitrary dimension. This would really test our routing algorithms to the full.