4 - Reduction Pattern Flashcards
What is the Reduction pattern?
Reducing N elements into a single value
What is the issue with the Reduction pattern?
There is data dependency between elements, sum at i depends on the sum at i-1
How do you implement the Reduction pattern?
Parallelise calculating the partial pairwise sums at each step then combine the steps sequentially
What is the Reduce function?
A combiner function used to combine all the elements of a collection pairwise and create a summary value.
Pairs of elements can be combined in any order, combiner function should be associative to be parallelisable
Name some example combiner functions
Addition, multiplication, max, min
What is an associative function?
Where the order in which operations are performed does not matter if the sequence of operands is unchanged
What is the complexity of the serial Reduction pattern?
Work = O(n) Span = O(n)
What is the complexity of the parallel Reduction pattern?
Work = O(n) Span = O(log n)
What is the synchronisation problem in the reduction pattern?
Individual work items take different time to execute
i.e in step 1 all threads check the if condition, the even threads need to read/write to memory, the odd threads just carry on
Potential for race conditions
How do you solve the synchronisation problem in the Reduction pattern?
Use a Barrier to wait for all threads to finish each step
How do you do Reduction with large inputs?
Multi-pass reduction, break down a large problem into smaller chunks then operate on each chunk and then combine the results
What is Tiling in the Reduction pattern?
Breaking down into chunks/tiles/blocks, operating on each tile separately and then combining the results
In the reduction pattern what are global and local indices?
Tiling requires different work item indexing as the number of elements to be reduced within a group is M (group size)
Local ID is a unique index within each work group
What is the Fusion of Map and Reduction pattern?
Combining the Map and Reduce results in a straightforward and efficient implementation
What is the Fusion of Map and Reduction patterns useful for?
Dot product and matrix multiplication
