A parallel router for printed circuit boards

Describes a parallel router for printed circuit boards. Two different parallelisation strategies were employed; one decomposed the board into independent regions and then routed the regions concurrently; the other parallelised the wave-front algorithm which is used to find the shortest path between points. Whilst the first strategy is attractive because it requires very little synchronisation, it achieves poor performance even on boards in which most of the wires are independent. The second strategy is fairly efficient, but performs better on long wires than short independent ones. A combination of the two strategies is efficient for boards containing many independent short wires as well as some long wires which span the board. The paper supports the claims with experimental results taken from an Encore Multimax multi proccessor