1
Q
Serial Map?
A
Work = O(n) Span = O(n)
2
Q
Parallel Map?
A
Work = O(n) Span = O(1)
3
Q
Serial Reduction?
A
Work = O(n) Span = O(n)
4
Q
Parallel Reduction?
A
Work = O(n) Span = O(log n)
5
Q
Serial Scan?
A
Work = O(n) Span = O(n)
6
Q
Span Efficient Hillis-Steele Scan?
A
Work = O(nlogn) Span = O(log n)
7
Q
Work Efficient Blelloch Scan?
A
Work = O(n) Span = O(log n)
8
Q
Parallel Gather/Scatter?
A
Same as map
Work = O(n)
Span = O(1)
9
Q
Serial Bubblesort?
A
Work = O(n2)
10
Q
Linear Search?
A
Work = O(n) Span = O(n)
11
Q
Odd-Even Sort?
A
Work = O(n2) Span = O(n)
12
Q
Bitonic Sort?
A
Work = O(nlog2n) Span = O(log2n)
13
Q
Binary Search?
A
O(logn)
14
Q
P-ary Search?
A
Span = O(logpn)
Parallel Computing
flashcards
Decks in class (13)
# Cards
-
2 - Hardware & Architectures55
-
8 - Algorithms 1 (Sorting)24
-
3 - Map & Stencil Pattern18
-
1 - Introduction12
-
7 - Communication & Synchronisation30
-
10 - Algorithms 3 (Search)27
-
11 - Performance & Optimisation29
-
4 - Reduction Pattern16
-
5 - Scan Pattern25
-
6 - Gather & Scatter Pattern26
-
9 - Algorithms 2 (Histogram)15
-
EXAM QUESTIONS56
-
Complexities14
