Recursion and Concurrency

MSDN Blog Postings » Recursion and Concurrency

MSDN Blog Postings » Recursion and Concurrency — Fri, 01 Feb 2008 01:02:21 GMT

PingBack from http://msdnrss.thecoderblogs.com/2008/01/31/recursion-and-concurrency-2/

MSDN Blog Postings » Recursion and Concurrency

MSDN Blog Postings » Recursion and Concurrency — Fri, 01 Feb 2008 01:02:30 GMT

PingBack from http://msdnrss.thecoderblogs.com/2008/01/31/recursion-and-concurrency/

re: Recursion and Concurrency

Wei Lu — Fri, 01 Feb 2008 07:28:39 GMT

Nice one, Actually I did some similar work (http://portal.acm.org/citation.cfm?id=1272462) for the parallel XML processing in C#, which is mainly about the parallel DOM tree traversal. The thread is keeping traversing the tree by manipulating a stack just like the sequential algorithm does, but other threads, when out of work, can steal the work from the bottom of the stack. I think your solution based on the Task has the same effect.

Also controlling the depth of the parallel traversal is exactly right, my experiments show that it is key to the performance win of the parallel xml processing.

re: Recursion and Concurrency

toub — Fri, 01 Feb 2008 10:22:47 GMT

Cool, thanks for the link and information.

re: Recursion and Concurrency

Chris Mullins — Sat, 02 Feb 2008 00:57:47 GMT

Great article! I love the work you guys are doing with this, and am looking forward to a solid concurrency framework!

I have a question though: In one section, you mention that creating and waiting on Wait Handles requires a (sometimes) unacceptable number of kernel transistions.

... how does Task.WaitAll (that you reference later in the document) avoid this? Are you using a user-mode wait object in there, and each task enlists in that, or does this mechanism suffer the same issues with Wait handle creation and use?

re: Recursion and Concurrency

toub — Sat, 02 Feb 2008 03:23:53 GMT

Thanks, Chris. Task.WaitAll can, in effect, just wait on each Task in sequence. In many situations, waiting on a Task that hasn't started yet will actually cause the Task to be executed inline, rather than blocking waiting for it to complete execution on another thread. In addition, even if we do need to do a true wait, we may spin a bit in user-mode first.

Récursif & parallèle...

Pierrick's Blog — Mon, 04 Feb 2008 18:39:46 GMT

un excellent article de l' équipe PFX (Parallel Framework), sur comment parallèliser un algorithme récursif

re: Recursion and Concurrency

Yury Serdyuk — Sun, 17 Feb 2008 13:33:07 GMT

Synchronization mechanism based on counters and events is very complicated and hard especially for non-qualified programmers.

Some proof of that is that the author overlooked some simplification in the code below:

public static void Process<T>(Tree<T> tree, Action<T> action)

{

if (tree == null) return;

// Use an event to wait for all of the nodes to complete

using (var mre = new ManualResetEvent(false))

{

//int count = 1;

int count = 0; // NOTE THIS !!!

// Recursive delegate to walk the tree

Action<Tree<T>> processNode = null;

processNode = node =>

{

if (node == null) return;

// Asynchronously run the action on the current node

Interlocked.Increment(ref count);

ThreadPool.QueueUserWorkItem(delegate

{

action(node.Data);

if (Interlocked.Decrement(ref count) == 0)

mre.Set();

});

// Process the children

processNode(node.Left);

processNode(node.Right);

};

// Start off with the root node

processNode(tree);

// Signal that no more work items will be created

//if (Interlocked.Decrement(ref count) == 0)

//mre.Set(); WE CAN DROP GIVEN STATEMENT !!!

// Wait for all of the work to complete

mre.WaitOne();

}

For synchronization purposes more transparent and easy are so called "chords" costructions

(see languages as Polyphonic C#, COmega, MC#(www.mcsharp.net)).

re: Recursion and Concurrency

toub — Wed, 20 Feb 2008 04:02:12 GMT

Yury, thanks, but that is not a valid simplification. Let's say the count did begin at 0, as you suggest. We then kick off a work item to process the first node; before doing so, we increment the count to 1, and after doing so, we decrement the count and check whether it's now 0, setting the ManualResetEvent if it is. Now, let's say the tree has 500 nodes in it, but we end up finishing the first work item before we even get to the pre-increment for the second work item. The completion of the first item sets the event, and now Process will not wait for all of the nodes to complete before exiting. That's why I initialize the count to 1 and then decrement it after all of the work items have been queued, so that I can be sure Process will wait for all items to complete before returning.

As an aside, I appreciate your passion around your MC# language, but please stop replying to our forum threads and blog posts plugging it. We certainly welcome your contributions on both the forums and blog comments, as it seems like you have a lot to contribute, but please keep your posts relevant to Parallel Extensions; for example, if there are constructs you think would be useful for us to add, please do let us know. Thanks!

re: Recursion and Concurrency

Yury Serdyuk — Thu, 21 Feb 2008 15:56:28 GMT

>The completion of the first item sets the event, and >now Process will not wait for all of the nodes to >complete before exiting.

No, it's impossible because the initial call

processNode(tree);

can't be completed ( and so we can't move to check

mre.WaitOne(); ) until

Interlocked.Increment(ref count);

has been performed for all nodes of the tree.

re: Recursion and Concurrency

toub — Fri, 22 Feb 2008 04:52:13 GMT

No, it's not impossible. Here's the sequence of events:

1) We call Process() on the root node. The count is 0.

2) We call Interlocked.Increment on count, increasing it to 1, and we queue a work item.

