Autorouter == Specctra to Bitmap+JSON

Software
1

I won’t get into the quality and/or religious aspects of using an autorouter here, but this appears to be one of the key areas where commercial offerings distinguish themselves.

In my case, I need to route a 40-pin bus operating at 200 Mhz so I probably should have tight length matching. The KiCAD “Tune Length of a Single Track” command is working great, but doing 40 lines by hand is very time consuming.

I also don’t believe that KiCAD should integrate an autorouter, because that’s a lot of work and you need experience and large budgets to get good results. I tried https://github.com/freerouting/freerouting and it can route all the connections, but then I afterwards need to manually move the wires into position to create space for KiCAD’s meandering. The source code of freerouting looks pretty messy and like data model and GUI are all mixed up, so enhancing that one won’t be easy.

But what I believe could be done with relatively little effort is to create a development platform to make it as easy as possible for others to build a great autorouter.

For that, one would need a command-line tool that can read a KiCAD PCB - or better yet a Specctra DSN - and convert that into a black/white bitmap and a JSON file with a list of routing targets.

The advantage would be that the autorouting problem is converted into image-based pathfinding. And for the latter, game developers have been building creative GPU-accelerated solutions for a while now:
https://nullprogram.com/blog/2014/06/22/

Plus having the routing problem as an image means one could “train an AI” to solve it. I put that in quotes because actually one would just let a network memorize good solutions from training examples. So the “artificial intelligence” would be more like “find the closest example board and copy&paste the routing from there”.

1 Like
3

Autorouting using ML is certainly an interesting area of research.

I think for your testbed platform idea, exporting the board is easy (like you said, you can just use the DSN format) - what would take a bit more thought is how to create a system for defining routing constraints. Usually to drive an autorouter to acceptable results you need many more constraints than just a graph of what nodes need to connect to each other (i.e. what traces can route on what layer? what strategies should be used in different areas? what are the design rules? etc etc)

4

If your like to do some background reading how router algorithms can work:

1 Like
5

Thank you for linking to that interesting discussion :slight_smile:, so now I know where to start researching algorithms in the future.

That said, my intention with posting this thread was not that I plan to build a router, but that I’m hoping to build the tools that others need to bridge the gap between PCB specific technical details and the actual algorithms. A good data export together with some common algorithms as a python package could go a long way there.

As an ideal outcome I’d imagine someone writing a blog post called “How to build your own autorouter in 50 lines of python”

Once things are that accessible, we suddenly enable lots of people to try out their routing algorithm ideas by creating short scripts. I’m quite optimistic that at that point someone is going to make a beginner-friendly 1 click routing script. The results will likely be too bad for professional use, but if you’re just connecting LEDs and buttons to an Arduino pin header, pretty much any routing will do.

1 Like
6

You are severely underestimating the complexity of even remotely usable autorouter.

To make a construction analogy you are suggesting to build a scaffolding for a building before the building plan is even known or actual builders enter the picture. With the scaffolding being a miniscule amount of effort compared to actually building a house you are not really saving anyone any amount of time, especially considering that your scaffolding may not be useful at all, depending on construction methods of the builders.

There already is a good export mechanism to a openly documented DSN format. It has all one needs to build an autorouter.

7

@craftyjon I agree that a generic autorouter will need a lot of configuration to produce good results. I believe the solution is to make it easy to produce task-specific routers.

I usually work on 2 layer boards with HF traces and plenty of empty space. So I might want to have a router that’ll deliberately leave gaps in between the data lines so that I can manually ground fill those gaps and so that I’ll have space for meanders for length matching.

Someone else might build a router that’s great for BGA fanout. But if both of us build small contained scripts on top of the same API, it should be easy to share.

So I would imagine this not as one autorouter that can be configured to handle everything, but more like a toolbox with many small and opinionated single-purpose tools.

But to get there, the first step is to make it easy to create those tools. In my opinion, the biggest issue with freerouting is that it’s too complicated for people to tinker with.

8

@qu1ck to build a simple autorouter, I need the PCB as images or as a graph, because otherwise pathfinding algorithms like astar won’t work. Based on my preliminary research, it appears that commercial autorouters internally work on a bitmap grid representation. Once you have that, python has good astar and optimization packages.

With a graph representation, you can even combine areas into just one node, thereby making things faster to calculate

So in my opinion, that would be the shared fundament that pretty much every autorouter needs.

9

You have pcb as vector objects, that’s all you need to build your graph.

And I doubt any router works with bitmaps, they don’t have arbitrary precision needed.

10

You can install the Elecctra trial. It has a configuration option for the bitmap resolution.

Oddly enough, they call their approach shape based routing to differentiate it from the previous generation which used grid based routing where every layer has a preferred direction.

