Title
Parallel algorithms for single-layer channel routing
Document Type
Conference Proceeding
Publication Date
12-1993
Publication Title
ISAAC '93 Proceedings
Pages
456-465
Publisher Name
Springer-Verlag
Abstract
We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the “river-routing” context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lg N) time on a CREW PRAM or O(lg N/lg lg N) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of the channel contains single-sided nets. For the optimal offset problem with single-sided nets on one side of the channel, we obtain time O(lg N lg lg N) on a CREW PRAM or O(lg N) time on a CRCW PRAM with O(N lg lg N) work. Not only does this improve on previous results for river routing, but we can obtain an even better time of O((lg lg N)^2) on the CRCW PRAM in the river routing context.
Recommended Citation
Algorithms and Computation: 4th International Symposium, ISAAC '93 Proceedings, Volume 762 of the series Lecture Notes in Computer Science, pp. 456--465.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
