EEVblog Electronics Community Forum

Electronics => PCB/EDA/CAD => KiCad => Topic started by: timofonic on August 26, 2015, 06:50:50 pm

Title: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on August 26, 2015, 06:50:50 pm
Hello.

I found the following projects related to PCB autorouting. How are they in terms of functionality?

The common saying is that PCB autorouting is like black magic and just a few big companies managed to make it somewhat work.

Why is PCB autorouting so difficult to manage efficiently? Where's the problem behind it? Why are there still issues about it after so many years? Or is the research just fine by private companies and kept their algorithms secret?

I know what happened about Zuken and FreeRouting. Despite its coded in Java, it looked promising.


Just for information, some URLs about PCB autorouting projects;

https://github.com/markemer/pcb/blob/master/src/toporouter.c

http://apt.cs.manchester.ac.uk/projects/tools/mucs-pcb/

http://www.ssalewski.de/Router.html.en

https://github.com/markemer/pcb/blob/master/src/autoroute.c

https://github.com/sephamorr/FreeRoute

https://github.com/iank/route1

https://github.com/vygr/C-PCB



Kind regards.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: BloodyCactus on August 26, 2015, 06:53:28 pm
i use freerouting. I grabbed the source when it came up about the zuken takedown. built it to run locally (no webstart etc needed), the others I cant comment on.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: free_electron on August 26, 2015, 06:54:17 pm
the definition of the problem is very simple : you are trying to solve the 'travelling salesman problem' , except you are doing it for thousands of salesmen travelling at the same time and they can't use the same roads ... throw in rules for certain roads to be the same length and rules to keep certain roads specific distances away from others and how many bridges you can built between point a and b ... and you can imagine how the complexity simply explodes...

There is only one router that really works and that is SPECCTRA. And even that is a bitch to control and set up and get anything useful out of it.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: janoc on August 26, 2015, 07:03:52 pm
Yo and a little detail - traveling salesman is most likely NP-hard too, so writing an autorouter that will actually do its job and finish in a reasonable time is pretty much black magic.

Then you have pesky domain-specific details that an experienced board designer will know but autorouters generally don't - like don't run weak ADC input traces next to the main Vcc rail. It is a much more complex problem than just routing few lines and making sure they don't cross.

Autorouter is not something that a hobbyist or someone working on an open source project in their free time is likely going to have resources and knowledge to tackle - that's why there are no decent ones around.

