An efficient parallel logarithmic time algorithm for the channel routing problem

In this paper the authors present a parallel algorithm for the channel routing problem, using the knock-knee mode. The algorithm requires O(logN) time with O(N²/logN) (N number of nets) processors on a CREW-PRAM. The wire layout constructed by this algorithm is area optimal if the channel routing problme is a permutation channel routing problem. For the general channel routing problem it determines a wire layout, which uses a minimal number of vertical lines and only a small number of additional horizontal lines.