Autorouter == Specctra to Bitmap+JSON

twl · June 14, 2021, 9:41pm

OK, I must agree that soupToBus function has a very intriguing name But it would be great to know what are the algorithms involved in routing the bus the way you like. Does soupToBus() function call something like readDesignersMindWhereToPlaceTheTracesViasAndOnWhichLayersSoThatTheDesignerIsHappy()?

Jokes aside, as many people in this thread already posted, autorouting is an extremely challenging problem in terms of both algorithms used and complexity (and it’s not ‘just A* path search’). In more advanced routers no grid/bitmap approach is used.

Sometimes merely configuring a top notch, expensive autorouter takes way longer than routing a simple board by hand (and by all professional standards, the example in the previous post is very simple).

PS. If the post above shows the actual 200 MHz routing that requires length tuning, I’m not surprised it doesn’t work.

yoq · June 15, 2021, 1:09am

Simple “Manhattan routing” only works at low frequencies <100MHz, and <10MHz with slow rise times if you care about passing EMI testing.
High speed routing is best looked at as designing a waveguide - the electromagnetic signal travels in 3D space, within the PCB dielectric, with the “signal” line and an equally important GND “line” right below it acting as guiding rails. Even for differential lines, 70%+ of the return is on GND, not the complementary line. This is why, if you plan on passing EMI, you need GND adjacent to every signal at all times, see PCIe pinout as an example: https://pinouts.ru/Slots/pci_express_pinout.shtml
Doing a layer switch is possible, but you need to keep you layer stackup in mind and often need an extra GND via to keep the return current contained locally and stop it from spreading out all over your board and ruining your EMI.

Often, when faced with a tricky routing problem, the right thing to do is not to put in gordian knot with a thousand vias, but to change component placement and also go back to the connector / controller / fpga and look into swapping pins.

fxtentacle · June 15, 2021, 8:03am

FYI, I myself am new to this and still pretty much an amateur, but I know someone who has plenty of experience and they used a similar routing at work.

Yes, that’s also the assumption that I am using. In my case, I learned it from this YouTube tutorial:
https://www.youtube.com/watch?v=ySuUZEjARPY

My knowledgeable acquaintance argued the same way, and then he suggested to put copper pour connected to GND between every two signal lanes. In my picture, I hid the GND pours because otherwise the wire placement would be difficult to see.

So the full routing is that from the pins to the “bus”, there’s the signal trace on the top layer and a matching GND trace on the bottom. Then in the “bus to bus” manhattan matrix, there’s the signal on top with a GND pour on top next to it. Then when the signal swaps to bottom, the GND pour travels with it. That’s why the traces in the “bus” are 1mm apart, so that there’s enough gap for the GND lines to travel alongside the signal lines.

So throughout the entire board, each of the high-speed data wires has it’s accompanying dedicated GND wire which is usually only 0.2mm away.

It starts with pins in an arbitrary location and then routes all of them on a single layer onto a predefined set of potential target locations. So it doesn’t do any vias and it doesn’t care about the wire ordering at all. If you look at this https://youtu.be/PPTc-lYLS0A?t=74 Altium advertisement at 1:14 you’ll see that they advertise their “interactive river route that gives high completion without vias”.

I believe that what you see there could be scripted with my soupToBus on both ends of the red guide line and then the connection drawn by the red line would be busToBus. In their example case, there’s no Manhattan routing on the bus because it’s not needed. The bus is sorted in the same order on both ends. Their example board also has 6 signal layers separated by GND planes, so that makes the actual pathfinding from the pins to the bus much easier than in my single-layer case above…

Also, I’m not trying to build a full autorouter here. I’m patching the gaps that my existing tools have. Since Altium, ELECTRA, and freerouting all failed on my single-layer fanout, I built a tool that can do it. Afterwards, I can still use a “proper” autorouter to connect my wires. So most people would probably skip busToBus and instead continue in freerouting.

And lastly, a complete but only okay routing might be better than an incomplete one. freerouting has a nice post-optimizer which can reduce vias and improve routing, but you need to have a complete solution for it to start working. So people could also skript a draft using steps like this and then afterwards let other tools refine it into a good solution.

That might be correct. But if I had the $500k to buy one of them, I probably wouldn’t bother with KiCAD either

yoq · June 15, 2021, 9:13am

