Intro To The Work-Span Model

Question 1

Dynamic Multithreading Model

Answer 1

Two parts:
- A computation can be represented by a directed acyclic graph, in which each node is an operation and each edge a dependence.
- Pseudocode notation, or programming model, for writing down the algorithm. Designed so that “when you execute one of these algorithms, it generates a DAG, at least conceptually.”

Question 2

From the point of view of exploiting parallelism, what is the key property of a “good” DAG?

Answer 2

It has few dependencies.

Question 3

What separation does the pseudo code notation do?

Answer 3

It separates how to produce work (algorithm) from how to schedule and execute it (hardware).

Question 4

What is a scheduling problem?

Answer 4

The problem of how to take free units of work and assign them to processors.

Question 5

Given a complete binary tree with n leaves, how many levels does it have?

Answer 5

log(n)

Question 6

What is work?

Answer 6

Total number of nodes/verticies in a multithreaded DAG model

Question 7

What is span?

Answer 7

The length of the longest path through the multithreaded DAG model (from start to end). Also called “depth”.

Notated D(n)

Question 8

What is another name for the longest path through a DAG?

Answer 8

Critical path

Question 9

How much time does it take to execute all operations in DAG with one processor, assuming all ops have unit cost?

Answer 9

W(n), i.e., total work

Question 10

How much time does it take to execute all operations in DAG with infinite processors, assuming all ops have unit cost?

Answer 10

D(n)

Question 11

Average available parallelism

Answer 11

W(n)/D(n)

Average work per critical path vertex. This is the amount of parallelism we can take advantage of at each critical path vertex, and is a good starting point for choosing an appropriate number of processors.

Question 12

Span Law

Answer 12

T_p(n) >= D(n)

i.e., Span is the lower bound on the execution time given p processors.

Question 13

Work Law

Answer 13

T_p(n) >= ceiling(W(n)/p)

Another lower bound on the execution time given p processors. This time it’s total work divided by number of processors.

Question 14

Work-Span Law

Answer 14

Both the Work Law and Span Law must be true simultaneously, so we can combine them.

T_p(n) >= max{D(n), ceiling(W(n)/p)}

This gives a lower bound on execution time.

Question 15

How do you derive Brent’s Theorem (which provides an upper bound on execution time of a DAG)?

Answer 15

1) Break up the DAG into k phases, where each phase meets three conditions:
- Each phase has STRICTLY one critical path vertex.
- All vertices within a phase that are NOT on the critical path must be independent, i.e., have no dependencies between them.
- Each vertex must belong to some phase.
2) Each phase k has a number of vertices in it, W_k (including critical path vertex)
3) By condition three of our phase conditions, the sum of W_k for all k = W, total work for the DAG.
4) How long does it take to execute phase k? t_k = ceiling(W_k/p)
5) 4 implies that the total time T_p = sum from k=1 to D of ceiling(W_k/p)
6) We can algebraically rearrange the ceiling of the quotient in 5 to turn it into a floor: total time T_p = sum from k=1 to D of floor( (W_k-1) / p) + 1
7) floor(x) is always <= x, so T_p <= sum from k=1 to D of (W_k-1)/p + 1
8) 7 implies that T_p <= (W - D)/p + D! Brent’s Theorem!

Question 16

What is Brent’s Theorem?

Answer 16

T_p <= (W - D)/p + D

T_p := total execution time of DAG given p processors
W := work of DAG, i.e., number of vertices or operations
D := span of DAG, i.e., depth
p : number of processors

Question 17

What is the intuitive interpretation of Brent’s Theorem?

Answer 17

Total time to execute the DAG is less than or equal to the time needed to execute the critical path (D) plus the time needed to execute all other nodes using p processors.

Note that the time to execute the critical path does not depend on p because you can’t execute nodes of the critical path in parallel.

Question 18

What’s the equation for speedup of parallel time over best sequential time?

Answer 18

S_p(n) := T_*(n)/T_p(n)

Question 19

What does T_p(n) depend on?

Answer 19

T_p(n) = f(W, D; n, P)

work, span, problem size, and number of processors

Question 20

What does T_*(n) depend on?

Answer 20

T_(n) = W_(n)

Work done by best sequential algorithm

Question 21

What is the ideal speedup of a parallel algorithm over the best sequential algorithm?

Answer 21

Ideal speedup is linear in P, also called linear speed up, linear scaling, or ideal scaling.

S_p(n) = Theta(P)

Question 22

How does big-Theta notation work?

Answer 22

big-Theta depends on both big-O and big-Omega.

big-O provides an upper bound on the performance of an algorithm. f(n) is O(g(n)) if there exist some constants C_1 and n_0 s.t. 0 <= f(x) <= C_1*g(n) for all n >= n_0.

big-Omega provides a lower bound on the performance of an algorithm. f(n) is Omega(g(n)) if there exist some constants C_2 and n_0 s.t. 0 <= C_2*g(n) <= f(n) for all n >= n_0.

big-Theta provides the tightest bound on execution time. f(n) is Theta(g(n)) if there exist some constants C_1, C_2, and n_0 such that 0 <= C_2g(n) <= f(n) <= C_1g(n) for all n >= n_0.

Question 23

How do you use Brent’s Theorem to get a lower bound on speedup (and then make it easier to analyze)? Using the resulting equation, what has to be true to get ideal scaling?

Answer 23

S_p(n) = T_(n)/T_p(n) = W_(n)/T_p(n) because we know execution time using the best sequential algorithm is basically just a function of work done using that algorithm.

Brent’s Theorem gives us an upper bound on execution time. By plugging it in to this equation we get a lower bound on speedup: S_p(n) = W_(n)/T_p(n) >= W_(n)/[(W-D)/P + D] = (via a little algebra) P/[(W/W_) + (P-1)/(W_/D)]

