Topological Autorouter¶

In this article we will cover the various behaviors of the JITX Autorouter, with particular attention to explaining its topological nature and how this affects its behavior in various situations.

We will cover the following three main interactions with the autorouter

Autorouting with Q
Repositioning - recreating routes after objects have been created, deleted, or moved
Manual routing or rerouting with Shift+Q

Note that despite the name, “manual” routing also uses (parts of) the autorouter, because in the JITX architecture all routes are represented topologically.

We should clarify the usage of the term route. In the context of the topological autorouter, one route means one leg or segment of a route which connects two objects (pads, vias, or control points) through free space on a single layer. A “route” in the broader sense may then continue by additional routes originating at the previous route's terminus, but as far as the autorouter is concerned, these are different routes.

Note also that the autorouter only ever operates on one layer at a time.

In addition to basic autorouter interactions, we will als discuss the following closely related topics that influence or are influenced by the autorouter:

SI routing - how to set it up, and how it interacts with the autorouter
Adaptive route shapes
Overlapping shapes - rules for when they are subtracted or merged

Basic usage: autorouting¶

Select two or more objects, such as pads, and press q. The autorouter will try to find as many legal routes between objects in the selection as possible and add them to the board. Routeable objects include:

pads
vias
control points (used in SI routing, or to manipulate route geometry)

and legal encompasses:

both ends of the route are
- routeable objects
- in the current selection
- on the board
- have no illegal overlaps
the two objects can be legally connected, considering the combined effect of the design's
- nets
- legal pin assignments
- topology constraints (for SI routing)
the search algorithm is able to find a route which satisfies design rules including
- trace width
- clearance to all board obstacles
- clearance to other routes
- any applicable overrides to the above.

The basic workflow can be enhanced by using shortcuts to select relevant objects quickly:

Press A to select objects on the same net as any selected object
Press Ctrl+A to select objects which can legally be connected to a selected object

Basic usage: manual routing¶

This section covers two different, but closely related, interactions:

Manual routing - guiding a topo-route by hand between two endpoints.
Manual rerouting - modifying an existing route by replacing a portion of it with a manually guided route.

In the JITX Physical Design UI, manual routing does not refer to drawing exact route geometry by hand. Rather it refers to an interaction whereby you can specify a route topology by hand. All other aspects of the route are still determined by the autorouter.

To draw a manual route, you do not need to have any objects selected. Press Shift+Q, then click on a routeable object, then click zero or more times anywhere you like, and then click on another routeable object. If the objects can be legally connected, the autorouter will try to create a route which follows the topology given by this sequence of points.

Manually rerouting is similar, except that for one or both endpoints you click somewhere on an existing route instead of a terminal object.

When you draw a full route manually, internally the autorouter follows this algorithm to determine a topological route:

Take the piecewise linear path through these points.
Deform the path continuously, shortening and smoothing the corners gradually, without moving through any obstacles, until the path becomes as short as possible. (See the discussion of topo-routes below.)
Apply the trace width and clearance rules to the path. If all design rules are satisfied, the route succeeds.

Basically, if running the full autorouter is not giving satisfactory results, and you want to guide it by having a route go around an obstacle in a particular way, you can click a jagged path around that obstacle and the autorouter will smooth it out for you.

