Routers (trackers)

Two classes of routers were implemented: Serial Routers and Global Routers:

Serial Routers

The Layer-Pair Router (not supplied, obsolete)

The original software tracker written was developed as a basis for a hardware implementation of the tracker. It implements a layer-pair algorithm. The layer-pair algorithm uses a pair of layers with opposite biases, and then tries to route as many connections as possible on the pair of layers selected. Any failures are then routed on another layer pair and so on until all layers have been routed on, or there are no failed connections. The original software tracker can be specified using the -o option and the hardware equivalent, by the -h option. Currently the hardware router is not available for general use. Further details may be found in [Spie83], [Spie85], [Spie87]

The Modified Layer-Pair Router - layer_pair

This tracker is essentially the same as the previous tracker but with some bugs corrected and minor changes in the algorithm. The layer-pair structure is retained. The results from this tracker are usually better than that obtained from the original tracker, although improvements are minor. This tracker may also be specified by the -n option.

The True Multilayer Router - mat

The third software tracker available is a true multilayer tracker in which all connections are routed on all the available layers simultaneously (as opposed to routing only on pairs of layers). This tracker may be specified by the -m option. For more than 2 routing layers, this router distributes tracks more evenly between the available routing layers than the layer-pair trackers, and the results are generally better. It is the default tracker.

Global Routers

The Simuated Annealing Router - procore

A global router has been implemented that uses the technique of simulated annealing to perform ripup and rerouting operations. This is a useful facility because it allows the modification of existing routes to make room for unrouted connections. A true multilayer routing algorithm is used to route all the connections. This tracker may be specified by the -a option. A separate version has been implemented that basically employs the same ripup and reroute operations but restricts the size of the search space in an effort to converge to a final solution more quickly. The latter choice can be specified using the -g option.

Critical to the annealing process is the way the initial configuration is determined. By default, the annealed tracker determines an appropriate starting solution internally. The user can overide this default by specifying another initial tracker on the command line. This initial tracker is then used to determine the starting configuration for the annealed router.

A characteristic of the global routers are their non-deterministic nature. Rerouting a board with the same annealing parameters and board layout may not give the same results as previously obtained. It may be possible therefore to obtain a better result by re-running the annealed router on the same data.

For performance reasons, buried-vias are not allowed when using the global routers.