What are the important properties of a Map function?
Map: A function that applies a given function to each element of a list, and returning a list of results
Two important properties:
Side-effect free:
- Only returning a value, no modifications of state with the rest of the application
Independent:
- Has an independent piece of work, where its input does not depend on another function
What are the important properties of a Reduce function?
reduce: A function that takes in a list of objects and builds up A return value Important properties for parallel reduction:
- Associativity:
a+(b+c)==(a+b)+c- Allows elements to be reduced in parallel in a tree
- In CUDA,the synchronization has to be managed by the programmer:
a+b+c+d+e+f+g+h = ( (a+b)+(c+d) )+( (e+f)+(g+h) ) = (a+b+c+d) + (e+f+g+h)
What are the important properties of a Scan function?
Scan (prefix#sum): Takes a binary associative operator $⊕$ with identity $I$, and an array of $n$ elements $a0, a_1, ..., a{n-1}$ and returns the ordered set $[I, a0, (a0 ⊕ a1), ..., (a0 ⊕ a1 ⊕ ... ⊕ a_{n-2})]$.
How to compact an array in a data-parallel way?
Compaction: Removing elements from an array # take in an array, and produce an shorter array
How to find unique elements in an array in a data-parallel way?
Removing duplicates from an array – take in an array, produces a equal or shorter array
