Optimal algorithms on the pipelined hypercube and related networks

TitleOptimal algorithms on the pipelined hypercube and related networks
Publication TypeJournal Articles
Year of Publication1993
AuthorsJaJa JF, Ryu KW
JournalParallel and Distributed Systems, IEEE Transactions on
Pagination582 - 591
Date Published1993/05//
ISBN Number1045-9219
Keywordsalgorithms;pipeline, algorithms;pipelined, combinatorial, geometry;parallel, hypercube;shuffle-exchange;combinatorial, mathematics;computational, packing;monotone, polygon;parallel, problems;cube-connected-cycles;line, processing;

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/((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