Things I would have told myself before building an autorouter

We will absolutely be supporting KiCad! Placement is something we have big plans for but I think it’s important to have a really fast, cache-friendly autorouter as a foundation (if you are cache friendly, moving components and trying different layouts is much much faster)

Javascript is fairly portable now with many runtimes (some even quite small such as QuickJS or Proffor), so I anticipate people will be able to run locally and build their own ginormous cache :)

I think everyone should be concerned about lockin and fragmenting ecosystems in EDA, but tscircuit and our autorouter are MIT-permissive technology (very rare in EDA) so we play nice (interoperable) with everyone.

Years ago the long-gone and unlamented OrCAD Layout had a spreadsheet view of your nets that was a slightly better than good-enough interface for setting constraints for autorouting. Once you got your footprints, placement, constraints, and hand-routed nets locked down, you could iterate very quickly.

It's nice to see anyone at all working on PCB autorouters, which have been pretty stagnant since Cadence bought SPECCTRA in the nineties. The guys who wrote SPECCTRA went to the VLSI world iirc and never came back - I guess that's where all the fame and fortune is. Probably was a patent minefield for a while there too; might still be. Autoplacement was an utterly intractable problem back then, still seems to be, and it's probably ripe for a generative AI approach - a good generative AI first pass at parts placement could be a net time saver. The biggest problem would be convincing the cranks that you can be good even if you can't be perfect.

I'm sort of puzzled by the kids out there trying to do schematics-as-code. On the one hand, I would love to see that work as a backend format - especially where folks like the jitx guys seem to be making a lot of progress in encoding appnote and datasheet-level design rules into parts models. Reading every datasheet in the detail needed for commercial designs is more work than people expect, and so is getting junior engineers on board with the process. So any automation there is beneficial. The problem is that the approaches all seem rooted in this idea of schematics as data entry for layout, a kind of source code, rather than as design documentation with a carefully evolved visual language that needs to be accessible to people who won't have an EDA suite installed on their computer. I guess people who learned from puzzling out schematics in the Adafruit/Sparkfun/Shenzhen style with explicit wiring minimized might not understand the value of a good schematic.

The other thing is leaning too far into thinking-by-analogy and trying to make PCB-level design like VLSI design. I don't think it's entirely impossible - if we had better tools for DRC and validation, component-level design would look more like VLSI design. But the design space is so different, with such loose coupling between design, EDA/CAM/simulation, validation, fabricators, assemblers, component vendors, regulators/certifiers, and so on that just getting one corner of it really right would be a major accomplishment.

For any benefit the auto-router adds, it usually ends up costing a project later...

In general, impedance controlled UHF design work with domain specific simulation tools is the modern workflow. Thus, one manually does the critical tracks first, island-pours, and finally power interconnects.

KiCad is slightly better than nothing for layout, and trying to make it into yet another half-baked simulation tool seemed silly. =3

The tools are fractured, the existing players are lumbering behemoths, and the users are cranky zealots (you will have to pry KiCad out of my cold dead hands).

These last five years have been absolutely incredible to watch in Kicad’s development. Last two releases have added the two major things that Kicad didn’t have that professional CAD tools did:

* database support

* outjob features

Beyond that, it’s really just a matter of adoption and end user preference of how to put these features to work. (Databases tend to come with a lot of internal corporate bureaucracy around organizing data than anything else.)

But, for the topic at hand: don’t you think Kicad is already moving sort of in the direction you talk about, as far as workflow to speed up layout is concerned?

Best example I can think of is the “trace autocomplete” feature in I think 7.0. Hit hotkey (I think it’s F in pcbnew) and the trace will be laid for the track currently being placed. Combine this with the “route from other end of track” (hotkey E), this is a blazing productivity boost, especially when you’re working across two different ball out grids.

Version 9 enabled buses/multiple tracks to be draggable, meaning this whole system could go even faster still.

Many times when starting a design my placements aren't set and that has a huge impact on routing.

