An Introduction to Topological Autorouting
Parent page: The Routing
Routing the connections on a printed circuit board is a complex and time consuming activity. On large or dense boards, the process of routing can take a designer considerable time - time that is becoming increasingly rare as product life-cycles shorten. Autorouters aid a designer in the routing process by automatically placing tracks and vias on the board to make the connections. Autorouting is a numerically intensive and complex process that, to be truly useful, must combine adherence to relevant design rules, achieve high or 100% routing completion, and provide good routing quality.
While many current-generation autorouters deliver on each of these requirements to some degree, the grid-based, shape-based or geometrical approaches that they take in mapping the routing space present serious limitations with denser, non-orthogonal and geometrically irregular component packaging technologies - technologies that are becoming more common in modern board design. Current-generation autorouters, because of their geometric limitations, also tend to produce results that "look autorouted", leading to extensive manual rework. Indeed many designers shy away from using autorouters because of this limitation alone.
2 of the internal layers of a board that has been topologically autorouted.
Altium's Situs™ autorouter does not suffer from these limitations. It uses a topological-analysis technique to map the board space, which, unlike geometric or shape-based mapping, is not dependent on obstacle shape or coordinates. Topological mapping provides greater flexibility in route path determination and unrestricted routing direction.
The name Situs comes from Situs Analysis, a branch of mathematics that studies the properties of geometric figures or solids that are not normally affected by changes in size or shape, commonly known today as topology.
Expand the collapsible sections below to learn more about topological autorouting, or continue reading to learn how to get the best out of the autorouter.
The Problems with Traditional Approaches to Autorouting
The Problems with Traditional Approaches to Autorouting
An electronic design is essentially a collection of components whose pins are connected to each other in a particular way. The design is implemented by arranging the components onto a multi-layered mechanical structure, called a printed circuit board (PCB). The connections are physically implemented though discrete copper paths that travel across and through the PCB, from one component pin to another.
The task of creating the discrete copper path, or route, for each connection can be very complex. A typical design could have many thousands of connections between the components' pins, and the paths may have to be created between components that are very tightly packed onto the PCB surface.
Early autorouters mapped a design space by defining a set, regular grid over the entire board, the objectives being to have each component pin lying directly on a grid point and to include sufficient grid points in the free space to route all the connections. Early components were supplied with their pins spaced in multiples of 0.1 of an inch, so defining a suitable grid was relatively easy, as shown below.
When components all had pins on a 0.1" pitch, a grid router could be used.
With the introduction of surface-mount components the spacing between the component pins became much smaller, and manufacturers also started supplying components with metric pin spacing. Improvements in fabrication technology allowed the designer to use very narrow routing paths, which could be spaced more closely together. These factors combined to make traditional uniform grid routers unusable on designs employing these packaging and fabrication technologies. Because the grid needed to be fine enough to effectively cope with the new technologies, gridded routers needed vast amounts of memory and processing power - not to mention time - to build the routing grid and route the design.
To improve on this approach, a technique known as rectilinear expansion # was developed. This technique defines the space between obstacles on the board as a series of rectangles. Once the set of rectangles has been defined, a routing path is determined by following the edges of the rectangles. This technique allowed components with different pin spacing to be routed, and it also allowed the autorouter to cope with the then-newer fabrication technologies such as surface-mounted components. This approach is often referred to as shape-based autorouting, because it models the routing channels using rectangular shapes, as shown in the image below.
A rectilinear router divides the pace into rectangular zones, which were then used to find a route path.
While rectilinear expansion autorouters can overcome some of the speed and memory problems of uniform-grid routers, they are still geometrically constrained in the possible route paths they can identify. Once the rectangular map is established for a board, the routing "wave fronts" expand out along the edges of adjoining rectangles - only in vertical and horizontal directions. Routing is constrained orthogonally to the boundaries of the rectangles. Problems can arise with non-orthogonal geometries, such as are found with, for example, staggered pin grid array components or rotated components. Often in these cases an orthogonal routing path cannot be found and rectilinear expansion routers will fail.
Component packaging continues to shrink in size and pin pitch, and newer packages such as Ball Grid Arrays (BGAs) use staggered grids to maximize the density of their pins. Combined with this, small and unusual product packaging often requires components to be placed in irregular orientations and on unusually shaped PCBs. As these trends gain momentum, it will become more and more difficult for rectilinear expansion routers to meet the routing challenges of modern board design.
What was needed was a new technique for mapping the routing space, that does not model the board as simple rectangles and is not limited to rectilinear paths between the obstacles.
# A Method for Gridless Routing of Printed Circuit Boards, 22 nd Design Automation Conference, Paper 32.2 1984, A.C. Finch, K.J. Mackenzie, G.J. Balsdon, G Symonds of Racal Redac Ltd.
The Topological Approach
The Topological Approach
A topological approach to autorouting, such as that used by Altium's Situs autorouter, uses a different method of mapping the routing space - one that is not geometrically constrained. Rather than using workspace coordinate information as a frame of reference, a topological autorouter builds a map using only the relative positions of the obstacles in the space, without reference to their coordinates.
Topological mapping is a spatial-analysis technique that triangulates the space between adjacent obstacles. This triangulated map is then used by the routing algorithms to "weave" between the obstacle pairs, from the start route point to the end route point. The greatest strengths of this approach are that the map is shape independent (the obstacles and routing paths can be any shape) and the space can be traversed at any angle - the routing algorithms are not restricted to purely vertical or horizontal paths, as with a rectilinear expansion routers.
To build a topological map of a board, Situs links each obstacle on the board to its neighboring obstacles, creating something akin to a set of connected spiders' webs. Potential routing paths are then defined by stepping from one web strand to the next web strand, then to the next web strand, and so on, until the target is reached. This approach to mapping is not geometrically tied to the routing space; the potential path simply weaves its way between each pair of obstacles, as shown in Figure 3.
The topological map removes the fundamental limitation of earlier routers - the limitation created by using the same geometric space to map paths as they do to route in. By separating the mapping space from the routing space the topological router is able to map more natural paths and also to find routing paths that are non-orthogonal. This mapping process works much like designers would, in that designers look for a path that traverses the board in the most direct fashion, while maintaining, to some degree, the layer directions they have assigned. Designers do not constrain their decisions based on whether a connection through a particular area can be made using a series of orthogonal tracks but simply decides whether a track will or will not fit through a possible routing channel.
As shown by the path mapped in the image on the left, the initial topologically defined path may not be suitable as a finished route path. Through sophisticated routing algorithms, Situs converts the mapped path to a suitable routing path, an example of which is shown in the image on the right.
A topological router does not attempt to map into the geometry of the space, it seeks a path between the obstacles.
The initial topological analysis of a route path, without regard to the coordinates of obstacles, leads to high completion rates and high speeds on boards traditionally considered difficult for autorouters - for example those with nonstandard geometries, dense staggered-pin components, or irregularly shaped outlines and cutouts.
Finding a Route Path
Finding a Route Path
Another benefit of the topological approach is that the analysis and determination of routing paths is much more like that used by a designer when manually routing a board.
For example, experience has shown that it is most efficient to route all the connections that are sharing a layer in the same direction, giving rise to the concept of routing layer direction. On simple two-layer boards this is done by assigning one layer to be horizontal and the other to be vertical. Both the designer and the autorouter can then place the routes in accordance with this convention.
Like lanes on a road, this approach brings order to the routing task, allowing the designer or autorouter to view the board as a series of channels, which can then be assigned in an orderly fashion. In both traditional grid routers and rectilinear expansion routers, the layer directions are limited to vertical - tracks running from the top of the board to the bottom, and horizontal - tracks running across the board from one side to the other.
As the density of the design increases, however, so too will the number of layers required to route the board. Once the design requires more than two layers it may be more efficient to search for routing paths in directions other than vertical and horizontal. This is exactly what a designer would do - examine the flow of connection lines and, if there is a sufficient number traveling in a particular orientation, say diagonally, assign a layer to that direction, then route those connections on that layer in that direction.
Neither the fixed-grid router or the rectilinear expansion router can map directly in a non-orthogonal direction; they can only map the space in a horizontal/vertical manner. To produce neat diagonal routes, these types of autorouters must first define a route using orthogonal tracks and then run special post-processing routines to convert the right-angle corners to diagonals.
A topological router, on the other hand, is not constrained by orthogonal geometries and can identify diagonal routes directly and assign them to the correct layer. This not only leads to more "natural" autorouting, it produces more efficient routing and minimizes the number of vias needed in the finished design.
Finishing the Routing
Finishing the Routing
As mentioned earlier, topological analysis provides an efficient way of determining a possible routing path, but this topological path must be translated into a quality finished route. Like a designer, the autorouter will encounter a variety of situations that need to be dealt with in different ways, such as resolving the routing path through the map, following a boundary, or pushing against existing route objects in an attempt to move them over.
To cater for these different situations Situs employs an array of routing engines, including a memory router, pattern routers, a power and ground router, a wavefront router, shape-based push and shove routers, and a number of heuristic routers for specific situations, such as BGA fanout. These engines are based on mature and powerful routing algorithms and have been developed over many years. In Situs these routing engines exploit the intelligent route path determination of the topological mapping process to produce high-quality finished connections.
The Situs routing engines are controlled by a sophisticated set of strategy files that act as the "brain" of the autorouter. A human designer has a number of advantages over an autorouter when it comes to routing a board. The human mind can plan, and as it does it can consider and order a large number of factors, zoom in to focus on an individual element, then return to reconsider the situation. Autorouters use a strategy file to define their patterns of thought. The strategy file controls the routing engines, calling them when necessary and weighting their actions as it does.
To appreciate the important role of the strategy file, consider how the nature of the routing task changes as the routing progresses. The approaches used to route an empty board early in the routing process are quite different from those used as the routing density increases, requiring different routing engines, weighted accordingly. The instructions written in the strategy file define a plan of how to route the board, calling and weighting the routing engines in a particular way when the routing space is relatively empty, then changing the engines and their weightings as it squeezes the final routes through densely occupied routing space.
By implementing the thought processes or brain of the autorouter in a strategy file, it is possible for Altium to easily evolve the autorouter as board technologies change. The Situs strategy file is one of the most sophisticated strategy files of any autorouter available today. It embodies years of research into the routing process, capturing the expertise of many senior PCB designers.
Autorouting the Board
The Situs Topological Router brings a new approach to the autorouting challenge. It uses advanced topological mapping to first define the routing path, then calls on a variety of proven routing algorithms to convert this 'human-like' path to a high-quality route. As an integral part of the PCB Editor, it follows the PCB electrical and routing rule definitions.
Board Setup
While Situs is straightforward to set up and run, there are certain points you should be aware of to produce optimal routing.
Component Placement
Ultimately, the component placement has the most significant impact on routing performance. Altium Designer's PCB Editor includes a number of tools, such as dynamically optimized connection lines, that allow you to fine tune component placement. The optimal component placement is when the connection lines are as short and least 'tangled' as possible.
Other good design practices include placing components so their pads are on a regular grid (to maximize the amount of free space between the pads for routing), placing similar sized surface mount components exactly opposite each other on double sided boards, and consulting device manufacturers datasheets for decoupling placement guidelines. This is not a complete list of placement considerations, simply a few suggestions.
Keepouts
The router requires a closed boundary, made up of tracks and arcs on the keepout layer. Typically, this boundary follows the edge of the board. Placed objects will obey the applicable clearance rule to ensure that they remain a suitable distance away from this boundary, to satisfy any mechanical or electrical clearance requirements that the design may have. The router will also obey keepout layer definitions within this outer boundary, as well as layer-specific keepouts.
You can create a closed boundary that follows the edge of the board shape, using the Line/Arc Primitives from Board Shape dialog.
Polygon Pours
Polygon (or copper) pours can be either solid (filled with one or more copper regions) or hatched (constructed from tracks and arcs). A medium to large hatched polygon pour includes a large number of tracks and arcs. While the router can route a board that includes such polygon pours, the sheer number of objects they introduce increases the complexity of the routing process.
Typically you should only place polygon pours prior to routing if they are required, for example, they are being used to construct unusually shaped pre-routing, perhaps the incoming mains routing or a critical ground region. Otherwise it is preferable that polygon pours be added to the design once routing is complete.
Is it Routable?
An autorouter is a human attempt to understand and model the routing process, then replicate that process automatically. If the board contains an area that can not be routed by hand, then it will not be autorouted either. If the router is continually failing on a component or a section of the board then you should attempt to route it interactively. It may be that there are placement or rule configuration issues that make it impossible to route at all.
Pre-routing
Pre-route critical nets and, if it is essential that they are not changed by the routing process, lock them by enabling the Lock All Pre-routes option in the Situs Routing Strategies dialog. Avoid unnecessary locking though; a large number of locked objects can make the routing problem much more difficult.
Differential pairs nets must be manually routed and locked before using the autorouter. If you do not so this, the routing is very likely to change and alter the signal integrity of the differential pair.
Configuring the Design Rules
The term default rule is used to describe a rule with a query scope of All.
If a rule includes Minimum, Preferred and Maximum values, the autorouter will use the Preferred value.
Make sure the routing design rules are appropriate to the board technology you are using. Poorly targeted or inappropriate design rules can lead to very poor autorouting performance. Note that the router obeys all Electrical and Routing design rules, except the Routing Corners rule.
Rules are defined in the PCB Rules and Constraints Editor dialog (Design » Rules), which can be accessed directly from the Situs Routing Strategies dialog.
If a rule includes Minimum, Preferred and Maximum values, the autorouter will use the Preferred value.
The Altium Designer rules system is hierarchical. The idea is that you start with a default rule for all objects, then add additional rules to selectively target other objects which have different requirements. For example, you should have a default rule for the routing width which covers the most common routing width used on the board, then add subsequent rules to selectively target other nets, classes of nets and so on.
To check that a rule is targeting the correct objects, copy the rule's Query into the Filter panel and Apply it. Only those objects targeted by the rule should pass through the filter and remain displayed at full strength.
The most important rules are the Width and Clearance rules. These routing technology settings define how tightly the routing can be 'packed'. Selecting these is a balancing process - the wider the tracks and bigger the clearance, the easier it is to fabricate the board; versus the narrower the tracks and clearances, the easier it is to route the board. It is advisable to consult your fabricator to establish their 'price points' for routing widths and clearances, those values which if you go below will result in lower fabrication yields and higher priced PCBs. As well as satisfying the electrical requirements of the design, the routing technology should also be chosen to suit the component technology, to allow each pin to be routed to.
The third rule that is part of the routing technology is the Routing Via Style. It should also be selected to suit the track and clearances being used, while considering the fabrication costs of the chosen hole size and annular ring.
You should also avoid excessive or unnecessary rules - the more rules, the more processing time, the slower the routing. Rules can be disabled if not required for autorouting.
Routing Width
Ensure there is a Routing Width rule with a Query of All (a default rule), and that the Preferred setting is appropriate for the most common routing width you require. Make sure that this width, in combination with the appropriate clearance rule, allows all pads to be routed to. Configure additional routing width rules for nets that require wider or narrower routing.
If there are fine pitch components that have pins on nets with wider routing widths - for example, power nets - test route out from a power pin and also route out the pin on either side to ensure that it is physically possible to route these pins.
Clearance Constraint
Check for special clearance requirements, such as fine pitch components whose pads are closer than the standard board clearances. These can be catered for using a suitably scoped and prioritized design rule, as shown in the image. Note that while you can define a rule to target a footprint, it will not target the routing that connects to that footprint. As just mentioned in the Routing Width section, test route to ensure that the component pins are routable.
Routing Via Style
Ensure there is a Routing Via Style rule with a Query of All and that the preferred setting is appropriate. Include higher priority rules for those nets that need a different via style than the default rule.
Altium Designer supports blind and buried vias, when these will be used is determined by the drill pair definitions set up in the Layer Stack Manager dialog (Design » Layer Stack Manager). Like interactive routing, when the autorouter switches between two layers it checks the current drill pair definitions - if these layers are defined as a pair then the via that is placed will have these layers as its start and end layers. It is important to understand the restrictions to using blind/buried vias; they should only be used in consultation with your fabricator. As well as the restrictions imposed by the fabrication stackup technology, there are also reliability and testing accessibility considerations. Some designers consider it better to add more routing layers than to use blind/buried vias.
Routing Layers
Ensure there is a Routing Layers rule with a query of All. All enabled signal layers (defined in the layer stack) will be listed. Enable the layers upon which you wish to allow routing as required. Include higher priority rules for nets that you want to have routed on specific layers only.
Should you wish to exclude a particular net (or class of nets) from being routed by the autorouter, define a Routing Layer rule targeting that net or net class and, in the Constraints region for that rule, ensure that the Allow Routing option for each enabled signal layer is disabled. The priority for the rule must be higher than that of the default rule (the one with a query of All).
Layer Directions
Layer routing direction is specified in the Layer Directions dialog, which is accessed from the Situs Routing Strategies dialog. All enabled signal layers (defined in the layer stack) will be listed. Choose appropriate layer directions to suit the flow of the connection lines. Situs uses topological mapping to define routing paths, so it is not constrained to route horizontally and vertically. Typically it is best to have outer layers as horizontal and vertical. If, however, you have a multi-layer board with a large number of connections at a '2 O'clock' angle, then set one or more internal layers to have this as the preferred routing direction. The Layer Patterns pass in particular makes use of this information, and choosing the right direction can make a significant difference to routing performance in terms of both time and quality. Note that when you use angled layers you do not need to have a partner layer running at 90 degrees to this layer, since the router will typically route horizontally or vertically if it needs to avoid an obstacle on an angled layer.
Avoid using the Any direction - the layer that is chosen to route a connection on is based on how closely the connection is aligned with the layer direction, so this layer becomes the layer of last resort. The Any direction is typically only used on single-sided boards.
Routing Priority
Use the Routing Priority rules to set a higher priority on difficult nets, or those that you want to have the cleanest routing.
SMD Fanout Control
The query system includes keywords that specifically target the different surface mount component packages including IsLCC (Leadless Chip Carrier), IsSOIC (Small Outline IC), IsBGA (Ball Grid Array) and IsSMSIP (Surface Mount Single In-line Package). Default rules are automatically created for the most common packages and since fanout passes are run early in the autorouting process, there is little penalty in keeping rules that do not apply to any components. You should have at least one SMD fanout control design rule if there are surface mount components on the board - a suitable query for a single rule targeting all surface mount components would be IsSMTComponent. For information on how each query keyword identifies a component package, open the Query Helper, type in the required keyword and press F1 .
The fanout rules include settings that control if the pads are to be fanned in or out, or a mixture of both. To help become familiar with the behavior of the Fanout Control rule attributes, the Route » Fanout » Component command can be run on any surface mount component that has no nets assigned to it. As well as using this to check how well a component fans out with the current routing technology defined in the board, you can also use it to fan out a component that you want to keep in a library as a pre-fanned out footprint. Once it is fanned out in the PCB workspace, copy and paste the component and the fanout tracks and vias into a library.
Rule Priorities
The precedence, or priority, of rules is defined by the designer. The rule priority is used to determine which rule to apply when an object is covered by more than one rule. If the priority is not set correctly, you may find that a rule is not being applied at all.
For example, if the rule with a query of InNet('VCC') has a lower priority than the rule with a query of All, then the All rule will be applied to the VCC net. Use the Priorities button in the PCB Rules and Constraints Editor dialog to correct this. Note that priority is not important when two rule scopes do not overlap (do not target the same objects). For example, it makes no difference which of these two rule scopes has a higher priority - InNet('VCC') or InNet('GND').
The Golden Rule
Make sure that the Routing Setup Report is clean before starting the autorouter.
The most important step is to perform a design rule check (DRC) prior to starting the autorouter. When using the Route » Auto Route » Setup, or Route » Auto Route » All commands, Situs conducts its own pre-routing analysis and presents the results as a report in the Situs Routing Strategies dialog. The report provides information including:
- Design rules currently defined for the design that will be adhered to by the autorouter (and the number of design objects - nets, components, pads - affected by each rule)
- Routing directions defined for all signal routing layers
- Drill layer pair definitions
The report lists potential problems that could affect router performance. Where possible, hints are provided in order to advise in the better preparation of the design for autorouting. Any errors/warnings/hints that are listed should be scrutinized and, if needed, the corresponding routing rules adjusted, before proceeding to route the design.
Check all errors, warnings and hints to understand what potential problems the autorouter will face.
It is essential that any routing-related rule violations are resolved before starting the autorouter. Not only can violations prevent routing at the location of the violation, they can also greatly slow the router as it continually attempts to route an unrouteable area.
Tips on Running the Router
- The Autorouter commands are in the Route » Auto Route sub-menu.
- Both the Route » Auto Route » All and Route » Auto Route » Setup commands open the Situs Routing Setup dialog, the difference is that when you choose All, the dialog includes a Route All button.
- Don't be afraid to experiment. If the results are not acceptable, do something to change the router's approach. Add intermediate cleanup and straighten passes, make more room around dense areas, or change layer directions.
- As you experiment with the router - creating your own strategies to control the order of passes, changing the number of vias with the Via control, changing the routing layer directions, constraining the router to orthogonal routes only, and so on - keep notes of the combinations that you have tried. That way you will be able to identify and reuse which configurations work best with your designs.
- Run fanout passes on their own first and assess the quality. You may need to manually fanout any problem areas.
Summary of the Routing Passes and Routing Strategies
Editing an existing user-defined strategy (the default strategies cannot be edited), click the Add button to create your own routing strategy.
Currently defined routing strategies are listed in the lower region of the Situs Routing Strategies dialog. Click the Add button to access the Situs Strategy Editor dialog, from where you can specify the passes to be included in a new strategy.
The following routing passes are available. The passes can be used in any order, as a guide examine an existing strategy to see the order of passes.
| PAss |
Function |
| Adjacent Memory |
A connection-level routing pass. It is used to route adjacent same-net pins requiring fan-out, with a simple U pattern. |
| Clean Pad Entries |
A connection level routing pass. It reroutes out from each pad center along the longest axis of the pad. If there are components with pads that have different X and Y dimensions, always include a Clean Pad Entries pass after the Memory pass. |
| Completion |
A connection level routing pass. It is essentially the same as the Main pass, costed differently to resolve conflicts and complete difficult connections. Examples of costing differences include vias being cheaper and wrong-way routes being dearer. |
| Fan Out Signal |
A component level pass, based on the fanout settings defined by the Fanout Control. It checks for patterns in pads, considers clearance, routing width and via style, then selects a suitable fan out arrangement (inline row, staggered, etc) to meet the requirements defined in the design rule. Fanout is to signal layers only. |
| Fan out to Plane |
A component level pass, based on the fanout settings defined by the Fanout Control. It checks for patterns in pads, considers clearance, routing width and via style, then selects a suitable fan out arrangement (inline row, staggered, etc) to meet the requirements defined in the design rule. Fanout is to an internal plane layer only. |
| Globally Optimized Main |
A connection level routing pass. It provides optimal routing. It ignores contentions/violations on its first iteration. It then reroutes connections, with increased conflict costs, until there are no violations remaining. This pass, used in conjunction with the Orthogonal option enabled, can produce nicely routed patterns. Add a Recorner pass to the strategy to provide mitered cornering. |
| Hug |
A connection level routing pass that reroutes each connection, following existing routing with the minimum clearance possible. The hug pass is used to maximize free routing space. Note that this pass is very slow. |
| Layer Patterns |
A connection level routing pass. It only routes connections that match a layer direction (within a tolerance). It is costed to hug or follow existing routing to maximize free space. |
| Main |
A connection level routing pass. It uses the topological map to find a routing path, then uses the push and shove router to convert the proposed path to actual routing. Only one main-type pass should be specified for a routing strategy - either Main, Multilayer Main, or Globally Optimized Main. |
| Memory |
A connection level routing pass. It checks for two pins on different components on the same layer that share X or Y coordinates. |
| Multilayer Main |
A connection level routing pass. It is similar to the Main pass, but with costs optimized for multilayer boards. |
| Recorner |
A connection level routing pass that is used to provide mitering of routed corners. This pass is used when the Orthogonal option is enabled for the strategy - essentially overriding it and mitering the corners of each route. If the Orthogonal option is disabled for the strategy being used, there is no need to include a Recorner pass as the autorouter will miter corners by default. |
| Spread |
A connection level routing pass that reroutes each connection, attempting to spread the routing to use free space and equally space routing when it passes between fixed objects (such as component pads). Note that this pass is very slow. |
| Straighten |
A connection level routing pass that attempts to reduce the number of corners. It does this by walking along the route to a corner, then from that corner performs a (horizontal/vertical/45up/45down) probe searching for another routed point on the net. If one is found, it then checks to see if this new path reduces the routed length. |
See Also
