Task Blocks

Contents[Show]

Task blocks use the well-known fork-join paradigm for the parallel execution of tasks.

Who has invented it in C++? Both Microsoft with its Parallel Patterns Library (PPL) and Intel with its Threading Building Blocks (TBB) were involved in the proposal N4441. Additionally, Intel used its experience with their Cilk Plus library.

The name fork-join is quite easy to explain.

Fork and join

The simplest approach to the fork-join paradigm is a graphic.

ForkJoin

How does it work?

The creator invokes define_task_block or define_task_block_restore_thread.  This call creates a task block that can create tasks or can wait for their completion. The synchronisation is at the end of the task block. The creation of a new task is the fork phase, the synchronisation of the task block the join phase of the process. Admittedly, that was easy. Let's have a look at a piece of code. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
template <typename Func> 
int traverse(node& n, Func && f){ 
    int left = 0, right = 0; 
    define_task_block(                 
        [&](task_block& tb){ 
            if (n.left) tb.run([&]{ left = traverse(*n.left, f); }); 
            if (n.right) tb.run([&]{ right = traverse(*n.right, f); });
         }
    );                                                         
    return f(n) + left + right; 
} 

 

traverse is a function template that invokes on each node of its tree the function func. The keyword define_task_block defines the task block. The task block tb can start a new task in this block. Exactly that happens at the left and right branch of the tree in line 6 und 7. Line 9 is the end of the task block and hence the synchronisation point.

That was my first overview. Now I will write about the missing details to the definition of a task block, the task block itself, its interface and the scheduler

Task Blocks

You can define a task block by using one of the both functions define_task_block or define_task_block_restore_thread.

define_task_block versus define_task_block_restore_thread

The subtle difference is that define_task_block_restore_thread guarantees that the creator thread of the task block is the same thread that will run after the task block.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
...
define_task_block([&](auto& tb){  
  tb.run([&]{[] func(); });
  define_task_block_restore_thread([&](auto& tb){
    tb.run([&]([]{ func2(); });
    define_task_block([&](auto& tb){
       tb.run([&]{ func3(); }
    });
    ...
    ...
  });
  ...
  ...
});
...
...

 

Task Bocks guarantee that the creator thread of the outermost task block (line 2 - 14) is exactly the same thread that will run the statements after finishing the task block. That means that the thread that executes the line 2 is the same thread that executes the lines 15 and 16. This guarantee will not hold for nested task blocks. Therefore, the creator thread of the task block in line 6 - 8 will not automatically perform the lines 9 and 10. If you need that guarantee, you should use the function define_task_block_restore_thread (line 4). Now it holds that the creator thread performing the line 4 is the same thread performing the lines 12 and 13.

task_block

To make you not crazy, I will distinguish in this section between the task block and task_block. I mean with task block that block that was created by one of the two functions define_task_block or define_task_block_restore_thread. In contrary task_block tb is the object that can start via tb.run new tasks.

A task_block has a very limited interface. You can not explicitly define it. You have to use one of the two functions define_task_block or define_task_block_restore_thread. The task_block tb is in the scope of its task block active and can, therefore, start new tasks (tb.run) or wait (tb.wait) until a task is done.

1
2
3
4
5
define_task_block([&](auto& tb){  
  tb.run([&]{ process(x1, x2) });
  if (x2 == x3) tb.wait();
  process(x3, x4);
});

 

What is the code snipped doing? A new task is started in line 2. This task needs the data x1 and x2 b. In line 4 the data x3 and x4 are used. If x2 == x3 is true, the variable have to be protected from shared access. That is the reason that the task block tb now waits until the task in line 2 is done.

The scheduler

The scheduler takes care which thread is running. That is with task blocks this is no more in the responsibility of the programmer. Therefore, threads are exactly reduced to their minimum usage: an implementation detail. There are two strategies for the tasks that are started by the task block tb.run call. The parent stands for the creator thread and the child for the new task.

Child stealing: The scheduler steals the task and executes it.

Parent stealing: The task block tb itself executed the task. The scheduler steals now the parent.

The proposal N4441 is open for both strategies.

What's next?

At first, I want to have a closer look at concepts. My post "Concepts" gave you a first idea what concepts are about in C++20. In my next post, I will write about the placeholder syntax and the definition of concepts.

 

 

 

title page smalltitle page small Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Get your e-book. Support my blog.

 

 

 

 

 
Tags: C++20

Add comment


My Newest E-Book

Latest comments

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 172

All 277626

Currently are 192 guests and no members online