Is it a bad idea to create a large amount of tasks for a few available cores only?

Question

I'm new to parallel programming with TPL and just finished listening a TPL course. I have just written a small piece of demo software to test my understanding of it.

Let me explain the context of my prallelised code before asking my general questions: (if bored, skip directly to the questions ;-)

Context:

I first wrote a sequential recursive tree traversing recursive code (for any two-players state-known game) and tried then to parrallelise it, exposing as much parallelism as possible, by creating concurrent subtasks on each traversed (and evaluated) node. (One subtask is launched for each child node). The subtrees issuing from each child-node of the currently evaluated head node beeing themselves evaluated by the same recursive method called by one of the launched concurrent subtasks.

In the game-tree, the nodes represent game positions. The root node beeing the current game position and its n child nodes (on 2nd tree level) the game positions that can be reached by applying the n legal moves for the player A in the root position. The 3rd level nodes represent the reachable positions by applying the legal moves played by player B on each 2nd level positions/nodes, and so on until a given max search depth is reached..

The tree is traversed in a depth-first traversal order until a given max search depth where the "leaf" positions will be evaluated by an heuristic evaluation function that returns an integer value representing the advantage of player A vs player B on this game position. The greater this value is, the better the position is supposed to be for the player A.

The best value of all child nodes is reported to their common parent node, (Of course if the parent node represents a position played by player A, the best child node is the child-node with the highest value, and if it is played by player B, the best child node is the one with the lowest value).

The best child values are finally reported to the root node with the index of the 2nd level child node that reported its best value to the root node. Of course, this index represents the "best" move for player A. That means the move that guarantee to the player A that the reported value (or a better one) can be reached at the explored depth ("leaf" position) whatever the moves played by the player B.

Ok, this is the well known minimax algorithm for two-players state-games.

You maybe also know the classical optimisation of this sequential algorithm, called alpha-beta, allowing to prune some branches/sub-branches of the game tree when we know they are not leading to interesting leaf positions.

So I tried to parallelise this recursive tree traversal reporting the leaf values to the root node and allowing complete full tree traversal cancellation (if the user cancels the search) but also allowing partial sub-tree tasks cancellation to implement the alpha-beta pruning that has to abort the tasks performing the evaluation of some child-node sub-trees without interruping the tasks working on other subtrees.

The work is done succesfully, the parallelised search is faster than the sequential one and dispatches the work on all the available cores running almost always à 100% (according to the task manager). I don't want to bore you with my source code. I just want to precise that I also applied the .Net 4.5 async await pattern to my recursive parallelised method, and implemented the "wait-all one by one" pattern (actually await Task.WhenAll()) to create the sub-tasks exploring the sub-trees issued from each child node. (Note: To allow subtree traversal cancelling, I had to pass a list of cancellation tokens to the recursive async subtree exploration method, each recursing exploration level adding a new CancellationToken to the list).

Now that you understand the context, here are my questions:

1. Launching a search will rapidly create millions of tasks evaluating millions of subtrees issued from each tree node, but only a few processor cores are actually available to execute these tasks with a few threads (one per core ?). So is that a good idea not to take this into account and to create tasks for each child node/subtree having to be evaluated/traversed ? Is there no overhead induced by creating more tasks than necessary to expose the maximum of parallelism ? Wouldn't it be better to limit the number of launched tasks (for exemple by lauching tasks for the highest level nodes only and using a purely sequential traversal method for the lowest level ones ?) Or can we not care about this by creating million of tasks, even if we know that some of them (these launched on the deepest tree nodes) perform a very small work ?

2. I didn't prevent the "passing loop index variable to the launched task by closure" issue using a lambda expression argument (like proposed in the course) but by copying the loop index variable in a local copy variable before launching the task and referring this copy by closure, instead of the index loop variable from the lambda expression. What do you think of this workaround ? Is that as safe as the lambda expression argument passing ?

3. The alpha-beta pruning optimisation of the minimax algorithm is based on the sequential traversal of each subtree. Parallel traversing makes the alpha-beta pruning less efficient since if all the parallel subtree traversals of the child nodes take aproximately the same time to return, none subtree traversal task will be aborted, and if they will, they will be aborted as they all were already almost completed... This will highly limit the gain given by the alpha-beta optimisation. Do you know smart strategies to adress this issue when parallelising the game-tree traversal with alpha-beta optimisation ?

Answer 1

The question about "how many tasks" is really driven by two things:

• conceptual program organization
• task overhead

Assigning one task per node in the tree is conceptually clean and easy. That's the upside.

The downside is that the reasoning for using tasks is utilization of parallelism effectively, not program organization. You end up with the best parallelization when you have lots of work for your processors to do, and the overhead of managing that work is small compared to the work.

The reason you chose tasks at the node level is that is it easy to see there are (arguably) lots of nodes. [In your comment, you remarked that there were fewer units of work than you expected for a deep search tree!]. The other reason is that you don't know exactly how much work a node takes, so having lots of tasks around means a processor can take one, work on it till finished, and then go get another. If they all have some average time, the processors will execute and find other work, without wasting a lot of time waiting for other work to appear.

The key problem is overhead. To "have" a task, there's a bunch of overhead: something must create it, fill it with work, put it into a work queue where some other processor can get it; that other processor must pull it out of the queue, pick up its content, [not overhead: execute it ], and finally un-create it. Each of these bits of overhead takes some computer instructions, some memory accesses (if you are lucky they are cache hits) and usually some expensive synchronization between processors (you can't have all the CPUs putting new tasks in the available work queue at the same moment).

I don't know what the work overhead is for C# TPL. You can probably measure it by writing simple loop that simulates a task body and measure that; and then measure how long that loop takes when dumped into a task. I do know that you want to minimize the overhead (I designed a parallel programming language PARLANSE around that idea) and maximize the work you put into a task.

In your case, I'd be worried that work in a node ("generate next move and trivially evaluate it") wasn't really very much, and that you would actually lose performance by going parallel. Have you measured how fast you same program runs if you take out the parallelism? (PARLANSE is fast enough so that one can code a parallel 8 puzzle solver, yet have the generate-move-evaluate still be considerably more work than the overhead).

The standard trick when you don't have enough work in task to overwhelm overhead, is to put more work into the task.

In your case, you might decide to let a task represent a 2 ply or 3 ply search; that should create plenty of work per task. And for an 8 ply game search, you'll still have plenty of generated tasks to keep the processors busy. I show a similar trick (coarse-grain-threshold) to make parallel Fibonacci work, which is about as awful a work/overhead ratio scheme that one can invent.

It is well known in the chess world that a sophisticated board evaluation acts as if one had done a 2 or 3 ply search at that board position. So your other choice is implement an expensive board evaluation routine; that will make the overhead small in the leaves.

Alpha-beta may be saving you ("only 1000 tasks") from running out of VM due to "big stacks" and many tasks. The good news about generating lots of work is you have lots to give the CPUs. The bad news is that they can take up a lot of space in the VM while they are sitting around not being executed; MS's big-stack model aggravates this. Even if it doesn't run you out of VM, it may cause your program to touch vast amounts of memory, thus negating the value of the processor's cache. I'd worry about this, but don't have good advice for C#; I built PARLANSE to avoid these problems; it automatically throttles task generation when it has "enough" work. MS has some smart cookies, though.