Reduction and prefix-sums are collective operations.

A set of processors cooperatively carrying out an operation on a data-set.

• Other examples

  Broadcast One processor has data that all the others receive

  Scatter One processor has data that all the other’s receive in their blocks

  Gather Blocks from all processors get collected by one processor

  Allgather Blocks from all processors get collected by all processors

  also called: broadcast-to-all

  Alltoall Each processor collects block from other processor

Given sequence $\small x= (x_{0},~x_{1},~x_{2},~\dots, x_{n-1})$

and associative operation $\small +$

compute

• Examples: Reduction as collective operation

  • Reduction-to-one

    All processors participate. Result stored in “root”-processor.

  • Reduction-to-all

    All processors participate. Result available to all.

  • Reduction-with-scatter

    Using vectors. Result stored in blocks over the processors according to some rule.

Given sequence $\small x$ compute all inclusive/exclusive prefix sums $\small (y_0,~y_1,~\dots,~y_{n-1})$ .

$\footnotesize i > 0$ and there is a special definition for $\small i = 0$

$\small \tt exscan(i,n)$

$\small \tt scan (i,n)$

For computing the prefix-sums of an $\small n$ input sequence, the following trade-off holds between:

Solution to both reduction and prefix sums problem.

This is the best possible, since output depends on$\small x_i$.

• implementation (not the best)

  for (i=1; i<n; i++) {
  x[i] = x[i-1] + x[i];
  }

  $\small 2(n-1)$ memory reads

  $\small \text{Tseq}(n) = n-1 = O(n)$ summations

• implementation - improved

  1 read, 1 write per iteration

  optimizer in compiler can improve performance significantly

  register int sum = x[0];  // compiler stores in register for faster access
  for (i=1; i<n; i++) {
  sum += x[i];  // read
  x[i] = sum;   // write
  }

Solution to both reduction and prefix sums problem.

What we ideally want:

We want to make use of the associativity of the operator:

There are 3 parallel solutions to inclusive prefix sums:

Sum pairwise, then recurse on smaller problems.

Scan(x,n) {
if (n==1) {
return;
}for (i=0; i<n/2; i++) {
y[i] = x[2*i] + x[2*i+1];
}// solve recursively in y -> implicit (with fork-join) or explicit barrier
Scan(y,n/2);// take back
x[1] = y[0];
for (i=1; i<n/2; i++) {
x[2*i] = y[i-1] + x[2*i];
x[2*i+1] = y[i];
}if (odd(n)) {
x[n-1] = y[n/2-1] + x[n-1];
}
}

Work $\color{pink}\small W(n) \in O(n)$

Time $\textcolor{pink}{\small \text{Tpar}(p,n) = }W(n)/p + T_\infin(n) = \textcolor{pink}{O(n/p+\log n)}$

Parallelism $\color{pink} \large \frac{\text{Tseq}(n)}{T_\infin(n)} \small = n/\log n$ processors

Parallel steps $\color{pink}\small T_\infin(n) = 2 \log n$ parallel steps (recursive calls)

2 synchronizations per recursive call

$\small +$ operations $\color{pink}\small 2n \in O(n)$

Advantages

Drawbacks

in $\small \log_2(n)$ rounds:

This way:

Reduction can be performed out in $\small r = \log_2(n)$ synchronized rounds for $\small n$ (if it’s a power of two).

Total number of $\small +$ operations are $\small$$\small n/2+ n/4 + n/8 + \dots < n ~(= n-1)$

for (k=1; k<n; k=kk) {
kk = k<<1; // double
par (i=kk-1; i<n, i+=kk) {
x[i] = x[i] + x[i-k];
}barrier;
}

for (k=1; k<n; k=kk) {
kk = k<<1; // halve
par (i=kk-1; i<n, i+=kk) {
x[i] = x[i] + x[i-k];
}barrier;
}

The inner for-loop can be parallelized (not the outer one).

This way we can get from $2^{k+1}$ operations in each round to $\small n/2^{n+1}$ .

Factor $\small 2$ is off from sequential $\small n-1$ work.

• Invariant for Up-Phase

  $\small x[i] = X[i-2^k+1]+\dots + X[i]$

  $\small j = 1, 2, 3, \dots$

  $\small i = j\cdot 2^k-1$

  $\small k = 0, 1, \dots, \lfloor \log_2(n)\rfloor$

• Invariant for Down-Phase

  $\small x[i] = \sum_{0 \leq j \leq i} X[i]$

  $\small j = 1, 2, 3, \dots$

  $\small i = j\cdot 2^k-1$

  $\small k = \lfloor \log_2(n)\rfloor, \lfloor \log_2(n)\rfloor-1, \dots$

Synchronization can get very expensive for large$\small n$relative to$\small p$in in distributed memory models.

$\small 2\cdot \log_2(n)$ communication rounds each with $\small n/2^k$$\small$ concurrent communication operations.

$\small 2n$ operations in total.

Since often $\small n \gg p$ this is too expensive.

Work $\color{pink}\small \text{W}(n)\approx 2n \in O(\text{Tseq}(n))$

Time $\small 2\cdot \lfloor\log_2(n)\rfloor$ rounds each $\small O(n/2^{n+1})$ = $\color{pink}\small O(n/2^{n} \cdot \log n)$

Linear speedup $\color{pink}\small S_p(n) \in O(p/2)$ - half the processors are lost

$\small +$ operations about $\color{pink}\small 2n \in O(n)$

Advantages

Disadvantages

$\small x[i] = x[i-k] + x[i]$

$\small k = 2^{k'}$

Round $\small k'$

with $\small \lceil \log_2n\rceil$ rounds needed in total.

Before each iteration of step $\small k$ :

Advantages

Drawbacks