ForkJoin

Task Blocks

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

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

The name fork-join is relatively easy to explain.

Fork and join

The most straightforward approach to the fork-join paradigm is 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 wait for completion. The synchronization is at the end of the task block. Creating a new task is the fork phase; the synchronization of the task blocks 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 branches of the tree in lines 6 and 7. Line 9 is the end of the task block and, hence, the synchronization point.

 

Rainer D 6 P2 500x500Modernes C++ Mentoring

Be part of my mentoring programs:

  • "Fundamentals for C++ Professionals" (open)
  • "Design Patterns and Architectural Patterns with C++" (open)
  • "C++20: Get the Details" (open)
  • "Concurrency with Modern C++" (starts March 2024)
  • Do you want to stay informed: Subscribe.

     

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

    Task Blocks

    You can define a task block by using one of 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 (lines 2 – 14) is the same thread that will run the statements after finishing the task block. That means that the thread that executes line 2 is the same thread that executes lines 15 and 16. This guarantee will not hold for nested task blocks. Therefore, the creator thread of the task block in lines 6 – 8 will not automatically perform lines 9 and 10. Use the function define_task_block_restore_thread (line 4) if you need that guarantee. Now it holds that the creator thread performing line 4 is the same thread performing lines 12 and 13.

    task_block

    To make you not crazy, I will distinguish between the task block and task_block in this section. I mean with a task block created by one of the two functions define_task_block or define_task_block_restore_thread. In contrast, 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 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 snippet doing? A new task is started in line 2. This task needs the data x1 and x2. In line 4, the data x3 and x4 are used. If x2 == x3 is true, the variable has to be protected from shared access. This is why the task block tb now waits until the task in line 2 is done.

    The scheduler

    The scheduler takes care of which thread is running. This is no more in the responsibility of the programmer. Therefore, threads are exactly reduced to their minimum usage: an implementation detail. Two strategies for the tasks 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 now steals the parent.

    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 of the concepts in C++20. In my next post, I will write about placeholder syntax and the definition of concepts.

     

     

     

    Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Stephen Kelley, Kyle Dean, Tusar Palauri, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery,and Matt Godbolt.

    Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.

    My special thanks to Embarcadero
    My special thanks to PVS-Studio
    My special thanks to Tipi.build 
    My special thanks to Take Up Code
    My special thanks to SHAVEDYAKS

    Seminars

    I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

    Standard Seminars (English/German)

    Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

    • C++ – The Core Language
    • C++ – The Standard Library
    • C++ – Compact
    • C++11 and C++14
    • Concurrency with Modern C++
    • Design Pattern and Architectural Pattern with C++
    • Embedded Programming with Modern C++
    • Generic Programming (Templates) with C++
    • Clean Code with Modern C++
    • C++20

    Online Seminars (German)

    Contact Me

    Modernes C++ Mentoring,

     

     

    0 replies

    Leave a Reply

    Want to join the discussion?
    Feel free to contribute!

    Leave a Reply

    Your email address will not be published. Required fields are marked *