Rick Hartley talks are excellent on this topic, I was about it recommend it
Maybe “adjacent” was not the ideal word choice on my part, better would be to say: there needs to be a continuous ground path running with the signal line at all times. But generally its best for that ground path to be on the plane below, and you only need additional ground lines/pour between the signal lines if you have very strict requirements for reducing crosstalk.
I was mostly thinking of the connectors, because in a row of pins there is no ground plane “below”, and standard practice there would be to alternate signal and ground pins. The connectors ground pins would then immediately terminate into vias into the ground plane right at the connector. It looks as though all the pins on your connector are signal?

Adding flood fill is tricky, because at those frequencies it only acts as ground to an adjacent line if you put a ground via at the beginning and the end. If the pour is only connected to ground with a random via at some distance, its not going to much, because it is effectively a piece of copper connected to ground with an inductor.

Also you probably want to keep the impedance of your traces constant, and you’d have to compensate by making the trace narrower for the sections that have a extra ground line running next to it compared to those that only have ground below. Generally if you add ground lines on the top copper, I’d do it either all the way or not at all.

fxtentacle · June 23, 2021, 8:05am

I’m going to keep using this post as my sort of research notes about routing improvements…

I am getting surprisingly good results just from combining together seemingly primitive steps.

One thing that I see existing autorouters struggle with again and again is doing a fanout that will provide a good starting point for future routing. I can do that by hand much better and it is highly repetitive. Looking back, a lot of it boils down to turning the 2D pin/pad locations into a linear sequence, so I have decided to extract that out of soupToBus and turn it into its own function calculatePinOrder.

Starting the routing with the correct pin order is highly important, because in many of my test cases basic A* pathfinding gives great results if - and only if - pins are routed starting with the most difficult one first and then always routing adjacent pins to prevent the situation where a past trace will block the path for a future trace.

For most connectors, a simple circular order works well, so

b1o = calculatePinOrder("H1", "circular", "H1-15");

generates

ROUTING ORDER 00: NET 06  H1-15
ROUTING ORDER 01: NET 04  H1-13
ROUTING ORDER 02: NET 08  H1-17
ROUTING ORDER 03: NET 02  H1-11
ROUTING ORDER 04: NET 39   H1-9
ROUTING ORDER 05: NET 37   H1-7
ROUTING ORDER 06: NET 10  H1-19
ROUTING ORDER 07: NET 35   H1-5
ROUTING ORDER 08: NET 22   H1-3
ROUTING ORDER 09: NET 00   H1-1
ROUTING ORDER 10: NET 13  H1-21
ROUTING ORDER 11: NET 41  H1-S2
ROUTING ORDER 12: NET 15  H1-23
ROUTING ORDER 13: NET 17  H1-25
ROUTING ORDER 14: NET 11   H1-2
ROUTING ORDER 15: NET 33   H1-4
ROUTING ORDER 16: NET 19  H1-27
ROUTING ORDER 17: NET 36   H1-6
ROUTING ORDER 18: NET 38   H1-8
ROUTING ORDER 19: NET 21  H1-29
ROUTING ORDER 20: NET 01  H1-10
ROUTING ORDER 21: NET 24  H1-31
ROUTING ORDER 22: NET 03  H1-12
ROUTING ORDER 23: NET 26  H1-33
ROUTING ORDER 24: NET 28  H1-35
ROUTING ORDER 25: NET 05  H1-14
ROUTING ORDER 26: NET 30  H1-37
ROUTING ORDER 27: NET 32  H1-39
ROUTING ORDER 28: NET 07  H1-16
ROUTING ORDER 29: NET 09  H1-18
ROUTING ORDER 30: NET 40  H1-S1
ROUTING ORDER 31: NET 12  H1-20
ROUTING ORDER 32: NET 34  H1-40
ROUTING ORDER 33: NET 31  H1-38
ROUTING ORDER 34: NET 29  H1-36
ROUTING ORDER 35: NET 14  H1-22
ROUTING ORDER 36: NET 27  H1-34
ROUTING ORDER 37: NET 25  H1-32
ROUTING ORDER 38: NET 23  H1-30
ROUTING ORDER 39: NET 16  H1-24
ROUTING ORDER 40: NET 20  H1-28
ROUTING ORDER 41: NET 18  H1-26

and then afterwards

