TY - CONF
T1 - An efficient parallel algorithm for channel routing
T2 - Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings., 1990 IEEE International Conference on
Y1 - 1990
A1 - Krishnamurthy, S.
A1 - JaJa, Joseph F.
KW - 21000;channel
KW - access
KW - algorithm;sequential
KW - algorithms;
KW - algorithms;shared
KW - balance
KW - CAD;computational
KW - complexity;parallel
KW - Layout
KW - machine;standard
KW - memory
KW - model;circuit
KW - nets;parallel
KW - Parallel
KW - PRAM;Sequent
KW - random
KW - routing;multiprocessor
KW - system;multiterminal
KW - two-layer
AB - 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(n^{2}/p+log^{2}p), with p processors, on a shared memory parallel random access machine (PRAM) model where 1 les;p les;n^{2} radic; and n is the size of the input. An efficient adaptation of this algorithm on a Sequent Balance 21000 multiprocessor system is reported
JA - Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings., 1990 IEEE International Conference on
M3 - 10.1109/ICCD.1990.130261
ER -