Re: [boost] [parallel_sort] Proposal

Subject: Re: [boost] [parallel_sort] Proposal
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-02-02 17:49:51

Hi,

----- Original Message ----- 
From: "Edouard A." <edouard_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, February 02, 2009 7:21 PM
Subject: Re: [boost] [parallel_sort] Proposal

> On Mon, 02 Feb 2009 17:41:58 +0000, "Phil Endecott"
> <spam_from_boost_dev_at_[hidden]> wrote:
> 
>> So basically it's something like this:
>> 
>>    thread t( sort(begin,mid) );
>>    sort(mid,end);
>>    t.join();
>>    merge(begin,mid,end);  // [*]
> 
> Exactly, with some differences as I do a memory copy before the thread and
> I run two threads.
> 
> Working on different buffers allows to prevent hidden system locks when
> you reach the middle.

Please could you be more precise, which kind of hidden system locks?
 
> so it's more like 
> 
> buffer = new [];
> copy(...)
> thread t1(sort(buffer,...);
> 
> buffer2 = new [];
> copy(...)
> thread t2(sort(buffer2, ...);
> 
> t2.join();
> t1.join();
> 
> merge(buffer, buffer2, result);

The second thread is not realy useful, as noted by Phil. 

I would like to be able to write something more generic, something like:

template <
    typename DirectSolver, 
    typename Composer, 
    typename AsynchronousExecutor, 
    typename Input>
void inplace_solve(AsynchronousExecutor& ae, Problem& input) {
  //  if (problem is small)
    if (size(range) < concurrency_threshold) {
    // directly solve problem
        DirectSolver()(input);
    } else {
        // split problem into independent parts        
        BOOST_AUTO(partition, partition_view(input));
        // evaluates asynchronously inplace_solve on each element of the partition 
        // using the asynchronous executor as scheduler
        wait_for_all(ae, inplace_solve, partition);
        // compose the result in place from subresults
        Composer()(partition);
    }
}

So parallel sort could be

template <typename Range>
void parallel_sort(range& range) {
    boost::tp::pool<> ae;
    parallel::inplace_solve<sort, merge>(ae, input);
}

I'm working on a Asynchronous Execution framework that you can get from http://www.boostpro.com/vault/index.php?action=downloadfile&filename=interthreads.zip&directory=Concurrent%20Programming&. It provides a wait_for_all function which will fork each function except the last one which will be executed in the current thread. So if you make 4 partitions you need to use it as 

        wait_for_all(ae, bind(inplace_solve, at_c<0>(partition)), 
                                    bind(inplace_solve, at_c<1>(partition)),
                                    bind(inplace_solve, at_c<2>(partition)),
                                    bind(inplace_solve, at_c<3>(partition)),
        );

I'll try to implement this overloading.

    template< typename AE, typename F, typename Sequence>
    typename result_of::wait_for_all<AE, F,Sequence >::type
    wait_for_all( AE& ae, F f, Sequence seq );

HTH,
Vicente