Map/Reduce Pattern
Map/Reduce is a two-phase parallel programming pattern. The first step (map) is to apply a singe function f to all data inputs, producing a (value,tag) tuple. The second step (reduce) is to combine results of the map step, where elements with the same tag are combined to a single value per tag.
// map(input → output)
forall inputs:
(tag_i, output_i) = f(input_i)
// Reduce({tag_i, output_i})
for (tag_i = T)
g(result_T, output_i)
The combining function used in the reduce step must be associative, and can be done in parallel and/or pipelined with the map step.
Example: given a forest of rooted trees where each node carries a weight, one can calculate the aggregate weights of each root’s respective descendants with Map/Reduce.
// map(nodes → (tag_root, weight))
forall nodes:
(root_i, weight_i) = (find_root(node_i), weight(node_i))
// reduce({root_i, weight_i})
for (root_i = T)
tot_weight_T += weight_i
for each node, find its root.
- Reduce: (root_tag(node), weight of node)
In general, Map/Reduce is useful when processing a large amount of data and producing some smaller set of aggregate data.
Theoretical Parallel Models
PRAM: Parallel RAM
Parallel Tasks
___ ___ ___ ___
|T0 | |T1 | |T2 | . |Tn |
|___| |___| |___| . |___|
\ | | . /
__ __ __ __ __ __ __ __
| Shared Namespace |
|__ __ __ __ __ __ __ __|
Works fine for a small number of parallel tasks (~4), but doesn’t work for a large number (> ~1000) parallel tasks.
BSP: Bulk Synchronous Programming
Parallel Tasks
___ ___ ___ ___
|T0 | |T1 | |T2 | . |Tn |
|___| |___| |___| . |___|
.
__ __ __ __ Barrier __ __ __ __ __
__ __ __ __ __ __ __ __
| All communication |
|__ __ __ __ __ __ __ __|
__ __ __ __ Barrier __ __ __ __ __
___ ___ ___ ___
|T0 | |T1 | |T2 | . |Tn |
|___| |___| |___| . |___|
.
NB: Map/Reduce is of this form.
One optimization that can be made to the PRAM model is to split tasks and pipeline execution and communication.
e.g.
Parallel Tasks
___ ___ ___ ___
|T0 | |T1 | | |T2 | |T4 |
|___| |___| | |___| |___|
|
__ __ __ __ __ __ | __ __ __ __ __ //barrier
__ __ __ __ | __ __ __ __
| Comm. ||| Comm. |
|__ __ __ __|||__ __ __ __|
__ __ __ __ __ __ | __ __ __ __ __ //barrier
___ ___ | ___ ___
|T0 | |T1 | | |T2 | |T4 |
|___| |___| | |___| |___|
\__ __ __ __ __/ \__ __ __ __ __/
| |
Partition 0 Partition 1
Communication and Synchronization Patterns
Types of Communication
- Point-to-Point
- Broadcast
- Reduction
- Multicast
Types of Synchronization
- Locks and Mutexes
- Monitors and Events
- Barriers (wait for all)
- Split-phase barriers (aka Fuzzy Barriers)
- Named Barriers (which allow waiting on a subset)
- Transactions (atomic operations)
// Transactions
atomic {
// …
// critical section
}
Algorithm Structure and Organization
| Task Parallelism | Divide & Conquer | Geometric | Recursive Data | Pipeline | Event-Based Coordination | |
|---|---|---|---|---|---|---|
| SPMD | **** (Note 1) | ** (Note 2) | **** (Note 3) | ** (Note 2) | **** | (*) (Note 4) |
| Loop Parallelism | **** (Note 5) | * (Note 6) | **** | * (Note 6) | **** (Note 7) | - |
| Master/Worker | **** | *** | *** | *** | ** (Note 8) | **** |
| Fork/Join | **** | **** (Note 3) | ** | **** (Note 3) | - | * (Note 9) |
Notes:
- SPMD is very general and task parallelism can be made to work.
- Divide & Conquer tends to spawn many dynamic threads, which complicates SPMD.
- This combination is a very common decomposition/structure pair.
- Way too much communication if the graph is dynamic. If the graph is static, this combination can work well.
- When there are no dependencies between tasks (e.g. in the ‘forall’ sense), this combination works well.
- Recursion doesn’t map well to loop parallelism.
- This maps well with to software pipelining.
- Master/worker is very inefficient with pipelining. Data flows master → worker 1 → master → worker 2 → …
- Synchronization only occurs on joins, so software sometimes will have to do tons of joins to get to a common synchronization point.
