Does parallel mergesort run differently on mesh vs linear array of processors?
https://softwareengineering.stackexchange.com/questions/246833
-
04-10-2020 - |
题
I'm currently taking course on introduction to algorithm and I came across the parallel mergesort algorithm. My question is: Is there any differences in the algorithm plan if it runs on a 2d mesh instead of infinite linear proccessors ?
Thank you,
解决方案
Please define the terms mesh
and linear array of processors
, and/or provide online references to such definitions.
There are different flavors of mergesort algorithms. One remarkable difference is:
- For merging two sorted halves of size
N/2
arrays into a fully sortedN
array, does it take exactly one stage (performing exactlyN
orO(N)
comparisons), or does it take multiple stages, most commonlyO(log(N))
as many stages (for a total number ofO(N*log(N))
comparisons)?
- The single-threaded mergesort, the one typically taught in the introduction to programming classes, relies on scanning the two halves, "dequeuing" the smaller value of the two front values out of the two halves. This takes exactly
N-1
comparisons. Because it is sequential, it takesO(N)
time steps.
- The parallel mergesort, which is most likely a parallel bitonic mergesort, such as
- http://en.wikipedia.org/wiki/Bitonic_sorter
- http://pages.cs.wisc.edu/~tvrdik/17/html/Section17.html
- Requires
log(N)
stages; - Inside each stage,
O(N)
comparisons are performed - one comparison per processing element - and all processing elements do this simultaneously. - Therefore, it requires
O(log(N))
time, despite having performed vastly many more total number of comparisons ofN*log(N)
There are other flavors of parallelized merge sort. I can't answer them unless you clarify what flavor of merge sort you're learning.