Parallel Algorithms for Channel Routing in the KnockKnee Model.

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.