6 - Gather & Scatter Pattern Flashcards
Name 2 applications of a gather & scatter pattern
Matrix operation (transpose) only on non-zero elements in a sparse matrix
Given a mask, perform image processing operation only on foreground pixels
Discuss data movement in data reorganisation
Data movement is the major bottleneck of parallel applications, sometimes more important than parallel computation
What should you do for data reorganisation in data-intensive applications?
Reorganise data first then perform computation
What does reorganisation not always imply
Direct data reduction
What do gather and scatter patterns arise from?
A combination of random read and write with the map pattern
What is the input in Gather?
A collection of read locations (addresses or array indices)/source array
What does Gather do?
Reads data from a source array at given locations into the output
Name some applications of the Gather pattern?
Sparse matrix operations, ray tracing, volume rendering, proximity queries, collision detection
What is Shift?
A special case of gather
Moves data to the left or right in memory
Data accesses are offset by a fixed distance
What does Shift require?
Out of bounds data.
There are different variants based on how boundary conditions are handled
Discuss the Stencil pattern using Shift
For each offset in stencil, generate a new input vector by shifting the input by the offset
Good for 1d stenciles
What is the input in Scatter?
Collection of write locations (addresses or array indices)/source array
What does Scatter do?
Writes data into output indicated by the given location, similar to gather which used the locations for reading
What happens when Parallel writes to the same location?
Collisions
What are Collisions/Conflicts?
Where two or more values are being written to the same location n the output collection.
Result is undefined, needs rules to be resolved
Name 4 strategies to solve conflicts in scatter
Atomic scatter
Permutation scatter
Merge scatter
Priority scatter
What happens in the Atomic Scatter?
Only one value is written (non-deterministic)
Useful with boolean variables
What happens in the Permutation Scatter?
Collisions are not allowed
Output is a permutation of the input
Check for collisions in advance: turn scatter into gather
FFT scrambling, matrix/image transpose, unpacking
What happens in the Merge Scatter?
Associative and commutative operators as merge elements
Commutative properties are required since scatters to a particular location could occur in any order
What happens in the Priority Scatter?
Input elements are assigned a priority based on their position
What is the complexity of Gather & Scatter?
Same as the parallel Map pattern
Work = O(n) Span = O(1)
What is the performance of Gather & Scatter affected by?
Random nature of memory accesses
Gather: performance lower due to random reads
Scatter: performance lower due to random writes and potential write conflicts
What is the Pack Pattern used for?
Used to eliminate unused elements from a collection. Retained elements are moved so they are contiguous in memory
What happens in the Pack Pattern?
Assign boolean keys to all elements in the collection; false/0 if an element needs to be filtered out
Perform the exclusive scan on keys, result is an array with output indices
What is a Histogram?
An estimator of data distribution. Uses bins (value intervals) to count number of values falling into that interval
How do Atomic functions resolve the conflict?
By serialising accesses to a variable
