Physical Sciences and Mathematics Commons^™

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

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 …