Author Topic: Open Source High Quality Autorouting: Is it possible?  (Read 46095 times)

0 Members and 1 Guest are viewing this topic.

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #25 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
 

Offline free_electron

  • Super Contributor
  • ***
  • Posts: 8515
  • Country: us
    • SiliconValleyGarage
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #26 on: November 10, 2015, 08:59:10 pm »
yuckkk. Look at all the whacky pad terminations... what a pile of garbage.
Professional Electron Wrangler.
Any comments, or points of view expressed, are my own and not endorsed , induced or compensated by my employer(s).
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #27 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
 

Offline Godzil

  • Frequent Contributor
  • **
  • Posts: 458
  • Country: fr
    • My own blog
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #28 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! :)
« Last Edit: November 10, 2015, 10:25:08 pm by Godzil »
When you make hardware without taking into account the needs of the eventual software developers, you end up with bloated hardware full of pointless excess. From the outset one must consider design from both a hardware and software perspective.
-- Yokoi Gunpei
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #29 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
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #30 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
 

Offline Godzil

  • Frequent Contributor
  • **
  • Posts: 458
  • Country: fr
    • My own blog
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #31 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
When you make hardware without taking into account the needs of the eventual software developers, you end up with bloated hardware full of pointless excess. From the outset one must consider design from both a hardware and software perspective.
-- Yokoi Gunpei
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #32 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
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #33 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
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #34 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.
« Last Edit: November 13, 2015, 03:15:12 pm by timofonic »
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #35 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
 

Offline Godzil

  • Frequent Contributor
  • **
  • Posts: 458
  • Country: fr
    • My own blog
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #36 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
When you make hardware without taking into account the needs of the eventual software developers, you end up with bloated hardware full of pointless excess. From the outset one must consider design from both a hardware and software perspective.
-- Yokoi Gunpei
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #37 on: November 28, 2015, 06:10:21 pm »
Does anyone know about the SES format?
 

Offline donotdespisethesnake

  • Super Contributor
  • ***
  • Posts: 1093
  • Country: gb
  • Embedded stuff
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #38 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. 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...
Bob
"All you said is just a bunch of opinions."
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #39 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


Just for fun...
I found this old forum thread about freerouting...
https://www.eevblog.com/forum/projects/can-you-route-better-than-an-autorouter/
« Last Edit: December 13, 2015, 06:35:35 pm by timofonic »
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #40 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
 

Offline vygr

  • Contributor
  • Posts: 14
  • Country: gb
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #41 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
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #42 on: December 19, 2015, 10:40:59 pm »
@vygr

Thanks a lot!
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #43 on: January 08, 2016, 10:31:13 pm »
Stefan Salewski updatedhis website 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 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
« Last Edit: January 08, 2016, 11:05:11 pm by timofonic »
 

Offline Godzil

  • Frequent Contributor
  • **
  • Posts: 458
  • Country: fr
    • My own blog
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #44 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
« Last Edit: January 09, 2016, 03:11:29 am by Godzil »
When you make hardware without taking into account the needs of the eventual software developers, you end up with bloated hardware full of pointless excess. From the outset one must consider design from both a hardware and software perspective.
-- Yokoi Gunpei
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #45 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 ;)
« Last Edit: January 09, 2016, 01:29:58 am by timofonic »
 

Offline timofonicTopic starter

  • Frequent Contributor
  • **
  • Posts: 904
  • Country: es
  • Eternal Wannabe Geek
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #46 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.
 

Offline mikeselectricstuff

  • Super Contributor
  • ***
  • Posts: 13693
  • Country: gb
    • Mike's Electric Stuff
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #47 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.
Youtube channel:Taking wierd stuff apart. Very apart.
Mike's Electric Stuff: High voltage, vintage electronics etc.
Day Job: Mostly LEDs
 

Offline janoc

  • Super Contributor
  • ***
  • Posts: 3781
  • Country: de
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #48 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.
 

Offline lem_ix

  • Regular Contributor
  • *
  • Posts: 192
  • Country: cs
Re: Open Source High Quality Autorouting: Is it possible?
« Reply #49 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:
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf