Parallel Algorithms for Wiring Module Pins to Frame Pads.

Abstract

We present fast and 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. Our basic model of parallel processing is the CREW-PRAM model which is characterized by the presence of an unlimited number processors sharing the main memory. Concurrent reads are allowed while concurrent writes are not. All our algorithms use O(n) processors, where n is the input length. Our algorithms have fast implementations on other parallel models such as the mesh or the hypercube.