>> In theory you take a DAG and you scheduled it on a PRAM.
But here a question where do DAGs come from?
The answer is from you.
But you need a programming model to generate the DAGs.
Let me show you one that, I think is especially clean and elegant.
Here's the DAG for a divide and conquer algorithm to computer reduction.
You have argued that it's work optimal and it has logarithmic span.
Now, I want to give you an algorithm that produces this DAG.
Let's start with just a sequential algorithm that implements the divide and
conquer scheme.
So here is the pseudo code for such an algorithm.
It takes an array A of length n, and
if there are at least two elements it does divide and conquer.
So recursively calls itself on each half of the array, and returns the sum.
Otherwise the array is just of size one and it returns that element.
Now what you can observe is that the two recursive
calls are independent of one another.
Now since the two recursive function calls are independent.
I'm going to give you a special keyword to mark that fact.
That keyword is called a spawn.
The target of a spawn is always either a function call or a procedure call.
In this case I'm showing a function call.
Now the spawn keyword is a signal to either the compiler or
the runtime system that the target is an independent unit of work.
By inserting the spawn you're effectively saying that the target
may be executed asynchronously from the collar
any time a processor is available.
Now even though these two calls are independent units of work,
notice that they produce intermediate results that then have to be combined.
In other words there's a dependence from a and b and the return statement.
That means in addition to spawns,
we also need a way to indicate these kinds of dependences.
For that, I will give you a second special keyword called sync.
So, one question.
To which spawns does a given sync apply?
So we will use a particular convention which is that the sync waits for
any spawn that has occurred so far within the same stack frame.
If you need a refresher on call stacks and stack frames,
please see the instructor's notes.
Let me make one final remark about spawn and sync.
Now, suppose you leave the sync out.
Even if you leave sync out, there will always be an implicit sync at the return
immediately before going back to the caller.
Let me show you what that means by transforming this code to match
the note.
So instead of return of a+b, we'll generate three statements.
The first will evaluate the operand a+b.
The second will perform the sync.
And then finally will return the value to the caller.
And notice where the sync appears, and
you transform the other return in the same way.
Now, an important point.
Even with this transformation, the program is still wrong.
Can you see why?
Notice that the sync appears after the sum.
Now the two spawned calls are only guaranteed to be complete at the sync.
Therefore the values of a and b might not yet be valid at that point.
Now the fact of Implicit syncs will constrain the kinds of DAGs that this
programming model can produce.
The style of parallelism in such DAGs is sometimes called nested parallelism.
Now once you see how this pseudo code gives rise to a DAG you'll understand
where the term nested parallelism comes from.
Let's go back to the correct code.
Now what I want you to do is try simulating the algorithm to see how
the DAG unfolds.
So in particular let's say we start to execute a reduce on an array of
size four.
The first step is to enter the reduce call.
That creates the first unit of work within the DAG.
Then there's the conditional test.
Then you encounter the spawn.
Here's where things get interesting.
The spawn creates a new branch in the DAG.
Essentially the spawn signals that there's a new independent of work
that's ready to go.
And it creates a new path as well.
Now in the mean time, the current path will continue.
So this is an extremely important point to that the spawn creates
essentially two independent paths.
One path carries the new work and the other path is the path
that continues executing immediately after the spawn.
Now while the main path is happily going about its business,
the newly spawned path is a recursive call.
And therefore it has to generate its own subgraph.
Now you are travelling along the main path and
so you'll encounter the second spawn.
This branching will happen again.
Next, you'll reach the sync.
The sync waits for the previous spawns to complete.
In terms of the DAG, that should create some dependence edges between these
subgraphs and the sync point.
Control then goes to the return statement, and
you'll evaluate a+b and then finally return that value.