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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1988
Accession Number
ADA452383

Entities

People

  • Joseph Jaja
  • Shing-chong Chang

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Contracts
  • Information Operations
  • Instructions
  • Maryland
  • Monitoring
  • Parallel Computing
  • Parallel Processing
  • Security
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Science.
  • Integrated Circuit Design and Technology.