@Circuiteromalaguito, if you are looking for a "push a button for a ready to manufacture board" type of solution, better spend the time elsewhere - even the expensive commercial autorouters are not anywhere near to that sort of ability yet, unless you are doing very simple boards (but then why to use autorouter?).
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: marshallh on August 27, 2015, 03:39:43 am
I have used both freerouting and ELECTRA, freerouting produces superior results for small boards with zero effort.
ELECTRA scales to large boards well, but does need a lot of care and feeding to produce something meaningful.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: rs20 on August 27, 2015, 04:13:47 am
Autorouting is not the travelling salesman problem at all, because the complexity in TSP is in finding the one and only optimal solution. Meanwhile, autorouters just have to find a solution that conforms to certain geometric constraints (tracks mustn't intersect), a problem which TSP isn't concerned with at all. TSP is really hard with 2000 points, right? I can write you an autorouter right now that can instantly connect 2000 points (all on the same net) on a PCB right now easily. TSP is one continuous, unbranching path. Autorouters are allowed to branch.

So no, there's basically nothing at all in common between TSP and autorouting. TSP doesn't even operate in a cartesian space, it's on a graph.

The misapprehension about TSP aside, autorouters need a lot of careful training before they can be useful -- "these are power rails, they should be short and thick". "This chip should have no signal lines running under it". "These are delicate analog signal traces that should be kept far away from the switching power supply". "The ground plane shouldn't be interrupted unnecessarily". It's very hard a) for the user to teach the autorouter all this, and b) for the autorouter to be able to take this all into account. Just the UI for the human-machine interaction there is a pain. It's one of those really ill-defined problems that benefits from man-years of hacky little adjustments and special cases and painstaking, expensive development. And even when an autorouter is done well, it requires a great deal of user configuration to actually work well. Which is why completely autorouting a board from scratch should never be done; you'll spend more time teaching the computer how to route certain parts than how long it'd take you to do yourself. Now if you have already routed your power lines and CPU and all that, and all you have left is 250 lines from shift registers than lead to 250 LEDs, then you're in autorouter territory. And even a fairly dumb autorouter will do well in thus circumstances. Routing CPUs to PCI express slots and memory slots is another example where autorouters shine, although those autorouters have 8 or more PCB layers to work with and undoubtedly that's not what you're planning to do.

Oh, and also, autorouting on even just a 4 layer board is much better than a 2 layer board. Once you have four layers, fairly trivial strategies like "Layer 1 is signals running horizontal, Layer 2 is ground, Layer 3 is power, Layer 4 is signals running vertical" work quite nicely.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: zapta on August 27, 2015, 04:29:10 am
the definition of the problem is very simple : you are trying to solve the 'travelling salesman problem' , ...

Minimal Steiner tree is a closer problem because you are allowed to introduce junction points. And then you have the obstacles, dependencies between nets (one blocking the other) and multi layers.

It was shown that the hard part of routing is finding the topology of the traces (how they go in relation to pads, obstacles and to each other). Once this is determined, assigning exact x/y locations to the traces can be done algorithmically fast in polynomial time. IIRC Altium is using a topological router.

This guy designed a topological router  http://www.ssalewski.de/Router.html.en (http://www.ssalewski.de/Router.html.en) . You can see how he cares only on the topological aspects of the routing, representing the wires as rubber bands.

Arduino Blinky is much more fun IMO.

(http://www.ssalewski.de/rpics/pic046.png)



 
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on August 27, 2015, 04:37:01 am
Autorouting is not the travelling salesman problem at all, because the complexity in TSP is in finding the one and only optimal solution. Meanwhile, autorouters just have to find a solution that conforms to certain geometric constraints (tracks mustn't intersect), a problem which TSP isn't concerned with at all. TSP is really hard with 2000 points, right? I can write you an autorouter right now that can instantly connect 2000 points (all on the same net) on a PCB right now easily. TSP is one continuous, unbranching path. Autorouters are allowed to branch.

So no, there's basically nothing at all in common between TSP and autorouting. TSP doesn't even operate in a cartesian space, it's on a graph.

The misapprehension about TSP aside, autorouters need a lot of careful training before they can be useful -- "these are power rails, they should be short and thick". "This chip should have no signal lines running under it". "These are delicate analog signal traces that should be kept far away from the switching power supply". "The ground plane shouldn't be interrupted unnecessarily". It's very hard a) for the user to teach the autorouter all this, and b) for the autorouter to be able to take this all into account. Just the UI for the human-machine interaction there is a pain. It's one of those really ill-defined problems that benefits from man-years of hacky little adjustments and special cases and painstaking, expensive development. And even when an autorouter is done well, it requires a great deal of user configuration to actually work well. Which is why completely autorouting a board from scratch should never be done; you'll spend more time teaching the computer how to route certain parts than how long it'd take you to do yourself. Now if you have already routed your power lines and CPU and all that, and all you have left is 250 lines from shift registers than lead to 250 LEDs, then you're in autorouter territory. And even a fairly dumb autorouter will do well in thus circumstances. Routing CPUs to PCI express slots and memory slots is another example where autorouters shine, although those autorouters have 8 or more PCB layers to work with and undoubtedly that's not what you're planning to do.

Oh, and also, autorouting on even just a 4 layer board is much better than a 2 layer board. Once you have four layers, fairly trivial strategies like "Layer 1 is signals running horizontal, Layer 2 is ground, Layer 3 is power, Layer 4 is signals running vertical" work quite nicely.

Couldn't a PCB autorouter be collectively trained and learn in some way plus having a component library with useful metadata (this chip needs specific routing, take care of power lines, these RF stuff must be fine in certain way...), then submit that training data somewhere and improve it based on "big data"? And even make it learn from  manual routing.

I know it's an insane idea and just thinked about OCR and speech recognition systems. Maybe some kind of weak AI could be applied here?

I'm a total layman, just speculating and very curious about why it's so difficult.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: rs20 on August 27, 2015, 06:28:21 am
You should have a look at a PCB netlist file... it's just "there's a chip called U1, it has package TQFP-48, and pin 1 connects to the net called "Net-U1-1", pin 2 connects to the net "+5V", etc etc. Obviously in a machine-readable text-format, but that's the gist of it. An AI can't glean anything from that (aside from making assumptions based on the name of the nets, which is just a horrible idea), even a human would have to either make the name-based assumption, or reverse-engineer the original schematic to understand what net is actually doing (complete with reading component datasheets). You think an AI can handle this when 99.9% of humans aren't able to?

I'm not sure if you're saying that you're a layman with respect to software engineering, or PCB layout as well. But if you're a software layman, this doesn't need to be a mystery to you. I'd encourage you to imagine teaching another layman how to do PCB layout, since a computer is the ultimate extremely fast, pedantic, stupid layman. Try to imagine a list of written-out instructions that you could hand to a temp worker to do PCB layout. Because a computer program is just that, a written-out pile of instructions.

Regarding machine learning and AI, you perhaps appear (like many) to think that AI is some sort of magical panacea that just solves any problem. But the problems you mentioned (OCR, speech recognition) are recognition problems: take a large file (image of words, or speech audio) and output text (which has precisely one correct answer). In the case of image recognition, the successive layers in the neural net recognise progressively more complex/higher level concepts -- lines/bends, then junctions and loops, then digits. Similar for audio. PCB autorouting as a huge space of different-looking but essential equally acceptable outputs, so the solution is not unique; the output is a huge amount of data because it's a fully routed board, not some condensed text output; and it's really hard for me to imagine what the different layers of the neural net would be doing. What does the first layer of the neural net do?

One last thought: 4 year old humans can do OCR and speech recognition. They can't lay out PCBs better than autorouters.  Just imagine trying to teach a 4 year old to route a PCB, and you should have a good sense of what trying to program a computer is like.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Bassman59 on August 27, 2015, 07:24:58 pm
Couldn't a PCB autorouter be collectively trained and learn in some way plus having a component library with useful metadata (this chip needs specific routing, take care of power lines, these RF stuff must be fine in certain way...), then submit that training data somewhere and improve it based on "big data"? And even make it learn from  manual routing.

The time you spend specifying all of the various layout constraints is better spent doing something else -- like, perhaps, doing the layout work manually.

Here's the problem I see with the whole notion of hobbyist autorouters:  In order to get useful output from the autorouter, the designer needs to fully understand the design requirements and all of the specialist layout rules. This requires experience.

The hobbyist thinks that all he needs to do is just hand the netlist and the board size off to the autorouter and a high-quality board layout, better than the person can do manually, will pop out. But perhaps this hobbyist doesn't have the experience required to know what defines "high-quality board layout," so he can't properly constraint the autorouter, and the result is basically the same thing he'd get if he did it manually.

In other words, just expecting a high-quality result from the autorouter when you don't know what that means is a mistake.

I will offer the following comparison: lots of people complain about the lack of open-source FPGA synthesis and place-and-route tools. The problem domain for FPGA tools and PCB autorouters is highly similar. It's very complex work that requires disparate skills -- programming, obviously, but also a full understanding of the problem domain. The handful of people (compared to the number of skilled application programmers) who can do this work have a simple choice: a) do it as an open-source project, and maybe make a name for yourself, or b) work for Cadence or Mentor Graphics and get paid a nice salary and let someone else handle the marketing and support.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: nctnico on August 27, 2015, 07:29:51 pm
Couldn't a PCB autorouter be collectively trained and learn in some way plus having a component library with useful metadata (this chip needs specific routing, take care of power lines, these RF stuff must be fine in certain way...), then submit that training data somewhere and improve it based on "big data"? And even make it learn from  manual routing.

The time you spend specifying all of the various layout constraints is better spent doing something else -- like, perhaps, doing the layout work manually.
That thought has kept me from attempting to use an autorouter with SMD boards. I think I autorouted one SMD board but I wasn't satisfied with the result. Back in the IC-in-DIP-package days I used the autorouter in Protel Autotrax a lot but it took a lot of tweaking to get useful results. And in many cases doing the last 3% of the traces and tidying up the power distribution took a lot of time as well.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: free_electron on August 27, 2015, 07:52:33 pm
Autorouting is not the travelling salesman problem at all, because the complexity in TSP is in finding the one and only optimal solution. Meanwhile, autorouters just have to find a solution

Quote

whoa ... ever heard of daisy chain routing ?

try doing any kind of high speed bus : they are all daisy chain routing.
You try routing a bank of DDR3 or DDR5 memory .. or USB3 or HDMI or multilane PCI express or any other modern interface. Try that on a very dense board where busses have to come from the other side of the board and weave around hundreds and thousands of other traces, components and via's , all the while throwing in limitations in terms of the number of via's that are allowed.


An unconstrained router is not hard to do. it simply barfs traces everywhere, as long as electrical connectivity is met it's ok. That is why 99% of the autorouted boards look like crap. click a button and the spaghetti is ready.

Set up the router with a few thousand rules and things become very hard very quickly. To the point it takes weeks to set up the router and prepare the board to even attempt a first trial run... that then takes a whole night to run and bombs out at 25% .. completion. so you can go back and tweak the placement and pre-routes much more to try another attempt a few days later. and keep at it for a few months.  Then we'll talk about how complex it is to drive an autorouter.



Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: ScribblesOnNapkins on August 28, 2015, 01:34:29 pm
The real question is will any router closed or open source ever actually prove useful. For digital stuff maybe they can do the bulk work of doing buses but still.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Bassman59 on August 28, 2015, 08:45:45 pm
The real question is will any router closed or open source ever actually prove useful. For digital stuff maybe they can do the bulk work of doing buses but still.

At a previous job where some of the products were multiple-CPU processor boards, the layout gang would use specctra for the processor memory and PCI etc bus routing. Doing a couple hundred matched-length lines by hand is a royal pain in the ass. The autorouter could do it in minutes. The rest of the board was routed by hand.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on August 29, 2015, 02:00:46 pm
Hi folks, I'm the author of https://github.com/vygr/C-PCB.

I just wanted to do this as it was a technical challenge, I did the dsn import prog so I could test against a friends shower room controller board files :)

I can route his board at 2-Layers in 1 second on the default settings, although more complex settings push that time up a little. There are a lot of paramaters to control direction vectors, wire grouping, Z transition cost and so forth to play around with, as well as various distance metrics worth trying. Viewer output can be alpha'd coloured layers or a Gerber style PCB copper mask for each layer. You can view the route in realtime as it calculates or view an animation too.

It uses glfw3 lib for the viewer, but the rest is plain old c++11/14 so should be easy to build on most systems for anyone that wants to play with it.

Not had much exposure to bigger test files, and the dsn importer was done by reverse engineering the spec via just looking at the dsn files :)

Best regards to all.

Chris

ps. I might be slow to reply as I'm of on holiday for a while, so excuses my tardiness !
pps. Why not take a look at the prog and maybe give it a few Github stars :)

Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on August 30, 2015, 12:49:22 am
Thanks a lot for your reply!

