Accession Number:

ADA454692

Title:

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

Descriptive Note:

Corporate Author:

MARYLAND UNIV COLLEGE PARK SYSTEMS RESEARCH CENTER

Personal Author(s):

Report Date:

1988-01-01

Pagination or Media Count:

27.0

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 0np logn time, with p processors, 1 p n, and n is the size of the input.

Subject Categories:

  • Computer Systems
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE