Distributed autorouting of printed circuit boards: it's true--there is strength in numbers. Learn how to take advantage of multiple CPUs when routing large PCBs.

Many years have passed since the last significant advancement in autorouting PCBs. It can be argued that since the advent of gridless routing, there has been little news on the autorouting front except for enhancements to improve route quality and address high-speed requirements, new via structures and packaging technologies.

Now, though, it appears the season of innovation is coming around again in the form of distributed autorouting, which allows multiple clients to route the same board up to 10 times faster than one designer. Achieving this kind of performance is significant on very large boards when normal routing takes one to two weeks. If designers have to reroute for engineering changes or want to try different placement scenarios, quickly finishing the routing is even more important (FIGURE 1).

[FIGURE 1 OMITTED]

I have been involved in the design, development and use of numerous autorouters since 1982 and have seen many attempts to effectively route on multiple clients fail time after time. It seems logical and appropriate to route this way, so why have PCB touters been unable to make the transition? The answer is surprisingly simple. The general approach taken by engineering teams to create a distributed autorouter required either an ineffective partitioning of the design or a rewrite of the routing algorithms. Both methods led to the eventual abandonment of the project.

Early Attempts

Partitioning of the design in either the vertical or horizontal axis and sending each section to a different client was fine for connections wholly contained inside the area. However, connections that spanned multiple areas created too many problems that the autorouter couldn't overcome. This method worked well for simple routing, but difficult routes could not be addressed effectively because they require rip-up and retry, significant push and shove, and tuning for delay across area boundaries. Since difficult connections take the longest to complete, speeding up simple routes didn't really affect the board's total completion time. In a partitioned environment, difficult connections either a) could not be routed, or b) the management of boundary crossing became such a problem that it was faster to just route them on a single CPU without any partitions.

Rewriting the routing algorithms for distributed autorouting is not economically feasible and the approach creates a self-defeating performance problem. Generally, a rewrite is required to enable each client router to become aware of the changes being made by other clients while it is doing expansions (searching for potential open paths). Allowing a dynamic change of the structures during expansion requires changes so deep in the routing technology that the routing algorithms would quickly deviate from the standard algorithms and require a separate development and maintenance effort, which you don't want.

Over the past decade autorouting has become much more complex and expansion algorithms are not the dominant tasks anymore. Algorithms for push and shove, manufacturers' rules, high-speed rules, and rip-up and retry consume considerable time as well. This means that to save significant time on the overall routing task in an environment where each client was dynamically aware of the other clients, all the algorithms would have to be rewritten. In addition to this, when a new algorithm is developed for the single-CPU router, it would likely have to be rewritten to be applied in the distributed routing environment. Software vendors have never been able to fully support the design, development, enhancement and maintenance of two different high-end routers.

If a client is made aware of other client changes during the expansion phase, there are frequent expansion failures, plus the burden of keeping track of the changes. The more clients added, the more failures occur and the more time it takes to keep track of the changes. This creates a self-defeating performance problem. The intent is to add more clients to enable faster routing, but the overhead of synchronizing the clients overwhelms the benefit of distributing the individual routing tasks.

A More Effective Approach

The most important element in successful distributed routing is enabling a client to accomplish its routing tasks using standard routing algorithms without concern for any other client. This takes designers back to square one with a couple of unanswered questions:

* How can this be accomplished without conflict?

* How can a dozen clients work simultaneously and have their results merged without creating hundreds of violations?

The second-most important element in successful distributed routing is managing the assignment of routing tasks to each client and the merging of their results in a manner that minimizes conflicts. Using a host for this management task has been proven to be effective. The configuration now becomes one in which a single host manages the routing session for the clients. It is best that the host and each client has its own CPU and memory space (FIGURE 2).

[FIGURE 2 OMITTED]

The host manages the master database in memory and each client has its own copy of the database in its own memory space. When a client completes a route, it sends only the changes to the host. When the host updates the master database, it synchronizes all the clients with only the incremental changes. Communicating only the changes in an efficient format is a vital part of making this distributed autorouting method fast.

Here is the high-level flow:

* Analyze. The host analyzes the connections to be routed and organizes them to minimize potential conflicts and distributes them to the clients.

* Route. The client routes the connection it is given using standard algorithms and following all the rules.

* Merge. When a client finishes a route, it sends the changed data back to the host where it is merged into the master database.

* DRC. A design rule check (DRC) is run on the host for that new route and if there are conflicts, the host attempts to resolve them.

* Update. If successful, then all clients are updated with the changes.

* Rejection. If unsuccessful, the route is rejected and the connection is thrown back into the pool of connections to be routed by the clients.

Analysis

Minimizing potential conflicts so that completed routes can be merged without DRC violations is the goal of the analysis phase. There are obvious methods such as:

* Layering. If it is clear that a set of nets can be routed on a single layer without vies, or if the rules dictate that a group of nets must be located on certain layers, then sending a layered set to each client is appropriate.

* Areas. If there is a set of nets that can be routed in a relatively small area, then sending that set of nets to a single client makes sense.

* Buses. Find a bus of nets and send it to a client to route them as a set.

These three methods work just fine at the early stages of the routing process. There are plenty of opportunities to fulfill these group requirements and have successful routing without conflicts.

As the routing progresses, it becomes necessary to go beyond the obvious methods. Again, the goal is to minimize potential conflicts and optimize the total performance. Two possibilities include:

1. When addition of length is required for fulfilling delay requirements, one client could be working on the tuning effort in an isolated area while other clients are still working on the routing task.

2. Towards the end of a routing session, the last routes are more difficult and always take a lot of time. Sending a net to multiple clients, each with a slightly different costing, then picking the first one to finish usually results in a shorter time per net.

When a client finishes the routing of an individual net, that route path and the changes made to other routes (through push-and-shove, and rip-up and retry) are sent back to the host. Changed data is put into a queue of updates from other clients that are waiting to be merged into the master database. The queue must empty quickly, especially at the beginning of the routing task when individual routes are completed with blazing speed. This means that the host has to perform the merge, DRC, resolve conflicts and update processes with little overhead.

The host takes the change from the queue, merges it into the master database and performs a localized DRC on the changes. There are three potential outcomes:

* If there are no violations, then the changes are sent out to all the clients.

* If violations are found, the host applies push-and-shove algorithms to resolve the conflicts. The effort expended by the host is reasonably low to ensure that it doesn't get bogged down with resolving conflicts instead of managing the change queue.

* If the routing session is near the end and the clients are taking a long time to complete their routes, then the host can take more time if needed to resolve conflicts without affecting its ability to manage the queue.

* A client accepts and merges the update(s) from the host between each individual routing task. This way, before each new net is started, the client database is synchronized with the host.

The hardware requirements for this type of distributed routing are quite flexible. The primary need is for the host and each client to have its own CPU and memory space, with multiple-core CPUs working well for these requirements. Of comparable importance is to have a network with adequate performance and minimal latency. Normal LAN and WAN configurations of today are more than adequate. This method allows for a heterogeneous mixture of operating systems as long as they co-exist within the network. Since the host software manages the routing session and the clients, it is not necessary to use special software to manage distributed resources.

Achieving up to 10X performance improvement on large boards that usually take a week or two to route is not only significant in the context of time-to-market for product design, but it also allows for implementing engineering changes and attempting different placement scenarios within the normal schedule.

For anyone who designs big PCBs, distributed autorouting may save the day, or even a week.

CHARLES PFEIL is product marketing director, Systems Design Division, Mentor Graphics. He can be reached at [e-mail].