Manual rerouting is similar except that the router will take additional guide points from the existing route. (Exactly what those guidepoints are depends on that route's RBE.)

Inner Workings¶

In order to discuss advanced usage and troubleshooting, it will be helpful to dig a little deeper into how the autorouting algorithm is structured. When the autorouter is run, it goes through these steps in order:

Determine the legal connections among selected objects.
Autorouter: search for topological routes (or topo-routes for short) which make legal connections and fit within design rules.
Realization: compute the minimal geometry which follows the found topo-routes while respecting design rules.

As a terminological note, we sometimes refer to this entire process as autorouting, but properly speaking that would only refer to step 2. Step 2 attempts to solve an NP-hard problem whereas steps 1 and 3 are straightforwardly deterministic algorithms, even though their behavior can still be complex and occasionally hard to predict in practice.

One reason to know these steps is that the consequences of each individual step failing are different.

If there are no legal connections where you expected them, that typically means the board was not set up correctly or you accidentally selected the wrong pads. If there are no legal connections in the entire selection, you will get an error message similar to
```
There are no valid connections in the selection.
```
The autorouter proper, i.e. the search for topo-routes, may fail to find valid routes even where they exist. Or, it may find some strategically inadvisable routes which then cause other routes not to be able to fit, when a better strategy would have allowed all possible connections to be made. There are some messy heuristics for when the search will give up in various scenarios to save on cpu time, so a failure here does not necessarily mean the selection is not routeable. If the selection has legal connections but no topo-routes could be found, you will get an error message similar to
```
Unable to find a valid route for the selection.
```
Realization may fail to produce concrete geometry that satisfies design rules even though the topo-route in question passed the autorouter's checks. This can happen for a few reasons:
- design rule checks necessarily involve approximate floating point calculations, and the autorouter and realization algorithms necessarily use different data representations so they may disagree in edge cases.
- in cases with unusual geometry at the endpoints of the route, such as differential pair control or merge points, these approximations are especially prone to diverging due to the special restrictions on how routes may enter or leave these controls.

When realization fails, instead of giving up completely on the route, the topo-route is still added to the design as a Rubber Band Equivalent (RBE).

Note that if the autorouter runs a long time, already committed routes are shown as RBEs so you can track its progress even before realization runs. This should not be confused with RBEs that are left in the UI even afterwards due to a realization failure.

Topological Routes and Rubber Band Equivalents¶

Topological routes (topo-routes) are a concept designed to distill the idea of a route down to its essence. Intuitively, a topo-route is just the information of how to get from one board object to another, more specifically which way to go around various obstacles, with all other geometric details abstracted. Thus it ignores for example:

trace width
clearance
feature geometry (pad shapes, via radius, and so on)
curvature

The mathematically precise definition is as follows. For each board object we choose a representative point. Then a topo-route consists of the two end objects (in some order) with a homotopy class of paths between their respective representative points through the topological space consisting of the board shape minus the representative points of all other objects. (Note that this definition neglects some nuances of how non-convex board objects are broken down.)

In this context homotopy means continuously deforming the path, as if it were elastic and malleable, without any cutting/splicing or passing through obstacles. Thus the effect of this definition is that two topo-routes are the same if they go around obstacles the same way.

The use of topo-routes internally is what makes the autorouter “topological”. The main advantages are that topo-routes can be represented and operated on very efficiently, and the search algorithm does not have to use any kind of ad hoc “shove routing” to move routes out of the way when bending new routes around the same obstacle. We get that for free - the topo-routes have not changed; only the realization (i.e. the actual route geometry) changes.

There are many ways to represent topo-routes as data, just as there are many ways to represent numbers, lists, or graphs. One such representation is known as a Rubber Band Equivalent or RBE for short. As the name suggests, the RBE is the path an idealized rubber band would take on a pegboard with a peg for each obstacle, and the rubber band is tied to the pegs corresponding to the endpoints. The pegs are placed at the chosen representative point in each board object or obstacle (the same one used to define the topology as mentioned above). The exact choice of representative point is somewhat arbitrary but will always be in the interior of the object's shape. For RBE purposes, the detailed shape geometry is ignored; the shape is effectively replaced by the representative point or peg. The RBE is a unique representation for a topo-route because if the rubber band initially took any other path representing the topo-route, it would shrink homotopically down to the same minimum path.

To be precise, an RBE consists of the two endpoints together with a sequence of waypoints, where each waypoint is paired with a clockwise or counter-clockwise orientation, indicating which way around that obstacle the path should go. An RBE can be thought of as a series of navigation instructions like this:

Start at (10,20)
Go straight to the obstacle at (20,20) and turn right (CW) around it.
Go straight to the obstacle at (20,0) and turn left (CCW) around it.
Go straight and finish at (30,0).

The endpoints and waypoints in the RBE are the representative points (pegs) of the objects involved - the ends of the route and some obstacles the route “goes around” in some sense. Using a representative points for each object is a necessary precision to keep calculations consistent, and it has the added benefit of allowing the RBE to retain some residual, approximate meaning even when the topology changes.

When a topo-route has failed to successfully realize, the JITX UI will display the route's RBE in a different color. The RBE is drawn with the trace width the realized route would be expected to have, but otherwise corresponds closely to the mathematical RBE. Currently there is no way to visually determine the orientations / turning directions at each waypoint. You can perform most of the same UI interactions on an RBE as you can on a normal route. The significance of having an RBE is that if anything on the board changes, the realization algorithm (step 3 of the autorouter) runs again automatically and if successful the RBE will be replaced by a normal route with the same topology, or in other words, a correct realization of the same topo-route.

The advantage of keeping RBEs is that the UI will remember the topo-route and all of its properties, so you have a chance to troubleshoot whatever caused realization to fail without having to re-enter that information.

Basic behavior: repositioning¶

When board objects are moved around, the autorouter tries to preserve any existing routes even in cases where the exact geometry cannot be reused. The procedure goes roughly like this: 1. Identify all routes that are affected by the movement. 2. Re-walk the RBEs of the old routes in the new board topology. 3. Run the full autorouter on any routes that failed the previous step.

Step 2 is necessary because not only the geometry but even the topology has changed - as we saw in the previous section, the topological space routes live in is defined by where all the obstacles are. To preserve the old routing as much as possible, we do this re-walking step which basically means to re-interpret the old RBE in the new topology, and this is called “re-walking”. To re-walk a route, we follow these steps:

If either of the endpoints have moved, apply a corresponding transformation to the entire RBE.
Calculate a new RBE based on how this transformed path goes around current obstacles. This is the same algorithm that we run when the user specifies a topo-route manually.
Check the new RBE for conflicts with other routes, and for satisfying the current design rules.

The transformation in step 1 is chosen heuristically to maximize the chances of preserving the existing routing patterns. If both endpoints and all relevant obstacles have moved in a uniform way (by a rigid motion), and there is still room for the routes' trace width and spacing in the new location, then all of the routes will be recreated. In all other circumstances, recreation of routing is best effort only.

Route settings in the UI¶

If you select a route in the UI, there is a drop-down setting which can affect the behavior of the router and/or realization in various ways. The options are:

Normal (default)
Neckdown - this changes the routing rules (e.g. trace width and clearance) to the neckdown rules (already specified in code) instead of the standard rules
Pour - makes the route into a pour, see the pours documentation
Length Matching - makes the route into a length matching envelope, see [that other section]
Adaptive - affects the route end shape geometry, see next section

Note that if the design rules are overridden using the Neckdown option, or using the direct edit fields, the route will be replayed just as described in the section on repositioning.

Shapes and routes¶

This section addresses a couple of nuances of how the router interacts with complicated shapes.

Ends of routes¶

Generally speaking, the topological autorouter internally only details with the route as an idealized mathematical path, and uses a proxy calculation to determine whether the route fit. This approach works well for most of the length of the route, but the endpoints are harder. Wwhen realization computes actual route shapes it has to ensure that the calculated route geometry connects appropriately with the shapes of the endpoint objects, the target shapes, and the behavior of this calculation can be influenced by various factors. In general there are three behavioral modes, which can be changed using the UI drop-down that appears when selecting a route:

Normal (default) - the route will terminate as disk whose diameter is the same as the trace thickness. This disk will be placed in the center of the target object, for some heuristic definition of center. This basic behavior applies for all route settings other than Adaptive, although the trace thickness may be affected.
Adaptive - in the last “leg” of the realized route, the boundaries will expand or contract gradually to encompass the diameter of the target shape. For polygons this typically means the route geometry is expanded to share the widest pair of corners of the target shape. This results in more natural looking end shapes without unnecessary interior angles. The last leg usually means whatever the final straight segment would be after the last bend, if the route were realized normally. However, in some cases heuristics are used which deviate from this principle to avoid having the affected region be unexpectedly small or large.

Exception

If the setting is Normal but it happens that termination disk does not actually fit in the target shape, then realization will behave exactly as if the setting were Adaptive.

There is currently no way to make only one end of a route adaptive.

Ordinarily, the target shape considered in the foregoing explanation is simply the shape of the object at which the route terminates. However, if there is more than one overlapping shape, the target shape will be determined based on the rules described in the next subsection.

Overlapping object shapes¶

Internally, the autorouter requires that all objects have disjoint shapes. When shapes are overlapping, an auxiliary algorithm modifies the shapes as seen by the autorouter to observe this rule. This algorithm can reach several possible outcomes for any given pair of overlapping shapes:

The shapes may be merged into a single bigger shape, treated as one object by the autorouter.
One of the shapes may be discarded outright.
One of the shapes may be subtracted from the other. (This results in a different outcome from the previous case only if the first shape was not entirely contained in the second.)

The rules determining the outcome are as follows:

If the two shapes are both copper (including pads, vias, or bare copper) and are allowed to connect, then they will be merged into a single shape and marked as connected. This means the autorouter regards this connection as already made and will not try to find a route for it. (Note that this is true even if the overlap is very thin - the geometric quality of the connection is not considered.)
If the two shapes are both pads or vias and are not allowed to connect, then one of them will be discarded. Which one is determined heuristically and depends on a number of factors; exact behavior is subject to change unpredictably between versions.
If the two shapes are both bare copper shapes and not allowed to connect, the outcome is the same as the previous case.
Otherwise, the two shapes will be ranked according to this list:
1. cutouts or board exterior
2. pads or vias
3. bare copper
4. forbid region
If they have the same rank, they will be merged. (This can only happen for cutouts or forbid regions, per the above superseding rules.) Otherwise the lower priority shape (lower in list, higher number) will be modified to have the higher priority shape subtracted from it, so that the shapes appear disjoint to the router. (An infinitesimal separating line is drawn between them so the resulting shapes do not touch at all.) For example, a pad shape will be reduced if it overlaps a cutout or the board edge.

Note that the board exterior is treated slightly specially, in that it is not a genuine object of its own, but the overlap handling treats it as one. If a pad is completely off the board it is not routeable. If it is partially off the board, the router will see only the portion that is on the board.

If the target shape of a route has been reduced in this way, this is the target shape that will be used for the end shape calculations.

However, if the target shape has been reduced in this way, there is one complication that does not apply to ordinary target shapes: the original “center” of the shape is still used if possible, even if that no longer resembles the geometric center. This can cause the forced adaptive behavior to trigger if the center is too close to the (new) boundary of the shape. If the original center is not in the reduced shape, then a new center is calculated.

This rule can cause some confusing behavior when the exact extent of the overlap changes. For example if you take a decently big pad with a Normal route attached and move the pad to overlap the board edge, gradually leaving less and less of the original pad shape on the board, you can go through a sequence of changes where the forced-adaptive end shape behavior starts happening when there is not enough space left to fit the trace width around the original center, then stops because the original center is off the board and a new one is calculated center is off the board), then starts again because the pad altogether is not big enough.

