Parallel Algorithms for Channel Routing in the Knock-Knee Model
Joseph F. JáJá, Shing-Chong Chang · SIAM Journal on Computing · 1991
The channel routing problem of a set of two-terminal nets in the knock-knee model is considered. 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 is developed. The routing and the layer assignment algorithms run in $O(\log n)$ time with $n / \log n$ processors on the CREW PRAM model under the reasonable assumption that all terminals lie in the range $[1,N]$, where $N = O(n)$.