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
