Topo-geometric detour router
2. Detour search
This chapter focuses on the topological (high) level of the router and assumes
the geometric (low) level is available and can calculate the geometry of
a detour of a trace object and a network.
2.1. Board state
The routing is driven by the detour search performed on possible
board states. A board state is a specific render of the board, all
two-nets realized with copper tracks. A board state does not need to be free
of short-circuits. Each copper object is explicitly bound to a network.
The initial board state is:
- all terminals and unmovable objects are placed
- all two-nets are connected with straight copper lines on the first layer
The initial board state usually contains a high number of conflicts:
short circuits caused by objects of different nets crossing, overlapping or
getting too close.
2.2. Detours
Each conflict, regarded as an isolated case, considering only the two
two-nets participating needs to be resolved. One way of doing that is
writing an ordered list of resolutions. Figure 2/1 shows the possible resolutions
of a simple crossing.
Figure 2/1.
a. Input: Two 2-nets, N1 and N2 are crossing at #1. Yellow lines are the initial
two-nets, blue lines are final choices, grey lines are alternative choices.
Possible resolutions:
b. N1 goes around N2 on the left or on the right;
c. N2 goes around N1 on the top or on the bottom;
d. two vias are inserted in N1 so it can bypass N2 on another layer;
e. if endpoint terminal of N1 is through-hole, one via can be saved;
f. ... or even both vias can be saved;
(Note: there are three more possibilities with vias where N1 goes to another
layer, these would have been drawn as g., h. i.).
To go from the initial state (a.) to any of the resolved states (b. to i.),
we need to define an operation. For example the operation for b. is
"N1-N2 CW" for the right-side solution and "N1-N2 CCW" for the left-side
solution. "N1-N2 CW" means "on N1 at the first crossing of N2, N1 makes
a detour to go around N2 clock-wise". To be able to determine which is the
"first" crossing on N1, each two-net has one of its endpoint marked as the
starting point.
Note: if there are more than 2 layers, each new layer adds 6 more possible
states using vias.
2.3. Choosing between detour options
It is possible to draw a tree of the possible solutions. Each node of
the tree is a board state and each edge of the tree is an operation
which transforms the parent state into the child state.
The complete tree for the above example is shown on Figure 2/2.
Figure 2/2. The detour tree of Figure 2/1.
Let us consider a slightly more complicated case with three 2-nets and
two crossings (Figure 2/3).
Figure 2/3.
a. Input: three 2-nets, N1, N2 and N3 are crossing at #1 and #2.
Yellow lines are the initial two-nets, grey lines are final choices, blue lines
are alternative choices. Steps b. and c. shows the search
progress of a possible resolution.
First step, b. tries an N1-N2 CW. This resolves #1. The next step, c.
tries a N1-N3 CW, which resolves #2. So the final script is:
N1-N2 CW
N1-N3 CW
An alternative solution in c., drawn with blue, is N3-N1 CWW;
given there is enough space, between N2 and N3, this would also resolve
#2. This would change the second line of the script from CW to CCW.
Another alternative to step c. is leaving N1 as is and make a detour
with N3: N3-N1 CCW. This is a valid solution to the problem and is
drawn on Figure 2/3. d. and the corresponding script is:
N1-N2 CW
N3-N1 CCW
Another alternative in c. would be to do an N3-N1 CW. This is a valid move,
but introduces a new conflict, marked as #3 on Figure 2/3. e. Since there
is a conflict, state e. is not a solution. However, with one more detour,
N2-N3 CCW it can be a solution: Figure 2/3. e, or as a script:
N1-N2 CW
N3-N1 CW
N2-N3 CCW
The above part of the state tree is drawn on Figure 2/4.
Figure 2/4. The detour tree of Figure 2/3. Initial state is a., states that
are acceptable solutions are marked red, further subtrees omited from are
indicated as "...".
(Note: the tree can grow deeper than the number of crossings, since an operation
can introduce one or more new crossings.)
The above example showed three different
valid solutions (and omitted a lot more, including using a second layer).
These solutions differ in cost, which is normally a function of total wire
length and number of vias. If the goal is to find the board state for the
least-cost solution, it is very likely that all possible solutions would need
to be rendered. That is not feasible as the search space explodes
with the number of two-nets growing.
However, if it is enough to find a relatively good valid solution, it is
possible consider only a part of the tree. For example it is possible to
implement an A* search on the state tree using the following considerations:
- the target, when the search stops, is the first time the number of conflicts is zero
- the cost function combines total wire length and number of vias of a board state
- heuristics is the a function of the number and severity of conflicts of a board state
Furthermore there are ways to reduce tree size early on:
- if a conflict arises between a two-net and a non-movable object, the state is invalid
- when considering a new state, if a two-net introduces a new conflict with another
two-net which it already had a conflict with in any parent state,
check if the same object in the other two-net is affected as in the
parent state; if so, this is likely an oscillation (see section 4.1.7);
this state is invalid and should be discarded
- always choose the first conflict on a two-net to resolve, since this
may resolve further conflicts automatically (see section 4.1.2) plus
keeps the decision tree smaller, removing redundant options.