Re: [Boost-users] Hybrid parallelism, no more + mpi+serialization, many questions

Subject: Re: [Boost-users] Hybrid parallelism, no more + mpi+serialization, many questions
From: Brian Budge (brian.budge_at_[hidden])
Date: 2010-11-18 11:34:51

Here's how I'd probably do this using a pull model:

I'd have N nodes which might have M_i threads.  Node 0 is the master,
and it will traverse your "tree".  You'll have N-1 other nodes, and
the will ask the master node for work to do.  When the master gets a
request for work, it will send a message with some number of tasks
(maybe 1000 at a time) by traversing the tree and putting the
parameter sets for those tasks in the message.  When the slaves
receive a message full of tasks, a pull model can  again be employed
with the M_i threads on each machine.  Each thread on each machine can
keep track of its current maximum along with the parameters used to
compute that maximum.  When the master runs out of work, the response
message will have zero tasks, and the slaves can decide the local
maximum from their local threads, and send that parameter set +
maximum to the master.  Then the master runs through the max from all
the slaves and chooses the parameter set that gave the maximum value.

You could simplify this slightly by having nodes run  per-cpu
processes instead of per-node, and then you don't have to manage your
threads.   This will have the advantage of being easier to write, but
may not perform quite as well.  Make sure you send enough tasks at a
time that you don't have a lot of waiting around for tasks (also,
larger messages tend to be higher throughput).

As a second round, if you want to get fancier, you can send for more
work while work is still being computed, thus never starving your work
threads.  Additionally, you could have the master actively queuing up
parameter sets between requests in order to handle the requests
quicker.

  Brian

On Thu, Nov 18, 2010 at 7:54 AM, Hicham Mouline <hicham_at_[hidden]> wrote:
> -----Original Message-----
> From: "Brian Budge" [brian.budge_at_[hidden]]
> Date: 18/11/2010 03:20 PM
> To: boost-users_at_[hidden]
> Subject: Re: [Boost-users] Hybrid parallelism, no more + mpi+serialization,
> many questions
>
>>> The 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.
>>> There is n0*n1*...*n9 runs
>>> Then I get the maximum of the return values.
>>>
>>>
>>> Imagining I have N mpi processes, ideally each process would run
>>> n0*n1*...*n9/N function evaluations.
>>> How do I split?
>>>
>>> In terms of current implementation, each of the x is a boost::variant
>>> over 4
>>> types:
>>> a double, a <min,max> pair, a <min, max, increment> triplet or a
>>> vector<double>
>>> A visitor is applied recursively to the variants in order to traverse the
>>> whole parameter space.
>>> apply_visitor on x0 => say if x0 is a triplet, then
>>> for (x0 from min to max with increment)
>>>   apply_visitor on x1
>>> and so on until x9, then we actually call the f function with all the
>>> arguments collected so far.
>>>
>>> How can one parallelize such a beast?
>>>
>>> rds,
>>>
>>>
>>> _______________________________________________
>>This partly depends on how many processors/machines you have
>>available. You need to find a way of partitioning your state space
>>into tasks, and then doling those tasks out to processes/threads. How
>>expensive is f()? How much memory is used?
>>Brian
> f() takes about 1ms. I have a couple of billion n-tuples in the parameter
> space for now but thinking of reaching easily a couple of trillions.
> In the serial mode, only about 20Mbytes of RAM is used. The parameter space
> is not generated ahead. It looks like a tree.
> The tree is generated, when I reach a leaf, I evaluate f(), and compare the
> return to the current maximum.
> So I'm not storing much.
> rds,
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>