3 - Map & Stencil Pattern

Question 1

What are parallel patterns?

Answer 1

Commonly recurring strategies to deal with problems, general, not dependent on particular platform

Question 2

What are the semantics of a parallel pattern?

Answer 2

How they work

Question 3

What is the Map pattern?

Answer 3

Map applies an elemental function to every element of data in parallel resulting in a new collection of the same shape as the input.

The result does not depend on the order in which various instances of the function are executed

Question 4

Describe dependencies in the Map pattern

Answer 4

There are no dependencies in the map pattern so each element can be processed spearately

Question 5

What are the 2 complexity measures for patterns?

Answer 5

Work = total number of operations and Span = total number of sequential steps

Question 6

What are embarrassingly parallel problems?

Answer 6

Problems solved by the map pattern. Straightforward to implement due to lack of dependency between tasks

Question 7

Name some applications of the Map pattern

Answer 7

Vector arithmetic, and brightness/contrast adjustment in image processing

Question 8

What are the 2 types of map pattern?

Answer 8

Unary = 1 input and 1 output, and N-array = n input and 1 output

Question 9

What is Sequence of Maps and Maps of Sequences?

Answer 9

Converting several map operations of the same size that occur in sequence into a map of sequences by fusing together the operations to perform them in a single map

Question 10

What are the benefits of maps of sequences?

Answer 10

Adds arithmetic intensity and reduces the memory requirements and bandwidth

Question 11

Give an example of a Map of Sequences

Answer 11

C = A * B + B

Question 12

What do you do if the number of elements in a map pattern is greater than the number of processors?

Answer 12

Partition the input data into smaller parts, with each partition being then processed in a serial sequences

Question 13

What do you do if the number of elements in a map pattern is greater than the amount of available device memory?

Answer 13

Partition into smaller parts, and take additional variables into account

Question 14

What is the Stencil pattern?

Answer 14

Stencil is a generalisation of the Map pattern in which an elemental function can access not only a single element in an input collection but also a set of neighbours

Question 15

In the Stencil pattern what does the output depend on?

Answer 15

A neighbourhood of inputs specified using a set of fixed offsets relative to the output position

Question 16

Name some applications of the Stencil pattern

Answer 16

Common in image and signal processing and PDE solvers over regular grids

Question 17

Describe the result of a 1D averaging filter implemented using the Stencil filter

Answer 17

The result is an average of values at the central position and immediate neighbours to the left and right

Question 18

How do you optimise the Stencil pattern?

Answer 18

Flexible stencil provided externally by the host as an input argument

Use temporary storage (local memory/cache) to store the neighbourhood which is much faster to access than normal memory

Boundary handling by keeping the main loop without boundary checks