The Unravel Algorithm - Untwisting PCB traces

An algorithm for untwisting PCB traces within a HyperGraph

After we run a HyperGraph Autorouter, we’re left with a “high level plan” on how to route our circuit board. HyperGraph multi-path pathfinders are great at minimizing the number of trace intersections using the space on the board- but they suffer from the same issue that almost all sequential path finders suffer from: they are highly sensitive to the order you choose to route traces in.

We do many tricks to reduce the impact of ordering, such as building congestion maps and using rip’n’replace, but at the end of the day there are just too many possible orderings, for a simple board with 50 traces, there are 30,414,093,201,713,378,043,612,608,166,064,768,844,377,641,568,960,512,000,000,000,000 possible ways to order the traces. You’re not going to enumerate that!

So what can we do? Enter the Unravel Algorithm.

Unraveling a HyperGraph

The unraveling algorithm takes an existing hypergraph, or a section of an existing hypergraph, and asks “what would happen if I swapped the assignment of ports at the boundary between regions?” This swap is a “mutation”, and our goal with the unravel algorithm is to improve small sections by finding small sets of mutations that reduce the number of via-causing intersections.

Unravelling uses A* and tracks a “path” of mutations. If a mutation path is winning, it continues to follow it. If a mutation path gets long or isn’t yielding wins, then it is pushed to the back of the queue.

Because unraveling can work on sections of a HyperGraph, it can execute in parallel and even has the possibility of recalling cached graphs. We’re able to correct all the “criss-crossing” that would have made for a messy, via-heavy high density route.

Because there is often a port at each layer of the PCB on each point, layer swapping is built in. Where it’s possible to swap to a different layer to avoid vias way later in our path, our mutation will apply it.

Our routes are now ready for high-density routing with the lowest number of vias.

Conclusion

The Unravel algorithm enables adjustments to global pathing to minimize the complexity of high density routing and reduce the impact of trace ordering on global pathing. It’s a highly parallelizable algorithm that can do no harm because it only accepts beneficial mutations.

If you’re interested in contributing to our autorouter or attempting some difficult algorithms, join the tscircuit discord or yell at me on twitter.