Routing programs are one of the major automated processes for converting the symbolic representation of circuits into a physical design or layout. After combinational logic blocks have been placed, it is necessary to connect, or wire, them to one another, being sure not to route over other connections, pins, or miscellaneous blockages. This complicated task is accomplished by using a routing program such as our Highly Optimized Routing Engine (HORE). HORE uses a ripup and reroute algorithm to find low cost wiring solutions, those solutions with the fewest number of vias, bends, overloaded nodes and small total wire length. This is also done quickly buy utilizing a highly tuned, hand-optimized mazerouter for finding the wiring paths.

The fundamental routing algorithm behind HORE is the mazerouter with path dependent penalty functions and path history dependent penalty functions. The mazerouter requires two pieces of information: a grid and a netlist. A grid consists of the placed logic (fixed pins) and empty grid cells through which wires route. A netlist consists of the information defining which pins should be connected together as a single net. The mazerouter uses these two files to determine how to route the connections from one pin to another.

Using the netlist, the mazerouter finds a source pin and a target pin and expands, or searches, the grid to find a "cheap" routing solution to get from the source to the target. The cost of a route is calculated by determining several characteristics of this path, such as total length, number of bends, number of vias, wrong way costs, etc. The ideas is that the shortest route and the one with fewest bends and vias is the most desirable. Wrong way costs are used to assign a directional preference to the wiring plane so that some planes tend to have wires running in the vertical direction while the others tend to have wires running in the horizontal direction. Assigning penalty costs to undesirable behaviors helps the mazerouter find better wiring solutions.

The powerful part of HORE is the ripup and reroute algorithm. The idea here is that once the routing has been done once, we can redo the routing, one net at a time, to find a better solution. This can be done several times, each pass finding better routing solutions. In addition, the mazerouter can now take advantage of path history dependent penalty functions. Path history dependent penalty functions can vary the cost of undesirable behavior non-linearly. That is that cost can be varied proportional to the number of occurrences on a given net, instead of a statically assigned cost for all nets. This technique dramatically reduces the amount of overflows, those grid cells on which more than one net routes through, in the final wiring solution.