Parallel Algorithms for Single-Layer Channel Routing

Authors

Ronald I. GreenbergFollow
Shih-Chuan Hung
Jau-Der Shih

Document Type

Article

Publication Date

1997

Publication Title

Parallel Processing Letters

Volume

7

Issue

3

Pages

267-277

Publisher Name

World Scientific

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 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.

Comments

Author Posting. © World Scientific Publishing, 1997. This is the author's version of the work. It is posted here by permission of World Scientific Publishing for personal use, not for redistribution. The definitive version was published in Ronald I. Greenberg, Shih-Chuan Hung, and Jau-Der Shih, Parallel Process. Lett. 07, 267 (1997). https://doi.org/10.1142/S0129626497000280.

This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/112

Recommended Citation

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.

Copyright Statement

© World Scientific Publishing, 1997.