1 of 34

Parallel Prefix

CSE 332 – Section 8

Slides by James Richie Sulaeman

2 of 34

Parallel Prefix/Suffix

3 of 34

Parallel prefix is a type of programming problem where:

  • A given array of elements needs to be processed in parallel
  • Each element is combined with its predecessors through some operation
    • i.e. in parallel prefix sum, each element is summed with its predecessors

Parallel Pre/suffix

Allows for efficient computation of certain operations on large datasets since it enables multiple threads to work simultaneously on different portions of the data.

Parallel Suffix is just the reversed version of prefix:

  • Also: elements need to be processed in parallel
  • This time each element is combined with its successors

4 of 34

Problem 0

Parallel Prefix Sum

Parallel Suffix Sum

5 of 34

  1. Divide problem into parallel pieces

cutoff = 1

Problem 0a

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

input =

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

6 of 34

  1. Divide problem into parallel pieces

cutoff = 1

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

input =

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

  1. Find sum at cutoff

leaves[i].sum = input[i]

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

range: 1,2

sum: 9

fromLeft:

range: 0,1

sum: 8

fromLeft:

range: 3,4

sum: 3

fromLeft:

range: 2,3

sum: 6

fromLeft:

range: 5,6

sum: 5

fromLeft:

range: 4,5

sum: 2

fromLeft:

range: 7,8

sum: 4

fromLeft:

range: 6,7

sum: 7

fromLeft:

Problem 0a - Fill in sum

7 of 34

  1. Divide problem into parallel pieces

cutoff = 1

range: 0,2

sum:

fromLeft:

input =

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

range: 0,8

sum: 44

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

  1. Find sum at cutoff

leaves[i].sum = input[i]

  1. Propagate sum up

parent.sum = left.sum + right.sum

range: 1,2

sum: 9

fromLeft:

range: 0,1

sum: 8

fromLeft:

range: 3,4

sum: 3

fromLeft:

range: 2,3

sum: 6

fromLeft:

range: 5,6

sum: 5

fromLeft:

range: 4,5

sum: 2

fromLeft:

range: 7,8

sum: 4

fromLeft:

range: 6,7

sum: 7

fromLeft:

range: 0,2

sum: 17

fromLeft:

range: 2,4

sum: 9

fromLeft:

range: 4,6

sum: 7

fromLeft:

range: 6,8

sum: 11

fromLeft:

range: 0,4

sum: 26

fromLeft:

range: 4,8

sum: 18

fromLeft:

Problem 0a - Fill in sum (cont.)

8 of 34

  1. Divide problem into parallel pieces

cutoff = 1

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

  1. Find sum at cutoff

leaves[i].sum = input[i]

  1. Propagate sum up

parent.sum = left.sum + right.sum

  1. Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

range: 1,2

sum: 9

fromLeft:

range: 0,1

sum: 8

fromLeft:

range: 3,4

sum: 3

fromLeft:

range: 2,3

sum: 6

fromLeft:

range: 5,6

sum: 5

fromLeft:

range: 4,5

sum: 2

fromLeft:

range: 7,8

sum: 4

fromLeft:

range: 6,7

sum: 7

fromLeft:

range: 0,2

sum: 17

fromLeft:

range: 2,4

sum: 9

fromLeft:

range: 4,6

sum: 7

fromLeft:

range: 6,8

sum: 11

fromLeft:

range: 0,4

sum: 26

fromLeft:

range: 4,8

sum: 18

fromLeft:

range: 0,8

sum: 44

fromLeft:

range: 1,2

sum: 9

fromLeft: 8

range: 0,1

sum: 8

fromLeft: 0

range: 3,4

sum: 3

fromLeft: 23

range: 2,3

sum: 6

fromLeft: 17

range: 5,6

sum: 5

fromLeft: 28

range: 4,5

sum: 2

fromLeft: 26

range: 7,8

sum: 4

fromLeft: 40

range: 6,7

sum: 7

fromLeft: 33

range: 0,2

sum: 17

fromLeft: 0

range: 2,4

sum: 9

fromLeft: 17

range: 4,6

sum: 7

fromLeft: 26

range: 6,8

sum: 11

fromLeft: 33

range: 0,4

sum: 26

fromLeft: 0

range: 4,8

sum: 18

fromLeft: 26

range: 0,8

sum: 44

fromLeft: 0

Problem 0a

9 of 34

  1. Divide problem into parallel pieces

cutoff = 1

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[0],...,input[i])

  1. Find sum at cutoff

