recursive decomposition aka divide & conquer
use when data structures are trees & graphs
use when geographic or geometric aspects are used
The Basics
walking the tree sequentially
static void SequentialWalk<T>(Tree<T> tree, Action<T> action)
{
if (tree == null) return;
action(tree.Data);
SequentialWalk(tree.Left, action);
SequentialWalk(tree.Right, action);
}
use parallel tasks to walk the tree
static void ParallelWalk<T>(Tree<T> tree, Action<T> action)
{
if (tree == null) return;
var t1 = Task.Factory.StartNew(() => action(tree.Data));
var t2 = Task.Factory.StartNew(() => ParallelWalk(tree.Left, action));
var t3 = Task.Factory.StartNew(() => ParallelWalk(tree.Right, action));
Task.WaitAll(t1, t2, t3);
}
when using dynamic task parallelism nodes are not visited in a fully predictable
order
quick sort example
static void SequentialQuickSort(int[] array, int from, int to)
{
if (to - from <= Threshold)
{
InsertionSort(array, from, to);
}
else
{
int pivot = from + (to - from) / 2;
pivot = Partition(array, from, to, pivot);
SequentialQuickSort(array, from, pivot);
SequentialQuickSort(array, pivot + 1, to);
}
}
parallel implementation
static void ParallelQuickSort(int[] array, int from, int to, int depthRemaining)
{
if (to - from <= Threshold)
{
InsertionSort(array, from, to);
}
else
{
int pivot = from + (to - from) / 2;
pivot = Partition(array, from, to, pivot);
if (depthRemaining > 0)
{
Parallel.Invoke(
() = > ParallelQuickSort(array, from, pivot, depthRemaining - 1),
() = > ParallelQuickSort(array, pivot + 1, to, depthRemaining - 1));
}
else
{
ParallelQuickSort(array, from, pivot, 0);
ParallelQuickSort(array, pivot + 1, to, 0);
}
}
}
depthRemaining arg used to limit number of tasks created
generally not useful to create more tasks than cores
calculate approximate depth using
int approximateDepth = (int) Math.Log(Environment.ProcessorCount, 2) + 4;
formula limits the number of tasks to approximately sixteen times the number of
cores
Variations
Parallel While-Not-Empty
concurrent collection keeps track of work to be done
static void ParallelWhileNotEmpty<T>(IEnumerable<T> initialValues, Action<T, Action<T>> body)
{
var from = new ConcurrentQueue<T>(initialValues);
while (!from.IsEmpty)
{
var to = new ConcurrentQueue<T>();
Action<T> addMethod = to.Enqueue;
Parallel.ForEach(from, v => body(v, addMethod));
from = to;
}
}
walk a binary tree using parallelWhileNotEmpty
static void ParallelWalk4<T>(Tree<T> tree, Action<T> action)
{
if (tree == null) return;
ParallelWhileNotEmpty(new[] { tree }, (item, adder) =>
{
if (item.Left != null) adder(item.Left);
if (item.Right != null) adder(item.Right);
action(item.Data);
});
}
in both examples additional work can be added dynamically
Task Chaining with Parent/Child Tasks
AttachedToParent is task creation option
links subtask to the task that created the subtask
subtask is called child task while task is called parent task
use AttachedToParent option in two situations
want to link status of parent task to status of its child tasks
use VS debugger to see parent/child relationships
order of execution is unchanged by the option
static void ParallelWalk2<T>(Tree<T> tree, Action<T> action)
{
if (tree == null)
return;
var t1 = Task.Factory.StartNew(() => action(tree.Data),
TaskCreationOptions.AttachedToParent);
var t2 = Task.Factory.StartNew(() => ParallelWalk2(tree.Left, action),
TaskCreationOptions.AttachedToParent);
var t3 = Task.Factory.StartNew(() => ParallelWalk2(tree.Right, action),
TaskCreationOptions.AttachedToParent);
Task.WaitAll(t1, t2, t3);
}
if a parent task has a running child the parent's Status property will be WaitingForChildrenToComplete
exceptions from attached children are observed in the parent task
Design Notes
default task scheduler's thread injection heuristics aren't appropriate for every cases of dynamic task parallelism
profiling long-running, processor-intensive tasks may show processor oversubscription