-
Notifications
You must be signed in to change notification settings - Fork 129
/
example8_13.cpp
90 lines (78 loc) · 1.93 KB
/
example8_13.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//通过成对更新的partial_sum的并行实现
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(); //是将当前线程所抢到的CPU”时间片A”让渡给其他线程
}
}
}
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
{
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)?buffer[i]:ith_element;
value_type& dest=(step%2)?ith_element:buffer[i];
value_type const& addend=(step%2)?buffer[i-stride]:*(first+i-stride);
dest=source+addend;
update_source=!(step%2);
b.wait(); //开始下一步之前在屏障上等待
}
//如果你的最终结果存储在缓冲器中的话,就更新原先范围里的元素
if(update_source)
{
ith_element=buffer[i];
}
b.done_waiting();
}
};
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);
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,std::ref(buffer),i,std::ref(b));
}
process_element()(first,last,buffer,length-1,b);
}