down ward pass of in binary tree

[Walter_D_]

Hi, I'm new to tbb and like to implement the downward pass of a tree structure. Let's assume we have a binary tree of nodes

     struct node { node*parent,*child; int n_all; };   std::vector<node> nodes;

such that node has children child[0] and child[1] if child!=0 and descendants child[0..n_all), all of which have node as ancestor. In a downward pass, a user-provided function f(node*) has to be called such that f(n) is called after f(n->parent). Nodes are ordered such that children come after their parents. Thus, a serial code just loops all nodes in a forward manner as in  "for(auto n:nodes) f(n);" In recursive parallelism, one would call f(n) followed by calls to f(n->child) and f(n->child+1), which can be executed in parallel. Eventually, splitting can be avoided by looping all descendants of a node in a forward manner.

How best to implement this using tbb?

[Walter_D_]

I should add that I have seen the example/task/tree_sum, but would like to have a more automated way to decide on when to switch over to serial execution, ideally similarly to auto_partitioner for parallel range loops.

[RafSchietekat]

You can apply the Range concept (requirements listed in the Reference Manual) to trees, and get all the algorithms and partitioners for free.

[Walter_D_]

Raf, I cannot see how this should work. How can I guarantee that f(n->parent) is called before f(n) ? Please explain.

[RafSchietekat]

When you split a singleton Range, first execute the parent.

(BTW, please note that "eventually" in English has a different meaning than in other languages.)

[Walter_D_]

Raf, okay that may work, you're right. (BTW, I'm fully aware of the meaning of "eventually", though I did struggle ~15 years ago or so. I meant that for nodes containing only a limited number of descendants, a serial code shall be employed as usual. Thus, using "eventually" to mean "in the end" or "after a period [of splitting]", see also http://thesaurus.com/browse/eventually?s=t :-)

Now, what about the up-ward pass. In this case, f(n) has to be called *after* f(n->child) (and so on, recursively). Can this also be implemented using ranges? I cannot think of a way, but then that may not mean much. I've implemented it using tasks, see file attached. Comments appreciated.

[RafSchietekat]

OK, I did not understand what you meant in that sentence (containing the word "eventually"). If you happen to know how many nodes are in any subtree, you can use that knowledge for better balancing, to improve is_divisible() to avoid empty subranges, and perhaps to use a grainsize. You would have code for serial execution anyway (in the Body), otherwise there's little use for a Range to be used with auto_partitioner. I won't hide that it's not very elegant, but it seems the simplest way to program what you want to do.

The other way around seems a lot more adventurous, but if you want to leverage auto_partitioner it may still be worth your while to give it a try.

(Added 2013-03-08) A more obvious approach is to just emulate the auto_partitioner (by using stealing as the trigger for (recursive!) subdivision of the current Range into O(default_num_threads()) pieces), but it's also less of a challenge... :-)