leaves[i].sum = input[i]

  1. Propagate sum up

parent.sum = left.sum + right.sum

  1. Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

  1. output[i] = leaves[i].fromLeft + input[i]

range: 1,2

sum: 9

fromLeft: 8

range: 0,1

sum: 8

fromLeft: 0

range: 3,4

sum: 3

fromLeft: 23

range: 2,3

sum: 6

fromLeft: 17

range: 5,6

sum: 5

fromLeft: 28

range: 4,5

sum: 2

fromLeft: 26

range: 7,8

sum: 4

fromLeft: 40

range: 6,7

sum: 7

fromLeft: 33

range: 0,2

sum: 17

fromLeft: 0

range: 2,4

sum: 9

fromLeft: 17

range: 4,6

sum: 7

fromLeft: 26

range: 6,8

sum: 11

fromLeft: 33

range: 0,4

sum: 26

fromLeft: 0

range: 4,8

sum: 18

fromLeft: 26

range: 0,8

sum: 44

fromLeft: 0

8

17

23

26

28

33

40

44

Problem 0a

10 of 34

1. Divide problem into parallel pieces

cutoff = 1

range: 0,2

sum:

fromLeft:

input =

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

range: 0,8

sum: 44

fromRight:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = sum(input[i],...,input[input.length-1])

2. Find sum at cutoff

leaves[i].sum = input[i]

3. Propagate sum up

parent.sum = left.sum + right.sum

range: 1,2

sum: 9

fromRight:

range: 0,1

sum: 8

fromRight:

range: 3,4

sum: 3

fromRight:

range: 2,3

sum: 6

fromRight:

range: 5,6

sum: 5

fromRight:

range: 4,5

sum: 2

fromRight:

range: 7,8

sum: 4

fromRight:

range: 6,7

sum: 7

fromRight:

range: 0,2

sum: 17

fromRight:

range: 2,4

sum: 9

fromRight:

range: 4,6

sum: 7

fromRight:

range: 6,8

sum: 11

fromRight:

range: 0,4

sum: 26

fromRight:

range: 4,8

sum: 18

fromRight:

Problem 0b

Same steps to calculate sum

11 of 34

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

  1. Propagate fromRight down

right.fromRight = parent.fromRight

left.fromRight = parent.fromRight + right.sum

range: 1,2

sum: 9

fromRight:

range: 0,1

sum: 8

fromRight:

range: 3,4

sum: 3

fromRight:

range: 2,3

sum: 6

fromRight:

range: 5,6

sum: 5

fromRight:

range: 4,5

sum: 2

fromRight:

range: 7,8

sum: 4

fromRight:

range: 6,7

sum: 7

fromRight:

range: 0,2

sum: 17

fromRight:

range: 2,4

sum: 9

fromRight:

range: 4,6

sum: 7

fromRight:

range: 6,8

sum: 11

fromRight:

range: 0,4

sum: 26

fromRight:

range: 4,8

sum: 18

fromRight:

range: 0,8

sum: 44

fromRight:

range: 1,2

sum: 9

fromRight: 27

range: 0,1

sum: 8

fromRight: 36

range: 3,4

sum: 3

fromRight: 18

range: 2,3

sum: 6

fromRight: 21

range: 5,6

sum: 5

fromRight: 11

range: 4,5

sum: 2

fromRight: 16

range: 7,8

sum: 4

fromRight: 0

range: 6,7

sum: 7

fromRight: 4

range: 0,2

sum: 17

fromRight: 27

range: 2,4

sum: 9

fromRight: 18

range: 4,6

sum: 7

fromRight: 11

range: 6,8

sum: 11

fromRight: 0

range: 0,4

sum: 26

fromRight: 18

range: 4,8

sum: 18

fromRight: 0

range: 0,8

sum: 44

fromRight: 0

Problem 0b

1. Divide problem into parallel pieces

cutoff = 1

2. Find sum at cutoff

leaves[i].sum = input[i]

3. Propagate sum up

parent.sum = left.sum + right.sum

Same steps to calculate sum

Given an array input, output an array such that

output[i] = sum(input[i],...,input[input.length-1])

​

12 of 34

range: 0,8

sum: 44

fromRight:

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

5. output[i] = leaves[i].fromRight + input[i]

44

36

27

21

18

16

11

4

Problem 0b

range: 1,2

sum: 9

fromRight:

range: 0,1

sum: 8

fromRight:

range: 3,4

sum: 3

fromRight:

range: 2,3

sum: 6

fromRight:

range: 5,6

sum: 5

fromRight:

range: 4,5

sum: 2

fromRight:

range: 7,8

sum: 4

fromRight:

range: 6,7

sum: 7

fromRight:

range: 0,2

sum: 17

fromRight:

range: 2,4

sum: 9

fromRight:

range: 4,6

sum: 7

fromRight:

range: 6,8

sum: 11

fromRight:

range: 0,4

sum: 26

fromRight:

range: 4,8

sum: 18

fromRight:

range: 1,2

sum: 9

fromRight: 27

range: 0,1

sum: 8

fromRight: 36

range: 3,4

sum: 3

fromRight: 18

range: 2,3

sum: 6

fromRight: 21

range: 5,6

sum: 5

fromRight: 11

range: 4,5

sum: 2

fromRight: 16

range: 7,8

sum: 4

fromRight: 0

range: 6,7

sum: 7

fromRight: 4

range: 0,2

sum: 17

fromRight: 27

range: 2,4

sum: 9

fromRight: 18

range: 4,6

sum: 7

fromRight: 11

range: 6,8

sum: 11

fromRight: 0

range: 0,4

sum: 26

fromRight: 18

range: 4,8

sum: 18

fromRight: 0

range: 0,8

sum: 44

fromRight: 0

  1. Propagate fromRight down

right.fromRight = parent.fromRight

left.fromRight = parent.fromRight + right.sum

1. Divide problem into parallel pieces

cutoff = 1

2. Find sum at cutoff

leaves[i].sum = input[i]

3. Propagate sum up

parent.sum = left.sum + right.sum

Same steps to calculate sum

Given an array input, output an array such that

output[i] = sum(input[i],...,input[input.length-1])

​

13 of 34

Problem 1

Parallel Prefix FindMin

14 of 34

  1. Divide problem into parallel pieces

cutoff = 1

Problem 1

range: 1,2

min:

fromLeft:

range: 0,1

min:

fromLeft:

range: 0,2

min:

fromLeft:

input =

range: 3,4

min:

fromLeft:

range: 2,3

min:

fromLeft:

range: 2,4

min:

fromLeft:

range: 0,4

min:

fromLeft:

range: 5,6

min:

fromLeft:

range: 4,5

min:

fromLeft:

range: 4,6

min:

fromLeft:

range: 7,8

min:

fromLeft:

range: 6,7

min:

fromLeft:

range: 6,8

min:

fromLeft:

range: 4,8

min:

fromLeft:

range: 0,8

min:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

15 of 34

range: 1,2

min:

fromLeft:

range: 0,1

min:

fromLeft:

range: 0,2

min:

fromLeft:

input =

range: 3,4

min:

fromLeft:

range: 2,3

min:

fromLeft:

range: 2,4

min:

fromLeft:

range: 0,4

min:

fromLeft:

range: 5,6

min:

fromLeft:

range: 4,5

min:

fromLeft:

range: 4,6

min:

fromLeft:

range: 7,8

min:

fromLeft:

range: 6,7

min:

fromLeft:

range: 6,8

min:

fromLeft:

range: 4,8

min:

fromLeft:

range: 0,8

min:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

range: 1,2

min: 9

fromLeft:

range: 0,1

min: 8

fromLeft:

range: 3,4

min: 3

fromLeft:

range: 2,3

min: 6

fromLeft:

range: 5,6

min: 5

fromLeft:

range: 4,5

min: 2

fromLeft:

range: 7,8

min: 4

fromLeft:

range: 6,7

min: 7

fromLeft:

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

  1. Divide problem into parallel pieces

cutoff = 1

  1. Find min at cutoff

leaves[i].min = input[i]

16 of 34

range: 0,2

min:

fromLeft:

input =

range: 2,4

min:

fromLeft:

range: 0,4

min:

fromLeft:

range: 4,6

min:

fromLeft:

range: 6,8

min:

fromLeft:

range: 4,8

min:

fromLeft:

range: 0,8

min:

fromLeft:

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

range: 1,2

min: 9

fromLeft:

range: 0,1

min: 8

fromLeft:

range: 3,4

min: 3

fromLeft:

range: 2,3

min: 6

fromLeft:

range: 5,6

min: 5

fromLeft:

range: 4,5

min: 2

fromLeft:

range: 7,8

min: 4

fromLeft:

range: 6,7

min: 7

fromLeft:

range: 0,2

min: 8

fromLeft:

