3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file parallel/workstealing.h
26 * @brief Parallelization of embarrassingly parallel execution by
27 * means of work-stealing.
29 * Work stealing is described in
31 * R. D. Blumofe and C. E. Leiserson.
32 * Scheduling multithreaded computations by work stealing.
33 * Journal of the ACM, 46(5):720–748, 1999.
35 * This file is a GNU parallel extension to the Standard C++ Library.
38 // Written by Felix Putze.
40 #ifndef _GLIBCXX_PARALLEL_WORKSTEALING_H
41 #define _GLIBCXX_PARALLEL_WORKSTEALING_H 1
43 #include <parallel/parallel.h>
44 #include <parallel/random_number.h>
45 #include <parallel/compatibility.h>
47 namespace __gnu_parallel
50 #define _GLIBCXX_JOB_VOLATILE volatile
52 /** @brief One __job for a certain thread. */
53 template<typename _DifferenceTp>
56 typedef _DifferenceTp _DifferenceType;
58 /** @brief First element.
60 * Changed by owning and stealing thread. By stealing thread,
61 * always incremented. */
62 _GLIBCXX_JOB_VOLATILE _DifferenceType _M_first;
64 /** @brief Last element.
66 * Changed by owning thread only. */
67 _GLIBCXX_JOB_VOLATILE _DifferenceType _M_last;
69 /** @brief Number of elements, i.e. @__c _M_last-_M_first+1.
71 * Changed by owning thread only. */
72 _GLIBCXX_JOB_VOLATILE _DifferenceType _M_load;
75 /** @brief Work stealing algorithm for random access iterators.
77 * Uses O(1) additional memory. Synchronization at job lists is
78 * done with atomic operations.
79 * @param __begin Begin iterator of element sequence.
80 * @param __end End iterator of element sequence.
81 * @param __op User-supplied functor (comparator, predicate, adding
83 * @param __f Functor to "process" an element with __op (depends on
84 * desired functionality, e. g. for std::for_each(), ...).
85 * @param __r Functor to "add" a single __result to the already
86 * processed elements (depends on functionality).
87 * @param __base Base value for reduction.
88 * @param __output Pointer to position where final result is written to
89 * @param __bound Maximum number of elements processed (e. g. for
91 * @return User-supplied functor (that may contain a part of the result).
93 template<typename _RAIter,
99 for_each_template_random_access_workstealing(
100 _RAIter __begin, _RAIter __end, _Op __op, _Fu& __f, _Red __r,
101 _Result __base, _Result& __output,
102 typename std::iterator_traits<_RAIter>::difference_type __bound)
104 _GLIBCXX_CALL(__end - __begin)
106 typedef std::iterator_traits<_RAIter> _TraitsType;
107 typedef typename _TraitsType::difference_type _DifferenceType;
109 const _Settings& __s = _Settings::get();
111 _DifferenceType __chunk_size =
112 static_cast<_DifferenceType>(__s.workstealing_chunk_size);
115 _DifferenceType __length = (__bound < 0) ? (__end - __begin) : __bound;
117 // To avoid false sharing in a cache line.
119 __s.cache_line_size * 10 / sizeof(_Job<_DifferenceType>) + 1;
121 // Total number of threads currently working.
122 _ThreadIndex __busy = 0;
124 _Job<_DifferenceType> *__job;
126 omp_lock_t __output_lock;
127 omp_init_lock(&__output_lock);
129 // Write base value to output.
132 // No more threads than jobs, at least one thread.
133 _ThreadIndex __num_threads =
134 __gnu_parallel::max<_ThreadIndex>(1,
135 __gnu_parallel::min<_DifferenceType>(__length, __get_max_threads()));
137 # pragma omp parallel shared(__busy) num_threads(__num_threads)
142 __num_threads = omp_get_num_threads();
144 // Create job description array.
145 __job = new _Job<_DifferenceType>[__num_threads * __stride];
148 // Initialization phase.
150 // Flags for every thread if it is doing productive work.
151 bool __iam_working = false;
154 _ThreadIndex __iam = omp_get_thread_num();
157 _Job<_DifferenceType>& __my_job = __job[__iam * __stride];
159 // Random number (for work stealing).
160 _ThreadIndex __victim;
162 // Local value for reduction.
163 _Result __result = _Result();
165 // Number of elements to steal in one attempt.
166 _DifferenceType __steal;
168 // Every thread has its own random number generator
169 // (modulo __num_threads).
170 _RandomNumber rand_gen(__iam, __num_threads);
172 // This thread is currently working.
176 __iam_working = true;
178 // How many jobs per thread? last thread gets the rest.
180 static_cast<_DifferenceType>(__iam * (__length / __num_threads));
182 __my_job._M_last = (__iam == (__num_threads - 1)) ?
183 (__length - 1) : ((__iam + 1) * (__length / __num_threads) - 1);
184 __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
186 // Init result with _M_first value (to have a base value for reduction)
187 if (__my_job._M_first <= __my_job._M_last)
189 // Cannot use volatile variable directly.
190 _DifferenceType __my_first = __my_job._M_first;
191 __result = __f(__op, __begin + __my_first);
201 // Work on own or stolen current start
204 // Work until no productive thread left.
205 # pragma omp flush(__busy)
207 // Thread has own work to do
208 while (__my_job._M_first <= __my_job._M_last)
210 // fetch-and-add call
211 // Reserve current job block (size __chunk_size) in my queue.
212 _DifferenceType __current_job =
213 __fetch_and_add<_DifferenceType>(
214 &(__my_job._M_first), __chunk_size);
216 // Update _M_load, to make the three values consistent,
217 // _M_first might have been changed in the meantime
218 __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
219 for (_DifferenceType __job_counter = 0;
220 __job_counter < __chunk_size
221 && __current_job <= __my_job._M_last;
225 __current = __begin + __current_job;
229 __result = __r(__result, __f(__op, __current));
232 # pragma omp flush(__busy)
235 // After reaching this point, a thread's __job list is empty.
238 // This thread no longer has work.
242 __iam_working = false;
245 _DifferenceType __supposed_first, __supposed_last, __supposed_load;
248 // Find random nonempty deque (not own), do consistency check.
250 # pragma omp flush(__busy)
251 __victim = rand_gen();
252 __supposed_first = __job[__victim * __stride]._M_first;
253 __supposed_last = __job[__victim * __stride]._M_last;
254 __supposed_load = __job[__victim * __stride]._M_load;
257 && ((__supposed_load <= 0)
258 || ((__supposed_first + __supposed_load - 1)
259 != __supposed_last)));
264 if (__supposed_load > 0)
266 // Has work and work to do.
267 // Number of elements to steal (at least one).
268 __steal = (__supposed_load < 2) ? 1 : __supposed_load / 2;
270 // Push __victim's current start forward.
271 _DifferenceType __stolen_first =
272 __fetch_and_add<_DifferenceType>(
273 &(__job[__victim * __stride]._M_first), __steal);
274 _DifferenceType __stolen_try =
275 __stolen_first + __steal - _DifferenceType(1);
277 __my_job._M_first = __stolen_first;
279 __gnu_parallel::min(__stolen_try, __supposed_last);
280 __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
282 // Has potential work again.
285 __iam_working = true;
287 # pragma omp flush(__busy)
289 # pragma omp flush(__busy)
290 } // end while __busy > 0
291 // Add accumulated result to output.
292 omp_set_lock(&__output_lock);
293 __output = __r(__output, __result);
294 omp_unset_lock(&__output_lock);
299 // Points to last element processed (needed as return value for
300 // some algorithms like transform)
301 __f._M_finish_iterator = __begin + __length;
303 omp_destroy_lock(&__output_lock);
309 #endif /* _GLIBCXX_PARALLEL_WORKSTEALING_H */