GrPPI  0.2
Generic and Reusable Parallel Pattern Interface
omp/divideconquer.h
Go to the documentation of this file.
1 
21 #ifndef GRPPI_OMP_DIVIDECONQUER_H
22 #define GRPPI_OMP_DIVIDECONQUER_H
23 
24 #ifdef GRPPI_OMP
25 
26 #include "parallel_execution_omp.h"
27 
28 namespace grppi {
29 
30 template <typename Input, typename Divider, typename Solver, typename Combiner>
31 typename std::result_of<Solver(Input)>::type
33  Input & input,
34  Divider && divide_op, Solver && solve_op,
35  Combiner && combine_op,
36  std::atomic<int> & num_threads)
37 {
38  // Sequential execution fo internal implementation
39  using Output = typename std::result_of<Solver(Input)>::type;
41  Output out;
42  if(num_threads.load()>0) {
43  auto subproblems = divide_op(input);
44 
45 
46  if(subproblems.size()>1) {
47  std::vector<Output> partials(subproblems.size()-1);
48  int division = 0;
49  auto i = subproblems.begin()+1;
50  for(i; i!=subproblems.end() && num_threads.load()>0; i++, division++){
51  //THREAD
52  #pragma omp task firstprivate(i, division) shared(divide_op, solve_op, \
53  combine_op, partials, num_threads)
54  {
55  partials[division] = internal_divide_conquer(ex, *i,
56  std::forward<Divider>(divide_op),
57  std::forward<Solver>(solve_op),
58  std::forward<Combiner>(combine_op), num_threads);
59  //END TRHEAD
60  }
61  num_threads --;
62 
63  }
64  for(i; i != subproblems.end(); i++){
65  partials[division] = divide_conquer(seq, *i,
66  std::forward<Divider>(divide_op),
67  std::forward<Solver>(solve_op),
68  std::forward<Combiner>(combine_op));
69  }
70 
71  //Main thread works on the first subproblem.
72  out = internal_divide_conquer(ex, *subproblems.begin(),
73  std::forward<Divider>(divide_op),
74  std::forward<Solver>(solve_op),
75  std::forward<Combiner>(combine_op), num_threads);
76 
77  #pragma omp taskwait
78 
79  for(int i = 0; i<partials.size();i++){
80  out = combine_op(out,partials[i]);
81  }
82  }
83  else {
84  out = solve_op(input);
85  }
86  }
87  else {
88  return divide_conquer(seq, input, std::forward<Divider>(divide_op),
89  std::forward<Solver>(solve_op), std::forward<Combiner>(combine_op));
90  }
91  return out;
92 }
93 
115 template <typename Input, typename Divider, typename Solver, typename Combiner>
116 typename std::result_of<Solver(Input)>::type
118  Input & input,
119  Divider && divide_op, Solver && solve_op,
120  Combiner && combine_op)
121 {
122  std::atomic<int> num_threads{ex.concurrency_degree()-1};
123 
125 
126  using Output = typename std::result_of<Solver(Input)>::type;
127 
128  if (num_threads.load()<=0) {
129  return divide_conquer(seq, input,
130  std::forward<Divider>(divide_op),
131  std::forward<Solver>(solve_op),
132  std::forward<Combiner>(combine_op));
133  }
134 
135  auto subproblems = divide_op(input);
136  if (subproblems.size()<=1) {
137  return solve_op(input);
138  }
139 
140  std::vector<Output> partials(subproblems.size()-1);
141  int division = 0;
142 
143  Output out;
144 
145  #pragma omp parallel
146  {
147  #pragma omp single nowait
148  {
149  auto i = subproblems.begin() + 1;
150  for (i; i!=subproblems.end() && num_threads.load()>0; i++, division++) {
151  //THREAD
152  #pragma omp task firstprivate(i,division) \
153  shared(partials,divide_op,solve_op,combine_op,num_threads)
154  {
155  partials[division] = internal_divide_conquer(ex, *i,
156  std::forward<Divider>(divide_op),
157  std::forward<Solver>(solve_op),
158  std::forward<Combiner>(combine_op), num_threads);
159  //END TRHEAD
160  }
161  num_threads --;
162  }
163 
164  for (i; i!=subproblems.end(); i++) {
165  partials[division] = divide_conquer(seq, *i,
166  std::forward<Divider>(divide_op),
167  std::forward<Solver>(solve_op),
168  std::forward<Combiner>(combine_op));
169  }
170 
171  //Main thread works on the first subproblem.
172  if (num_threads.load()>0) {
173  out = internal_divide_conquer(ex, *subproblems.begin(),
174  std::forward<Divider>(divide_op),
175  std::forward<Solver>(solve_op),
176  std::forward<Combiner>(combine_op), num_threads);
177  }
178  else {
179  out = divide_conquer(seq, *subproblems.begin(),
180  std::forward<Divider>(divide_op),
181  std::forward<Solver>(solve_op),
182  std::forward<Combiner>(combine_op));
183  }
184  #pragma omp taskwait
185  }
186  }
187 
188  for (auto && p : partials) { out = combine_op(out,p); }
189  return out;
190 }
191 
197 }
198 
199 #endif
200 
201 #endif
Definition: callable_traits.h:24
std::result_of< Solver(Input)>::type divide_conquer(parallel_execution_native &ex, Input &problem, Divider &&divide_op, Solver &&solve_op, Combiner &&combine_op)
Invoke Divide/conquer pattern with native parallel execution.
Definition: native/divideconquer.h:124
OpenMP parallel execution policy.
Definition: parallel_execution_omp.h:40
Sequential execution policy.
Definition: sequential_execution.h:31
std::result_of< Solver(Input)>::type internal_divide_conquer(parallel_execution_native &p, Input &input, Divider &&divide_op, Solver &&solve_op, Combiner &&combine_op, std::atomic< int > &num_threads)
Definition: native/divideconquer.h:33
int concurrency_degree() const noexcept
Get number of grppi trheads.
Definition: parallel_execution_omp.h:85