Parallel Algorithms for Wiring Module Pins to Frame Pads.
Parallel Algorithms for Wiring Module Pins to Frame Pads.
Files
Publication or External Link
Date
1988
Authors
Chang, Shin-Chong
JaJa, Joseph F.
Advisor
Citation
DRUM DOI
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.