11.2.0/parallel/workstealing.h

// -*- C++ -*-

// Copyright (C) 2007-2021 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 */
Revision:	1166
Committed:	Tue Oct 26 14:22:36 2021 UTC (4 years ago) by rossy
Content type:	text/x-chdr
File size:	9610 byte(s)
Log Message:	Daodan: Replace MinGW build env with an up-to-date MSYS2 env
#	Content
1	// -- C++ --
2
3	// Copyright (C) 2007-2021 Free Software Foundation, Inc.
4	//
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
9	// version.
10
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.
15
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.
19
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/>.
24
25	/** @file parallel/workstealing.h
26	* @brief Parallelization of embarrassingly parallel execution by
27	* means of work-stealing.
28	*
29	* Work stealing is described in
30	*
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.
34	*
35	* This file is a GNU parallel extension to the Standard C++ Library.
36	*/
37
38	// Written by Felix Putze.
39
40	#ifndef _GLIBCXX_PARALLEL_WORKSTEALING_H
41	#define _GLIBCXX_PARALLEL_WORKSTEALING_H 1
42
43	#include <parallel/parallel.h>
44	#include <parallel/random_number.h>
45	#include <parallel/compatibility.h>
46
47	namespace __gnu_parallel
48	{
49
50	#define _GLIBCXX_JOB_VOLATILE volatile
51
52	/** @brief One __job for a certain thread. */
53	template<typename _DifferenceTp>
54	struct _Job
55	{
56	typedef _DifferenceTp _DifferenceType;
57
58	/** @brief First element.
59	*
60	* Changed by owning and stealing thread. By stealing thread,
61	* always incremented. */
62	_GLIBCXX_JOB_VOLATILE _DifferenceType _M_first;
63
64	/** @brief Last element.
65	*
66	* Changed by owning thread only. */
67	_GLIBCXX_JOB_VOLATILE _DifferenceType _M_last;
68
69	/** @brief Number of elements, i.e. @c _M_last-_M_first+1.
70	*
71	* Changed by owning thread only. */
72	_GLIBCXX_JOB_VOLATILE _DifferenceType _M_load;
73	};
74
75	/** @brief Work stealing algorithm for random access iterators.
76	*
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
82	* functor, ...).
83	* @param __f Functor to @a process an element with __op (depends on
84	* desired functionality, e. g. for std::for_each(), ...).
85	* @param __r Functor to @a 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
90	* std::count_n()).
91	* @return User-supplied functor (that may contain a part of the result).
92	*/
93	template<typename _RAIter,
94	typename _Op,
95	typename _Fu,
96	typename _Red,
97	typename _Result>
98	_Op
99	__for_each_template_random_access_workstealing(_RAIter __begin,
100	_RAIter __end, _Op __op,
101	_Fu& __f, _Red __r,
102	_Result __base,
103	_Result& __output,
104	typename std::iterator_traits<_RAIter>::difference_type __bound)
105	{
106	_GLIBCXX_CALL(__end - __begin)
107
108	typedef std::iterator_traits<_RAIter> _TraitsType;
109	typedef typename _TraitsType::difference_type _DifferenceType;
110
111	const _Settings& __s = _Settings::get();
112
113	_DifferenceType __chunk_size =
114	static_cast<_DifferenceType>(__s.workstealing_chunk_size);
115
116	// How many jobs?
117	_DifferenceType __length = (__bound < 0) ? (__end - __begin) : __bound;
118
119	// To avoid false sharing in a cache line.
120	const int __stride = (__s.cache_line_size * 10
121	/ sizeof(_Job<_DifferenceType>) + 1);
122
123	// Total number of threads currently working.
124	_ThreadIndex __busy = 0;
125
126	_Job<_DifferenceType> *__job;
127
128	omp_lock_t __output_lock;
129	omp_init_lock(&__output_lock);
130
131	// Write base value to output.
132	__output = __base;
133
134	// No more threads than jobs, at least one thread.
135	_ThreadIndex __num_threads = __gnu_parallel::max<_ThreadIndex>
136	(1, __gnu_parallel::min<_DifferenceType>(__length,
137	__get_max_threads()));
138
139	# pragma omp parallel shared(__busy) num_threads(__num_threads)
140	{
141	# pragma omp single
142	{
143	__num_threads = omp_get_num_threads();
144
145	// Create job description array.
146	__job = new _Job<_DifferenceType>[__num_threads * __stride];
147	}
148
149	// Initialization phase.
150
151	// Flags for every thread if it is doing productive work.
152	bool __iam_working = false;
153
154	// Thread id.
155	_ThreadIndex __iam = omp_get_thread_num();
156
157	// This job.
158	_Job<_DifferenceType>& __my_job = __job[__iam * __stride];
159
160	// Random number (for work stealing).
161	_ThreadIndex __victim;
162
163	// Local value for reduction.
164	_Result __result = _Result();
165
166	// Number of elements to steal in one attempt.
167	_DifferenceType __steal;
168
169	// Every thread has its own random number generator
170	// (modulo __num_threads).
171	_RandomNumber __rand_gen(__iam, __num_threads);
172
173	// This thread is currently working.
174	# pragma omp atomic
175	++__busy;
176
177	__iam_working = true;
178
179	// How many jobs per thread? last thread gets the rest.
180	__my_job._M_first = static_cast<_DifferenceType>
181	(__iam * (__length / __num_threads));
182
183	__my_job._M_last = (__iam == (__num_threads - 1)
184	? (__length - 1)
185	: ((__iam + 1) * (__length / __num_threads) - 1));
186	__my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
187
188	// Init result with _M_first value (to have a base value for reduction)
189	if (__my_job._M_first <= __my_job._M_last)
190	{
191	// Cannot use volatile variable directly.
192	_DifferenceType __my_first = __my_job._M_first;
193	__result = __f(__op, __begin + __my_first);
194	++__my_job._M_first;
195	--__my_job._M_load;
196	}
197
198	_RAIter __current;
199
200	# pragma omp barrier
201
202	// Actual work phase
203	// Work on own or stolen current start
204	while (__busy > 0)
205	{
206	// Work until no productive thread left.
207	# pragma omp flush(__busy)
208
209	// Thread has own work to do
210	while (__my_job._M_first <= __my_job._M_last)
211	{
212	// fetch-and-add call
213	// Reserve current job block (size __chunk_size) in my queue.
214	_DifferenceType __current_job =
215	__fetch_and_add<_DifferenceType>(&(__my_job._M_first),
216	__chunk_size);
217
218	// Update _M_load, to make the three values consistent,
219	// _M_first might have been changed in the meantime
220	__my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
221	for (_DifferenceType __job_counter = 0;
222	__job_counter < __chunk_size
223	&& __current_job <= __my_job._M_last;
224	++__job_counter)
225	{
226	// Yes: process it!
227	__current = __begin + __current_job;
228	++__current_job;
229
230	// Do actual work.
231	__result = __r(__result, __f(__op, __current));
232	}
233
234	# pragma omp flush(__busy)
235	}
236
237	// After reaching this point, a thread's __job list is empty.
238	if (__iam_working)
239	{
240	// This thread no longer has work.
241	# pragma omp atomic
242	--__busy;
243
244	__iam_working = false;
245	}
246
247	_DifferenceType __supposed_first, __supposed_last,
248	__supposed_load;
249	do
250	{
251	// Find random nonempty deque (not own), do consistency check.
252	__yield();
253	# pragma omp flush(__busy)
254	__victim = __rand_gen();
255	__supposed_first = __job[__victim * __stride]._M_first;
256	__supposed_last = __job[__victim * __stride]._M_last;
257	__supposed_load = __job[__victim * __stride]._M_load;
258	}
259	while (__busy > 0
260	&& ((__supposed_load <= 0)
261	\|\| ((__supposed_first + __supposed_load - 1)
262	!= __supposed_last)));
263
264	if (__busy == 0)
265	break;
266
267	if (__supposed_load > 0)
268	{
269	// Has work and work to do.
270	// Number of elements to steal (at least one).
271	__steal = (__supposed_load < 2) ? 1 : __supposed_load / 2;
272
273	// Push __victim's current start forward.
274	_DifferenceType __stolen_first =
275	__fetch_and_add<_DifferenceType>
276	(&(__job[__victim * __stride]._M_first), __steal);
277	_DifferenceType __stolen_try = (__stolen_first + __steal
278	- _DifferenceType(1));
279
280	__my_job._M_first = __stolen_first;
281	__my_job._M_last = __gnu_parallel::min(__stolen_try,
282	__supposed_last);
283	__my_job._M_load = __my_job._M_last - __my_job._M_first + 1;
284
285	// Has potential work again.
286	# pragma omp atomic
287	++__busy;
288	__iam_working = true;
289
290	# pragma omp flush(__busy)
291	}
292	# pragma omp flush(__busy)
293	} // end while __busy > 0
294	// Add accumulated result to output.
295	omp_set_lock(&__output_lock);
296	__output = __r(__output, __result);
297	omp_unset_lock(&__output_lock);
298	}
299
300	delete[] __job;
301
302	// Points to last element processed (needed as return value for
303	// some algorithms like transform)
304	__f._M_finish_iterator = __begin + __length;
305
306	omp_destroy_lock(&__output_lock);
307
308	return __op;
309	}
310	} // end namespace
311
312	#endif /* _GLIBCXX_PARALLEL_WORKSTEALING_H */