Despite the massive advances in technology over the last few decades, many circuit boards are still partially or completely layed out by hand. Rather than using computers as drawing tools, we should be using them as computers.
The topological autorouter began as a project funded by Google and mentored by DJ Delorie in 2008. The goal was to create a topological autorouter for the gEDA suite of open source hardware development tools, mostly implementing the algorithms described in Tal Dayans PhD thesis, "Rubberband based topological router".
The resulting code demonstrated the capability of the topological algorithms by solving some simple and contrived problems which geometric routers typically fail. The algorithms excelled when presented with many layers of free (chanelless) wiring space, by being able to via through the problem. Unfortunately, when applied to typical PCB problems, and especially when constrained to few layers and with dense constraints, the results were poor.
Since the initial project, a new topological autorouter has been started. Rather than stabilize and document the first attempt, I decided my time would be better spent starting from scratch and addressing some of the shortcomings of the first implementation. PCB already has a highly optimized an efficient autorouter developed by Harry Eaton and C. Scott Ananian, and I was doubtful the first implementation could produce better results in most situations.
Some results for a new detour optimization are available. Wiring length for boards such as LED and Meggy Jr are reduced by a about 5 and 30 inches, respectively.
The following sections demonstrate the code (available in the git repository). Please keep the following in mind when looking over the results:
This simple contrived layout demonstrates the power of topological autorouters over geometric autorouters. Geometric autorouters trying to route the nets with a shortest path will obstruct at least one of the nets, resulting in failure. The runtime of each router was << one second. The toporouter runtime was 0.08 second.
This board is from a laser diode current driver with modulation capability, designed by Kai-Martin Knaak. It contains 51 nets, and was completely routed by the toporouter and the autorouter. The autorouter runtime was < 1 second and the toporouter runtime was 0.135 second.
This board is a very low noise DC to MHz photo diode receiver, designed by Kai-Martin Knaak. It contains 142 nets. The autorouted ran for about 4 seconds and failed 30 nets, while the toporouter ran for 6.248 and failed 28 nets.
The Meggy Jr RGB is a platform to develop handheld pixel games, developed by Evil Mad Scientist Laboratories. It contains 158 nets. The autorouter ran for about 6 seconds and failed 13 nets. Three different runs of the toporouter with subtle variations in the algorithms (the algorithms are *not* probabilistic though) produced three different results, all which were fully routed. The first two solutions required a runtime of approximately 45 seconds, while the third had a runtime of about 35 seconds.
See the detour optimizations for an improved Meggy Jr board.
The Altera FLEX 6024A Protoboard is designed by Ben Jackson and contains 269 nets. The autorouter ran for about 27 seconds and failed 43 nets, while the toporouter ran for 89.833 seconds and failed 35 nets.
This is an adapter for R8C/27 TQFP-32 (0.8mm pitch) chips, designed by DJ Delorie. It contains 44 nets to route. The autorouted failed all nets, because it does not support the unusually angle pads. The toporouter routed 41 nets in 0.888 second.
This is a splitter for PPS and NMEA signals received from a GPS, designed by Rafael Whyte. It contains 158 nets to route. The autorouted ran for about 9 seconds, and failed 48 nets, while the toporouter ran for 65.929 and failed 31 nets
This board was designed by DJ Delorie, and contains 69 nets to route. The autorouter runtime was approx. one second, and failed eights nets. The toporouter runtime was 4.79 seconds, and failed two nets.
This board was designed by DJ Delorie to add digital temperature control to an otherwise fixed-temperature laminator (or other heating device). The board contains of 111 nets to route. The autorouter runtime was approx. two to three seconds, and failed seven nets. The toporouter runtime was 10.248 seconds, and failed two nets.
This board is a temperature controller for beer brewing designed by Sam Bartels. It is constrained to one layer and contains 72 nets to route. The autorouter took approx. one second and failed eight nets. The toporoute routed all nets successfully with a runtime of 0.853 second.
The Flare Genesis board by Harry Eaton is contained in the PCB source code as the standard example board. The board contains 123 nets to route. The autorouter takes less than one second and routes all nets. The toporouter runtime was 2.318 seconds and routed all nets.
See the detour optimizations for an improved flare genesis board.
This board was submitted by Dima Kogan to the bug tracker in 2008 to illustrate a problem with the autorouter which has since been fixed. The board contains 63 nets to route. The autorouter runtime was approx. one second and six nets failed routing. The toporouter runtime was 1.879 seconds and all nets were routed.
2009-06-27 - One pass curvilinear wiring.
2009-06-27 - Multiple traces on constraint edges.
2009-07-02 - Greedy ROAR routing and optimization.
2009-07-02 - Replaced last years outdated webpage.
2009-07-06 - Rewrote cluster code, speccut code. LED board before changes.
2009-07-07 - Detour optimization.
Eric Brombaugh - Web page style.
Peter Clifton - PCB colour scheme.
