40 #ifndef _GLIBCXX_PARALLEL_WORKSTEALING_H
41 #define _GLIBCXX_PARALLEL_WORKSTEALING_H 1
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);
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
One job for a certain thread.
Compatibility layer, mostly concerned with atomic operations. This file is a GNU parallel extension t...
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.
class _Settings Run-time settings for the parallel mode, including all tunable parameters.
volatile difference_type last
Last element.
GNU parallel code for public use.
volatile difference_type load
Number of elements, i. e. last-first+1.
Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...
static const _Settings & get()
Get the global settings.
volatile difference_type first
First element.
void yield()
Yield the control to another thread, without waiting for the end to the time slice.
const T & min(const T &a, const T &b)
Equivalent to std::min.
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
unsigned int cache_line_size
Overestimation of cache line size. Used to avoid false sharing, i. e. elements of different threads a...
Random number generator, based on the Mersenne twister.