Orthoroute, or a new autorouter plugin for IPC APIs

Community
1

Hi, I had a wicked hard board to route (200x160mm backplane with 8192 nets) and decided it would be easier to write an autorouter instead of routing it by hand. That’s what I did.

You can see the project writeup here: OrthoRoute | Benchoff Design Portfolio
And the GitHub repo is here: GitHub - bbenchoff/OrthoRoute: A GPU-accelerated PCB autorouter for KiCad
And there’s a Youtube demo on both of those pages showing it routing a 512 net board in about 2 minutes.

This project began with figuring out the new IPC API, and it’s great. I can put my own Python stuff in here and not be tied to one set system. Awesome. So I built a GPU-accelerated autorouter. I did the ‘traditional’ autorouter first, but it is just one pass, not push-and-shove, and performs as you think an autorouter would. That is to say, not well.

The real test was building the ‘Manhattan’ autorouter. This defines a grid of traces – only horizontal on layer 2, vertical on layer 3, horizontal on layer 4, etc… and routes with the PathFinder algorithm taken from FPGA fabric routers. Blind and buried vias connect the traces together.

Algorithmically, it’s not ideal, because PathFinder operates on a constrained set; if you calibrate the constants of the algorithm for one family of FPGAs, you can use it on all other FPGAs. But all PCBs are different, so you’ll have to tune the algorithm for each board. I’m attempting some auto-tuning but it’s not really great.

But still, the idea is there. I’m really looking for feedback on this and if anyone could actually use this. The project is very much in a pre-alpha state, but it does route and commit tracks to KiCad. That’s all I needed it to do, so now I’m releasing it to the public.

Two things that are explicitly KiCad specific I’d like to ask: First off, it seems the IPC API only ‘works’ when the ‘select items’ (the arrow pointer) is active and nothing is selected. Trying to connect to the API when ‘route tracks’ is selected simply doesn’t work.

To be fair, I didn’t investigate this much beyond ‘just make sure nothing’s selected’, but I’m wondering if this is expected behavior.

Secondly, when building the ‘traditional’ autorouter engine for this, I needed a way to get the ‘free routing space’ of a board. My hack was to read the polygon of a copper pour, the idea being that I can route through a copper pour, I can’t route through anything that isn’t included in the copper pour.

So, Feature Request: Could the IPC API expose a ‘get_free_routing_space(int layer)’ function? This would return a polygon representing the routable area (basically board outline minus pads, tracks, keepouts) similar to how a copper pour is calculated but without needing actual pours on the board. This is incredibly hacky, but it’s something that actually does sound simple to implement.

Anyway, just wondering if anyone else would find this useful. Feel free to try it out.

5 Likes
2

I know there is not a lot of enthusiasm for autorouters in certain part of the EE crowd, for good reasons too - they are either bad or require so much setup work for each design that it rarely saves any time.

But there is always demand for automating some menial routing in simple-ish designs that is not critical. So your project will definitely find it’s user if you can deliver on these points:

  • Make it easy to install and use (you are mostly there)
  • Improve on at least some of the common gripes for Freerouter (only other viable alternative free autorouter that I know of)

You can search this forum or any other for freerouter threads to immediately see some issues it has.

But here is an idea that will definitely make your project stand out among even most pro autorouters: implement some form of component auto placement or nudging. Kicad api lets you do that and you can take into account locked footprints (think mounting holes, connectors).

3

I’ve thought about an “auto placement” plugin. In fact, I kinda already did it with this ‘monster backplane’ – when I was placing the nets, the components stayed static, but I ran the nets through a simulated annealing function to make sure the placement of all nets was optimal, in terms of length.

The problem with an ‘auto placement’ plugin is…. jesus christ, that’s an NP hard problem. That’s a hard NP hard problem. Right now if I built that I’d be looking at the space of all possible placement configurations of all the parts, which is insane. Then I’d have to place those ‘optimally’ respecting the fact that I’d eventually have to connect these parts with traces, so you’re running a DRC-aware autorouter for every iteration of placement. No matter what you do, it’s going to be slower than looking at an un-placed, un-routed board, thinking about the problem, and then doing it.

You could do it better, though – you could divide the schematic up into blocks, and say, “hey this chip goes with these caps and resistors, but they’re also attached these nets which connect to this group of chips and components. So let’s group those together into logical blocks, and connect these blocks together’. This is basically deriving - or creating your own model of hierarchical sheets. But have it make logical sense and making it work with whatever schematic KiCad works with.

That would be a start to the auto-placement plugin, but holy shit that’s a hard problem.

I’m not discounting that an auto-placement plugin wouldn’t be useful, I’m just saying a human could do it better than any algorithm. It would literally be easier to create artificial general intelligence than to define and create this algorithm. And if you do create AGI, you already have someone who could do the auto-placement for you.

4

It is expected behavior that most modification actions only work when the selection tool is active (but they should work regardless of whether or not anything is selected, in fact it’s important that it supports working when things are selected!). The reason is that if any other tool is active, the user may be in the middle of doing some modification to the design, and since IPC API plugins are asynchronous to KiCad, there is no way to prevent synchronization issues like the user modifying the board in the “middle” of the plugin trying to do something.

It is pretty unlikely that this would get implemented by anyone on the core team anytime soon. The reason is that this feature doesn’t really need to exist to support any use case built-in to KiCad that I can think of. I think your “hack” is actually probably the best way to do this. While we are likely to accept someone proposing to implement this as long as the implementation is sound, I just want to be honest that it sounds like the kind of very niche thing that we would tend to say should be implemented in a plugin.

5

Yeah full auto placement is very hard but here are some ideas I had when I was considering writing something similar:

  • Simplify the problem to only allow autoplacement of 2 pad components (passives), making algorithm consider them as a fixed length net with an odd shaped courtyard.
  • Require user to place everything else roughly where they think it should be and then try to optimize unrouted trace lengths by rotating and “jiggling” components around. Bonus points if it will also try to uncross unrouted nets.
6

Looks like a cool start, but it being limited to only manhattan / orthogonal routing wouldn’t have much appeal to me. The old Specctra autorouter would start mostly with a manhattan approach, but subsequent passes would introduce diagonal elements and pull out a lot of trace lengths along the way.

7

Thanks for posting, very interesting!

I played with autoplacing a bit: Programmatically generating schematic

I used that for my discrete logic projects. You could have yosys generate a multiplier or and ALU out of transistors. No one would attempt to place or route this mess by hand. So I wrote an autoplacer, using the simulated annealing optimizer as it is done with FPGAs. This is easy for cell-based layouts (you have a fixed grid and just swap cells), more difficult for a gridless variable size optimizer (see my last post).

I then used freerouting as router, which seemed to work well enough. I did not continue with that project, so I’ll never know if the discrete 16x16 multiplier will ever work. Maybe I should order it from JLC just for fun.

Martin