range: 2,4

min: 3

fromLeft:

range: 4,6

min: 2

fromLeft:

range: 6,8

min: 4

fromLeft:

range: 0,4

min: 3

fromLeft:

range: 4,8

min: 2

fromLeft:

range: 0,8

min: 2

fromLeft:

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

  1. Divide problem into parallel pieces

cutoff = 1

  1. Find min at cutoff

leaves[i].min = input[i]

  1. Propagate min up

parent.min = min(left.min, right.min)

17 of 34

range: 0,8

min: 2

fromLeft:

range: 0,4

min: 3

fromLeft:

range: 4,8

min: 2

fromLeft:

range: 6,8

min: 4

fromLeft:

  1. Divide problem into parallel pieces

cutoff = 1

input =

8

9

6

3

2

5

7

4

output =

  1. Find min at cutoff

leaves[i].min = input[i]

  1. Propagate min up

parent.min = min(left.min, right.min)

  1. Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = min(parent.fromLeft, left.min)

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

range: 0,2

min: 8

fromLeft:

range: 2,4

min: 3

fromLeft:

range: 0,1

min: 8

fromLeft:

range: 4,6

min: 2

fromLeft:

range: 1,2

min: 9

fromLeft:

range: 3,4

min: 3

fromLeft:

range: 2,3

min: 6

fromLeft:

range: 5,6

min: 5

fromLeft:

range: 4,5

min: 2

fromLeft:

range: 7,8

min: 4

fromLeft:

range: 6,7

min: 7

fromLeft:

range: 0,8

min: 2

fromLeft: ∞

range: 0,4

min: 3

fromLeft: ∞

range: 4,8

min: 2

fromLeft: 3

range: 6,8

min: 4

fromLeft: 2

range: 0,2

min: 8

fromLeft: ∞

range: 2,4

min: 3

fromLeft: 8

range: 0,1

min: 8

fromLeft: ∞

range: 4,6

min: 2

fromLeft: 3

range: 1,2

min: 9

fromLeft: 8

range: 3,4

min: 3

fromLeft: 6

range: 2,3

min: 6

fromLeft: 8

range: 5,6

min: 5

fromLeft: 2

range: 4,5

min: 2

fromLeft: 3

range: 7,8

min: 4

fromLeft: 2

range: 6,7

min: 7

fromLeft: 2

​

​

​

​

​

​

​

​

18 of 34

  1. Divide problem into parallel pieces

cutoff = 1

input =

8

9

6

3

2

5

7

4

​

​

​

​

​

​

​

​

output =

  1. Find min at cutoff

leaves[i].min = input[i]

  1. Propagate min up

parent.min = min(left.min, right.min)

  1. Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = min(parent.fromLeft, left.min)

  1. output[i] = min(leaves[i].fromLeft, input[i])

8

8

6

3

2

2

2

2

Problem 1

Given an array input, output an array such that

output[i] = min(input[0],...,input[i])

range: 0,8

min: 2

fromLeft: ∞

range: 0,4

min: 3

fromLeft: ∞

range: 4,8

min: 2

fromLeft: 3

range: 6,8

min: 4

fromLeft: 2

range: 0,2

min: 8

fromLeft: ∞

range: 2,4

min: 3

fromLeft: 8

range: 0,1

min: 8

fromLeft: ∞

range: 4,6

min: 2

fromLeft: 3

range: 1,2

min: 9

fromLeft: 8

range: 3,4

min: 3

fromLeft: 6

range: 2,3

min: 6

fromLeft: 8

range: 5,6

min: 5

fromLeft: 2

range: 4,5

min: 2

fromLeft: 3

range: 7,8

min: 4

fromLeft: 2

range: 6,7

min: 7

fromLeft: 2

19 of 34

Problem 2

Parallel Pack

20 of 34

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Problem 2 Overview

Given an array input, output an array that contains only the elements that are less than 10

  1. Parallel map to compute bits array where bits[i] = (input[i] < 10)
  1. Parallel prefix sum on bits array to compute bitsum array
  1. Parallel populate to produce output array where output.length = bitsum[n-1] and output[bitsum[i]-1] =input[i] if bits[i] == 1

12

5

-8

34

6

10

2

7

input =

bits =

0

1

1

0

1

0

1

1

bitsum =

0

1

2

2

3

3

4

5

output =

5

-8

6

2

7

21 of 34

Problem 2

  1. Parallel map to compute bits array where bits[i] = (input[i] < 10)

input =

12

5

-8