To get ideal scaling, the denominator must be constant (since P is the numerator and ideal scaling means linear scaling in P). To do this, W(n) must equal W_(n) (so W/W_ = a constant fraction). This is called “work-optimality”.

We also need p to be proportional to W_/D, i.e., P = O(W_/D). Could be rewritten as W*/P = Omega(D), which says the work per processor must grow with the span, which in turn depends on n. This is called “weak scalability”.

Question 24

What is work-optimality?

Answer 24

W(n) = O(W*(n)), i.e., the work of our parallel algorithm must be proportional to the work of our best sequential algorithm. We use this to get ideal scaling.

Question 25

What is weak-scalability?

Answer 25

P = O(W/D) implies W/P = Omega(D), i.e., the work per processor must grow with the span, which in turn depends on n, the problem size. We use this to get ideal scaling.

Question 26

Spawn

Answer 26

A keyword that tells the compiler or runtime system that the target is an independent unit of work, i.e., may be executed asynchronously. The target is either a function or procedure call.

Question 27

Sync

Answer 27

A keyword that tells the compiler or runtime system that the program can only continue after all spawns have finished their work, i.e., when everyone’s caught up!

To which spawns does sync apply? In this class we’ll assume sync always applies to any spawn that has occurred on the same stack frame.

Question 28

Call stack

Answer 28

A stack data structure that stores information about the active subroutines of a computer program.

Its main purpose it to keep track of the point to which each active subroutine should return control when it completes execution.

A call stack is composed of stack frames.

Question 29

Stack frame

Answer 29

These are the components of the call stack. Each stack frame corresponds to an active subroutine; it is a data structure that contains state information about its corresponding subroutine.

Question 30

Returns include an implicit sync. Why might this give us incorrect results?

Answer 30

Say you spawn two processes that put some values in variables A and B, then return A+B. The return call will evaluate A+B first and store it in a temporary variable and only sync afterwards.

However, we need to sync BEFORE the addition. If we don’t, then we can’t guarantee that the values in A and B are the values we computed in our spawned processes! They might be junk, or they might be values previously stored to those variables.

Question 31

Within the span-sync framework, can you analyze work-span algorithms the same way you analyze sequential algorithms?

Answer 31

Basically, yes!

If we assume spawns and syncs are O(1) (which is often true in practice), then we can ignore them and do the usual sequential analysis.

The recurrence for work W(n) will look like the recurrence for the sequential analysis T(n)! The recurrence for span will be different, but not too bad.

Question 32

What are your goals as a parallel algorithm designer, with respect to work and span?

Answer 32

1) Work-optimality: Achieve work that matches the best sequential algorithm, i.e. O(n) if at all humanly possible.

2) Poly-logarithmic span (or “low” span): D(n) = O(log^k n). Because our work goal is O(n) and log n grows more slowly than n, this means is that the average available parallelism grows with n. Note: this is because span is DEPTH, so basically a good parallel algorithm doesn’t grow too much deeper as the amount of work increases.

Question 33

par-for

Answer 33

Parallel-for, or for-any or for-all. A kind of loop where all iterations are independent of one another. You can execute in any order.

In DAG terms, this creates n independent sub-paths. Like executing n spawns simultaneously.

At the end of the par-for, there is an implicit sync point.

Question 34

Work and span of par-for

Answer 34

If each iteration is bounded by a constant cost, then work is O(1) for each of them and O(n) all together.

In theory, span would be constant. However, span actually depends on implementation. If we implement par-for with a for loop that spawns each iteration, then span is O(n)! That’s terrible!

A more realistic implementation would be to create a procedure call that spawns iterations of the loop, and call it recursively while using divide and conquer. This results in the standard binary tree recursion gives us a span of O(log n). Better!

Assume the O(log n) span implementation for this class.

Question 35

Race condition

Answer 35

When a data race leads to an error.

NOTE: Data race does not always lead to an error! So data race does not necessarily imply a race condition.

Question 36

What does it mean to “reduce” an array?

Answer 36

FROM WHAT I CAN TELL, it means to convert an array to a single value, most commonly by summing its elements. A lot of programming languages seem to have a reduce() method for arrays (Swift, Javascript, etc).

In Swift, for example, arr.reduce(0, +) will start with a value of 0, then combine that with the first element of arr using 0+arr[0], then combine that with arr[1], until it has summed all elements in arr. Presumably this could be done with any other binary operator, though I’m not confident about that.

Question 37

Vector notation tricks

Answer 37

In this class we will do at least two things to make pseudocode more compact:

1) Slicing: Instead of looping over some variable and using that to index an array, we can just use slicing a la Python, like, arr[1:n], or arr[:] for all elements of array. We could express the element-wise summation of two arrays by z[:] = x[:] + y[:].

2) Temporary arrays are implied: Instead of writing them out, we might do something like the following.

t[:] <- A[i,:]*x[:]
y(i) <- y(i) + reduce(t)

becomes…

y(i) <- y(i) + reduce(A[i,:]*x[:])

…where we recognize that there is an implicit temp array inside the reduce.

3) We should also recognize that something like t[:] <- A[i,:]*x[:] is easily parallelizable with par-for. Use the work and span for par-for here.

Question 38

Good algorithm vs bad algorithm in terms of DAG height, width, and number of operations

Answer 38

A good algorithm has low “mass”, or fewer operations, and has short and wide. i.e. lots of parallelism, little work, low span.

A bad algorithm has a lot of operations and is tall and skinny. So a lot of work, large span, and little parallelism.

Question 39

Divide and conquer: how important is it here?

Answer 39

It should usually be the first thing you try!