[Boost-users] Boost parallel graph: a tree

Subject: [Boost-users] Boost parallel graph: a tree
From: Hicham Mouline (hicham_at_[hidden])
Date: 2010-11-19 10:43:37

Hello,

Following a thread titled "Hybrid parallelism, no more + mpi+serialization, many questions ", I reproduce the main question here:

A large calculation that I currently do serially and that I intend to 
parallelize is the maximum of the return values of a large number of 
evaluations of a given "function" in the mathematical sense. 
The number of arguments of the function is only known at runtime. 
Let's say it is determined at runtime that the number of arguments is 10, ie 
we have 10 arguments x0, ..., x9 
Each argument can take a different number of values, for e.g. x0 can be 
x0_0, x0_1 .... x0_n0 
x1 can be x1_0, x1_1, ...x1_n1 and so on...n0 and n1 are typically known at 
runtime and different .
So serially, I run :
f(x0_0, x1_0, ..., x9_0) 
f(x0_0, x1_0, ..., x9_1) 
... 
f(x0_0, x1_0, ..., x9_n9) 
then with all the x8 then all the x7 ... then all the x0. 

More accurately, some of the arguments are constrained, for e.g.,  x3+x4+x5 =100 always

I am looking at this as a vertical tree, from the top level (x0) down to the leaves (x9).
x0 can have n0 values. For each of these nodes, there are n1 children, for each of these children, there are n2 children,  and so on.
The bottom-est children (for x9) are the leaves of the tree.
The constraints that exist on some of the variables will remove a number of branches from the tree, however in my use case, this proportion is small.
Once I reach the leaves, I evaluate a function with the 10 arguments selected by that branch.
The objective is to obtain the minimum/maximum of return values over all evaluations.

Is a tree a special case of a graph?
Should I look at the parallel graph library? If so, what algorithm can help me with this?

In the other thread, Brian provided a solution that I will implement if this problem doesn't lend itself to boost graph,

regards,