Honestly, I’d trust an autorouter to complete a good chunk of my designs if I can get to a placement I’m satisfied with, and I can give the autorouter some constraints on where to route. For example: did a board last year using an NXP iMX8MP with an eMMC. The peripheral ballout on the processor matches the eMMC ballout really nicely - was just a matter of lining the chips up and drawing the lines. An autorouter could have done in seconds what it took me ~10 minutes if it had known to keep everything in the data bus on the top layer.

I think that’s a success criteria autorouter projects suffer from: they don’t consider their autorouter “done” unless their router can do _everything_ on a board. As a working EE, I don’t actually want that. I want an autorouter that can work with me to do a satisfactory job on a little chunk of the design at a time, give me some time to review it for correctness, then move on to the next chunk.

That would be killer. Especially if you could give constraints beyond layers: I.e “keep all nets with names D0-7 on layer one and three, and match their length to 5mm of one another. Use D0 as the net length reference.” If you can do that, then boom: you’ve solved DRAM length tuning. Huge range of design complexity now within reach of the unwashed masses.

OP - if I can find some time to show you what I mean, I’d be more than happy to give you a demo of what I’m talking about.

I once had to do bringup on an autorouted prototype PCB. The traces between the CPU and DRAM looped three times round the board.

> Point 8, the fast dismissal of Monte-Carlo method is a huge blunder.

Yeah, I had the exact same reaction when I read the article.

MC is the "keeping it real" algorithm, slow, but almost always dead simple to implement and that can be trusted with super high certainty to double-check that you've not completely wandered off in the weeds.

I was this many days old when I learned the word "imbricated".

Yet the author mentioned simulated annealing, so was probably not even trying a neural net, since SA does not compute a gradient.

Haha I feel like the right reaction to "vibe-*" is to cringe. I cringe a little bit every time I see someone promoting a vibe-coded app at the moment, but I think back to how I got started in coding (I was constantly annoying people on old ActionScript forums to fix my code) and I see so much potential in people being able to get started quickly in any domain. I hope that our autorouter (and others that follow!) will similarly allow people to ship their first electronics without needing tons of guidance or formal education.

That said a good autorouter should also be useful to professionals! So hopefully we help with that as well!

I wish these folks well and hope that their autorouter gets folded into KiCad.

However, as one of the cranky old people who don't really want to see KiCad expend any energy on autorouters, PCB autorouters are a pain in the ass that never work.

We can look at VLSI autorouters to determine why that is. VLSI autorouters also were a pain in the ass that never worked. But what happened was that VLSI suddenly got lots of layers and you could dedicate a layer to routing vertically, a layer to routing horizontally, a layer to routing power and still have a couple of layers for global vertical interconnect, global horizontal interconnect, and global power.

The fundamental problem with PCB autorouting is that PCBs have WAY more obstructions than VLSI chips do. First, components themselves are obstructions and choke points. Second, PCB vias almost always obstruct all the layers of the board while VLSI vias only obstruct the two layers being connected. Third, PCB vias tend to be bigger than your interconnect metal width. Fourth, the number of PCB layers in use is way smaller than the number of layers in VLSI--the most common numbers of layers are 4 layers (most projects--of which only 2 are really used for general routing), 2 layers (because of cost engineering--good luck autorouting these) and 6 (a tiny minority).

It all adds up to PCB autorouting being a significantly more complicated job than VLSI autorouting.

> recursive == DFS

The intuition there is that people tend to write algorithms recursively when they easily map to interactions with the top of the stack, since that's easier to express in most languages than bringing in an external stack to think about. Hence, if you see something recursive in the wild it likely looks more like DFS than BFS. As you point out, that isn't a hard rule.

Indeed, BFS, DFS, and A* are the same algorithm just with a different data structure to track unexplored nodes. BFS uses a FIFO queue, DFS uses a LIFO stack, and A* uses a priority queue (generally a heap)

