Parallel Algorithms for Wiring Module Pins to Frame Pads
| Title | Parallel Algorithms for Wiring Module Pins to Frame Pads |
| Publication Type | Reports |
| Year of Publication | 1988 |
| Authors | Chang S-C, JaJa JF |
| Date Published | 1988/// |
| Institution | Institute for Systems Research, University of Maryland, College Park |
| Keywords | *ALGORITHMS, *PARALLEL PROCESSING, COMPUTER PROGRAMMING AND SOFTWARE, efficiency, INPUT, LAYERS, length, MEMORY DEVICES, MODELS, MODULAR CONSTRUCTION, NUMERICAL MATHEMATICS, PARALLEL ORIENTATION, PINS, WIRE |
| 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 houndary 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 0(n) processors, where n is the input length. Our algorithms have fast implementations on other parallel models such as the mesh or the hypercube. |
| URL | http://stinet.dtic.mil/oai/oai?&verb=getRecord&metadataPrefix=html&identifier=ADA452383 |