An efficient parallel algorithm for channel routing

TitleAn efficient parallel algorithm for channel routing
Publication TypeConference Papers
Year of Publication1990
AuthorsKrishnamurthy S, JaJa JF
Conference NameComputer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings., 1990 IEEE International Conference on
Date Published1990/09//
Keywords21000;channel, access, algorithm;sequential, algorithms;, algorithms;shared, balance, CAD;computational, complexity;parallel, Layout, machine;standard, memory, model;circuit, nets;parallel, Parallel, PRAM;Sequent, random, routing;multiprocessor, system;multiterminal, two-layer

The channel-routing of a set of multiterminal nets in the standard two-layer model is considered. The sequential algorithms based on the greedy strategy do not seem to be easily parallelizable. Proposed is an efficient parallel algorithm for routing channels with cyclic constraints. The algorithm runs in time O(n2/p+log2p), with p processors, on a shared memory parallel random access machine (PRAM) model where 1 les;p les;n2 radic; and n is the size of the input. An efficient adaptation of this algorithm on a Sequent Balance 21000 multiprocessor system is reported