Data Parallelism in Algorithms
Data-parallel algorithms exploit the parallelism inherent in many large data structures.
- A problem is an (identical) algorithm applied to multiple points in data “array”
- Usually iterate over such “updates”
- Example: Red-Black Relaxation
- All “red” points can be updated in parallel; then all the “black”
Analysis:
- Scalable parallelism -- can usually get million or more way parallelism
- Hard to express when “geometry” irregular or dynamic