{"id":5208,"date":"2017-03-03T21:51:01","date_gmt":"2017-03-03T21:51:01","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/task-blocks\/"},"modified":"2023-06-26T12:20:24","modified_gmt":"2023-06-26T12:20:24","slug":"task-blocks","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/task-blocks\/","title":{"rendered":"Task Blocks"},"content":{"rendered":"

Task blocks use the well-known fork-join paradigm for the parallel execution of tasks.<\/p>\n

<\/p>\n

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

The name fork-join is relatively easy to explain.<\/p>\n

Fork and join<\/h2>\n

The most straightforward approach to the fork-join paradigm is graphic.<\/p>\n

\"ForkJoin\"<\/p>\n

How does it work?<\/p>\n

The creator invokes define_task_block<\/span> or define_task_block_restore_thread<\/span>.  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. <\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11<\/pre>\n<\/td>\n
\n
template<\/span> <typename<\/span> Func> \r\nint<\/span> traverse(node& n, Func && f){ \r\n    int<\/span> left = 0, right = 0; \r\n    define_task_block(                 \r\n        [&](task_block& tb){ \r\n            if<\/span> (n.left) tb.run([&]{ left = traverse(*n.left, f); }); \r\n            if<\/span> (n.right) tb.run([&]{ right = traverse(*n.right, f); });\r\n         }\r\n    );                                                         \r\n    return<\/span> f(n) + left + right; \r\n} <\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
traverse<\/span> is a function template that invokes on each node of its tree the function func<\/span>. The keyword define_task_block<\/span> defines the task block. The task block tb <\/span>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.<\/p>\n
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.<\/p>\n<\/p>\n
Task Blocks<\/h2>\n
You can define a task block by using one of both functions define_task_block<\/span> or define_task_block_restore_thread<\/span>.<\/p>\n
define_task_block versus define_task_block_restore_thread<\/h3>\n
The subtle difference is that define_task_block_restore_thread<\/span> guarantees that the creator thread of the task block is the same thread that will run after the task block.<\/p>\n
\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16<\/pre>\n<\/td>\n
\n
...\r\ndefine_task_block([&](auto<\/span>& tb){  \r\n  tb.run([&]{[] func(); });\r\n  define_task_block_restore_thread([&](auto<\/span>& tb){\r\n    tb.run([&]([]{ func2(); });\r\n    define_task_block([&](auto<\/span>& tb){\r\n       tb.run([&]{ func3(); }\r\n    });\r\n    ...\r\n    ...\r\n  });\r\n  ...\r\n  ...\r\n});\r\n...\r\n...\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
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.<\/p>\n
task_block<\/h3>\n
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<\/span> or define_task_block_restore_thread<\/span>. In contrast, task_block tb <\/span>is the object that can start via tb.run<\/span> new tasks.<\/em><\/p>\n
A<\/em> task_block <\/span>has a very limited interface. <\/span><\/span>You can not explicitly define it. You have to use one of the two functions define_task_block<\/span> or define_task_block_restore_thread<\/span>. <\/span>The task_block tb<\/span> is in the scope of its task block active and can start new tasks (tb.run)<\/span> or wait (tb.wait)<\/span> until a task is done.<\/p>\n
\n\n\n\n
\n
1\r\n2\r\n3\r\n4\r\n5<\/pre>\n<\/td>\n
\n
define_task_block([&](auto<\/span>& tb){  \r\n  tb.run([&]{ process(x1, x2) });\r\n  if<\/span> (x2 == x3) tb.wait();\r\n  process(x3, x4);\r\n});\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
What is the code snippet doing? A new task is started in line 2. This task needs the data x1<\/span> and x2<\/span>. In line 4, the data x3<\/span> and x4<\/span> are used. If x2 == x3<\/span> is true, the variable has to be protected from shared access. This is why the task block tb<\/span> now waits until the task in line 2 is done.<\/p>\n
The scheduler<\/h2>\n
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 <\/span>call. The parent stands for the creator thread, and the child for the new task.<\/p>\n
Child stealing<\/strong>: The scheduler steals the task and executes it.<\/p>\n
Parent stealing<\/strong>: The task block tb<\/span> itself executed the task. The scheduler now steals the parent.<\/p>\n
Proposal N4441<\/a> is open for both strategies.<\/p>\n
What’s next?<\/h2>\n
At first, I want to have a closer look at concepts. My post “Concepts<\/a>” gave you a first idea of the concepts in C++20. In my next post<\/a>, I will write about placeholder syntax and the definition of concepts.<\/p>\n
 <\/p>\n
 <\/p>\n
 <\/pre>\n","protected":false},"excerpt":{"rendered":"
Task blocks use the well-known fork-join paradigm for the parallel execution of tasks.<\/p>\n","protected":false},"author":21,"featured_media":5190,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[367],"tags":[482],"class_list":["post-5208","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-multithreading-c-17-and-c-20","tag-outdated"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5208","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5208"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5208\/revisions"}],"predecessor-version":[{"id":6880,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5208\/revisions\/6880"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5190"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5208"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}