Parallel algorithms for wiring module pins to frame pads

Abstract

The authors present efficient parallel algorithms for several problems related to wiring a set of pins on a module to a set of pads lying on the boundary of a chip. The one-layer model is used to perform the wiring. The basic model is the shared memory CREW PRAM (concurrent-read-exclusive-write parallel random-access machine) model. Concurrent reads are allowed while concurrent writes are not. All of the algorithms use O(n) processors, where n is the input length. The algorithms have fast implementations on other parallel models such as the mesh or the hypercube.