3) Before the main thread that's iterating over the nodes moves on to queue a work item for the next node, the work item for the first node executes and does an Interlocked.Decrement on count, setting count to 0. It sees that count is 0, and sets the event.

4) The main thread continues to queue work items for the rest of the nodes.

5) When it's done queueing work items, it waits on the event. But at this point, even though all of the work items may not have completed, the event has already been set (by the completion of the first work item).

re: Recursion and Concurrency

Yury Serdyuk — Fri, 22 Feb 2008 14:32:20 GMT

Yes, you are right.

Nevertheless, this subtle issue shows

that a programmer needs more simple and transparent

synchronization constucts/tools.

re: Recursion and Concurrency

Yury Serdyuk — Sun, 24 Feb 2008 14:35:06 GMT

Please, one more question.

Does the Parallel.Do uses ThreadPool to run the provided operations?

In any case, how the deadlock possibility is avoided in that case?

To my view, the method

public static void Process<T>(Tree<T> tree, Action<T> action)

{

if (tree == null) return;

Parallel.Do(

() => action(tree.Data),

() => Process(tree.Left, action),

() => Process(tree.Right, action));

}

is an abbreviation of (prone to deadlocks)

public static void Process<T>(Tree<T> tree, Action<T> action)

{

if (tree == null) return;

// Use an event to wait for the children

using (var mre = new ManualResetEvent(false))

{

int count = 2;

// Process the left child asynchronously

ThreadPool.QueueUserWorkItem(delegate

{

Process(tree.Left, action);

if (Interlocked.Decrement(ref count) == 0)

mre.Set();

});

// Process the right child asynchronously

ThreadPool.QueueUserWorkItem(delegate

{

Process(tree.Right, action);

if (Interlocked.Decrement(ref count) == 0)

mre.Set();

});

// Process the current node synchronously

action(tree.Data);

// Wait for the children

mre.WaitOne();

}

Thanks.

re: Recursion and Concurrency

toub — Sun, 24 Feb 2008 22:28:40 GMT

Good question. No, Parallel.Do does not use the ThreadPool. Under the covers, it uses a work-stealing pool implementation (which will be further revamped significantly for future preview releases; coding there is already well underway). When you wait on a task, if that task has already started running, yes, the current thread will block waiting on the task on an event similar to how I've done in my ThreadPool recursive walk. But, if the task has not already started executing (which will be the case most of the time), in most cases the task will actually be executed inline; in other words, rather than waiting for the task to complete elsewhere, the thread that would be waiting for another thread to start and finish the task instead simply executes it. As such, you don't end up in the same deadlock situation as with the ThreadPool, since pool threads aren't being blocked for every node.

re: Recursion and Concurrency

Yury Serdyuk — Tue, 26 Feb 2008 14:09:38 GMT

Many thanks, but, if you please, another question

concerning the replicable tasks in TPL.

In the paper

http://msdn.microsoft.com/msdnmag/issues/07/10/Futures/default.aspx?loc=en

there is the following example of using of replicable task (in fact, it's a Parallel.For implementation):

static void For( int from, int to, Action<int> body )

{

int index = from;

ReplicableTask rtask = new ReplicableTask( delegate {

int i;

while ((i = Interlocked.Increment(ref index)-1) < to) {

body(i);

}

});

rtask.Wait();

}

Lets look on the body of given method more abstractly as

int index = from;

ReplicableTask rtask = new ReplicableTask( delegate {

int i;

F ( i, index ); // some function

});

or even as

ReplicableTask rtask = new ReplicableTask( delegate {

});

The quiestion is -

how many (ordinary) Tasks ( i.e., action delegates running in other threads) will be created to perform

given Replicable task?

In other words, what's a criterion which bounds a Task generation?

Thanks.

re: Recursion and Concurrency

toub — Wed, 27 Feb 2008 19:31:25 GMT

We're currently reworking the implementation of replicating tasks to make them simpler and more efficient. However, the basic idea is that we'll create as few as we can while still ensuring that all of the virtual processors for the relevant TaskManager are able to have a replica if they need one to remain busy.

re: Recursion and Concurrency

Wei Lu — Tue, 20 Jan 2009 20:36:30 GMT

Stephen, If we use PLINQ (i.e., GetNodes(tree).AsParallel().ForAll(action);) for the parallel tree-wall, how does PLINQ internally work? will it work as your parallel recursive algorithm shown above, or it just flattens the tree in to a sequence of nodes for the linear partitioning to run action delegate? Thanks

re: Recursion and Concurrency

toub — Wed, 21 Jan 2009 05:03:14 GMT

In effect, that code will flatten the tree, passing to AsParallel the IEnumerable<Node> containing all of the nodes from the tree to be processed. We are planning to support the ability to provide your own custom partitioning scheme, such that you could more efficiently traverse a tree-like data structure if you chose to, but that functionality doesn't show up in the CTPs we've released thus far.

re: Recursion and Concurrency

Wei Lu — Wed, 21 Jan 2009 06:54:21 GMT

Thanks for the answer. Actually your recursive code has shown a very nature/dynamic partitions on the tree structure if we view the TPL and PLINQ in an integrated way. That is when one thread is traversing the tree, the rightmost sub-tree will be at the bottom of the stack. Since in TPL the thief always steal the task from the bottom (correct me if I am wrong), the thief thread will get the rightmost sub-tree while the owner thread is working on the left-most one.