Parallel Algorithms for Wiring Module Pins to Frame Pads.

Loading...
Thumbnail Image

Files

TR_88-25.pdf (614.44 KB)
No. of downloads: 333

Publication or External Link

Date

1988

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.

Notes

Rights