General reusable solution to commonly recurring problems in software design / algorithm design.

Design patterns with good parallel implementations.

“Automatic parallelization” won’t work because the concepts in the parallel solutions are not always found in the sequential solutions.

Parallelization is problem and architecture dependent. There is no general strategy for parallelizing an algorithm.

= When do data written by one processor become “visible” to other processors?

Different memory models for each implementation:

Shared memory programming model

Distributed memory programming model

ie. Graph search problems (DFS, BFS, ...) are extremely difficult to parallelize:

1. Partitioning

   Dividing computation into independent tasks

2. Communication

   Determining communication between tasks

3. Agglomeration/aggregation

   Combining tasks, communication to larger independent “chunks”

4. Mapping

   Assigning tasks, communication to processes, threads, ...

block-wise block j contains elements [jn/p, jn/p+1, ..., 2jnp-1]

cyclic round-robin distribution: element i is in block i%p

block-cyclic blocks of size k distributed cyclically

irregular blocks of possibly different sizes → mapping global to block index

“Owner computes rule”: Block j associated with / owened by processor j .

Possibly better performance for NUMA and distributed memory systems (spatial locality).

Owner of element i can be determined in $\small O(1)$ time and space.

Round-robin distribution of blocks of k elements.

Owner of element i can be determined in $\small O(1)$ time and space.

Owner of element i can be determined in $\small O(1)$ time and space with $\small O(n)$ sized array.

Otherwise compact data structure with fast lookup needed → then no longer $\small O(1)$ .

(shown below for a single processor)

$\small \text{Tpar}(n,p) = \max_{0 \leq j < p }\sum_{0 \leq i < n/p} T(F(j \cdot n / p + i))$

par (0≤i<n) {
a[i] = F(i,n,…);
}

Data parallelism / data parallel pattern

Map

SIMD parallelism / SIMD pattern

1. Gather Collect elements of data structure into consecutive compact blocks.

   Make input “denser” / more compact

2. Scatter Distribute elements of consecutive compact blocks into data structure.

   Compute

3. Reduce (as in MapReduce) Combine result into single block.

   Insert result into previous input structure

Available data assigned to available processors

then reduced with reduction operation (here: sum).

for (i=0; i<n; i++) {
a[i] = F(i,n,…);      // map
}
result = ∑ a[i];        // reduce

• Example: counting words in a document

  1. Distribute assign text parts to processors

  2. Map each processor creates own dictionary with (word, count) pairs

  3. Map each processors sorts dictionary lexicographically after words

  4. Reduce all dictionaries are merged, for each word, all counts added

  (requires load balancing)

Goal: Iterating through array

Sequential: not data parallel, dependent iterations

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

Parallel: Removing dependencies with extra space

for (i=n[j]; i<n[j+1]; i++) {
tmp[i] =a[i-1]+a[i]+a[i+1];
}
barrier;
x = tmp; tmp = a; a = x; // swap (more efficient than copying)

Given:

Pattern:

Domain decomposition:

Issues:

Data distribution decides how we parallelize: “perform computations where the data is”

Assumptions: locality matters because of NUMA model

1. Divide date structures across processors (based on some distribution)

2. “Owner computes”-rule

3. If processor accesses data owned by other processor: (implicit) communication.

Needs efficient ownership.

for (i=n[j]; i<n[j+1]; i++) {
a[i] = f(i);
}

for (i=0; i<n; i++) {
if (owns(i,j)) a[i] = f(i);
}

Pipeline latency after $\small k-1$ steps a first output is produced

Pipeline throughput in each step, a new output block is produced - each step takes $\small F_j(w_i)$

Worker processor $\small p_i$ requests work from master $\small p_0$ - returns solution

$+ \quad$ Pattern can potentially keep all $\small p$ processors busy: $\small S_p(n) = \Theta(p)$ .

$+ \quad$ Good if in subproblems work/size ratio is high and workers can compute asynchronously.

$+ \quad$ Master solves “Termination detection problem”: no more subproblems → terminate.

$- \quad$ Master can be sequential bottleneck.

Work-pool is distributed and workers have local pools.

Communication between workers allowed:

Problem: Termination detection gets difficult.