34

6

10

2

7

​

​

​

​

​

​

​

​

bits =

0

1

1

0

1

0

1

1

lo: 0

hi: 8

lo: 0

hi: 4

lo: 4

hi: 8

lo: 6

hi: 8

lo: 0

hi: 2

lo: 2

hi: 4

lo: 0

hi: 1

lo: 4

hi: 6

lo: 1

hi: 2

lo: 3

hi: 4

lo: 2

hi: 3

lo: 5

hi: 6

lo: 4

hi: 5

lo: 7

hi: 8

lo: 6

hi: 7

22 of 34

  1. Divide problem into parallel pieces

cutoff = 1

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

bits =

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

0

1

1

0

1

0

1

1

​

​

​

​

​

​

​

​

bitsum =

  1. Parallel prefix sum on bits array

to compute bitsum array

Problem 2

23 of 34

  1. Divide problem into parallel pieces

cutoff = 1

range: 1,2

sum:

fromLeft:

range: 0,1

sum:

fromLeft:

range: 0,2

sum:

fromLeft:

range: 3,4

sum:

fromLeft:

range: 2,3

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 5,6

sum:

fromLeft:

range: 4,5

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 7,8

sum:

fromLeft:

range: 6,7

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

​

​

​

​

​

​

​

​

  1. Find sum at cutoff

leaves[i].sum = bits[i]

range: 1,2

sum: 1

fromLeft:

range: 0,1

sum: 0

fromLeft:

range: 3,4

sum: 0

fromLeft:

range: 2,3

sum: 1

fromLeft:

range: 5,6

sum: 0

fromLeft:

range: 4,5

sum: 1

fromLeft:

range: 7,8

sum: 1

fromLeft:

range: 6,7

sum: 1

fromLeft:

  1. Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

24 of 34

  1. Divide problem into parallel pieces

cutoff = 1

range: 0,2

sum:

fromLeft:

range: 2,4

sum:

fromLeft:

range: 0,4

sum:

fromLeft:

range: 4,6

sum:

fromLeft:

range: 6,8

sum:

fromLeft:

range: 4,8

sum:

fromLeft:

range: 0,8

sum:

fromLeft:

​

​

​

​

​

​

​

​

  1. Find sum at cutoff

leaves[i].sum = bits[i]

  1. Propagate sum up

parent.sum = left.sum + right.sum

range: 1,2

sum: 1

fromLeft:

range: 0,1

sum: 0

fromLeft:

range: 3,4

sum: 0

fromLeft:

range: 2,3

sum: 1

fromLeft:

range: 5,6

sum: 0

fromLeft:

range: 4,5

sum: 1

fromLeft:

range: 7,8

sum: 1

fromLeft:

range: 6,7

sum: 1

fromLeft:

range: 0,2

sum: 1

fromLeft:

range: 2,4

sum: 1

fromLeft:

range: 4,6

sum: 1

fromLeft:

range: 6,8

sum: 2

fromLeft:

range: 0,4

sum: 2

fromLeft:

range: 4,8

sum: 3

fromLeft:

range: 0,8

sum: 5

fromLeft:

  1. Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

25 of 34

range: 0,1

sum: 0

fromLeft:

range: 0,2

sum: 1

fromLeft:

range: 1,2

sum: 1

fromLeft:

range: 2,3

sum: 1

fromLeft:

range: 2,4

sum: 1

fromLeft:

range: 3,4

sum: 0

fromLeft:

range: 4,5

sum: 1

fromLeft:

range: 5,6

sum: 0

fromLeft:

range: 6,7

sum: 1

fromLeft:

range: 7,8

sum: 1

fromLeft:

range: 6,8

sum: 2

fromLeft:

range: 4,6

sum: 1

fromLeft:

range: 4,8

sum: 3

fromLeft:

range: 0,4

sum: 2

fromLeft:

range: 0,8

sum: 5

fromLeft:

range: 7,8

sum: 1

fromLeft: 4

range: 6,7

sum: 1

fromLeft: 3

range: 5,6

sum: 0

fromLeft: 3

range: 4,5

sum: 1

fromLeft: 2

range: 3,4

sum: 0

fromLeft: 2

range: 2,3

sum: 1

fromLeft: 1

range: 1,2

sum: 1

fromLeft: 0

range: 0,1

sum: 0

fromLeft: 0

range: 0,2

sum: 1

fromLeft: 0

range: 2,4

sum: 1

fromLeft: 1

range: 4,6

sum: 1