b1 = soupToBus("H1", b1o, (800,0), (0,15000))

will do the pathfinding for connector H1 with the ordering from b1o onto a line with 0.8mm offsets in the x direction and placed 15mm above H1. And that produces:

I have also had to do some BGA routing on a 8 layer board and despite having 6 signal planes to work with, all 3 of my autorouters failed me again. I even asked an acquaintance with access to all the pro tools and they didn’t do a good job either. I know that BGA fanout is difficult, but for this specific case, I could manually route it with just top and bottom layer, so there is A LOT of room for improvement for those autorouters.

The correct approach to route that BGA was in my opinion:

route all the pins on the outer ring of pads directly on top, or at least fan them out a bit to make space
route whatever you can from the 2nd ring of pads directly on top
place dogbones for everything left, working from the outer to the inner rings and if given the choice, always use the outermost via location
go ring by ring from inside to outside and route the vias

To me, that seems like one can build a BGA-mode for calculatePinOrder which will encodify what I do manually anyway. And afterwards, it then boils down to simple pathfinding again.

Now is this going to do routing fully automatically? No. But if instead of spending hours doing manual routing, I can call a few of these functions and have my BGA, connectors, and data bus routed in a sane way, that will save me a lot of time.

Maybe every footprint should have two new parameters, namely an ordering class and a routing class to specify default values. My DP12-40 connector would be ordering circular while the BGA would be ordering BGA 2row direct or something like that. That should provide tools with enough information to derive a good pin ordering (which is crucial for routing) and it also gives the user control to tweak things, if needed.

As for the routing class, I find it really irritating that freerouting treats everything as equally valuable. I want it to first do all the length-matched data traces. Then once those are finished, it’ll route auxiliary signals around them. Once that is finished, only then should it do routed power and ground. So to make the autorouted results good and usable, I need a way to specify which pins and which components are important to me.

fxtentacle · June 24, 2021, 1:43pm

With a bit more research, I stumbled upon

Apparently, the concept that I called “soupToBus” above is called “Unordered escape routing” by Synopsys.

They also talk about their optimize topologies for BGA and other grid-arranged connectors, which suggests to me that professional autorouters ship with a library of known footprint shapes and optimized pin assignment and ordering algorithms for each of them.

The way I understand it, if they detect a BGA, they can calculate from pitch and trace width and clearance how many wires can fit between the vias placed for two adjacend BGA pins, which is usually 2. That allows them to construct a graph which means they can treat the actual routing like a 2D pathfinding problem.

One amazing idea which I found in https://doi.org/10.1145/1735023.1735033 is that by allowing each grid cell to have a capacity > 1, one can “flatten” a multi-layer routing problem into one single pathfinding grid.

Using integer linear programming (ILP) and/or heuristics and/or rip-up-and-reroute, that “Unordered escape routing” can then be upgraded to “Ordered escape routing”.

Applied to my attempt here, that means soupToBus(.. calculatePinOrder() ..) will do an unordered escape, while using a clever function to optimize the pin routing order the same pathfinding can be used to do ordered escape routing.

In https://doi.org/10.1109/ICCAD.2004.1382689 a very clever approach is then introduced, where they do ordered escape routing multiple times with random pin orders and store the results of which pin orders were successfully routed. That allows them to pre-optimize the bus routing because they can then choose for each component the escape routing that is most consistent with the pin orders of all other components.

fxtentacle · June 24, 2021, 2:10pm

Another interesting approach I learned about is the bus handshake:

Like this, all traces change the layer and every trace of the top (green) bus can be connected to every trace of the bottom (blue) bus, just by placing the via at the the correct intersection.

In effect, this makes it easy for routers on multi-layer boards to do arbitrary pin order changes. Because if you only re-order traces, then that means that you will never have two vias on adjacent horizontal traces, so as long as the via diameter is smaller than 2 traces and their clearance - which is almost always true - there cannot be a placing issue for the via.

paulvdh · June 24, 2021, 4:20pm

I’ve been reading this thread a bit (just like all others) but did not response earlier because I had nothing to add and did not know where it was going.

It looks like you’re thinking about or designing autorouter algorithms based on extremely simplified and “neat” examples. and they are all trivially simple to route. But such are nowhere close to any real-world application. (I do understand you have to start somewhere).

