Re: [Boost-users] Boost parallel graph: a tree

Subject: Re: [Boost-users] Boost parallel graph: a tree
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-11-19 15:19:45

On Fri, 19 Nov 2010, Hicham Mouline wrote:

> 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?

Yes, in a technical sense, but the algorithms are typically different for 
trees.

> Should I look at the parallel graph library? If so, what algorithm can help me with this?

I don't think you will get a benefit from using it; your code isn't going 
to benefit from the features in PBGL.

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

You might also want to search for "parallel parameter sweep", "parameter 
sweep library", ... since many other people have had the same problem that 
you are trying to solve.  On Windows, for example, there is 
<URL:http://msdn.microsoft.com/en-us/library/cc853429(VS.85).aspx>, and 
there seem to be several open source packages.

-- Jeremiah Willcock