* This article contains the following executables: NEVIN.ZIP

*Randy holds a BS in computer science from Oregon State University and an MS in computer science from the University of Washington. He has worked for Microsoft since 1983 on various programming languages and networking products. He can be reached at 1731 211th PL NE, Redmond, WA 98053.*

- Physical problems (trace lengths, board size, number of routing holes, holes that transfer a trace from one side of the board to the other, also called vias)
- Signal crosstalk
- Number of layers

Autorouting can also be viewed as a collection of search problems. The individual problems deal with finding a route and laying down a trace between two locations. There are many algorithms for solving search problems, each with different running time characteristics and data space requirements.

Autorouting search algorithms typically operate in two phases{1}, treating the board as a matrix of cells. The first phase starts at the source cell and searches for the target cell, usually by going in several directions at the same time. The algorithm builds an auxiliary data structure to keep track of how each cell was reached (this is referred to as "Pred" in the algorithms in Figure 1 and Figure 2 ). The first phase ends when the target cell has been found, and the second phase begins. If the first phase exhausts all possibilities without reaching the target cell, then no route exists between them, and there is no reason to do the second phase.

BFS Algorithm (* breadth-first search *) (* Search a graph or state space, depending on the problem definition. *) (* S is the start node, T is the goal node. *) (* Open is an ordered list of nodes (ordered by arrival time; nodes enter at the tail and leave at the head), also called a queue. Closed is a set of nodes (order doesn't matter). In general, nodes that need to be searched are put on Open. As they are searched, they are removed from Open and put in Closed. *) (* Pred is defined for each node, and is a list of "came from" indications, so when we finally reach T, we traverse Pred to construct a path to S. *) 1 Open <- {S} (* a list of one element *) Closed <- {} (* the empty set *) Pred [S] <- NULL, found <- FALSE WHILE Open <> {} and not found DO 5 x <- the first node on Open Open <- Open - {x} (* remove x from Open *) Closed <- Closed + {x} (* put x in Closed *) IF x = T THEN found <- TRUE (* we're done *) ELSE (* continue search through node x *) 10 let R be the set of neighboring nodes of x FOR each y in R DO IF y is not on Open or in Closed THEN Pred[y] <- x (* remember where we came from *) Open <- Open + {y} (* put y on Open (at the tail) *) 15 IF found THEN use Pred[T] to find Pred[Pred[T]] and so on until S is reached (* this traces out the solution path in reverse *) ELSE T cannot be reached from S

Figure 1 contains pseudocode for the breadth-first search algorithm. This algorithm works by processing a first in/first out (FIFO) queue of open cells; that is, cells that have been reached, but not yet searched. Initially, the open queue contains only the source cell. A cell is removed from the head of the open queue, placed in the set of closed cells (cells that have been searched), and checked to see if it is the target cell. If not, its neighbors are placed at the tail of the open queue. Neighboring cells that have already been reached are ignored. (If a cell's coordinates are on the open queue or in the closed set, then it has been reached, otherwise, it has not.) This continues until one of two things happens:

- The target cell has been found
- The open queue is empty, in which case the target cannot be reached from the source cell

Figure 2 shows the behavior of Lee's algorithm while searching for a path between the source cell S (r5c5) and the target cell T (r8c8). Lee's algorithm does not specify the order in which neighboring cells are placed on the open queue, but we'll use the compass directions north, east, south, and west, followed by northeast, southeast, southwest, and northwest. This order tends to produce traces with a minimal number of turns.

In Figure 2a, the source cell (r5c5) has been searched, and its eight neighbors have been placed on the open queue. The arrows indicate the direction from which each cell was reached, and correspond to the Pred data structure. After the first eight cells on the open queue have been reached and moved to the closed set, the algorithm searches the configuration in Figure 2b, where there are sixteen cells on the open queue. Once these sixteen cells have been searched, the configuration in Figure 2c is reached. Now the target cell (r8c8) is fourth from the end on the open queue, and a solution is imminent. Searching r8c8, the algorithm recognizes it as the target cell, and uses the Pred data structure to construct a trace back to the source cell.

You can see that the search progresses outward from the source cell in all directions, like ripples when you throw a pebble into the water. If we double the size of the problem so that S and T are six cells apart, the number of cells searched and therefore the processing time will be about four times as great. If we triple the size of the problem, the number of cells searched will be roughly nine times more. Thus, the behavior of Lee's algorithm is quadratic in the size of the problem, which makes it infeasible for large problems.

Figure 3 gives pseudocode for the A* search algorithm, while Listing One shows it implemented in C. This method also works by processing a queue of open cells, which initially contains only the source cell. But this is a priority queue, which means cells are inserted according to the estimated distance to the target{3}, not just at the end. Cells that are on the shortest estimated path from source to target go to the head of the queue. The A* algorithm removes the cell from the head of the open queue and checks to see if it's the target. If not, the neighboring cells are put on the open queue at the proper position. The algorithm checks neighboring cells that have already been searched to see if the new path between them and the source is shorter than the previous one. If it is, they are repositioned on the open queue according to the new estimated path length from source to target. As in breadth-first search, this continues until the target cell has been found or the open queue is empty.

A* Algorithm (* heuristic search *) (* Search a graph or state space, depending on the problem definition. *) (* S is the start node, T is the goal node. *) (* Open is an ordered list of nodes (ordered by lowest F value; see below), also called a priority queue. Closed is a set of nodes (order doesn't matter). In general, nodes that need to be searched are put on Open (at the proper position). As they are searched, they are removed from Open and put in Closed. Occasionally a newer, better route will be found to a node after it has already been searched, in which case we remove it from Closed and put it back on Open to be reconsidered. *) (* G[x] is the distance already traveled to get from S to node x, and is known exactly. H(x) is a function (heuristic) which returns an estimate of the distance from node x to T. F[x] is the estimated distance from S to T by going through node x, and is computed by F[x] = G[x] + H(x). H(x) can be calculated for any node, but F[x] and G[x] only become defined when node x is visited. *) (* Pred is defined for each node, and is a list of "came from" indications, so when we finally reach T, we traverse Pred to construct a path to S. *) (* Distance (x,y) is a function for calculating the distance between two neighboring nodes. *) 1 Open <- {S} (* a list of one element *) Closed <- {} (* the empty set *) G[S] <- 0, F[S] <- 0, Pred[S] <- NULL, found <- FALSE WHILE Open <> {} and not found DO 5 x <- the first node on Open (* node with smallest F value *) Open <- Open - {x} (* remove x from Open *) Closed <- Closed + {x} (* put x in Closed *) IF x = T THEN found <- TRUE (* we're done *) ELSE (* continue search through node x *) 10 let R be the set of neighboring nodes of x FOR each y in R DO IF y is not on Open or in Closed THEN G[y] <- G[x] + Distance (x,y) F[y] <- G[y] + H(y) (* estimate solution path length *) 15 Pred[y] <- x (* remember where we came from *) Open <- Open + {y} (* put y on Open *) ELSE (* y is on Open or in Closed *) IF (G[x] + Distance (x,y)) < G[y] THEN (* we've found a better route to y *) 20 G[y] <- G[x] + Distance (x,y) F[y] <- G[y] + H(y) Pred[y] <- x (* remember where we came from *) IF y is on Open THEN reposition y according to F[y] 25 ELSE (* y is in Closed *) Closed <- Closed - {y} (* remove y from Closed *) Open <- Open + {y} (* put y on Open *) IF found THEN use Pred[T] to find Pred[Pred[T]] and so on until S is reached 30 (* this traces out the solution path in reverse *) ELSE T cannot be reached from S

Figure 4 shows the behavior of the A* search algorithm. A* does not specify whether new cells go in front of or behind cells already on the open queue that evaluate to identical estimated path lengths. We use the convention that they are placed in front. This minimizes the time to insert a cell on the open queue.

In Figure 4a, the source cell (r3c3) has been searched, and its eight neighbors are on the open queue. Each cell on the open queue also includes the estimated length of the shortest path from S to T that goes through that cell. After the first cell (r4c4) has been searched and moved to the closed set, the configuration in Figure 4b is reached, where there are 12 cells on the open queue. After searching the next cell (r5c5), the algorithm reaches the configuration in Figure 4c. Now the target cell (r6c6) is at the head of the open queue, and a solution will be found on the next iteration of the loop. Searching r6c6, A* recognizes it as the target and uses the Pred data structure to construct a trace back to the source cell.

You can see that the search progresses more directly toward the target cell. The target draws the search much as the earth's gravity pulls objects toward the center of mass. If we double the size of the problem, the search will process about twice as many cells, and if we triple its size, the search will run through three times as many. This linear behavior makes A* more attractive for autorouting than the quadratic Lee's algorithm. With the incorporation of the heuristic -- the rule, that guides the search in the direction most likely to succeed -- it is difficult to estimate worst case behavior. However, A* will never take more time than Lee's algorithm, and it will never search any cells that Lee's algorithm could avoid.

The algorithms in Figures 1 and 3 solve the general search problem. When these algorithms are implemented and customized to a particular application, there are ways to speed them up.

The A* algorithm in Figure 3 recomputes the heuristic H(y) when it discovers a better way to reach a cell. Depending on how difficult this heuristic is to compute, you can probably save some work at the expense of complicating the algorithm. When lines 20 and 21 of Figure 3 are executed, the previous values of G[y] and F[y] are destroyed. But F[y] = G[y] + H(y), so you could save F[y] - G[y] (which is H(y)) in a temporary variable, and use that variable instead of recomputing H(y) on line 21. Also, the common sub-expression G[x] + Distance(x,y) should be placed in a temporary variable, instead of being computed twice (lines 18 and 20).

Often, rather than searching for a path between two individual cells, what is really desired is a path between one of a set of source cells and one of a set of target cells (as when connecting power and ground pins). Both algorithms can be modified by adding the entire set of source cells to the initial open queue, and checking for a member of the set of target cells on each iteration. When this is done, the heuristic used by the A* algorithm becomes more complicated. It must estimate the minimum distance from the current cell to any one of the target cells.

For breadth-first search, once the target cell is placed on the open queue, it is pointless to add any more cells to the open queue because when this happens, the problem is solved. An appropriate shortcut would be to insert a check before line 13 in Figure 1 to see if y is the target cell. If it is, use Pred[y] to construct the trace back to the source cell, and return.

Both search algorithms use quite a bit of memory to solve problems of non-trivial size. The breadth-first search algorithm needs memory to represent the board, the predecessor structure, and the closed set. The A* search algorithm needs these also, plus structures for F[x] and G[x] (see Figure 3). In addition, both algorithms dynamically allocate memory for the open cell queue.

The board is represented as a pair of two-dimensional arrays -- one for the front side, the other for the back -- in which the dimensions are the number of rows and columns of cells. Not counting holes and traces relating to holes (Figure 5, groups A, B, and C), there are 30 possible cell contents, which can be represented with 5 bits per cell.

The hole-related cells are more difficult to enumerate; they can be combined in many ways. If we simply assign 1 bit to each of the eight traces in groups B and C, and add one more bit to indicate a hole, 14 bits will be sufficient to represent any cell. On a board of N rows and M columns, we'll need N*M*28 bits total.

The predecessor structure is also a pair of two-dimensional arrays, where an entry must be able to represent one of the eight compass directions or an indication for the opposite side of the board. This takes 4 bits per cell, or N*M*8 bits total.

The closed set can be represented by a pair of two-dimensional, single-bit arrays, where a bit is one if the corresponding cell has been searched, and zero otherwise. This will take N*M*2 bits total.

F[x] and G[x] will be similar to the board arrays, but they must contain a 16-bit integer for each cell, requiring N*M*64 bits total. Note that if memory usage needs to be minimized at the cost of increased processing time, we could omit the F[x] arrays, and calculate the F values as they are needed from the G[x] arrays and the heuristic function, H(x).

Breadth-first search thus requires N*M*38 bits, and A* needs N*M*102 bits of static memory. For a printed circuit board 4 x 13 inches (80 cells x 260 cells), breadth-first search will need 98,800 bytes and A* will need 265,200 bytes. Different algorithms that solve the same problem often trade off memory against processing time to achieve better performance. This is the case with A* versus the breadth-first search.</entry>