Optimal algorithms on the pipelined hypercube and related networks |
| |
Authors: | JaJa J Ryu KW |
| |
Affiliation: | Maryland Univ., College Park, MD; |
| |
Abstract: | Parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing are presented. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles for any number p of processors satisfying 1⩽p⩽n/((log3n)(loglog n)2), where n is the input size. The lower bound results are established under no restriction on how the input is mapped into the local memories of the different processors |
| |
Keywords: | |
|
|