Provably Good Parallel Algorithms for Channel Routing of Multi- terminal Nets.

Loading...
Thumbnail Image

Files

TR_88-51.pdf (630.63 KB)
No. of downloads: 584

Publication or External Link

Date

1988

Advisor

Citation

DRUM DOI

Abstract

We consider the channel routing problem of a set of multi- terminal nets in the knockknee 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 O( n/p + log n) time, with p processors, 1 < p < n and n is the size of the input.

Notes

Rights