I'm the guilty of making you post here, I confess it!

I think it's a good idea to make your project gain visibility, suggestions, testing and possible collaborators.

Maybe the perfect autorouter isn't possible to do, but maybe there could be an Open Source one in the future that could compete with the propietary ones.

I really hope your project becomes this one!

I'll try your project soon, as I need to learn KiCad and would like to do autorouter as a way of testing. They are easy designs, but I'll provide feedback.

Anyway....

Could anyone try C-PCB with deferent designs in terms of complexity and compare it with good quality manual routing? Maybe this could provide interesting feedback.

I'm not skilled to make a complex PCB, I'm to newbie at electronics :(
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: zapta on August 30, 2015, 03:10:38 am
I use the eagle auto router on every project. I first route manually the critical nets and then let the auto router do the rest. I care about functionality, not traces aesthetics.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: rs20 on August 30, 2015, 04:30:27 am
I use the eagle auto router on every project. I first route manually the critical nets and then let the auto router do the rest. I care about functionality, not traces aesthetics.
If you're doing, for example, an audio amp with a SMPS, all your nets are "critical" to some extent.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: zapta on August 30, 2015, 05:14:06 am
I use the eagle auto router on every project. I first route manually the critical nets and then let the auto router do the rest. I care about functionality, not traces aesthetics.
If you're doing, for example, an audio amp with a SMPS, all your nets are "critical" to some extent.

I don't  ;-)

Mostly MCU stuff.  Roughly %25 of my nets are critical (power, crystal, USB lines, etc).  I also use the auto router to evaluate component placement.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on November 06, 2015, 06:51:16 pm
Hello.

Are there someone working on this?

Kind regards.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on November 07, 2015, 04:00:28 pm
I don't know what it is doing, but C-PCB is unable to route my design, where freerouter has done it in a snap  :-//

(Hu? we can't direct attach DSN files? o_O)

The two images are the hand routed version in 3D view without the solder mask, I can do it better for sure, and remove the two via on the board, but I'm lazy... :D
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on November 07, 2015, 11:02:38 pm
I don't know what it is doing, but C-PCB is unable to route my design, where freerouter has done it in a snap  :-//

(Hu? we can't direct attach DSN files? o_O)

The two images are the hand routed version in 3D view without the solder mask, I can do it better for sure, and remove the two via on the board, but I'm lazy... :D

Can you show the results by both C-PCB and Freerouter? It could be interesting to see them :)

OSHW retrocomputing? We need a retro section in eevblog, I'm also a retrocomputer/retrogaming fan ;)
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on November 07, 2015, 11:13:49 pm
Here are the results of freerouter, keeping the planes I've done manually for the routing I made by hand, the result without is better than when I don't keep them, but I'm not really fond of it. I will join the result of freerouter without the planes.

And for C-PCB, no results at all, I get nothing interesting I don't know why.

Edit: I've added the result without the planes, this one is really ugly
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on November 08, 2015, 01:52:33 am
I hope C-PCB developer read this, maybe he can find why...

Do you want to add this as an issue?

https://github.com/vygr/C-PCB/issues
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 10, 2015, 08:44:31 pm
Hey folks, C-PCB hasn't had a huge test with various DSN files ! If fact it only had two board designs to test with and I reverse engineered the DSN format so can't say for certain that I got it correct !

However I would be interested to look at the DSN file and see why nothing happens at all if you could get a copy to me for testing ?

When you tried it did it run the test files OK before you ran your own DSN file ? Just as a sanity check.

Can you send me a copy via the Github project maybe ?

Best regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 10, 2015, 08:50:34 pm
I've grabbed the Oric_mouse.dsn file and I'll have a look at the weekend to see if I can find the issue.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: free_electron on November 10, 2015, 08:59:10 pm
yuckkk. Look at all the whacky pad terminations... what a pile of garbage.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 10, 2015, 09:19:48 pm
Hi folks, just had a quick look before I have to turn in for the night. Looks like it completely gets the parsing of the DSN file wrong ! So no surprise the router prog gets nowhere. I didn't expect it to work on any other dsn file currently so this is no surprise to me :)

If I have permission from the owner I'll use the Oric_mouse.dsn file as a test dsn and try sort out my dsn2png prog. Thanks.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on November 10, 2015, 10:22:00 pm
vygr: Yes of course! If I've put the file there, it was for you to play with it! :)
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 11, 2015, 06:52:13 pm
OK, found two errors in my dsn2pcb parser thanks to the Oricmouse dsn file.

1) Did not understand Oval pins could be (0,0,0,0) ie a Circle ! Now it just parses them to a circular pin.
2) Was getting the rotation angle of components the wrong way round, clockwise<->anti-clockwise.

Fixed and uploaded the fix, could do with a better testing but I'll have to wait till weekend for that.

Couple of screen grabs with a few different parameters, routed in a few seconds.

Regards all

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 11, 2015, 07:09:26 pm
A few boards with some of the flood vector params tweaked a bit just for fun.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on November 12, 2015, 10:17:29 am
If I may, you should add an option to force pad neckdown to be either a 0/90/180/270° exit or a 0/45/90/135/180/225/270/315° exit, and if it takes only a few seconds thats interesting and much more quicker than freerouting, it only miss the "optimisation" phase I think
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 12, 2015, 05:54:45 pm
Neckdown ? Term I've never heard of ! Time for some more study :)

Yeah most of these runs took a few seconds. The test board I use from my friends wet room controller take 1.2s.

You can stretch that time out by using very high resolution routing or high Z bias values, but for a quick route it's generally taking a few seconds.

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 12, 2015, 06:04:54 pm
Example using route the following command line.

time ./dsn2pcb test4.dsn | ./pcb --v 0 -r 2 -z 16 | ./view -o 1 -s 6

Number of terminals: 242
Number of Nets: 83
Number of Vias: 36

real   0m4.347s
user   0m4.333s
sys   0m0.009s

Smallish Z bias.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on November 13, 2015, 03:02:32 pm
Hi.

