Document Type
Article
Publication Date
12-1993
Publication Title
Proceedings of the 4th Annual International Symposium on Algorithms and Computation
Volume
762 of Lecture Notes in Computer Science
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(lgN) time on a CREW PRAM or O(lgN/lglgN) 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(lgNlglgN)$ on a CREW PRAM or O(lgN) time on a CRCW PRAM with O(NlglgN) work. Not only does this improve on previous results for river routing, but we can obtain an even better time of O((lglgN)^{2}) on the CRCW PRAM in the river routing context.
Recommended Citation
Ronald I. Greenberg, Shih-Chuan Hung, and Jau-Der Shih. Parallel algorithms for single-layer channel routing. In Algorithms and Computation: 4th International Symposium, ISAAC '93 Proceedings, volume 762 of Lecture Notes in Computer Science, pages 456--465. Springer-Verlag, 1993.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
