Routing (electronic design automation)

The task of all routers is the same. They are given some pre-existing polygons consisting of pins (also called terminals) on cells, and optionally some pre-existing wiring called preroutes. Each of these polygons are associated with a net, usually by name or number. The primary task of the router is to create geometries such that all terminals assigned to the same net are connected, no terminals assigned to different nets are connected, and all design rules are obeyed. A router can fail by not connecting terminals that should be connected (an open), by mistakenly connecting two terminals that should not be connected (a short), or by creating a design rule violation. In addition, to correctly connect the nets, routers may also be expected to make sure the design meets timing, has no crosstalk problems, meets any metal density requirements, does not suffer from antenna effects, and so on. This long list of often conflicting objectives is what makes routing extremely difficult.

Almost every problem associated with routing is known to be intractable. The simplest routing problem, called the Steiner tree problem, of finding the shortest route for one net in one layer with no obstacles and no design rules is known to be NP-complete, both in the case where all angles are allowed or if routing is restricted to only horizontal and vertical wires. Variants of channel routing have also been shown to be NP-complete, as well as routing which reduces crosstalk, number of vias, and so on. Routers therefore seldom attempt to find an optimum result. Instead, almost all routing is based on heuristics which try to find a solution that is good enough.

Design rules sometimes vary considerably from layer to layer. For example, the allowed width and spacing on the lower layers may be four or more times smaller than the allowed widths and spacings on the upper layers. This introduces many additional complications not faced by routers for other applications such as printed circuit board or multi-chip module design. Particular difficulties ensue if the rules are not simple multiples of each other, and when vias must traverse between layers with different rules.

Types of routers

The earliest types of EDA routers were "manual routers"—the drafter clicked a mouse on the endpoint of each line segment of each net. Modern PCB design software typically provides "interactive routers"—the drafter selects a pad and clicks a few places to give the EDA tool an idea of where to go, and the EDA tool tries to place wires as close to that path as possible without violating design rule checking (DRC). Some more advanced interactive routers have "push and shove" (aka "shove-aside" or "automoving") features in an interactive router; the EDA tool pushes other nets out of the way, if possible, in order to place a new wire where the drafter wants it and still avoid violating DRC. Modern PCB design software also typically provides "autorouters" that route all remaining unrouted connections without human intervention.

The main types of autorouters are:

• Maze router
  • Lee router
  • Hadlock router
  • Flood router
• Line-probe router
  • Mikami–Tahuchi router
  • Hightower router
• Pattern router
• Channel router
  • Switchbox router
  • River router
  • Spine and stitch router
• Gridless router
  • Area router
  • Graph theory-based router
    • Bloodhound router (CADSTAR by Racal-Redac / Zuken)
    • Specctra (aka Allegro PCB Router) (gridless since version 10)
  • Topological router
    • FreeStyle Router (aka SpeedWay, a DOS-based autorouter for P-CAD)
    • TopoR (a Windows-based autorouter, also used in Eremex's Delta Design)
    • Toporouter (Anthony Blake's open-source router in PCB of the gEDA suite)
    • TopRouter (the topological pre-router in CadSoft/Autodesk's EAGLE 7.0 and higher)
    • SimplifyPCB (a topological router with a focus on bundle routing with hand-routing results)