Thanks a lot for your fixes!

Does it generate pcb files for gEDA's PCB? Have you considered making a tool for KiCad too?

As for GUI...

This project looked interesting but got abandoned since 2011:

https://launchpad.net/qautorouter


Anyone willing to provide all kind of .dsn files for testing? I'm going to export some old projects this weekend in a few spare time, as I'm very busy at this moment. But they are very simple designs, complex designs nicely routed to compare would be nicer to have, I think.

Kind regards.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on November 13, 2015, 04:59:37 pm
Dons't create anything that you would call a standard output format. I just wanted to work on the route solving problem, the viewer I created is just so I can sanity check the output. The router takes a simple format but it's not standard. I did the DSN converter so I could expose the router to more test files.

So no KiCAD plugin or anything else.

Problem is that, beyond some simple fixes, I don't have the capacity to do any heavy work on it now due to work consuming my time.

I would hope that if the routing speed is good that some enterprising person might have a go at using the router portion to create a KiCAD plugin.

My stretch goal for the router was to be able to do routing in near realtime, ie within a few seconds of moving your component on a GUI the board was re-routed and done. At least for simpler hobby boards.

One of the things that would need doing is to make sure that existing protected wiring is maintained. Currently even is there is a wiring section in the .DSN file I just ignore it.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on November 13, 2015, 05:01:50 pm
I don't know anything about the SES format, but for Kicad, if you could convert your output to the SES format, it would be possible to import the output of your router into kicad pcbnew, like we do using freerouter
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on November 28, 2015, 06:10:21 pm
Does anyone know about the SES format?
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: donotdespisethesnake on December 05, 2015, 09:28:09 am
The DSN and SES files are defined in "SPECCTRA Design Language Reference", I found a copy of the spec by google search : http://support.ema-eda.com/search/eslfiles/default/main/sl_legacy_releaseinfo/staging/sl3/release_info/psd142/spdlr/preface.html (http://support.ema-eda.com/search/eslfiles/default/main/sl_legacy_releaseinfo/staging/sl3/release_info/psd142/spdlr/preface.html). There are some other copies I found, that is the most recent. Not sure who owns the copyright or whether there is an official distribution point.

I started looking at C-PCB as it sounds promising. First I have to get/build clang...
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on December 13, 2015, 06:27:34 pm
I just wrote this in the Freerouting repo after some activity, in hoping someone might get interested at looking at C-PCB.

https://github.com/freerouting/freerouting/issues/7 (https://github.com/freerouting/freerouting/issues/7)


Just for fun...
I found this old forum thread about freerouting...
https://www.eevblog.com/forum/projects/can-you-route-better-than-an-autorouter/ (https://www.eevblog.com/forum/projects/can-you-route-better-than-an-autorouter/)
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on December 15, 2015, 09:10:56 pm
Hi guys, I just did some mods to the C-PCB repo to get it building on Ubuntu 15.10 but I have got some problem that I can't debug due to running on a VM.

For some reason the router is just spinning forever, which it doesn't do on the Mac, and I can't see the output on my VM (OpenGL issue) so can't see the live output easily to hunt down the problem.

I did have a problem with the Linux compiler not doing a lambda capture correctly, I tried a workaround, but it may be that this is just causing the spinning regardless. It was in a part of the code that would cause things to go wrong in a big way if the compiler error's there.

But I'll keep trying.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on December 16, 2015, 09:13:43 pm
Well the latest version of C-PCB is compiling and working on Ubuntu 15.10. I had to install the glfw3 libs to get the viewer app to compile but it does seams to run ok now.

Regards to all

Chris

https://github.com/vygr/C-PCB
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on December 19, 2015, 10:40:59 pm
@vygr

