40 #ifndef _GLIBCXX_PARALLEL_WORKSTEALING_H
41 #define _GLIBCXX_PARALLEL_WORKSTEALING_H 1
47 namespace __gnu_parallel
50 #define _GLIBCXX_JOB_VOLATILE volatile
53 template<
typename _DifferenceTp>
56 typedef _DifferenceTp difference_type;
62 _GLIBCXX_JOB_VOLATILE difference_type
first;
67 _GLIBCXX_JOB_VOLATILE difference_type
last;
72 _GLIBCXX_JOB_VOLATILE difference_type
load;
93 template<
typename RandomAccessIterator,
100 RandomAccessIterator end,
102 Result base, Result& output,
104 <RandomAccessIterator>::
105 difference_type bound)
110 typedef typename traits_type::difference_type difference_type;
114 difference_type chunk_size =
static_cast<difference_type
>(__s.workstealing_chunk_size);
117 difference_type length = (bound < 0) ? (end - begin) : bound;
127 omp_lock_t output_lock;
128 omp_init_lock(&output_lock);
135 __gnu_parallel::max<thread_index_t>(1,
136 __gnu_parallel::min<difference_type>(length, get_max_threads()));
138 # pragma omp parallel shared(busy) num_threads(num_threads)
143 num_threads = omp_get_num_threads();
152 bool iam_working =
false;
164 Result result = Result();
167 difference_type steal;
181 static_cast<difference_type
>(iam * (length / num_threads));
183 my_job.
last = (iam == (num_threads - 1)) ?
184 (length - 1) : ((iam + 1) * (length / num_threads) - 1);
191 difference_type my_first = my_job.
first;
192 result = f(op, begin + my_first);
197 RandomAccessIterator current;
206 # pragma omp flush(busy)
213 difference_type current_job =
214 fetch_and_add<difference_type>(&(my_job.
first), chunk_size);
219 for (difference_type job_counter = 0;
220 job_counter < chunk_size && current_job <= my_job.
last;
224 current = begin + current_job;
228 result = r(result, f(op, current));
231 # pragma omp flush(busy)
244 difference_type supposed_first, supposed_last, supposed_load;
249 # pragma omp flush(busy)
251 supposed_first = job[victim * stride].
first;
252 supposed_last = job[victim * stride].
last;
253 supposed_load = job[victim * stride].
load;
256 && ((supposed_load <= 0)
257 || ((supposed_first + supposed_load - 1) != supposed_last)));
262 if (supposed_load > 0)
266 steal = (supposed_load < 2) ? 1 : supposed_load / 2;
269 difference_type stolen_first =
270 fetch_and_add<difference_type>(
271 &(job[victim * stride].
first), steal);
272 difference_type stolen_try =
273 stolen_first + steal - difference_type(1);
275 my_job.
first = stolen_first;
284 # pragma omp flush(busy)
286 # pragma omp flush(busy)
289 omp_set_lock(&output_lock);
290 output = r(output, result);
291 omp_unset_lock(&output_lock);
298 f.finish_iterator = begin + length;
300 omp_destroy_lock(&output_lock);
static const _Settings & get()
Get the global settings.
volatile difference_type load
Number of elements, i. e. last-first+1.
const T & min(const T &a, const T &b)
Equivalent to std::min.
Compatibility layer, mostly concerned with atomic operations. This file is a GNU parallel extension t...
Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...
volatile difference_type last
Last element.
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
void yield()
Yield the control to another thread, without waiting for the end to the time slice.
Op for_each_template_random_access_workstealing(RandomAccessIterator begin, RandomAccessIterator end, Op op, Fu &f, Red r, Result base, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_type bound)
Work stealing algorithm for random access iterators.
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
Random number generator, based on the Mersenne twister.
One job for a certain thread.
unsigned int cache_line_size
Overestimation of cache line size. Used to avoid false sharing, i. e. elements of different threads a...
class _Settings Run-time settings for the parallel mode, including all tunable parameters.
volatile difference_type first
First element.
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.