The incremental pairwise algorithm computes partial sums in stages. At each stage, an element combines its current value with a partial sum from increasingly farther away. Separate elements can be updated in parallel. section 8.5.3
Each stage must finish before threads use its results in the next stage. Processors executing additions in lockstep may propagate intermediate results directly; general-purpose threads need explicit synchronization, such as a barrier. section 8.5.3
A barrier between stages
A barrier makes each thread wait until the required number has arrived, then releases them to continue. The C++11 Thread Library does not provide one directly, so the implementation supplies its own. section 8.5.3
Listing 8.13. A parallel implementation of partial_sum by pairwise updates
struct barrier
{
std::atomic<unsigned> count;
std::atomic<unsigned> spaces;
std::atomic<unsigned> generation;
barrier(unsigned count_):
count(count_),spaces(count_),generation(0)
{}
void wait()
{
unsigned const gen=generation.load();
if(!--spaces)
{
spaces=count.load();
++generation;
}
else
{
while(generation.load()==gen)
{
std::this_thread::yield();
}
}
}
void done_waiting()
{
--count;
if(!--spaces)
{
spaces=count.load();
++generation;
}
}
};
template<typename Iterator>
void parallel_partial_sum(Iterator first,Iterator last)
{
typedef typename Iterator::value_type value_type;
struct process_element #1
{
void operator()(Iterator first,Iterator last,
std::vector<value_type>& buffer,
unsigned i,barrier& b)
{
value_type& ith_element=*(first+i);
bool update_source=false;
for(unsigned step=0,stride=1;stride<=i;++step,stride*=2)
{
value_type const& source=(step%2)? #2
buffer[i]:ith_element;
value_type& dest=(step%2)?
ith_element:buffer[i];
value_type const& addend=(step%2)? #3
buffer[i-stride]:*(first+i-stride);
dest=source+addend; #4
update_source=!(step%2);
b.wait(); #5
}
if(update_source) #6
{
ith_element=buffer[i];
}
b.done_waiting(); #7
}
};
unsigned long const length=std::distance(first,last);
if(length<=1)
return;
std::vector<value_type> buffer(length);
barrier b(length);
std::vector<std::thread> threads(length-1); #8
join_threads joiner(threads);
Iterator block_start=first;
for(unsigned long i=0;i<(length-1);++i)
{
threads[i]=std::thread(process_element(),first,last, #9
std::ref(buffer),i,std::ref(b));
}
process_element()(first,last,buffer,length-1,b); #10
}
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":38,\"ch\":63},{\"line\":38,\"ch\":65}],[{\"line\":79,\"ch\":63},{\"line\":79,\"ch\":65}],[{\"line\":49,\"ch\":63},{\"line\":49,\"ch\":65}],[{\"line\":53,\"ch\":63},{\"line\":53,\"ch\":65}],[{\"line\":55,\"ch\":63},{\"line\":55,\"ch\":65}],[{\"line\":57,\"ch\":63},{\"line\":57,\"ch\":65}],[{\"line\":59,\"ch\":63},{\"line\":59,\"ch\":65}],[{\"line\":63,\"ch\":63},{\"line\":63,\"ch\":65}],[{\"line\":71,\"ch\":63},{\"line\":71,\"ch\":65}],[{\"line\":76,\"ch\":63},{\"line\":76,\"ch\":65}],[{\"line\":79,\"ch\":63},{\"line\":79,\"ch\":66}]]"}
!@%STYLE%@!
See the parallel partial-sum implementation using pairwise updates and a barrier. section 8.5.3