Thanks a lot!
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on January 08, 2016, 10:31:13 pm
Stefan Salewski updatedhis website (http://ssalewski.de/Router.html.en) again
Quote
PCB Routing Update -- December 2015
I have been working again on my PCB routing software, because recently some people asked about it.
  • I have made a tar archive containing all the Ruby glue code for CGAL and BOOST library, so you can play with it when you really want.
      I didn't have enough time to fully clean up the code yet :-(
  • If you want to play with it, you need:
      Ruby interpreter: preferably latest version 2.3.
    • ruby-gnome2: Required for cairo picture drawing.
    • CGAL and BOOST libraries.
        Maybe developer packages for some of these.
  • A Linux box with a working C compiler.
How to run it
  • Download Router20151229.tar from my website (http://ssalewski.de/Router.html.en) and extract it in an arbitrary named directory.
  • There'll be the following list of directories:
      Router
    • RAPOLLONIUS
    • RCGAL
    • RTREE_2D_POINT
    • RTREE_2D_RECT
    • RBOOST.
  • From the command line, enter into Router (cd Router)
  • Type "bash gen_bindings".
      This will generate .so files for the CGAL and BOOST bindings.
  • Now you can start testing with "ruby router.rb".
      Result should be a test routing generated with random numbers.Type "ruby pcbtr.rb" to generate pics for that example pcb.
NOTE: This is only a proof of concept, a test
Next steps would be:
  • Clean up the code.
  • Improve the layer assignment.
      We may route each subpath for this in advance, in order to detect barriers and get a lower bound for the detour.
  • When that is done, we may tune the real routing process:
      A very simple way may be to reorder the routing sequence, moving failed traces further to the start.
    • Of course, some GUI support should be added.
  • Another idea:
      Inserting some vias in larger empty areas before the routing process.
    • Use some of these vias for the remaining unrouted traces.
It would be really amazing if others would join forces with him to make a better project!
https://github.com/StefanSalewski/Ruby-PCB-Router (https://github.com/StefanSalewski/Ruby-PCB-Router)
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on January 08, 2016, 10:35:25 pm
Why using another just another langage??...

Will wait for the result but I fear that it will not help to integrate in tools like Kicad, which is already a big beast :D (aka they already struggle adding Python to Kicad, I don't think they may consider integrating a Ruby interpreter)

I hope the main dev is just using Ruby as a prototyping tool
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on January 08, 2016, 11:06:39 pm
Why using another just another langage??...

Maybe he was more comfortable with it for prototyping it. I dunno.

He seems to be more of a researcher. Let him research on whatever language while or provides interesting results for the first FOSS community and ;)
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on May 22, 2016, 06:54:36 am
Any news about this? gEDA people are playing with Freerouting, but the use of Java and controversial legal situation are a major issue.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: mikeselectricstuff on May 22, 2016, 08:15:40 am
I wonder if the combination of Deep Learning stuff (feed it a gazillion existing PCB layouts) and GPU horsepower might open up some possibilities, but as has been said, a major issue is simply explaining what the constraints are, however clever the routing algorithm is.

I think there probably is some scope for "assisted" routing, where a person guides the  progress of a partly automated process. And maybe if this gets used enough it would start to learn and present better options sooner, requiring less intervention.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: janoc on May 22, 2016, 10:24:02 am
I think that the problem is not the routing algorithm as such. That's relatively trivial part of the problem. A much bigger issue is how to bring all that "tribal knowledge" into it in the form of well performing constraints, as you have said.

So going to deep learning or GPU acceleration won't help much there - that is addressing the "easy" part of the problem. Unless you are auto-routing something on the scale of a PC motherboard, you likely don't care whether the routing takes 5 or 20 minutes so much, but you do care whether the setup is a 15 minutes or half a day of work.

Also constraint solvers are not really the type of problem that lends itself well to massive parallelization (which is where GPUs shine). The inter-dependencies will often force at least partial serialization of the problem and it may actually take more time if using GPU than doing it purely in software because of the non-negligible overheads involved.

For the assisted routing I would like to see some improvements of the push-and-shove router that is in KICAD already - e.g. routing several traces in parallel (like a bus). It can route differential pairs already, so this would be a natural extension. That pretty much covers most of the common needs for auto-routing already.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: lem_ix on May 22, 2016, 02:07:13 pm
Had a one semester subject on the topic. We used Matlab to auto route and place components in Altium but the results were far from stellar(better then altium tho) and the time to set these algorithms up is better spent just doing it by yourself. I could imagine using these algorithms for something repeatable maybe inside an IC for standard cells(just guessing no experience). Amazing amount of books and papers on the topic but the results published in them are far from real world examples. Think that most people interested in auto routers don't have much design experience  :palm:
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on May 27, 2016, 05:45:43 pm
It's surprising a student effort may offer better features than high end EDA software such as Altium Designer.

Is so difficult to make a top quality advanced autorouter or just a "boring" topic?

What able sending patches to KiCad or other projects?

Those are the most active autorouters. Do to know about some more?

C-PCB (https://github.com/vygr/C-PCB). Last commit: Apr 13, 2016.

 FreeRoutingNew (https://github.com/Engidea/FreeRoutingNew). Last commit: May 27, 2016.

My interest lies in assisted learning, mostly. Good autorouters aren't perfect, but they inspire me to what paths to choose and such. Routing is somewhat a therapy for my spatial issues of ADHD too.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on May 27, 2016, 06:19:56 pm
Is so difficult to make a top quality advanced autorouter or just a "boring" topic?
First reason. You know about the P=NP problems? and the Travelling salesman problem?
Autorouting is some order of magnitude more complex than that.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: altaic on May 27, 2016, 09:58:50 pm
First reason. You know about the P=NP problems? and the Travelling salesman problem?
Autorouting is some order of magnitude more complex than that.

I would be interested in seeing a proof of that.

TSP is NP-hard with a time complexity of O(n^2 * 2^n). Auto-routing is closer to the n-body problem, which has a time complexity of O(n^2). Furthermore, there are many approximation techniques which can reduce the time to O(n log n) if not O(n). Also, the algorithms for solving such problems are highly parallelizable and thus run nicely on GPUs. Finally, routing a PCB is unlikely to be a worst-case scenario, and algorithms exist that make solving common cases fast.

So, I respectfully disagree. Auto-routing is not so hard-- getting correct models from device manufacturers so can auto-routers can work is hard.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on May 28, 2016, 12:52:47 pm
There are also a lot of approximation on the TSP problem.

Auto routing is basically the TSP as we want the shortest path, but we have
- multiple path to look at the same time
- there are most of the time constrain on the path you have to choose because some sellers have to travel at the same time going to different borough of the same town (basically routing a bus)
- path MUST NOT cross in most conditions, where in the normal TSP it doesn't matter
- Highly parallelisable? Maybe by doing a lot of approximations, but there are some rules that would ultimately prevent parallelisations, like the fact that two track which does not belong to the same net must not ever cross, and that have a huge impact on parallelisation as each thread need to know what the other are doing, so basically they are not running asynchronously.
- Giving a solution "fast" does not mean that it's the best! It's also possible to give really fast a solution for the TSP, but it will never be the best solution.

There are way more constrain on routing than on the TSP, that's why it's more difficult.

Current approach of auto routing are approximations and not the "best results", as current TSP solvers.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on May 28, 2016, 01:24:57 pm
Why aren't brave souls improving projects like C-PCB or FreeRoutingNew? what about making a bounty for it?

- C-PCB is developed in C++14, it provides a better integration with EDA software and better performance.

- FreeRouting(New) provides better results, but it has a dubious legal situation and users the controversial and non-native Java programming language.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: zapta on May 29, 2016, 04:04:04 pm
Auto routing is basically the TSP as we want the shortest path, but we have ...

Nets are typically not routed as a long trace going through a sequence of pads. For a single layer, single net, no obstacles, any angle routing and total length minimization, this is a closer problem https://en.wikipedia.org/wiki/Steiner_tree_problem which allows to insert additional points and to fork the trace.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: nctnico on May 29, 2016, 05:06:34 pm
Why aren't brave souls improving projects like C-PCB or FreeRoutingNew? what about making a bounty for it?
IMHO fixing how Kicad handles components, symbols and footprints should have a much higher priority. As it is now you can't really use it in a (somewhat) professional environment. Once you get used to what Orcad Capture CIS offers (one click BOM generation from a database) you never want to go back to editing BOM files manually!
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Jeroen3 on May 29, 2016, 07:44:19 pm
Last routing sessing in Eagle I decided to record it using OBS. Inspired by Dave's Altium uSupply timelapse.
I must say that it is interesting to watch to see layout choices change on the way.
You can learn from yourself when playing back stuff like this.
https://www.youtube.com/watch?v=ZWagjO9EgOU (https://www.youtube.com/watch?v=ZWagjO9EgOU)
It must be really hard for an AI to perform this, because even I cannot think of all the variables at play when I'm routing a board. It's an art.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on May 30, 2016, 08:28:14 am
Extreme cases are extreme.

What are the best autorouters in the world? Specctre? Electra? TopoR?

Do they got analyzed and reverse engineered in Europe? Maybe clean room could help.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: Godzil on May 30, 2016, 03:00:39 pm
Reverse engineering? Yeah probably, but I will wish you a really good luck at that, and clean room is not possible are you are not documenting API but how it is working, aka the algorithm which is likely to be patented.

It's would be easier to start from a blank paper than to try to clone something existing which is that complex.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on June 02, 2016, 10:35:30 pm
I see.

Why not get C-PCB and improve it?

What developers think about the code base? What about making it a library?
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: timofonic on June 07, 2016, 12:45:28 am
No opinions? Any developer alive work some interest in it?
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: janoc on June 08, 2016, 07:22:06 pm
Extreme cases are extreme.

What are the best autorouters in the world? Specctre? Electra? TopoR?

Do they got analyzed and reverse engineered in Europe? Maybe clean room could help.

Considering that most people working on these things do so in their free time, I doubt that there is much interest in reverse engineering another program. The effort required in order to not put oneself in legal jeopardy (all the clean room stuff) is not something most will want to touch.

Even if the algorithms weren't patented (I doubt they are - there are many many publications on graph algorithms and specifically PCB routing, so at least the general ideas cannot really be patented), unless someone actually funds a project like that then nobody is going to do it just as a "hobby". Way too much legal risk (even if reverse engineering is legal, the costs of having to defend a baseless lawsuit are not free!) and there are much more pressing problems in the free EDA tools than the lack of an autorouter.


No opinions? Any developer alive work some interest in it?

C-PCB is pretty much a toy at the moment and not a serious/usable router. It takes a netlist and routes everything, without any constraints or rules, such as "don't route this high current trace around my ADC!". I don't think that anyone would want to spend the non-trivial time that it would take to integrate on something that is ultimately not usable yet. Also the development doesn't seem to be very active - one developer and the last significant changes were 6 and 11 months ago.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on August 18, 2016, 05:03:55 pm
Hi folks, got a little time to experiment with my PCB solver. I'm going to do a JavaScript version. With a view to eventually having a website where you drop your .dsn file and set a few options and it gives you back the Gerbers etc.

Just got the viewer going so far this weekend. Learning JavaScript while I go, and D3/SVG for the output. Nice thing about this version will be that any modern browser gives you all you need to route your boards, no software to install etc. The client does the solving, not the server.

I'm hoping that modern JavaScript jits are as good as they say 60% C++ speed. We will see..... ;) If it is, then hobby boards should solve in a few seconds. Well that's the plan.

https://github.com/vygr/JS-PCB

Regards to all as usual.

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on August 18, 2016, 05:12:28 pm
BTW I completely agree with Janoc's comments that for a comercial router you need more rules about how to route tracks. But you've got to start somewhere so I did. ;)

Thanks Timofonic for your enthusiastic push of C-PCB, but there does need to be more done than I can possibly do alone. I put it out there to see if it was useful to people. As I said before, I was interested in the problem but don't have full time I can spend on it. Certainly not if I can't make money for living from it !

I'll keep adding bits as I find time, and the JavaScript web version is the next idea I'm going to tackle.

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: vygr on August 23, 2016, 02:14:26 pm
Progress being made on the JS version.

Live view is now enabled at https://vygr.github.io/JS-PCB/. No need to download or clone anything, just give it a try on a DSN file, you might find a few issues ATM, enjoy.

Just got the DSN import going and the viewer. No solver ported yet, but working on it.

Regards

Chris
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: janoc on August 23, 2016, 04:24:35 pm
Um, I don't want to pour cold water on your effort, but you do realize that a JavaScript based autorouter has very little chance to be actually integrated into anything? (unless you are planning to run it as a web service hosted somewhere, of course).

I simply don't see Kicad/Geda/whatever developers to include Node.js or a Chrome/Webkit runtime (or whatever you are using) only to run your autorouter. You would stand a lot better chance to have it integrated if it had a C/C++ or Python interfaces, because that is what these projects are using already.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: BloodyCactus on August 23, 2016, 07:23:32 pm
I simply don't see Kicad/Geda/whatever developers to include Node.js or a Chrome/Webkit runtime (or whatever you are using) only to run your autorouter. You would stand a lot better chance to have it integrated if it had a C/C++ or Python interfaces, because that is what these projects are using already.

kicad is built with wxwidgets, wx already has a wxWebView which lets you run javascript...
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: janoc on August 23, 2016, 08:21:25 pm
kicad is built with wxwidgets, wx already has a wxWebView which lets you run javascript...

wxWebView actually has to be enabled at compile time first, it is an optional component in Wx. It is also meant to display HTML using Webkit (Linux & Mac) or Microsoft's IE engine (in Windows), but that is not a full blown browser by itself. So while you can run Javascript, I would be mightily surprised if some complex "weby" framework stuff relying on the presence of certain browser features was running in it out of the box, without hooking up a ton of extra plumbing to it first.

Anyhow, even if it did - have you actually tried interacting with HTML/Javascript code running inside of a webpage from outside of the HTML widget using C++ APIs? I can tell you, you don't want to go there - it is a huge and complex mess, because most of the Javascript apis are simply not accessible from outside. It is an encapsulated black box (by design) and all you get is an API to load a HTML page, navigate history, copy & paste and similar, but nothing to actually interact with the objects within the page (e.g. DOM access). So the "integration" would have to be done using temporary files, injecting bits of Javascript to the page and similar kludges. Gee, thank you ..

Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: BloodyCactus on August 24, 2016, 12:14:24 am
kicad is built with wxwidgets, wx already has a wxWebView which lets you run javascript...

wxWebView actually has to be enabled at compile time first, it is an optional component in Wx. It is also meant to display HTML using Webkit (Linux & Mac) or Microsoft's IE engine (in Windows), but that is not a full blown browser by itself. So while you can run Javascript, I would be mightily surprised if some complex "weby" framework stuff relying on the presence of certain browser features was running in it out of the box, without hooking up a ton of extra plumbing to it first.

Anyhow, even if it did - have you actually tried interacting with HTML/Javascript code running inside of a webpage from outside of the HTML widget using C++ APIs? I can tell you, you don't want to go there - it is a huge and complex mess, because most of the Javascript apis are simply not accessible from outside. It is an encapsulated black box (by design) and all you get is an API to load a HTML page, navigate history, copy & paste and similar, but nothing to actually interact with the objects within the page (e.g. DOM access). So the "integration" would have to be done using temporary files, injecting bits of Javascript to the page and similar kludges. Gee, thank you ..

huh thats interesting. I use javascript scripts in java all the time for scripting. as long as you dont do DOM manipulation, you can do all kinds of javascript stuff. I thought it would have been similar in wx.
Title: Re: Open Source High Quality Autorouting: Is it possible?
Post by: janoc on August 24, 2016, 12:31:17 pm
huh thats interesting. I use javascript scripts in java all the time for scripting. as long as you dont do DOM manipulation, you can do all kinds of javascript stuff. I thought it would have been similar in wx.

Well, look at the API of that class for yourself: http://docs.wxwidgets.org/trunk/classwx_web_view.html (http://docs.wxwidgets.org/trunk/classwx_web_view.html)

That's all you get. There is not even direct access to the Webkit backend.