No you don't have to search whole graph with BFS (it might happen if source and target is on opposite corners), first time you reach a node you know 100% that it is the shortest path. That's one of basic invariants allowing BFS to produce correct result, you can terminate early when all targets are reached. A difference between A* and BFS is that instead of searching shortest path between two points BFS finds shortest path from single point to ALL points in graph. A* makes a tradeof of speeding up individual query by answering to weaker question. When problem allows it replacing thousands of A* calls by single BFS or Dijkstra call can give a major speedup. Another important difference is that BFS only works on graphs where all edges have same length, A* supports mixed edge lengths. They are not interchangeable, just like finding minimum element in a list isn't replacement for sorting the list.

Measure measure measure measure. Each case is different.

But more seriously I think tree based algos tend to be overhyped, and people get a bit absorbed into thinking about big-O behavior when the constant factors are super important even when you’re looking at hundreds of thousands of elements. Not to mention stuff like data locality. Like sometimes your computer will be faster at just looking in a seq scan rather than dealing with the bookkeeping of a fancier structure. Sometimes.

I think a nicer argument overall is to build a tiny wrapper around your operations, build out what is easy, and then figure it out through measurements.

Worst case you end up entirely rewriting your program to accommodate a different structure to try for better perf but in my experience rewriting entire files from scratch tends to get you a good number of improvements for free.

For 3D I found octtrees very effective and fast. In my implementation you can even move items around without having to regenerate the tree.

I have yet to find a satisfactory way to store points (in 2d or 3d) and be able to query nearby points. a kD tree is nice, but I want to add points as I go, not build a structure around a fixed set.

It is a really fun idea to build a boids router (shelving that for a future article!) I wrote previously about recursive pattern autorouters which are really good at having small solution spaces (and therefore, easier to get conventional machine learning algorithms to predict). There are so many interesting unexplored areas in autorouting!!

I hadn't heard of jumpflooding (for others: fast, parallel algorithm for approximating distance fields), that could definitely be interesting, thanks for the tip!

I think the trees were a lot more useful in the past when memory and caches were smaller (and I suspect they can still be useful for precomputation, though I'd have to sit down and benchmark fixed-grid-with-smart-sizing vs. tree). Trees are also amendable to recursive algorithms but the author has noted that they have reasons to choose iterative over recursive algorithms, so these pieces of advice synergize.

(It is perhaps worth noting: broadly speaking, "recursive" vs. "non-recursive" is a bit of an artificial distinction. The real question is "does a pre-baked algorithm with rigid rules handle flow control, or do you?" If you care about performance a lot, you want the answer to be you, so having your run state abstracted away into an execution-environment-provided stack that you can't easily mutate weirdly at runtime begins to get in your way).

Algorithms are a lot more fun now that LLMs have all the geometric heuristics memorized. I think a lot of algorithms are just inescapable in game development, so if you're itching to make an algorithm making something like like a tower defense game has a lot of classic algorithms involved!

The core problem is a severe mismatch between academic curricula and what the job market actually needs on one side and the fact that companies use "needs a college degree" as a proxy to weed out risk and bypass ADA/anti discrimination laws. Both are a massive drain on the economy.

IMHO, at the very least the current CS degree needs to be split up - CS should be split into various smaller (and faster achievable) subdegrees - the fancy math stuff should be its own degree, possibly be fused with a new degree relating to AI, database and network theory should be its own degree, and frankly stuff like low-level assembler as well, and the "how do electronic components, NAND gates, boolean logic and whatnot work" moved off to electronics engineering. And what the market actually needs the most - people who can crank out CRUD app stuff - should be either its own degree if one insists that this needs academic knowledge, or be moved off to something like trades education.

In parallel, the job requirements gatekeeping should be tackled by laws - companies must no longer be allowed to require degrees that have little to no impact on the actual job duties. It's forcing our children to waste years of their life and take on five to six figures worth of debt, all only for companies to be able to weed out people.

I think there's a fair argument to be made that when you're chasing Big O algorithmic improvements, then the effective constant terms incurred by "faster or slower language execution" are premature optimisation. The difference between Rust or hardcoded assembler compared to Javascript or VisualBasic are pretty irrelevant if you're still trying to get your exponent or polynomial terms under control.

I think Javascript might doom the autorouter to small scale designs or very long processing times, but I have never used tscircuit so maybe I'm wrong.