I agree with you that vector representations can be helpful, but their benefit is in describing sparse data with a high boundary resolution. But a fully routed PCB is not sparse anymore. Instead, most parts of the board will be filled by either components, traces, or enforced copper gaps to separate things.

I hope you’ll agree that a 2mil routing resolution is plenty for pretty much every board. With modern GPUs, that means you get hardware acceleration up to 2x32768 mils = 1.6 meters. But only if you go with an image representation, because vector shape math won’t fly in a GPU shader.

11

I think you mix up routing and path-finding. While path-finding is indeed important for an auto-router, that part is not the complex part I would say (the PNS is a very good path-finder which incooporates all clearance constraints and is very fast). The problem is to put a lot of paths in a way to manage all connections, and to incooporate knowledge about the circuit to avoid coupling,…

12

For my board at hand, freerouting, Elecctra and Altium all fail to route the traces from a connector around the drill holes. So I’m having a pathfinding issue, it seems.

A tool that just fans out from a connector while avoiding obstacles until the ends have enough clearance between them for vias would solve my routing problem. The remainder is something that freerouting can handle.

That’s why I believe we need a framework that makes it easy to build small routing tools. I don’t intend to solve everything, I just need an easy way to complement existing software.

In a way, those are steps towards an interactive router inside KiCAD. If you have 20 command line tools where each does one specific thing, KiCAD could show that as 20 buttons in the GUI and let the user decide which steps to apply and in which order.

13

No, 2 mil is not enough. You need fractions of mils to squeeze tracks between clearance islands of other nets. There is a reason why pcbnew internal units are nanometers.

2 Likes
14

To give you some theroretical input:

  • Path finding is a classical search problem. You have introduced A* into the discussion which has a quadratic complexity as its worst case, and is very efficient as it has a “perfect” heuristic to guess the optimum route which might be possible. In other words, A* gurantees you to give you a route with the shortest length in a reasonable timeframe. A* does NOT require a bitmap. In fact, path-finding algorithms in games are usually based on triangles or some other high-level geometric structure, as this scales way better than pixels. Routing using pixels might look easier to implement, but, in fact, you introduce way more intermediate-calculations and require more intermediate memory while reducing accuracy.

  • Routing on the other hand is NP-hard or NP-complete, depending on the constraints and preconditions you define. If you have more than one trace you want to connect, you have a routing problem and no longer a path-finding problem (e.g. fan-out a connector). To find a perfect solution you often need to do a brute-force search, which does not scale. (Remember, A* gives you a perfect solution in reasonable time for very big inputs). Think about the travels-salesman problem, where a stupid algorithm would not even be able to calculate the optimum solution for 20 cities in a reasonable timeframe.
    When confronted with problems in the NP space, programmers usually rely heavily on heuristics (which A* also does), randomization, approximation,… and those algorithms have often the property to be very-good for many cases, but they don’t give any gurantees that a solution will be found in a reasonable timeframe (or proof that no solution is possible and give-up early).

I agree that it makes sense to split up the problem into sub-problem and have optimized algorithms for each (e.g. escape-routing, length-matched bus-routing,…) but if someone really likes to implement this, this should be done inside KiCad and not as some third-party tool. This is a serious investment, and ignoring things like clearances is a big no-go. I would argue that, every person which is capable of implementing such a router does not require such a framework as you propose. The problem is not getting data in/out, but to do something meaningful with it.

3 Likes
15

At 200MHz your clock period is 5ns, or 2.5ns if you use both edges. Assuming a parallel bus that gets sampled a 5ns/2.5ns you can probably get away with using 1ns for skew in the transition periods. On FR4, signals travel at about 7inches per nanosecond, so there is a good chance you don’t need any matching.

The only problem could be a weak driver that is already struggling to push 200MHz so check the driver’s rise time, that also eats into the budget.

2 Likes
16

The data hold time is only 0.5ns so I calculate roughly 80mm of tolerance. But when I built a prototype by hand with shielded cables, the first attempt didn’t work despite only having 2cm of length variance. The receiving chip would DMA in the correct number of readings, but roughly 2% of the bytes were wrong. The second attempt with <5mm length matched shielded cables then worked out OK. So my guess is 1cm of length variance is my budget. And yes, my oscilloscope shows me that the signal is pretty blurry, meaning I probably lose a lot to rise time.

But mainly, this would just be very tedious and difficult to route by hand, because the board has lots of holes and connectors to route around.

17

@pointhi I have people that I would like to collaborate and exchange designs with that are using Altium and my Eeschema fork isn’t going to be enough (for now) to convince them to switch. That’s why for my personal use case, having an external tool would be more convenient.

I thought I’ll just try my luck at building a DSN/SES file format handler with some convenience APIs and maybe Python bindings.

If my hunch is correct, that’ll enable others to use their algorithmic knowledge to build cool new routing tools.