My “favorite” PCB is the A64-Olinuxino. It’s still a relatively simple PCB for today’s world, but has enough complexity to make proper design techniques and routing mandatory. It’s also an open source project with the complete KiCad project downloadable from github (See: https://www.kicad.org/made-with-kicad/ for links to this and other projects to experiment with).

If you put such a PCB in an autorouter, my expectations for it to give passable results is not high.

I’ve never had much faith in autorouters myself (although I know the can be great tools in some cases). I do like the interactive router in KiCad very much. I’ve also seen some hints that other (big) companies are putting less emphasis on full autorouting, and are putting more effort into “guided routing”, “path routing” or whatever they call it. The Idea is to leave the high level overview to humans, and let the boring and repetitive details be filled in by computers. The Idea is to assign some PCB space to (for example) break out a databus from a big BGA chip into some direction (Human draws a rectangle, and gives a direction, PC draws 32 track stubs) or to define a PCB area for such a databus and the PC routes it between two footprints.

There have been some posts about this on the past, and also with links to youtube video’s.

An autorouter has to be very complex and takes a lot of development time before it can become very useful. The interactive router can be extended with small semi-automatic routing functions to speed up routing.

fxtentacle · June 24, 2021, 5:59pm

Thanks for pointing me at that Olinuxino project, @paulvdh I guess when I need to route RAM myself, that’ll be a great example especially because they were kind enough to include older revisions, which means I can also look at what they decided to change after trying out the earlier prototypes.

Well, I’m trying to automate what I need to route myself. Today, I finished a board that routes a DF12-DS80 plug onto 2 DF12-DP40 receptacles and some 2.54mm pin headers. For some reason, freerouting, Altium, and Electra all failed at the fan-out of the DF12-DP40. That socket is surrounded by drill holes and the autorouters got stuck trying to squeeze too many traces through too few gaps. That’s why I started with a small tool to do the fanout for me.

Yes, that is also where I am trying to go. That’s why I have one library for objects and algorithms and then the actual script which uses that library. My hope would be that sometime in the extended future, others can also use my library but combine it with their scripts.

Yes, that is precisely what my soupToBus function does. You provide it with a designator and a list of pins and it’ll route all of those pins side-by-side towards one position on the board.

That’s my busToBus. You provide it with two buses and it’ll connect them and reorder the traces as needed.

I agree that a good autorouter is most likely out of my reach. Accordingly, I’m building small routing functions and a library that allows me to more easily combine them into bigger constructs.

But I wouldn’t dismiss a mediocre autorouter. For my projects, I need many PCBs that are basically just “connect plug A to socket B with some resistors, leds, and switches”. Yes, there might be a few things with high frequency and I’ll need to route them by hand. But for just connecting LEDs to sockets, I’d want to have a 1-click solution.

fxtentacle · July 29, 2021, 9:02pm

In case someone is wondering how useful an image-based approach like I suggested here is in practice:

I received my USB3 + FPGA boards today and they work

When I routed the board, I used the A*-based tool I had described above to do all escape routing and via placement. It has two integrated rules for determining the pin order, which are either from inside to outside for BGA or in circular order for TSOP. The escape routing itself is done only on the top/bottom layer and then via placements are propagated to all layers. That generated those images (along with matching routing data for me to copy back into KiCAD):

Since the board has 6 layers, it was afterwards really easy to connect the via from the FPGA with the associated via for the TSOP or connector. The main script I used here was

    hadroki.Read("./USB3.dsn");
    hadroki.EscapeCircular("H1", 3);
    hadroki.EscapeCircular("U4", 1);
    hadroki.EscapeCircular("U5", 1);
    hadroki.EscapeBGA("U3");

so there isn’t much intelligence needed from the tool itself, because I manually specified which designators I want escaped and in which order. But despite its simplicity, this sure saved me a lot of time.

BTW once those vias are placed, the topology of each routing layer is afterwards fixed, which means that one can then use topological routing algorithms on them. For example, freerouting fails to route this board from scratch, or it takes more than 24 hours to find the solution, because I eventually cancelled the search. But once the vias are placed, freerouting can correctly connect them almost instantly.

Of course I did the USB3 stuff by hand, but for slow things like SPI from the FLASH to the FPGA, the automatic routing solution looked “good enough” to me.

system · October 27, 2021, 9:02pm

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.