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

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.