If I’m wrong, then at least I can use that library to solve my issue at hand.

As for the actual algorithms, I’d prefer to not focus on them too much for now. But in my mental model, my routing needs can be broken down into pathfinding and reordering. I need to get traces from the RAM to a parallel bus and from a parallel bus to the CPU. Plus I need to reorder the traces in between both busses, but there they are just moving in a straight line. During the pathfinding phases, trace lines never cross, so I can avoid a lot of complexity. For the reordering phase, I can decide on the correct exchange sequence by hand so that’s more of a pattern generator than anything clever.

You are of course correct that proper routing in the general case is at least NP-hard and very difficult to solve. But I’m not trying to do that. I just want a simple deterministic tool that solves my issue at hand. But I am trying to plan for the case when I’ll need another tool just like that in the future.

1 Like
18

@qu1ck Here’s a DF12(3.0)-40DP-0.5V with 0.5mm pitch and 0.28mm pads rasterized at 1 mil. The whole thing is roughly 1cm large in real life.

dbg_top

I would argue that 0.22mm clearance = 0.12mm solder mask bridge is the limit of what most people can produce or solder. Yet there’s still plenty of pixels between pads in that image. In fact, I would probably work on a lower resolution to speed up pathfinding… The default setting for the commercial Electra autorouter even appears to be 5x lower resolution than this, meaning it’s making the actual routing decisions on a 5mil grid before then smoothing things into the final positions.

19

When you are routing on a empty PCB, that grid based approach could work. But usually you will have connectors/pins at fixed positions, plus some manually routed sections. Once you start a trace from a connector/chip pin, often the most space-saving route is not on-grid, especially if you want the trace to enter the pad in a way that “looks good”. Same for tightly snaking around existing copper, the closest 45° pass is going to be something like sqrt(2)*grid. At that point, the diameter of a half a pixel will be about the space you lose on average, between every off-grid trace.

20

You are absolutely correct that routing on a grid will waste a bit of space. But on a 1mil grid that would be 0.4mils wasted, which to me seems like most people wouldn’t care.

I now succeeded in building a little tool to do my fanout - but looking back I probably would have finished much faster routing that by hand :sweat_smile:

example_routing
example_routing752×652 51.1 KB

One thing which I learned that I did not expect is that the order in which the traces get routed is the most important factor. With modern hardware, it’s no big deal to churn through 289,000,000 iterations of A* with multiple active paths, but depending on the order in which traces are routed, a single blocked path might undo a lot of otherwise acceptable routes.

So probably a good approach is:

  • try routing things with A* 1000x with random trace ordering and count how often each trace failed
  • now do the cooperative A* with traces ordered according to their failure rate

The whole problem of routing also looks even more attractive for AI, now that I have tried it. One can usually brute force a solution by spending a lot of CPU power, which means one can generate ground-truth data for the AI. But one usually doesn’t want to wait that long, so there might be a usability benefit to having an AI memorize pre-calculated solutions and then just copy&pasting them as appropriate.

Now that I tried my luck, I am more inclined to agree with you.

What I could imagine, though, is that users will use such a library to create the images (e.g. for AI), then create images representing a cost map, then call the library again to run the actual routing. In combination with a maximum distance for the traces to move forward, that could be quite helpful for implementing custom “routing recipes”. The user wouldn’t really be implementing algorithms, instead they would be scripting how they are applied and in which order.

The Mentor Sketch Router video that you linked to appears to me to have two main components behind the scenes:

  1. A cooperative pathfinder that will take a group of pins and route them while preserving their relative order.
  2. A library of via patterns to elegantly reorder traces while switching layers.

But they’re also not showing any case where there would be difficult situations, so I’m not sure how well they could handle a few drill holes in the way :wink:

21

Here’s an example of how I could imagine routing scripts could work.

Capture
Capture708×809 19.5 KB

In this example, the script would be something like

b1=soupToBus(['H2','H3'], d=1,Y=120)
b2=soupToBus(['H1'], d=1,Y=100)
busToBus(b1,b2)

The soupToBus commands will just route pins and pads arranged in any patter to end up on a line, without any regard for pin ordering. For this, there should be algorithms that’ll find a way if there is any.

The busToBus command will route a parallel bus, which again should always succeed if it is possible at all. Afterwards, it’ll use vias and another layer to reorder the traces into the correct order. Since that’s done after the actual pathfinding has finished, it should again always work.

And with the 1mm spacing in between traces, I can add ground pour in-between to reduce EMI and also I have enough clearance to use KiCADs meander feature for length matching.

Also, I’m sure that the output of soupToBus will work nicely with freerouting and other routing tools that start with a Manhattan assumption (meaning that traces are mostly horizontal or vertical, depending on layer).