Provably Good Parallel Algorithms for Channel Routing of Multi-Terminal Nets

Abstract

We consider the channel ronting problem of a set of multi-terminal nets in the knock-knee model. We develop a new approach to route all the nets within d+ alpha tracks, where d is the channel density, and 0 < alpha < d, such that the corresponding layout can be realized with three layers. Both the routing and the layer assignment algorithms have linear time sequential implementations. In addition both can be implemented on the CREW-PRAM model in 0(n/p + logn) time, with p processors, 1 < p < n, and n is the size of the input.

Open PDF

Document Details

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

Entities

People

  • J. Jaja
  • Sridhar Krishnamurthy

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Contracts
  • Information Operations
  • Instructions
  • Maryland
  • Monitoring
  • Security
  • Standards
  • Terminals
  • Universities

Fields of Study

  • Computer science

Readers

  • Computer Engineering
  • Computer Networking
  • Parallel and Distributed Computing.