Parallel Processing Letters
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 are known to 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 (common) 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(lgN lglgN) on a CREW PRAM or O(lgN / lglgN) time on a CRCW PRAM with O(N lglgN) 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. In addition, wherever our results allow a channel boundary to contain single-sided nets, the results also apply when that boundary is ragged and N incorporates the number of bendpoints.
Greenberg, Ronald I.; Hung, Shih-Chuan; and Shih, Jau-Der. Parallel Algorithms for Single-Layer Channel Routing. Parallel Processing Letters, 7, 3: 267-277, 1997. Retrieved from Loyola eCommons, Computer Science: Faculty Publications and Other Works, http://dx.doi.org/10.1142/S0129626497000280
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
© World Scientific Publishing, 1997.