5 - Scan Pattern

Question 1

What is a Cumulative Sum operations?

Answer 1

Add all elements and keep all the partial results, output is of the same size as the input

Question 2

What are the two types of Scan?

Answer 2

Span efficient (Hillis-Steele) and work efficient (Blelloch)

Question 3

What does the Scan pattern do?

Answer 3

Computes all partial reductions of a collection; every element of the output is a reduction of all the elements of the input up to the position of that output element

Question 4

What does the Combiner function take as input?

Answer 4

The output of the previous loop iteration as well as the new input value

Question 5

What is the complexity of a serial Scan?

Answer 5

Work = O(n)
Span = O(n)

Question 6

Discuss the requirements of the Scan operation

Answer 6

Exactly the same as the reduction pattern: function needs to be associative

Question 7

What happens if the combiner function is non-associative?

Answer 7

The Scan cannot be parallelised and it is then called a general fold pattern

Question 8

What are two categories of Scan?

Answer 8

Inclusive and exclusive

Question 9

What is an Inclusive Scan?

Answer 9

Includes the current element in partial reduction

Question 10

What is an Exclusive Scan?

Answer 10

Excludes the current element in partial reduction

Question 11

What is the process of Span-Efficient Inclusive Scan?

Answer 11

Form a reduction tree for every output element, then merge the redundant elements of all those trees

Question 12

What is the complexity of parallel Span-Efficient Scan (Hillis Steele)?

Answer 12

Work = O(n.log n) = worse than setial version 
Span = O(log n) = span efficient

Question 13

What does the Span-Efficient scan perform badly on and why?

Answer 13

Large arrays, due to its work-inefficiency

Question 14

What is the process of Work-Efficient Scan?

Answer 14

Since the combiner function is associative we can reorder operations to reduce span.

Two-phase reordering performing an up-sweep and a down-steep

Question 15

What is up-sweeping?

Answer 15

Reducing on input/computing the reduction

Question 16

What is down-sweeping?

Answer 16

Produces the intermediate results/values

Question 17

How do you traverse in a work efficient scan?

Answer 17

Up-sweep = leaves to roots

Down-sweep = root to leaves

Question 18

What is the complexity of Work Efficient Scan?

Answer 18

Requires 2 more steps than HS scan

Requires roughly 3 times more operations than serial scan

Span = O(log n) = less efficient than HS

Work = O(n) = less efficient than serial

Question 19

Which Scan should you use when you have more work than processors?

Answer 19

Work Efficient

Question 20

Which Scan should you use when you have more processors than work?

Answer 20

Span Efficient

Question 21

Which Scan should you use with 512 elements and 512 processors?

Answer 21

Hillis/Steele

Question 22

Which Scan should you use with 1M elements and 512 processors?

Answer 22

Blelloch

Question 23

Which Scan should you use with 128k elements and 1 processor?

Answer 23

Serial!

Question 24

How do you deal with large arrays?

Answer 24

The presented algorithms only work for a single block/work group

Use a two stage procedure to accomodate large arrays

Question 25

What is the Pack Pattern?

Answer 25

Assign boolean keys to all elements in collection, false if an element needs to be filtered out

Perform exclusive scan on keys, result is an array with output indices