Task Blocks setzen das beliebte Fork-Join Paradigma für die parallele Ausführung von Aufgaben um.

Wer hat es erfunden? Sowohl Microsoft mit ihrer Parallel Patterns Library (PPL) als auch Intels Threading Building Blocks (TBB) waren federführend bei dem Proposal N4441. Intel hat zusätzlich seine Erfahrung mit Cilk Plus eingebracht.

Der Name Fork-Join lässt sich einfach erklären.

Fork und Join

Die einfachste Annäherung an das Fork-Join Paradigma gibt eine Graphik.

Wie funktioniert das ganze?

Der Erzeuger ruft define_task_block oder define_task_block_restore_thread auf. Dadurch steht ein Task Block zur Verfügung, der neue Tasks erzeugen oder auf diese warten kann. Am Ende des Task Blocks findet die Synchronisation statt. Das Erzeugen der neuen Task ist die Fork Phase, die Synchronisation der Taks die Join Phase des Fork-Join Prozesses. Zugegeben, das war einfach. Wie schaut das ganze im Code aus?

 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 ist ein Funktions-Template, das auf jedem Knoten des Baumes node mit zwei Kindern die Funktion Func aufruft. Das Schlüsselwort define_task_block definiert den Task Block. In diesem kann der Task Block tb neue Tasks starten. Genau das findet für den linken und rechten Zweig des Baumes in Zeile 6 und 7 statt. Zeile 9 ist das Ende des Task Blocks und damit der Synchronisationspunkt.

Das war schon der grobe Überblick. Jetzt folgen die fehlenden Details zu der Definition des Task Blocks, dem Task Block und seinem Interface und dem Scheduler.

Task Blocks

Der Task Block wird durch die zwei Funktionen define_task_block oder define_task_block_restore_thread definiert.

define_task_block versus define_task_block_restore_thread

Der feine Unterschied ist, dass define_task_block_restore_thread zusichert, dass der Erzeuger-Thread des Task Blocks nach dem Ende des Task Blocks auch wieder der Thread ist, der die weiteren Anweisungen ausführt.

 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 sichern zu, das der Erzeuger-Thread des äußersten Task Blocks (Zeile 2 - 14) nach dem Beenden des Task Blocks auch wieder zu Zuge kommt. Das heißt, der Thread der die Anweisung in Zeile 2 ausgeführt, führt auch die Anweisungen in Zeile 15  und 16 wieder aus. Diese Zusicherung gilt aber nicht für alle verschachtelten Task Blöcke. Daher führt der Erzeuger-Thread des Task Block in Zeile 6 - 8 nicht automatisch die Zeilen 9 und 10 aus. Ist diese Anforderungen notwendig, muss die Funktion define_task_block_restore_thread (Zeile 4) angewandt werden. Nun gilt, der Thread der die Anweisung in Zeile 4 ausgeführt, führt auch die Anweisungen in Zeile 12 und 13 aus.

task_block

Um nicht zur Verwirrung beizutragen, werde ich in diesem Abschnitt zwischen Task Block und task_block unterscheiden. Mit Task Block bezeichne ich den Bereich, der durch die zwei Funktionen define_task_block oder define_task_block_restore_thread erzeugt wurde. Hingegen steht task_block tb für das Objekt, das mittel tb.run neue Aufgaben starten kann.

Ein task_block besitzt ein sehr eingeschränktes Interface. Er kann nicht explizit erzeugt werden. Dazu sind die zwei bekannten Funktionen define_task_block oder define_task_block_restore_thread notwendig. Der task_block tb ist im Bereich seines Task Block sofort aktiv und kann daher eine neue Aufgabe starten tb.run oder warten tb.wait, bis seine Aufgabe fertig ist. 

1
2
3
4
5

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

Wie ist der Code zu verstehen? In Zeile (2) wird wird eine neue Aufgabe gestartet, die die Daten x1 und x2 benötigt. Hingegen werden in Zeile 4 die Daten von x3 und x4 prozessiert. Im Falle, dass x2 == x3 ist, gilt es diese vor dem gemeinsamen Zugriff zu schützen. Daher wartet in diesem Fall der Task Block tb, bis seine Aufgabe in Zeile 2 fertig ist.

Der Scheduler

Der Scheduler sorgt dafür, welcher Thread zum Zuge kommt. Genau das liegt bei Task Blocks nicht mehr in der Verantwortung des Programmierers. Damit sind Threads genau auf die Rolle reduziert, die sie einnehmen sollten: Ein Implementierungsdetail.

Für das Scheduling gibt es zwei Strategien für die durch den Task Block tb mittels tb.run gestartete Aufgaben. Dabei bezeichnet Parent den Erzeuger-Thread und Child die neue Aufgabe.

Child stealing: Der Scheduler klaut die Aufgabe und führt sie aus.

Parent stealing: Der Task Block tb führt seine Aufgabe selber aus. Der Scheduler schnappt sich in diesem Fall aber den Parent.

Das Proposal N4441 ermöglicht beide Strategien.

Wie geht's weiter?

Als erstes will ich nochmals genauer auf Concept eingehen. Nach internationaler Kritik nenne ich sie jetzt bewusst Concepts und nicht Concepts Lite. Mein Artikel "Concepts" hat bereits eine erste Idee geliefert, warum es in Concepts in C++20 geht. In meinen nächsten Artikeln gehe ich auf den Stellvertreter (placeholder) Syntax ein und schreibe über die Definition von Concepts.

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.