Control points and SI routing¶

Main article here

(This section needs expansion.)

The SI routing tools have been designed to mostly operate separately from the autorouter, to keep overall behavior as simple and predictable as possible. The basic principles are:

Create control points and use the Length Matching route type to set up envelopes for length matching. For this type of route, you can change the width using a click-and-drag interface in the UI.
The autorouter sees only the envelope route so for collision and clearance purposes treats it as if the whole envelope were solid copper. The detailed copper geometry is determined entirely by the SI routing algorithms.
You can use the UI to move control points and change envelope widths in order to create as much space as needed for the SI routing to solve the constraints. The issues sidebar gives live feedback on which constraints are failing to be satisfied and by how much.

When things go wrong¶

As a general principle, you can use the undo command liberally to help understand the autorouter's behavior in a given situation. Any bad run of the autorouter can be wiped out immediately with an undo, and then you can try something different.

Autorouter refuses to make obvious routes¶

Try these troubleshooting steps:

Identify a single route that you are expecting and run the autorouter on only those two pads. By selecting only two pads, you can get a reliable error message indicating which part of the autorouter is failing. For example, you can tell if the autorouter thinks there is a legal connection to be made here or not. When running the autorouter on more than two pads, the autorouter cannot tell for certain how many routes are expected, and some attempted routes may fail at different parts of the process, so the feedback is more ambiguous.
If you get a route but it's not the one you're expecting, try manually creating the route that you would expect. If that works, then you can keep it and you can try running the original request again. Now that you have made this route, the autorouter has to respect it and may make other routes as you expect. If the manual route fails, then the error message should help you narrow down the problem. If the autorouter itself (step 2) is failing, measure the space available and double check the design rules.

Autorouter uses a bad routing strategy¶

If the autorouter is repeatedly using a bad strategy, it may force you to make many manual routes, or to repeatedly run the autorouter on small selections (perhaps just two pads). You can try to mitigate this by making a few key guiding routes by hand and coaxing the autorouter into better behavior that way.

When routing multiple nets at once, the autorouter generally tries to commit to the the shortest possible routes first. If that heuristic is not working well, you can try to help it by excluding problematic pads from the selection, or by manually making routes which block the problematic routes.