Parallel Algorithms for Channel Routing in the KnockKnee Model.

Loading...
Thumbnail Image

Files

TR_88-24.pdf (733.74 KB)
No. of downloads: 659

Publication or External Link

Date

1988

Advisor

Citation

DRUM DOI

Abstract

We consider the channel routing problem of a set of two-terminal nets in the knockknee model. The known strategy to handle this problem seems to beinherently sequential. We develop a new approach to route all the nets within d tracks, where d is the density, such that the corresponding layout can be realized with three layers. Both the routing and layer assignment algorithms can be implemented on the CREW-PRAM model in O(log n) time with O(n) processors, where n is the number of nets.

Notes

Rights