Close

First Steps

A project log for My Auto-Router

I am not that impressed with auto-routers. Why are they so bad?

agp.cooperagp.cooper 07/20/2019 at 02:230 Comments

First Steps

There is a lot of work setting up the interface between the schematic capture and PCB layout applications and the auto-routing applications. So I will just read in a simple text files to begin.

The Schematic

One of my first PCB schematics was a DTL (Diode Transistor Logic) three input NAND gate. Here is a KiCAD version.

First the KiCAD schematic:

And the KiCAD PCB:

Now I have tried to get a single sided PCB version of this design (in Eagle and EasyEDA) but it is surprisingly difficult to do. KiCAD does not even offer the option. In the end I had to hand route a design (okay it has nine copies):

With a bit of imagination you should see the KiCAD PCB here (map.txt):

And the links list:

SRC DST
 1    7
 7    8
 2   13
13   22
 3    9
 4   10
 5   11
 6   24
24   25
12   14
14   19
14   15
15   16
16   21
17   18
18   23
18   20
26   27

After a Day of Coding

Here is a series of images as I debugged and got the penalty function working.

Well its just about getting something on screen to look at!

I want to penalise paths that get too close to the pins (thus the small red dots):

Note: The red tracks failed to find a legal path. A diagonal path between tracks was consider illegal.

Here is a working case:

Note: The links are exactly honoured and thus the ugly links.

Finally with a pseudo-Steiner Tree modification gives a pretty reasonable result:

So for a single side PCB I have a result that works (for the small example).

So how is that, all of the above in less than 600 lines of code!

A lot more to do, add multi-able layers and back-tracking when the algorithm fails.

Update

Added some code to randomly swap around the links to see if I can improve the result.

I gave the router 1 second, it looked as 2083 options and reduced the penalty from 682 to 582:


I have been looking at the passes that failed to determine if there is an easy heuristic I could apply. Even in the above image the I can see faults that could be fixed that would improve the success rate.

A couple of papers suggested:

Currently I completely randomise the links for a run and run a many as I can in one second.

Here is an example where I use the above approach (i.e. a single run) but include a congestion penalty:

You can see that the congestion penalty has moved the tracks away from the pins (and other tracks) leaving space for later tracks. This in my mind is a pretty good result (for a single run). Without the congestion penalty you get:



Code

I have posted the code for the above.

Paper by Eric Rosenberg on Iterative Routers

I found a paper by Eric Rosenberg that describes an iterative method for improving the router performance. Here is a simplified version of his algorithm:

It should be noted the algorithm can be unstable and much of Eric Rosenberg's paper is about approaches to resolve this issue.

AlanX

Discussions