È molto semplice.
Quando si reciterebbe verso il basso il figlio sinistro quindi il bambino giusto, si avvierà invece un'attività che si ripete verso il basso a sinistra e proseguirà verso il basso a destra. Quando hai finito con la destra, potresti dover aspettare a sinistra, ma in un albero bilanciato che non sarà lungo
Quando sei al livello di profondità N nella struttura, hai il potenziale per 2^N di core funzionanti
Quel diagramma specifico è solo la generazione di attività a profondità specifiche, probabilmente perché non sono attività di accodamento. Ciò sta utilizzando la conoscenza della struttura dell'albero per non sovraccaricare lo schedulatore
Se hai una coda di attività e un pool di thread, l'implementazione può sfruttare quelli per non doversi preoccupare della quantità di attività generate.
Di 'che hai
class Node
{
int data; // or w/e
Node * left;
Node * right;
template <typname Action>
void SerialTraverse(Action action)
{
action(data); // Pre-order traversal
if (left) left->SerialTraverse(action);
// Traverse the left
if (right) right->SerialTraverse(action);
// Traverse the right
}
}
namespace library
{
template<typename Task, typename Class, typename Arg>
std::future<void> enqueue_task(Task task, Class * obj, Arg arg);
// on some other thread, call "obj->task(arg);"
// returns a handle upon which we can wait
}
Quindi puoi cambiare SerialTraverse in
template <typname Action>
void ParallelTraverse(Action action)
{
action(data);
std::future<void> fut;
if (left) fut = library::enqueue_task(ParallelTraverse, left, action);
// start traversing left on another thread
if (right) right->ParallelTraverse(action);
// traverse right on this thread, in parallel to traversing left
if (fut.valid()) fut.wait();
// wait for the left traversal to end
}
