J. Jaja et Kw. Ryu, OPTIMAL-ALGORITHMS ON THE PIPELINED HYPERCUBE AND RELATED NETWORKS, IEEE transactions on parallel and distributed systems, 4(5), 1993, pp. 582-591
Citations number
23
Categorie Soggetti
System Science","Computer Applications & Cybernetics","Engineering, Eletrical & Electronic
We present parallel algorithms for several important combinatorial pro
blems such as the all nearest smaller values problem, triangulating a
monotone polygon, and line packing. These algorithms achieve linear sp
eedups on the pipelined hypercube, and provably optimal speedups on th
e shuffle-exchange and the cube-connected-cycles, for any number p of
processors satisfying 1 less-than-or-equal-to p less-than-or-equal-to
n/((log3 n)(10 log n)2), where n is the input size. The lower bound re
sults are established under no restriction on how the input is mapped
into the local memories of the different processors.