An efficient parallel algorithm for channel routing
| Title | An efficient parallel algorithm for channel routing |
| Publication Type | Conference Papers |
| Year of Publication | 1990 |
| Authors | Krishnamurthy S, JaJa JF |
| Conference Name | Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings., 1990 IEEE International Conference on |
| Date Published | 1990/09// |
| Keywords | 21000;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 |
| Abstract | 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 |
| DOI | 10.1109/ICCD.1990.130261 |