Autorouters: gEDA pcb Toporouter - bert/pcb GitHub Wiki
Topological Autorouter
(Retrieved from: https://web.archive.org/web/20110227055406/http://anthonix.resnet.scms.waikato.ac.nz/toporouter/ , no pictures available)
Introduction
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.
Updates
See here for a sneak preview of trace length matching. I am proposing to complete TOF matching and vias as part of this years summer of code.
Results
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:
- Vias were turned off, and the results are a measure of single layer performance.
- Although the original code supported vias, the new code still requires work on the CDT to support my plans for improved performance. In any case, the results are more interesting if the router can’t just via its way through a problem. Although indications of runtime performance are given, it should be noted that the autorouter is highly optimized and the toporouter is highly unoptimized. Like Donald Knuth says, "premature optimization is the root of all evil". The results were obtained on an Intel E5300.
- The autorouter output has been left as rectilinear geometry. I believe most people transform it to octilinear wiring after autorouting, with the mitre function.
Puzzle
Puzzle (unrouted / autorouted / toporouted)
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.
Laser Diode Current Driver
Laser Diode Current Driver Board (unrouted / autorouted / toporouted)
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.
Photo Diode Receiver
Photo Diode Receiver (unrouted / autorouted / toporouted)
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.
Meggy Jr RGB
Meggy Jr board unrouted]()
Meggy Jr board autorouted]()
Meggy Jr board toporouted A]()
Meggy Jr board toporouted B]()
Meggy Jr board toporouted C]()
Meggy Jr RGB (unrouted / autorouted / toporouted (A) / toporouted (B) / toporouted (C))
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.
Altera FLEX 6024A Protoboard
Altera FLEX 6024A Protoboard unrouted
Altera FLEX 6024A Protoboard autorouted
Altera FLEX 6024A Protoboard toporouted
Altera FLEX 6024A Protoboard (unrouted / autorouted / toporouted)
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.
R8C/27 DIP Adapter
R8C/27 DIP Adapter (unrouted / toporouted)
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.
PPS splitter
PPS splitter (unrouted / autorouted / toporouted)
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
Linksys Power
Linksys power board autorouted
Linksys power board toporouted
Linksys Power Board (unrouted / autorouted / toporouted)
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.
Laminator Temperature Controller
Laminator Temperature Controller Board (unrouted / autorouted / toporouted)
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.
Beer Temperature Controller
Beer Temperature Controller Board (unrouted / autorouted / toporouted)
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.
Flare Genesis Board
PCB example board (unrouted / autorouted / toporouted)
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.
Random Board
Random board (unrouted / autorouted / toporouted)
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.
Status
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.
Credits
Eric Brombaugh - Web page style.
Peter Clifton - PCB colour scheme.
Last Updated: July 7, 2009
Comments to: Anthony Blake
Detour Optimization
(Retrieved from: https://web.archive.org/web/20110227055406/http://anthonix.resnet.scms.waikato.ac.nz/toporouter/detour.html , no pictures available)
The new detour optimization is more inclined to rip up in order to optimize.
The following is a selection of boards comparing the differences.
In all cases, the optimization improved the wiring, and sometimes resulted in a higher net completion rate.
In most cases, the runtime increased, however in others, such as the Meggy Jr, the runtime decreased as the router closed in on a solution faster.
The laminator had fewer successful nets, but those that were successful had better detours.
In some cases, applying the detour optimizations at an earlier stage produced even better results, as shown in the Meggy Jr and LED results.
In some other boards the results were worse. The further possible optimization will be explored later with probabilistic algorithms and machine learning.
Flare Genesis
Flare Genesis (autorouted / toporouted A, B, C)
| Router | Total Nets | Completed Nets | Wiring Length (inches) | Runtime (seconds) |
|---|---|---|---|---|
| Autorouter | 123 | 123 | 60.7064 | << 1 |
| Toporouter (before optimization) | 123 | 123 | 52.7943 | 2.724 |
| Toporouter (detour optimization) | 123 | 123 | 49.3204 | 3.248 |
| Toporouter (best optimization) | 123 | 123 | 47.9989 | 3.542 |
Meggy Jr
Meggy Jr (autorouted / toporouted A, B, C)
| Router | Total Nets | Completed Nets | Wiring Length (inches) | Runtime (seconds) |
|---|---|---|---|---|
| Autorouter | 158 | 145 | 194.4455 | ~6 |
| Toporouter (before optimization) | 158 | 158 | 190.8683 | 44.966 |
| Toporouter (detour optimization) | 158 | 158 | 188.7315 | 42.496 |
| Toporouter (best optimization) | 158 | 158 | 160.0793 | 51.541 |
Test
Test (autorouted / toporouted / toporouter with detour optimization)
| Router | Total Nets | Completed Nets | Wiring Length (inches) | Runtime (seconds) |
|---|---|---|---|---|
| Autorouter | 11 | 11 | 9.9016 | ~2 |
| Toporouter (before optimization) | 11 | 11 | 8.9696 | 0.332 |
| Toporouter (detour optimization) | 11 | 11 | 8.3151 | 0.424 |
Last Updated: July 7, 2009
Comments to: Anthony Blake
Snippets
Snippet #1
PCB includes a topological autorouter named Toporouter, developed by Anthony Blake in a Google-funded open source project mentored by DJ Delorie in 2008.
It is mostly based on an implementation of the algorithms described in Tal Dayan's 1997 PhD thesis, "Rubberband based topological router".
This router has meanwhile been adapted for use with the open-source KiCad project as well.
Snippet #2
If you want to have a play with new parameters, hybrid_router() in toporouter.c would be a good place to start.
From there you can change stuff like the thresholds for ROAR, number of iterations, termination conditions (effort), order and frequency of wiring optimization passes.
the results can sometimes be quite interesting even with minor modifications.
Just be careful not to waste too much time tuning for a specific board.
I guess if someone had some time it wouldn't be too hard to push all that stuff through to a dialog in PCB.
-Anthony
Snippet #3
OK, --enable-toporouter-output is for debugging.
But for PCB20091103 I do see no difference if built with --enable-toporouter-output or --disable-toporouter-output.
I have checked with GTK and Lesstif GUI and tut1.pcb -- final routing result is fine when traces are copied back to pcb program.
(Filesize of PCB program is increased with --enable-toporouter-output, so it has an effect. grep command shows me cairo operations in ifdef TOPO_OUTPUT constructs, so it is not a fake.)
It there only a visible effect of --enable-toporouter-output for the experimental OpenGL branch? Or only if --enable-debug is set at the same time?
Best wishes,
Stefan Salewski
Snippet #4
All my knowledge is from this list: toporouter works more or less fine with boards with no existing traces.
So I used tut1.pcb, deleted all existing traces and polygons (all in top and bottom layer), pressed key "O" to optimize rats nest and :toporouter().
Toporouter uses the active layers for traces, so I deactivate layers called "unused" before.
Generally in less than one minute toporouter is finished and traces are drawn in PCB board.
Stefan Salewski