--- /dev/null
+// -*- C++ -*-
+
+// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file parallel/workstealing.h
+ * @brief Parallelization of embarrassingly parallel execution by
+ * means of work-stealing.
+ *
+ * Work stealing is described in
+ *
+ * R. D. Blumofe and C. E. Leiserson.
+ * Scheduling multithreaded computations by work stealing.
+ * Journal of the ACM, 46(5):720–748, 1999.
+ *
+ * This file is a GNU parallel extension to the Standard C++ Library.
+ */
+
+// Written by Felix Putze.
+
+#ifndef _GLIBCXX_PARALLEL_WORKSTEALING_H
+#define _GLIBCXX_PARALLEL_WORKSTEALING_H 1
+
+#include <parallel/parallel.h>
+#include <parallel/random_number.h>
+#include <parallel/compatibility.h>
+
+namespace __gnu_parallel
+{
+
+#define _GLIBCXX_JOB_VOLATILE volatile
+
+ /** @brief One __job for a certain thread. */
+ template<typename _DifferenceTp>
+ struct _Job
+ {
+ typedef _DifferenceTp _DifferenceType;
+
+ /** @brief First element.
+ *
+ * Changed by owning and stealing thread. By stealing thread,
+ * always incremented. */
+ _GLIBCXX_JOB_VOLATILE _DifferenceType _M_first;
+
+ /** @brief Last element.
+ *
+ * Changed by owning thread only. */
+ _GLIBCXX_JOB_VOLATILE _DifferenceType _M_last;
+
+ /** @brief Number of elements, i.e. @c _M_last-_M_first+1.
+ *
+ * Changed by owning thread only. */
+ _GLIBCXX_JOB_VOLATILE _DifferenceType _M_load;
+ };
+
+ /** @brief Work stealing algorithm for random access iterators.
+ *
+ * Uses O(1) additional memory. Synchronization at job lists is
+ * done with atomic operations.
+ * @param __begin Begin iterator of element sequence.
+ * @param __end End iterator of element sequence.
+ * @param __op User-supplied functor (comparator, predicate, adding
+ * functor, ...).
+ * @param __f Functor to @a process an element with __op (depends on
+ * desired functionality, e. g. for std::for_each(), ...).
+ * @param __r Functor to @a add a single __result to the already
+ * processed elements (depends on functionality).
+ * @param __base Base value for reduction.
+ * @param __output Pointer to position where final result is written to
+ * @param __bound Maximum number of elements processed (e. g. for
+ * std::count_n()).
+ * @return User-supplied functor (that may contain a part of the result).
+ */
+ template<typename _RAIter,
+ typename _Op,
+ typename _Fu,
+ typename _Red,
+ typename _Result>
+ _Op
+ __for_each_template_random_access_workstealing(_RAIter __begin,
+ _RAIter __end, _Op __op,
+ _Fu& __f, _Red __r,
+ _Result __base,
+ _Result& __output,
+ typename std::iterator_traits<_RAIter>::difference_type __bound)
+ {
+ _GLIBCXX_CALL(__end - __begin)
+
+ typedef std::iterator_traits<_RAIter> _TraitsType;
+ typedef typename _TraitsType::difference_type _DifferenceType;
+
+ const _Settings& __s = _Settings::get();
+
+ _DifferenceType __chunk_size =
+ static_cast<_DifferenceType>(__s.workstealing_chunk_size);
+
+ // How many jobs?
+ _DifferenceType __length = (__bound < 0) ? (__end - __begin) : __bound;
+
+ // To avoid false sharing in a cache line.
+ const int __stride = (__s.cache_line_size * 10
+ / sizeof(_Job<_DifferenceType>) + 1);
+
+ // Total number of threads currently working.
+ _ThreadIndex __busy = 0;
+
+ _Job<_DifferenceType> *__job;
+
+ omp_lock_t __output_lock;
+ omp_init_lock(&__output_lock);
+
+ // Write base value to output.
+ __output = __base;
+
+ // No more threads than jobs, at least one thread.
+ _ThreadIndex __num_threads = __gnu_parallel::max<_ThreadIndex>
+ (1, __gnu_parallel::min<_DifferenceType>(__length,
+ __get_max_threads()));
+
+# pragma omp parallel shared(__busy) num_threads(__num_threads)
+ {
+# pragma omp single
+ {
+ __num_threads = omp_get_num_threads();
+
+ // Create job description array.
+ __job = new _Job<_DifferenceType>[__num_threads * __stride];
+ }
+
+ // Initialization phase.
+
+ // Flags for every thread if it is doing productive work.
+ bool __iam_working = false;
+
+ // Thread id.
+ _ThreadIndex __iam = omp_get_thread_num();
+
+ // This job.
+ _Job<_DifferenceType>& __my_job = __job[__iam * __stride];
+
+ // Random number (for work stealing).
+ _ThreadIndex __victim;
+
+ // Local value for reduction.
+ _Result __result = _Result();
+
+ // Number of elements to steal in one attempt.
+ _DifferenceType __steal;
+
+ // Every thread has its own random number generator
+ // (modulo __num_threads).
+ _RandomNumber __rand_gen(__iam, __num_threads);
+
+ // This thread is currently working.
+# pragma omp atomic
+ ++__busy;
+
+ __iam_working = true;
+
+ // How many jobs per thread? last thread gets the rest.
+ __my_job._M_first = static_cast<_DifferenceType>
+ (__iam * (__length / __num_threads));
+
+ __my_job._M_last = (__iam == (__num_threads - 1)
+ ? (__length - 1)
+ : ((__iam + 1) * (__length / __num_threads) - 1));
+ __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
+
+ // Init result with _M_first value (to have a base value for reduction)
+ if (__my_job._M_first <= __my_job._M_last)
+ {
+ // Cannot use volatile variable directly.
+ _DifferenceType __my_first = __my_job._M_first;
+ __result = __f(__op, __begin + __my_first);
+ ++__my_job._M_first;
+ --__my_job._M_load;
+ }
+
+ _RAIter __current;
+
+# pragma omp barrier
+
+ // Actual work phase
+ // Work on own or stolen current start
+ while (__busy > 0)
+ {
+ // Work until no productive thread left.
+# pragma omp flush(__busy)
+
+ // Thread has own work to do
+ while (__my_job._M_first <= __my_job._M_last)
+ {
+ // fetch-and-add call
+ // Reserve current job block (size __chunk_size) in my queue.
+ _DifferenceType __current_job =
+ __fetch_and_add<_DifferenceType>(&(__my_job._M_first),
+ __chunk_size);
+
+ // Update _M_load, to make the three values consistent,
+ // _M_first might have been changed in the meantime
+ __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
+ for (_DifferenceType __job_counter = 0;
+ __job_counter < __chunk_size
+ && __current_job <= __my_job._M_last;
+ ++__job_counter)
+ {
+ // Yes: process it!
+ __current = __begin + __current_job;
+ ++__current_job;
+
+ // Do actual work.
+ __result = __r(__result, __f(__op, __current));
+ }
+
+# pragma omp flush(__busy)
+ }
+
+ // After reaching this point, a thread's __job list is empty.
+ if (__iam_working)
+ {
+ // This thread no longer has work.
+# pragma omp atomic
+ --__busy;
+
+ __iam_working = false;
+ }
+
+ _DifferenceType __supposed_first, __supposed_last,
+ __supposed_load;
+ do
+ {
+ // Find random nonempty deque (not own), do consistency check.
+ __yield();
+# pragma omp flush(__busy)
+ __victim = __rand_gen();
+ __supposed_first = __job[__victim * __stride]._M_first;
+ __supposed_last = __job[__victim * __stride]._M_last;
+ __supposed_load = __job[__victim * __stride]._M_load;
+ }
+ while (__busy > 0
+ && ((__supposed_load <= 0)
+ || ((__supposed_first + __supposed_load - 1)
+ != __supposed_last)));
+
+ if (__busy == 0)
+ break;
+
+ if (__supposed_load > 0)
+ {
+ // Has work and work to do.
+ // Number of elements to steal (at least one).
+ __steal = (__supposed_load < 2) ? 1 : __supposed_load / 2;
+
+ // Push __victim's current start forward.
+ _DifferenceType __stolen_first =
+ __fetch_and_add<_DifferenceType>
+ (&(__job[__victim * __stride]._M_first), __steal);
+ _DifferenceType __stolen_try = (__stolen_first + __steal
+ - _DifferenceType(1));
+
+ __my_job._M_first = __stolen_first;
+ __my_job._M_last = __gnu_parallel::min(__stolen_try,
+ __supposed_last);
+ __my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
+
+ // Has potential work again.
+# pragma omp atomic
+ ++__busy;
+ __iam_working = true;
+
+# pragma omp flush(__busy)
+ }
+# pragma omp flush(__busy)
+ } // end while __busy > 0
+ // Add accumulated result to output.
+ omp_set_lock(&__output_lock);
+ __output = __r(__output, __result);
+ omp_unset_lock(&__output_lock);
+ }
+
+ delete[] __job;
+
+ // Points to last element processed (needed as return value for
+ // some algorithms like transform)
+ __f._M_finish_iterator = __begin + __length;
+
+ omp_destroy_lock(&__output_lock);
+
+ return __op;
+ }
+} // end namespace
+
+#endif /* _GLIBCXX_PARALLEL_WORKSTEALING_H */
projects / cross.git / blobdiff