TY - JOUR
T1 - Optimal algorithms on the pipelined hypercube and related networks
JF - Parallel and Distributed Systems, IEEE Transactions on
Y1 - 1993
A1 - JaJa, Joseph F.
A1 - Ryu,K. W.
KW - algorithms;pipeline
KW - algorithms;pipelined
KW - combinatorial
KW - geometry;parallel
KW - hypercube;shuffle-exchange;combinatorial
KW - mathematics;computational
KW - packing;monotone
KW - polygon;parallel
KW - problems;cube-connected-cycles;line
KW - processing;
AB - 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 les;p les;n/((log^{3}n)(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
VL - 4
SN - 1045-9219
CP - 5
M3 - 10.1109/71.224210
ER -