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(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 JA - Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings., 1990 IEEE International Conference on M3 - 10.1109/ICCD.1990.130261 ER -