fromLeft: 2

range: 6,8

sum: 2

fromLeft: 3

range: 4,8

sum: 3

fromLeft: 2

range: 0,4

sum: 2

fromLeft: 0

range: 0,8

sum: 5

fromLeft: 0

  1. Divide problem into parallel pieces

cutoff = 1

​

​

​

​

​

​

​

​

  1. Find sum at cutoff

leaves[i].sum = bits[i]

  1. Propagate sum up

parent.sum = left.sum + right.sum

  1. Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

  1. Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

26 of 34

range: 0,8

sum: 5

fromLeft: 0

range: 0,4

sum: 2

fromLeft: 0

range: 4,8

sum: 3

fromLeft: 2

range: 6,8

sum: 2

fromLeft: 3

range: 4,6

sum: 1

fromLeft: 2

range: 2,4

sum: 1

fromLeft: 1

range: 0,2

sum: 1

fromLeft: 0

range: 7,8

sum: 1

fromLeft: 4

range: 6,7

sum: 1

fromLeft: 3

range: 5,6

sum: 0

fromLeft: 3

range: 4,5

sum: 1

fromLeft: 2

range: 3,4

sum: 0

fromLeft: 2

range: 2,3

sum: 1

fromLeft: 1

range: 1,2

sum: 1

fromLeft: 0

range: 0,1

sum: 0

fromLeft: 0

  1. Divide problem into parallel pieces

cutoff = 1

​

​

​

​

​

​

​

​

  1. Find sum at cutoff

leaves[i].sum = bits[i]

  1. Propagate sum up

parent.sum = left.sum + right.sum

  1. Propagate fromLeft down

left.fromLeft = parent.fromLeft

right.fromLeft = parent.fromLeft + left.sum

  1. bitsum[i] = leaves[i].fromLeft + bits[i]

0

1

2

2

3

3

4

5

  1. Parallel prefix sum on bits array

to compute bitsum array

bits =

bitsum =

0

1

1

0

1

0

1

1

Problem 2

27 of 34

Problem 2

  • Parallel populate to produce output array where output.length = bitsum[n-1] and output[bitsum[i]-1] =input[i] if bits[i] == 1

​

input =

12

5

-8

34

6

10

2

7

lo: 0

hi: 1

​

​

​

​

​

​

​

​

0

1

2

2

3

3

4

5

bits =

bitsum =

0

1

1

0

1

0

1

1

output =

​

​

​

​

​

lo: 1

hi: 2

lo: 2

hi: 3

lo: 3

hi: 4

lo: 4

hi: 5

lo: 5

hi: 6

lo: 6

hi: 7

lo: 7

hi: 8

lo: 0

hi: 2

lo: 6

hi: 8

lo: 2

hi: 4

lo: 4

hi: 6

lo: 0

hi: 4

lo: 4

hi: 8

lo: 0

hi: 8

5

-8

6

2

7

28 of 34

Problem 3

29 of 34

  1. Define work and span.

​

​

​

  • How do we calculate work and span?

​

​

​

  • Does adding more processors affect the work or span?

​

Work is the runtime of a program on one processor.

Span is the runtime of a program on infinitely many processors.

​

​

Work is the sum of all the work done by all processors

Span is the sum of all the work done by the longest dependence chain / parallel ‘tree’ branch

​

​

Neither. Work is defined for one processor and span is defined for infinitely many processors. Adding more processors will not affect either work or span.

Problem 3

30 of 34

  1. What is the work and span of the process depicted by this thread graph?

Problem 3

T3

work: 2

T2

work: 2

T4

work: 2

T1

work: 1

T6

work: 1

T5

work: 4

T7

work: 1

​

Work = 1 + 2 + 2 + 2 + 4 + 1 + 1

= 13

Span ( T1→T2→T5 ) = 1 + 2 + 4

= 7

31 of 34

Amdahl’s Law Review

 

32 of 34

e) Suppose a program needs to do 20% of its work sequentially (the rest can be parallelized), what is the maximum speed up with 4 processors? What about 8?

Problem 3

Recall Amdahl’s Law:

​

33 of 34

e) Suppose a program needs to do 20% of its work sequentially (the rest can be parallelized).

​

Problem 3

Recall Amdahl’s Law:

​

Observe: we got way more parallelism from the first 4 processors (2.5) than the second 4 (0.833).

Takeaway: we get diminishing returns from additional processors

With 8 processors?

What is the maximum speed up with 4 processors?

34 of 34

Thank You!