So what are the kind of problems you've looked at recently as you were designing this
where dynamic parallelism really makes a difference either in terms of usability or performance?
>> In terms of usability, obviously, it's simpler to program when you
don't have to keep going backwards and forwards to the CPU.
So any kind of problem which dynamically discovers the work as it goes--iteratively works it's way through something.
Imagine you're constructing a tree.
You're partitioning something into an Octree, which is a common 3D spatial problem.
You don't necessarily know how many objects are going into which part of your tree
until you reach that point in your tree.
So typically the approach would be to do this level by level by level
which is not the most balanced way of doing things necessarily.
So as you discover the type of work that you need to do,
the ability to simply launch that work is much, much simpler.
We were very motivated by irregular parallelism, if you like;
problems which did not have nice, well-balanced things.
A similar sort of category or problem to that is task parallelism
where I might be wanting not just to do one thing that fills my whole GPU, which is often difficult.
Now the GPUs these days are a teraflop of performance.
It might be much easier to have half a dozen or a dozen things running on my GPU at a time,
and so if each of these can autonomously make forward progress,
it's much easier to manage them if they're just managing themselves
instead of having my CPU now juggle 12 different different things instead of just 1.
And finally there's the there's the new type of algorithm that you can approach.
You can approach recursive types of algorithm--
things where the category is generally the divide and conquer algorithm,
where you take all of the work that you need to do,
and you conquer it by subdividing and subdividing and subdividing repeatedly,
and a typical example would be quicksort, for example--
a well-known problem where you take your data that you want to sort
and recursively you progress through the data until you end up with a final sorted data set.
>> So 1 of the demos you guys showed when you launched this
was N body simulation interstellar,
a bunch of stars moving around, being attracted to each other with gravity.
And so, with dynamic parallelism, you were able to write that in a way that you hadn't written it before.
So how did that come about--like, what was the cool thing you could do with it?
>> I mentioned octree spatial partitioning just now,
and that is a key component of an N body simulation.
So the way that you approach an N body simulation with a very large number of bodies
is instead of doing an all to all comparison
where you just calculate the gravity between all the bodies--
so for N bodies that's an N squared problem.
You can cut down the complexity of the problem
to an N log N or an order of an N problem
by partitioning things into space, doing a local interaction of gravity between your close neighbors,
and doing an approximation to a center of mass at a more distant neighbor.
To do this, you build an octree, partitioning your bodies up into small octans, little cubes.
Everyone inside your cube, you do the N squared problem,
and for all of the other cubes you then only have an order of an N expansion for.
So what we did with dynamic parallelism in this N4 body problem
was we optimize the tree build which is about half of the time in the whole simulation.
We optimize the tree build by using this recursive property
by using this irregular parallelism ability
where the tree might--in the case of a galaxy of stars, for example, might be very, very dense in some regions
and very, very sparse in others to much more efficiently build the tree.
So instead of building the tree level by level by level
so that you're wasting work building the tree for areas of where the bodies are sparse,
you focus the compute performance on the area where you need it.
>> Could you have done this without dynamic parallelism?
>> Yes, I guess you could,
but the overhead of moving backwards and forwards between the CPU and GPU
would probably have negated the performance gain that we got.