Adventures in Autorouting (2017)(wp.josh.com)
wp.josh.com
Adventures in Autorouting (2017)
https://wp.josh.com/2017/10/23/adventures-in-autorouting/
37 comments
Autorouting will not work for most things due to the requirement to meet EMC standards. That board you created will not have any chance to pass EMC (at least if it were an automotive product - I guess CE would fly).
If it was going to take them 10 hours to manually route that small board, I think the real problem is just that they are really bad at pcb design.
Autorouting has been getting a bad rap because the autorouter in Altium is total crap. It creates design rule errors while failing to route the board.
But there are good autorouters. Back in the 90s I had a license to PADS, so I had access to Specctra and then Blaze. I still use the version of Blaze I bought then (originally for Windows-98) today. It used for my relay computer:
http://relaysbc.sourceforge.net/
It routes the entire board in about two minutes.
Unfortunately these tools are now very expensive ($6000).
But there are good autorouters. Back in the 90s I had a license to PADS, so I had access to Specctra and then Blaze. I still use the version of Blaze I bought then (originally for Windows-98) today. It used for my relay computer:
http://relaysbc.sourceforge.net/
It routes the entire board in about two minutes.
Unfortunately these tools are now very expensive ($6000).
I understand the frustration, but I can't relate. For me, routing the board is the most fun part. It's like a large puzzle that you have to solve, the result of which is useful to boot!
I keep wanting to design PCBs pretty much just so I can do the routing! That's for small, two-layer PCBs, though. If you had to do eight layers on a huge PCB, I can see how you wouldn't want to be bothered.
I keep wanting to design PCBs pretty much just so I can do the routing! That's for small, two-layer PCBs, though. If you had to do eight layers on a huge PCB, I can see how you wouldn't want to be bothered.
If anyone is interested in working on a fan-out autorouter (and has been before they saw this article), please shoot me an email! <username>@gmail.com
Honestly, for small boards, autorouting just isn't worth the time. Once you do a few layouts, it's very easy to see how everything can fit together.
Also, for some sensitive designs (boost, buck, high speed clock, memory interface etc) you definitely don't want and autorouter doing it, at least the ones that are available to hobbyists.
Would it be a time saver, sure. But for a board like that, we're talking ~15 minutes of saved time. There are much better optimizations to be made (standardized parts libraries) that would save way more time.
Also, for some sensitive designs (boost, buck, high speed clock, memory interface etc) you definitely don't want and autorouter doing it, at least the ones that are available to hobbyists.
Would it be a time saver, sure. But for a board like that, we're talking ~15 minutes of saved time. There are much better optimizations to be made (standardized parts libraries) that would save way more time.
> Honestly, for small boards, autorouting just isn't worth the time. Once you do a few layouts, it's very easy to see how everything can fit together.
That's the point of the article. It should be worth the time. The author feels that after layout it shouldn't take any time to layout the board. Single click and done.
That's the point of the article. It should be worth the time. The author feels that after layout it shouldn't take any time to layout the board. Single click and done.
I use an autorouter as part of my flow, but the final board generally is hand-routed. What I find the autorouter helps a lot with is verifying that I've got sane parts placement. I'll do manual parts placement using my intuition, and then run the autorouter. If the autorouter ends up with 50 routing failures, then I've got nice feedback that the layout is going to be hard to route (and my intuition was wrong). I then focus on the parts it had the most trouble with and tweak.
Then, once the autorouter has successfully routed everything, I tear it up and do hand routing. There's still a few placement tweaks that happen at this stage (considering things like analog vs. digital traces, EMC for clocks/high speed data lines, etc) but I know I'm starting from a reasonable base.
Then, once the autorouter has successfully routed everything, I tear it up and do hand routing. There's still a few placement tweaks that happen at this stage (considering things like analog vs. digital traces, EMC for clocks/high speed data lines, etc) but I know I'm starting from a reasonable base.
Nobody cares about autorouting trivial boards, but there are serious economic incentives to turn 8+ layer boards into 6+ layer boards.
The author makes a strong point in comparing the autorouting problem to the milestone achieved by Alpha Go in defeating some of the strongest human players. These problems are similar enough that the same insights are likely applicable to both.
The first time I ever heard the phrase "Monte Carlo tree search," it took me about five seconds for me to start wondering if it might be applicable to PCB routing.
The author makes a strong point in comparing the autorouting problem to the milestone achieved by Alpha Go in defeating some of the strongest human players. These problems are similar enough that the same insights are likely applicable to both.
The first time I ever heard the phrase "Monte Carlo tree search," it took me about five seconds for me to start wondering if it might be applicable to PCB routing.
No, comparison to Alpha Go was utterly naive.
Where do you get the training set? From thousands of proprietary boards you have full documentation of? The physics rules for the aforementioned difficult tasks, EMI, stripline, race, not to mention all the thermal and mechanical constraints for analog boards is a PhD thesis or four to get the AI auto router to “play itself.”
Wouldn't it be enough to come up with a scoring function for the final routing solution? E.g. number of violations in DRC/ERC + total number of vias + absolute trace length.
No, comparison to Alpha Go was utterly naive.
Where do you get the training set? From thousands of proprietary boards you have full documentation of? The physics rules for the aforementioned difficult tasks, EMI, stripline, race, not to mention all the thermal and mechanical constraints for analog boards is a PhD thesis or four to get the auto router to play itself.
>> Nobody cares about autorouting trivial boards, but there are serious economic incentives to turn 8+ layer boards into 6+ layer boards.
Sure, but if a tool can't route a trivial board like the author had, what hope does it have for doing complex designs?
On a related note, pick up an old arcade game board from the 70's or 80's made by Atari. They're all double sided and are very cleanly routed. The Cinematronic CPU made from 74xx series parts is also double sided and very cleanly routed. In both cases though there is a lot of area not covered by components, but they're still works of art.
Sure, but if a tool can't route a trivial board like the author had, what hope does it have for doing complex designs?
On a related note, pick up an old arcade game board from the 70's or 80's made by Atari. They're all double sided and are very cleanly routed. The Cinematronic CPU made from 74xx series parts is also double sided and very cleanly routed. In both cases though there is a lot of area not covered by components, but they're still works of art.
Sorry, I'm done with responding to people who didn't read the article. It's a cool article, with some worthwhile points to make. Nothing too profound, but worth a few minutes' surfing. Go read it.
I did. Top to bottom.
So, his whole point was exactly what you (and a half-dozen other people in the thread) are bringing up as some kind of revelation that no one considered. Yes, it's true, autorouters suck. Most professional PCB designers think of autorouting as a waste of time, and it typically is.
He's complaining about how autorouters have trouble with trivial boards like the one he was working with. He's pointing out that this is costing the industry a lot of time and money. He's asking why the problem remains largely unaddressed, at a time when computers running relatively generic tree-search algorithms with minimal prior training are beating 9-dan Go players like rented mules.
By trying to call the attention of ML/AI researchers to the issue, he's doing a good thing IMO. No one disputes that a well-routed PCB is a work of art, whether it was done with Altium or rubylith. But it shouldn't be.
He's complaining about how autorouters have trouble with trivial boards like the one he was working with. He's pointing out that this is costing the industry a lot of time and money. He's asking why the problem remains largely unaddressed, at a time when computers running relatively generic tree-search algorithms with minimal prior training are beating 9-dan Go players like rented mules.
By trying to call the attention of ML/AI researchers to the issue, he's doing a good thing IMO. No one disputes that a well-routed PCB is a work of art, whether it was done with Altium or rubylith. But it shouldn't be.
Perhaps I misunderstood. Someone (was it you?) said nobody cares about trivial boards like in the blog, but they do care about complex boards. I took that as a sort of rejection of the relevance of the article. So the point I wanted to make is this: If you're hoping for a tool to do good routing on complex boards, it really should be able to do a great job on simple ones. Hence the blog is entirely relevant by eliminating a bunch of autoroutes based on his simple project.
I applaud him for pointing out how bad most of them are and asking the question why they suck when machines can play GO now.
I applaud him for pointing out how bad most of them are and asking the question why they suck when machines can play GO now.
Perhaps you didn't read the article. Author's example circuit is fairly simple with handful of components. He estimates it would take him 10 hours to do manual routing to satisfy all the constraints. If things were more complex, I can easily see multiple days worth of effort. So, no, problem is not trivial and would save far more time than just 15-minutes.
Double sided PCBs costs almost same as single sided however going from 2 layer to 4 layer literally doubles the cost. Going from 4 layers to 6 layers increases cost by 50%. For boards like Raspberry Pi or Arduino, this could make massive difference if you doing production at scale.
So the problem is very real.
Double sided PCBs costs almost same as single sided however going from 2 layer to 4 layer literally doubles the cost. Going from 4 layers to 6 layers increases cost by 50%. For boards like Raspberry Pi or Arduino, this could make massive difference if you doing production at scale.
So the problem is very real.
I'm not sure if the author is the best reference though - a professional designer with good tooling wouldn't take anywhere near that long.
Professional tools like Altium, Allegro, etc. have really good interactive routing tools, and some pretty cool semi-automatic routing tools where you select groups of nets, plot an approximate routes, and it works out the finer details. This can make routing busses and stuff almost as fast as routing single tracks.
Secondly, sometimes dropping layers isn't an option - given EMI/EMC requirements you're going to need a ground plane in almost all high speed designs (anything over a couple of hundred hundred MHz). So for a lot of designs, four layers is the minimum. Add in impedance control, or RF, and you might need to go to eight (RF microstrip always needs to be next to a ground plane, or stripline needs one above and one below. So you can end up needing a lot of layers especially once you add in power planes).
At the end of the day, it's a trade-off between lots of different factors, and I don't think (for any skilled professional) that the quality of the route would really come into it much...
Professional tools like Altium, Allegro, etc. have really good interactive routing tools, and some pretty cool semi-automatic routing tools where you select groups of nets, plot an approximate routes, and it works out the finer details. This can make routing busses and stuff almost as fast as routing single tracks.
Secondly, sometimes dropping layers isn't an option - given EMI/EMC requirements you're going to need a ground plane in almost all high speed designs (anything over a couple of hundred hundred MHz). So for a lot of designs, four layers is the minimum. Add in impedance control, or RF, and you might need to go to eight (RF microstrip always needs to be next to a ground plane, or stripline needs one above and one below. So you can end up needing a lot of layers especially once you add in power planes).
At the end of the day, it's a trade-off between lots of different factors, and I don't think (for any skilled professional) that the quality of the route would really come into it much...
Or sketch routing: https://www.youtube.com/watch?v=fIi13gI9xEA
Took about 1 second to realize there were no bypass caps on the board. I stopped reading with any depth at that point.
Autorouters meet all physical rules, while violating all electrical rules. Manual routing with the application of push and hug (semi-auto) routing is the way to go. No one just pushes an autoroute button.
Autorouters meet all physical rules, while violating all electrical rules. Manual routing with the application of push and hug (semi-auto) routing is the way to go. No one just pushes an autoroute button.
For sure, in some designs there are some signals that should really be laid manually according to arcane constraints known only to the designing engineer. But even in those cases, the vast majority of the other traces on the board are probably pretty un-demanding low-speed digital signals and would work no matter how they were routed as long as there was an actual physical connection.
My current project uses a physically large but relatively simple board, and I've spent probably a total of two weeks' worth of time hand-routing all of the various iterations in KiCad. It's not difficult once you come up with some basic heuristics, but I sure wouldn't object to having those two weeks back. Even something as simple as the EagleCAD autorouter I used back in the early '00s would have been fine for most of it.
My current project uses a physically large but relatively simple board, and I've spent probably a total of two weeks' worth of time hand-routing all of the various iterations in KiCad. It's not difficult once you come up with some basic heuristics, but I sure wouldn't object to having those two weeks back. Even something as simple as the EagleCAD autorouter I used back in the early '00s would have been fine for most of it.
I've never worked with a board with curvy traces like that before, but I don't think I'd like them. They look a lot harder to debug than straight traces with 90 and 45 degree angles.
Some autorouters have options to only use 45 or 90 degree traces where possible (in fact some of the examples in the link show this behaviour). In a similar vein, I'd like to see an autorouter that also cares about ground plane impedance and continuity: attempting to avoid ground plane islands or regions where clearances prevent ground planes from separating tracks, and even trying to keep ground planes associated with tracks in certain classes (e.g. high speed vs power lines) separated, joining only at the external power supply jack.
But, given the autorouting problem's NP hardness, especially when there are extra constraints like above, I expect that manual routing for anything beyond trivial layouts will continue to be the norm.
But, given the autorouting problem's NP hardness, especially when there are extra constraints like above, I expect that manual routing for anything beyond trivial layouts will continue to be the norm.
Can humans magically solve NP hard problems that computers can't? I don't think so...
Humans make use of the fact that the optimal solution is not necessary (or probably even desirable, given the multitude of parameters to optimize for). By heuristics we can find a good solution that is also understandable to others.
A computer can understand that an optimal solution is not always needed. There is nothing about the problem being NP complete that means the computer HAS to find the optimal solution.
Humans are capable of deriving and applying new knowledge about a problem while solving it. So when confronted with a specific NP hard problem, a human solver applies intuition and thereby restricts the solution space that must be searched significantly. These intuitive rules can be very specific to the problem. There is no good computer algorithm that can do the same combination of creating and applying rules automatically.
I used to use freerouting a lot -- it's 'semi automatic' to be fair, you can hint at stuff, and you need to configure it pretty carefully for it to do a good job...
I used it as a 'first pass' routing, imported the result, deleted anything I didn't like and manually did the rest. Still saves a bundle of time!
I used it as a 'first pass' routing, imported the result, deleted anything I didn't like and manually did the rest. Still saves a bundle of time!
These are the type of articles that makes HN worth looking in to every once in while :). The circuit routing is indeed worth $100M problem. And it's going to remain unsolved in classical sense because its NP-Hard.
The reason this is very interesting problem is that basic version of the problem is fairly easy to specify: You are given bunch of polygons, each with few fixed points on it. You are also given series of sets, each containing list of points that must be connected together. Can you come up with connections that has minimum crossing with each other (see Wikipedia [1] for more formal statement of routing problem).
The more practical version of the problem will include more constraints 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.
Recently Travelling Salesman Problem was attacked using reinforcement learning[2] and that could be a good start to attack routing problem. I'll be definitely looking in to this!
[1] https://en.wikipedia.org/wiki/Routing_(electronic_design_aut...
[2] https://arxiv.org/abs/1611.09940
The reason this is very interesting problem is that basic version of the problem is fairly easy to specify: You are given bunch of polygons, each with few fixed points on it. You are also given series of sets, each containing list of points that must be connected together. Can you come up with connections that has minimum crossing with each other (see Wikipedia [1] for more formal statement of routing problem).
The more practical version of the problem will include more constraints 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.
Recently Travelling Salesman Problem was attacked using reinforcement learning[2] and that could be a good start to attack routing problem. I'll be definitely looking in to this!
[1] https://en.wikipedia.org/wiki/Routing_(electronic_design_aut...
[2] https://arxiv.org/abs/1611.09940
Topor is my go-to tool for small boards. I just start with manually tracing power nets, the rest is autorouted.
Comparing to other routers, Topor gives results almost instantaneously. This is really useful when placing parts: you try something, autoroute (no more than tens of seconds), see result, tweak here and there then repeat.
idk about seriously big boards, but they have examples with mammoth BGA on their site, so at least it is capable of routing those boards.
Comparing to other routers, Topor gives results almost instantaneously. This is really useful when placing parts: you try something, autoroute (no more than tens of seconds), see result, tweak here and there then repeat.
idk about seriously big boards, but they have examples with mammoth BGA on their site, so at least it is capable of routing those boards.
P.S.: near the end of article author lists what autorouter should do and what info (and freedom) we should give to the tool.
I think, the first show-stopper for 100% autorouted designs are power nets (of course, not only power, there are a lot of other corner cases, like thermals, but power is what you encounter right out of the door).
Router should know which nets handle (somewhat)high currents. And which direction the current flows. You do not want your power amp supply rail routed sequentially. And on the other side, not all power nets should be routed as stars (sometimes there is only small power draw, and sometimes it is only voltage sensing).
I think, the first show-stopper for 100% autorouted designs are power nets (of course, not only power, there are a lot of other corner cases, like thermals, but power is what you encounter right out of the door).
Router should know which nets handle (somewhat)high currents. And which direction the current flows. You do not want your power amp supply rail routed sequentially. And on the other side, not all power nets should be routed as stars (sometimes there is only small power draw, and sometimes it is only voltage sensing).
For these simple designs (and more complicated ones), my experience shows me that the problem has been solved with Eagle and a decent design rule file. I have autorouted tens of 2-layer designs with between 5 and 200 components with Eagle's autorouter and the seeedstudio .drc file as constraints. It's good and quick, give it a try (would take a few sec <50 parts, couple of minutes > 100parts)!
BTW nobody professional uses curved traces (except very rare cases), have a look at any electronics PCB
BTW nobody professional uses curved traces (except very rare cases), have a look at any electronics PCB
Is there a good reason that people don’t use curved traces anymore, except that it easier for CAD software?
When traces where done by hand, they used to be curved and flowing, and frequently looked very elegant. And occasionally you see a super high speed design that’s a bit curvy today.
When traces where done by hand, they used to be curved and flowing, and frequently looked very elegant. And occasionally you see a super high speed design that’s a bit curvy today.
I think the answer is the discontinuity you get from a sharp bend is smaller than the highest frequency/wavelength in the signal. So you don't get any reflections off it. The way I think is the length of the wave front heading down the trace is much longer than the size of the bend. I think very high speed stuff can start having trouble with via's.
I think curved traces were used make layout easier when running tape. Bending the tape is easier than doing a cut to shift the trace over.
And safer, a problem with old tape layouts is it's easy enough to knock off a small section of tape. Old draftsman I worked with would check the layout against a blue print on a light table to make sure nothing was amiss before making mods. He also got really antsy if anyone was rummaging around in the drawers holding PCB layouts.
I think curved traces were used make layout easier when running tape. Bending the tape is easier than doing a cut to shift the trace over.
And safer, a problem with old tape layouts is it's easy enough to knock off a small section of tape. Old draftsman I worked with would check the layout against a blue print on a light table to make sure nothing was amiss before making mods. He also got really antsy if anyone was rummaging around in the drawers holding PCB layouts.
High speed designs definitely do not like corners, especially fast serial interconnects are often problematic (they tend to have really high clocks), think PCIe, USB3,...
Sharp curves radiate more than mitered corners. The curves has two unequal current paths; inner and outer radius. Any imbalance results in an inductance. I assume it takes longer to photoplot too as the machine has to interpolate around the curves.