Topological Autorouting - Mapping the Changing Space

This paper outlines the limitations of current autorouting technologies when faced with the geometric constraints imposed by advancing component and board design technologies, such as staggered pin and ball grids and irregular shapes, and introduces the concept of topological analysis as applied to the autorouting process in Altium's next-generation autorouter - Situs™

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.

Introduction

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 sparse 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.

The Situs™ autorouter developed by Altium Limited does not suffer from the limitations of current-generation autorouters. 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 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 (see Figure 1).

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 (see Figure 2).

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 is needed is a new technique for mapping the routing space that does not model the board as simple rectangles and is, therefore, not limited to rectilinear paths between the obstacles.

Introducing Topological Autorouting

A topological approach to autorouting, such as that used by Situs™, 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 Figure 3, 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 Figure 4.

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.

Heading in the Right Direction

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

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.

Conclusion

Current trends in board design and new and emerging board technologies are testing the limits of current-generation autorouters. Just as fine-pitch components and surface-mount technology exposed the limitations of gridded autorouters and led to the development of shape-based technologies, current high-density components and board design trends are pushing the limits of shape-based autorouters.

Topological board analysis, combined with a sophisticated and versatile set of routing engines, frees autorouting from geometrical constraints, particularly those imposed by the orthogonal nature of traditional rectilinear expansion technologies. Topological autorouters, like Situs™, separate the mapping of the routing space from the coordinates of the objects on the board and allow for a more "natural" and intelligent determination of routing paths that is independent of the component packaging technology, component orientation and board shape and size.

About the Authors

Jason Hingston is Program Manager, Protel/Situs for Altium Limited.
Phil Loughhead is Product Manager for the Protel product line at Altium Limited.
Rob Irwin is Manager, Brand Strategy for Altium Limited.

Figures

Figure 1 and Figure 2

Figure 3 and Figure 4

^# 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.