Parallel merge sort using hypercube connection template

Question

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.

What I don't understand is how it's applied on the merge sort in §11.4 The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

procedure parallel_mergesort(myid, d, data, newdata)
begin
  data = sequential_mergesort(data)
  for dim = 1 to d
    data = parallel_merge(myid, dim, data)
  endfor
  newdata = data
end

Please, explain to me step by step, assuming we have an array of twelve elements $(3,1,5,7,4,2,8,9,4,2,7,5)$ and we've broken this data to four processors like this:

$\qquad ((3,1,5),(7,4,2),(8,9,4),(2,7,5))$.

What data will have each process after each iteration? I understand why we use the hybercube template in this algorithm, but why do we have exactly $i$ compare-exchanges at the $i$-th level? I mean, when $i=1$, we compare-exchange data from processes $1-2, 3-4, .. P-1, P$. That's not $1$, that's $P/2$? Do I misunderstand something?

Answer 1

They write

The $i$-th parallel merge takes two sequences, each distributed over $2^{i-1}$ tasks, and generates a sorted sequence distributed over $2^i$ tasks.

For $i=1$, that reads

The first parallel merge takes two sequences, each stored locally on one task, and generates a sorted sequence distributed over two tasks.

That is, every node performs one compare-merge. Similarly, for higher $i$, each node performs $i$ such operations.

They use it to derive "per-processor communication cost" $T_{comm}$ which clarifies that they do indeed count processor-wise in the prequel. That makes sense, too: communication happens in parallel, so in order to derive bounds on overall runtime you can bound every (abstract) step from above with the longest processing time found among all processors in that step.