Debian Codegraph @

include/deal.II/base/parallel.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2009 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_parallel_h
16 #define dealii_parallel_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/mutex.h>
23 #include <deal.II/base/std_cxx20/type_traits.h>
24 #include <deal.II/base/synchronous_iterator.h>
25 #include <deal.II/base/template_constraints.h>
26
27 #include <cstddef>
28 #include <functional>
29 #include <memory>
30 #include <tuple>
31
32 #ifdef DEAL_II_WITH_TASKFLOW
33 # include <deal.II/base/multithread_info.h>
34
35 # include <taskflow/algorithm/for_each.hpp>
36 # include <taskflow/taskflow.hpp>
37 #endif
38
39 #ifdef DEAL_II_WITH_TBB
40 # include <tbb/blocked_range.h>
41 # include <tbb/parallel_for.h>
42 # include <tbb/parallel_reduce.h>
43 # include <tbb/partitioner.h>
44 #else
45 # include <boost/range/iterator_range.hpp>
46 #endif
47
48 #ifdef DEAL_II_HAVE_CXX20
49 # include <concepts>
50 #endif
51
52
53 // TODO[WB]: allow calling functions to pass along a tbb::affinity_partitioner
54 // object to ensure that subsequent calls use the same cache lines
55
56 DEAL_II_NAMESPACE_OPEN
57
58 namespace parallel
59 {
60 namespace internal
61 {
62 /**
63 * Helper struct to tell us if we can use SIMD instructions for the given
64 * @p Number type.
65 */
66 template <typename Number>
67 struct EnableOpenMPSimdFor
68 {
69 static const bool value = true;
70 };
71
72 #ifdef __INTEL_COMPILER
73 // Disable long double SIMD instructions on ICC. This is to work around a
74 // bug that generates wrong code at least up to intel 15 (see
75 // tests/lac/vector-vector, tests/lac/intel-15-bug, and the discussion at
76 // https://github.com/dealii/dealii/issues/598).
77 template <>
78 struct EnableOpenMPSimdFor<long double>
79 {
80 static const bool value = false;
81 };
82 #endif
83
84 #ifdef DEAL_II_WITH_TASKFLOW
85 /**
86 * Internal function to do a parallel_for using taskflow
87 */
88 template <typename Iterator, typename Functor>
89 void
90 taskflow_parallel_for(Iterator x_begin,
91 Iterator x_end,
92 const Functor &functor,
93 const unsigned int grainsize)
94 {
95 tf::Executor &executor = MultithreadInfo::get_taskflow_executor();
96 tf::Taskflow taskflow;
97
98 // TODO: We have several choices for the Partitioner and we should spend
99 // some time benchmarking them:
100 // 1. StaticPartitioner(grainsize): all work items have grainsize number
101 // of items
102 // 2. GuidedPartitioner(grainsize):
103 // "The size of a partition is proportional to the number of unassigned
104 // iterations divided by the number of workers, and the size will
105 // gradually decrease to the given chunk size."
106 // 3. GuidedPartitioner(0): The default.
107 taskflow.for_each(
108 x_begin,
109 x_end,
110 [&](const auto &item) { functor(item); },
111 tf::StaticPartitioner(grainsize));
112 executor.run(taskflow).wait();
113 }
114 #endif
115
116 #ifdef DEAL_II_WITH_TBB
117 /**
118 * Encapsulate tbb::parallel_for.
119 */
120 template <typename Iterator, typename Functor>
121 void
122 parallel_for(Iterator x_begin,
123 Iterator x_end,
124 const Functor &functor,
125 const unsigned int grainsize)
126 {
127 tbb::parallel_for(tbb::blocked_range<Iterator>(x_begin, x_end, grainsize),
128 functor,
129 tbb::auto_partitioner());
130 }
131
132
133
134 /**
135 * Encapsulate tbb::parallel_for when an affinite_partitioner is provided.
136 */
137 template <typename Iterator, typename Functor>
138 void
139 parallel_for(Iterator x_begin,
140 Iterator x_end,
141 const Functor &functor,
142 const unsigned int grainsize,
143 const std::shared_ptr<tbb::affinity_partitioner> &partitioner)
144 {
145 tbb::parallel_for(tbb::blocked_range<Iterator>(x_begin, x_end, grainsize),
146 functor,
147 *partitioner);
148 }
149
150 #else
151
152 /**
153 * Just execute things sequentially.
154 */
155 template <typename Iterator, typename Functor>
156 void
157 parallel_for(Iterator x_begin,
158 Iterator x_end,
159 const Functor &functor,
160 const unsigned int)
161 {
162 functor(boost::iterator_range<Iterator>(x_begin, x_end));
163 }
164
165 #endif
166 } // namespace internal
167
168 /**
169 * An algorithm that performs the action <code>*out++ =
170 * function(*in++)</code> where the <code>in</code> iterator ranges over
171 * the given input range.
172 *
173 * This algorithm does pretty much what std::transform does. The difference
174 * is that the function can run in parallel when deal.II is configured to
175 * use multiple threads.
176 *
177 * If running in parallel, the iterator range is split into several chunks
178 * that are each packaged up as a task and given to the Threading Building
179 * Blocks scheduler to work on as compute resources are available. The
180 * function returns once all chunks have been worked on. The last argument
181 * denotes the minimum number of elements of the iterator range per task;
182 * the number must be large enough to amortize the startup cost of new
183 * tasks, and small enough to ensure that tasks can be reasonably load
184 * balanced.
185 *
186 * For a discussion of the kind of problems to which this function is
187 * applicable, see the
188 * @ref threads "Parallel computing with multiple processors"
189 * topic.
190 *
191 * @dealiiConceptRequires{(std::invocable<Function,
192 * decltype(*std::declval<InputIterator>())> &&
193 * std::assignable_from<decltype(*std::declval<OutputIterator>()),
194 * std::invoke_result_t<Function,
195 * decltype(*std::declval<InputIterator>())>>)}
196 */
197 template <typename InputIterator, typename OutputIterator, typename Function>
198 DEAL_II_CXX20_REQUIRES(
199 (std::invocable<Function, decltype(*std::declval<InputIterator>())> &&
200 std::assignable_from<
201 decltype(*std::declval<OutputIterator>()),
202 std::invoke_result_t<Function,
203 decltype(*std::declval<InputIterator>())>>))
204 DEAL_II_DEPRECATED_EARLY void transform(const InputIterator &begin_in,
205 const InputIterator &end_in,
206 OutputIterator out,
207 const Function &function,
208 const unsigned int grainsize)
209 {
210 #ifdef DEAL_II_WITH_TASKFLOW
211 using Iterators = std::tuple<InputIterator, OutputIterator>;
212 using SyncIterators = SynchronousIterators<Iterators>;
213 Iterators x_begin(begin_in, out);
214 Iterators x_end(end_in, OutputIterator());
215
216 internal::taskflow_parallel_for(
217 SyncIterators(x_begin),
218 SyncIterators(x_end),
219 [function](const auto &it) {
220 *std::get<1>(it) = function(*std::get<0>(it));
221 },
222 grainsize);
223
224 #elif defined(DEAL_II_WITH_TBB)
225 using Iterators = std::tuple<InputIterator, OutputIterator>;
226 using SyncIterators = SynchronousIterators<Iterators>;
227 Iterators x_begin(begin_in, out);
228 Iterators x_end(end_in, OutputIterator());
229 internal::parallel_for(
230 SyncIterators(x_begin),
231 SyncIterators(x_end),
232 [function](const auto &range) {
233 for (const auto &p : range)
234 *std::get<1>(p) = function(*std::get<0>(p));
235 },
236 grainsize);
237 #else
238 // make sure we don't get compiler
239 // warnings about unused arguments
240 (void)grainsize;
241
242 for (InputIterator in = begin_in; in != end_in;)
243 *out++ = function(*in++);
244 #endif
245 }
246
247
248
249 /**
250 * An algorithm that performs the action <code>*out++ = function(*in1++,
251 * *in2++)</code> where the <code>in1</code> iterator ranges over the given
252 * input range, using the parallel for operator of tbb.
253 *
254 * This algorithm does pretty much what std::transform does. The difference
255 * is that the function can run in parallel when deal.II is configured to
256 * use multiple threads.
257 *
258 * If running in parallel, the iterator range is split into several chunks
259 * that are each packaged up as a task and given to the Threading Building
260 * Blocks scheduler to work on as compute resources are available. The
261 * function returns once all chunks have been worked on. The last argument
262 * denotes the minimum number of elements of the iterator range per task;
263 * the number must be large enough to amortize the startup cost of new
264 * tasks, and small enough to ensure that tasks can be reasonably load
265 * balanced.
266 *
267 * For a discussion of the kind of problems to which this function is
268 * applicable, see the
269 * @ref threads "Parallel computing with multiple processors"
270 * topic.
271 *
272 * @dealiiConceptRequires{(std::invocable<Function,
273 * decltype(*std::declval<InputIterator1>()),
274 * decltype(*std::declval<InputIterator2>())> &&
275 * std::assignable_from<decltype(*std::declval<OutputIterator>()),
276 * std::invoke_result_t<Function,
277 * decltype(*std::declval<InputIterator1>()),
278 * decltype(*std::declval<InputIterator2>())>>)}
279 */
280 template <typename InputIterator1,
281 typename InputIterator2,
282 typename OutputIterator,
283 typename Function>
284 DEAL_II_CXX20_REQUIRES(
285 (std::invocable<Function,
286 decltype(*std::declval<InputIterator1>()),
287 decltype(*std::declval<InputIterator2>())> &&
288 std::assignable_from<
289 decltype(*std::declval<OutputIterator>()),
290 std::invoke_result_t<Function,
291 decltype(*std::declval<InputIterator1>()),
292 decltype(*std::declval<InputIterator2>())>>))
293 DEAL_II_DEPRECATED_EARLY void transform(const InputIterator1 &begin_in1,
294 const InputIterator1 &end_in1,
295 InputIterator2 in2,
296 OutputIterator out,
297 const Function &function,
298 const unsigned int grainsize)
299 {
300 #ifdef DEAL_II_WITH_TASKFLOW
301 using Iterators =
302 std::tuple<InputIterator1, InputIterator2, OutputIterator>;
303 using SyncIterators = SynchronousIterators<Iterators>;
304 Iterators x_begin(begin_in1, in2, out);
305 Iterators x_end(end_in1, InputIterator2(), OutputIterator());
306
307 internal::taskflow_parallel_for(
308 SyncIterators(x_begin),
309 SyncIterators(x_end),
310 [function](const auto &it) {
311 *std::get<2>(it) = function(*std::get<0>(it), *std::get<1>(it));
312 },
313 grainsize);
314
315 #elif defined(DEAL_II_WITH_TBB)
316 using Iterators =
317 std::tuple<InputIterator1, InputIterator2, OutputIterator>;
318 using SyncIterators = SynchronousIterators<Iterators>;
319 Iterators x_begin(begin_in1, in2, out);
320 Iterators x_end(end_in1, InputIterator2(), OutputIterator());
321 internal::parallel_for(
322 SyncIterators(x_begin),
323 SyncIterators(x_end),
324 [function](const auto &range) {
325 for (const auto &p : range)
326 *std::get<2>(p) = function(*std::get<0>(p), *std::get<1>(p));
327 },
328 grainsize);
329
330 #else
331 // make sure we don't get compiler
332 // warnings about unused arguments
333 (void)grainsize;
334
335 for (InputIterator1 in1 = begin_in1; in1 != end_in1;)
336 *out++ = function(*in1++, *in2++);
337 #endif
338 }
339
340
341
342 /**
343 * An algorithm that performs the action <code>*out++ = function(*in1++,
344 * *in2++, *in3++)</code> where the <code>in1</code> iterator ranges over
345 * the given input range.
346 *
347 * This algorithm does pretty much what std::transform does. The difference
348 * is that the function can run in parallel when deal.II is configured to
349 * use multiple threads.
350 *
351 * If running in parallel, the iterator range is split into several chunks
352 * that are each packaged up as a task and given to the Threading Building
353 * Blocks scheduler to work on as compute resources are available. The
354 * function returns once all chunks have been worked on. The last argument
355 * denotes the minimum number of elements of the iterator range per task;
356 * the number must be large enough to amortize the startup cost of new
357 * tasks, and small enough to ensure that tasks can be reasonably load
358 * balanced.
359 *
360 * For a discussion of the kind of problems to which this function is
361 * applicable, see the
362 * @ref threads "Parallel computing with multiple processors"
363 * topic.
364 *
365 * @dealiiConceptRequires{(std::invocable<Function,
366 * decltype(*std::declval<InputIterator1>()),
367 * decltype(*std::declval<InputIterator2>()),
368 * decltype(*std::declval<InputIterator3>())> &&
369 * std::assignable_from<decltype(*std::declval<OutputIterator>()),
370 * std::invoke_result_t<Function,
371 * decltype(*std::declval<InputIterator1>()),
372 * decltype(*std::declval<InputIterator2>()),
373 * decltype(*std::declval<InputIterator3>())>>)}
374 */
375 template <typename InputIterator1,
376 typename InputIterator2,
377 typename InputIterator3,
378 typename OutputIterator,
379 typename Function>
380 DEAL_II_CXX20_REQUIRES(
381 (std::invocable<Function,
382 decltype(*std::declval<InputIterator1>()),
383 decltype(*std::declval<InputIterator2>()),
384 decltype(*std::declval<InputIterator3>())> &&
385 std::assignable_from<
386 decltype(*std::declval<OutputIterator>()),
387 std::invoke_result_t<Function,
388 decltype(*std::declval<InputIterator1>()),
389 decltype(*std::declval<InputIterator2>()),
390 decltype(*std::declval<InputIterator3>())>>))
391 DEAL_II_DEPRECATED_EARLY void transform(const InputIterator1 &begin_in1,
392 const InputIterator1 &end_in1,
393 InputIterator2 in2,
394 InputIterator3 in3,
395 OutputIterator out,
396 const Function &function,
397 const unsigned int grainsize)
398 {
399 #ifdef DEAL_II_WITH_TASKFLOW
400 using Iterators = std::
401 tuple<InputIterator1, InputIterator2, InputIterator3, OutputIterator>;
402 using SyncIterators = SynchronousIterators<Iterators>;
403 Iterators x_begin(begin_in1, in2, in3, out);
404 Iterators x_end(end_in1,
405 InputIterator2(),
406 InputIterator3(),
407 OutputIterator());
408
409 internal::taskflow_parallel_for(
410 SyncIterators(x_begin),
411 SyncIterators(x_end),
412 [function](const auto &it) {
413 *std::get<3>(it) =
414 function(*std::get<0>(it), *std::get<1>(it), *std::get<2>(it));
415 },
416 grainsize);
417
418 #elif defined(DEAL_II_WITH_TBB)
419 using Iterators = std::
420 tuple<InputIterator1, InputIterator2, InputIterator3, OutputIterator>;
421 using SyncIterators = SynchronousIterators<Iterators>;
422 Iterators x_begin(begin_in1, in2, in3, out);
423 Iterators x_end(end_in1,
424 InputIterator2(),
425 InputIterator3(),
426 OutputIterator());
427 internal::parallel_for(
428 SyncIterators(x_begin),
429 SyncIterators(x_end),
430 [function](const auto &range) {
431 for (const auto &p : range)
432 *std::get<3>(p) =
433 function(*std::get<0>(p), *std::get<1>(p), *std::get<2>(p));
434 },
435 grainsize);
436 #else
437 // make sure we don't get compiler
438 // warnings about unused arguments
439 (void)grainsize;
440
441 for (OutputIterator in1 = begin_in1; in1 != end_in1;)
442 *out++ = function(*in1++, *in2++, *in3++);
443 #endif
444 }
445
446
447 namespace internal
448 {
449 #ifdef DEAL_II_WITH_TBB
450 /**
451 * Take a range argument and call the given function with its begin and
452 * end.
453 *
454 * @dealiiConceptRequires{(std::invocable<Function, Iterator, Iterator>)}
455 */
456 template <typename Iterator, typename Function>
457 DEAL_II_CXX20_REQUIRES((std::invocable<Function, Iterator, Iterator>))
458 void apply_to_subranges(const tbb::blocked_range<Iterator> &range,
459 const Function &f)
460 {
461 f(range.begin(), range.end());
462 }
463 #endif
464 } // namespace internal
465
466
467 /**
468 * This function applies the given function argument @p f to all elements in
469 * the range <code>[begin,end)</code> and may do so in parallel. An example
470 * of its use is given in step-69.
471 *
472 * However, in many cases it is not efficient to call a function on each
473 * element, so this function calls the given function object on sub-ranges.
474 * In other words: if the given range <code>[begin,end)</code> is smaller
475 * than grainsize or if multithreading is not enabled, then we call
476 * <code>f(begin,end)</code>; otherwise, we may execute, possibly in
477 * %parallel, a sequence of calls <code>f(b,e)</code> where
478 * <code>[b,e)</code> are subintervals of <code>[begin,end)</code> and the
479 * collection of calls we do to <code>f(.,.)</code> will happen on disjoint
480 * subintervals that collectively cover the original interval
481 * <code>[begin,end)</code>.
482 *
483 * Oftentimes, the called function will of course have to get additional
484 * information, such as the object to work on for a given value of the
485 * iterator argument. This can be achieved by <i>binding</i> certain
486 * arguments. For example, here is an implementation of a matrix-vector
487 * multiplication $y=Ax$ for a full matrix $A$ and vectors $x,y$:
488 * @code
489 * void matrix_vector_product (const FullMatrix &A,
490 * const Vector &x,
491 * Vector &y)
492 * {
493 * parallel::apply_to_subranges
494 * (0, A.n_rows(),
495 * [&](const unsigned int begin_row,
496 * const unsigned int end_row)
497 * {
498 * mat_vec_on_subranges(begin_row, end_row, A, x, y);
499 * },
500 * 50);
501 * }
502 *
503 * void mat_vec_on_subranges (const unsigned int begin_row,
504 * const unsigned int end_row,
505 * const FullMatrix &A,
506 * const Vector &x,
507 * Vector &y)
508 * {
509 * for (unsigned int row=begin_row; row!=end_row; ++row)
510 * for (unsigned int col=0; col<x.size(); ++col)
511 * y(row) += A(row,col) * x(col);
512 * }
513 * @endcode
514 *
515 * Note how we use the lambda function to convert
516 * <code>mat_vec_on_subranges</code> from a function that takes 5 arguments
517 * to one taking 2 by binding the remaining arguments. The resulting function
518 * object requires only two arguments, `begin_row` and `end_row`, with all
519 * other arguments fixed.
520 *
521 * The code, if in single-thread mode, will call
522 * <code>mat_vec_on_subranges</code> on the entire range
523 * <code>[0,n_rows)</code> exactly once. In multi-threaded mode, however, it
524 * may be called multiple times on subranges of this interval, possibly
525 * allowing more than one CPU core to take care of part of the work.
526 *
527 * The @p grainsize argument (50 in the example above) makes sure that
528 * subranges do not become too small, to avoid spending more time on
529 * scheduling subranges to CPU resources than on doing actual work.
530 *
531 * For a discussion of the kind of problems to which this function is
532 * applicable, see also the
533 * @ref threads "Parallel computing with multiple processors"
534 * topic.
535 *
536 * @dealiiConceptRequires{(std::invocable<Function, Iterator, Iterator>)}
537 */
538 template <typename Iterator, typename Function>
539 DEAL_II_CXX20_REQUIRES((std::invocable<Function, Iterator, Iterator>))
540 void apply_to_subranges(const Iterator &begin,
541 const std_cxx20::type_identity_t<Iterator> &end,
542 const Function &f,
543 const unsigned int grainsize)
544 {
545 #ifndef DEAL_II_WITH_TBB
546 // make sure we don't get compiler
547 // warnings about unused arguments
548 (void)grainsize;
549
550 f(begin, end);
551 #else
552 internal::parallel_for(
553 begin,
554 end,
555 [&f](const tbb::blocked_range<Iterator> &range) {
556 internal::apply_to_subranges<Iterator, Function>(range, f);
557 },
558 grainsize);
559 #endif
560 }
561
562
563
564 /**
565 * This is a class specialized to for loops with a fixed range given by
566 * unsigned integers. This is an abstract base class that an actual worker
567 * function is derived from. There is a public function apply that issues a
568 * for loop in parallel, subdividing the work onto available processor cores
569 * whenever there is enough work to be done (i.e., the number of elements is
570 * larger than grain_size). Inside the function, a virtual function
571 * apply_to_subrange specifying a range of two integers <tt>[lower,
572 * upper)</tt> is called which needs to be defined in a derived class.
573 *
574 * The parallelization cases covered by this class are a subset of what is
575 * possible with the function apply_to_subranges (which also covers the case
576 * of more general iterators that might not be described by an integer
577 * range). However, for simple integer ranges one might prefer this class,
578 * like when there are many structurally similar loops, e.g., some simple
579 * copy or arithmetic operations on an array of pointers. In that case,
580 * apply_to_subranges will generate a lot of code (or rather, a lot of
581 * symbols) because it passes the long names generated by std::bind to the
582 * templated parallel for functions in TBB. This can considerably increase
583 * compile times and the size of the object code. Similarly, the incorrect
584 * use of std::bind often results in very cryptic error messages, which can
585 * be avoided by this class (only a virtual function needs to be defined in
586 * a derived class). Finally, the additional cost of a virtual function is
587 * negligible in the context of parallel functions: It is much more
588 * expensive to actually issue the work onto a thread, which in turn should
589 * be much less than the actual work done in the for loop.
590 */
591 struct ParallelForInteger
592 {
593 /**
594 * Destructor. Made virtual to ensure that derived classes also have
595 * virtual destructors.
596 */
597 virtual ~ParallelForInteger() = default;
598
599 /**
600 * This function runs the for loop over the given range
601 * <tt>[lower,upper)</tt>, possibly in parallel when end-begin is larger
602 * than the minimum parallel grain size. This function is marked const
603 * because it any operation that changes the data of a derived class will
604 * inherently not be thread-safe when several threads work with the same
605 * data simultaneously.
606 */
607 void
608 apply_parallel(const std::size_t begin,
609 const std::size_t end,
610 const std::size_t minimum_parallel_grain_size) const;
611
612 /**
613 * Virtual function for working on subrange to be defined in a derived
614 * class. This function is marked const because it any operation that
615 * changes the data of a derived class will inherently not be thread-safe
616 * when several threads work with the same data simultaneously.
617 */
618 virtual void
619 apply_to_subrange(const std::size_t, const std::size_t) const = 0;
620 };
621
622
623
624 /**
625 * This function works a lot like the apply_to_subranges() function, but it
626 * allows to accumulate numerical results computed on each subrange into one
627 * number. The type of this number is given by the `ResultType` template
628 * argument that needs to be explicitly specified, and results are added
629 * up (i.e., the reduction of results from subranges happens by adding up
630 * these results).
631 *
632 * An example of use of this function is to compute the value of the
633 * expression $x^T A x$ for a square matrix $A$ and a vector $x$. The sum
634 * over rows can be parallelized and the whole code might look like this:
635 * @code
636 * void matrix_norm (const FullMatrix &A,
637 * const Vector &x)
638 * {
639 * return
640 * std::sqrt
641 * (parallel::accumulate_from_subranges<double>
642 * ([&](const unsigned int begin_row,
643 * const unsigned int end_row)
644 * {
645 * mat_norm_sqr_on_subranges(begin_row, end_row, A, x);
646 * },
647 * 0, A.n_rows(),
648 * 50);
649 * }
650 *
651 * double
652 * mat_norm_sqr_on_subranges (const unsigned int begin_row,
653 * const unsigned int end_row,
654 * const FullMatrix &A,
655 * const Vector &x)
656 * {
657 * double norm_sqr = 0;
658 * for (unsigned int row=begin_row; row!=end_row; ++row)
659 * for (unsigned int col=0; col<x.size(); ++col)
660 * norm_sqr += x(row) * A(row,col) * x(col);
661 * return norm_sqr;
662 * }
663 * @endcode
664 *
665 * Here, <code>mat_norm_sqr_on_subranges</code> is called on the entire
666 * range <code>[0,A.n_rows())</code> if this range is less than the minimum
667 * grainsize (above chosen as 50) or if deal.II is configured to not use
668 * multithreading. Otherwise, it may be called on subsets of the given
669 * range, with results from the individual subranges accumulated internally.
670 *
671 * @warning If ResultType is a floating point type, then accumulation is not
672 * an associative operation. In other words, if the given function object is
673 * called three times on three subranges, returning values $a,b,c$, then the
674 * returned result of this function is $(a+b)+c$. However, depending on how
675 * the three sub-tasks are distributed on available CPU resources, the
676 * result may also be $(a+c)+b$ or any other permutation; because floating
677 * point addition is not associative (as opposed, of course, to addition of
678 * real %numbers), the result of invoking this function several times may
679 * differ on the order of round-off.
680 *
681 * For a discussion of the kind of problems to which this function is
682 * applicable, see also the
683 * @ref threads "Parallel computing with multiple processors"
684 * topic.
685 *
686 * @dealiiConceptRequires{(std::invocable<Function, Iterator, Iterator> &&
687 * std::convertible_to<std::invoke_result_t<Function, Iterator, Iterator>,
688 * ResultType>)}
689 */
690 template <typename ResultType, typename Iterator, typename Function>
691 DEAL_II_CXX20_REQUIRES(
692 (std::invocable<Function, Iterator, Iterator> &&
693 std::convertible_to<std::invoke_result_t<Function, Iterator, Iterator>,
694 ResultType>))
695 ResultType
696 accumulate_from_subranges(const Function &f,
697 const Iterator &begin,
698 const std_cxx20::type_identity_t<Iterator> &end,
699 const unsigned int grainsize)
700 {
701 #ifndef DEAL_II_WITH_TBB
702 // make sure we don't get compiler
703 // warnings about unused arguments
704 (void)grainsize;
705
706 return f(begin, end);
707 #else
708 return tbb::parallel_reduce(
709 tbb::blocked_range<Iterator>(begin, end, grainsize),
710 ResultType(0),
711 [f](const auto &range, const ResultType &starting_value) {
712 ResultType value = starting_value;
713 value += f(range.begin(), range.end());
714 return value;
715 },
716 std::plus<ResultType>(),
717 tbb::auto_partitioner());
718 #endif
719 }
720
721
722 // --------------------- for loop affinity partitioner -----------------------
723
724 /**
725 * A class that wraps a TBB affinity partitioner in a thread-safe way. In
726 * Vector, we use a shared pointer to share an affinity partitioner
727 * between different vectors of the same size for improving data (and
728 * NUMA) locality. However, when an outer task does multiple vector
729 * operations, the shared pointer could lead to race conditions. This
730 * class only allows one instance to get a partitioner. The other objects
731 * cannot use that object and need to create their own copy.
732 */
733 namespace internal
734 {
735 class TBBPartitioner
736 {
737 public:
738 /**
739 * Constructor.
740 */
741 TBBPartitioner();
742
743 #ifdef DEAL_II_WITH_TBB
744 /**
745 * Destructor. Check that the object is not in use any more, i.e., all
746 * loops have been completed.
747 */
748 ~TBBPartitioner();
749
750 /**
751 * Return an affinity partitioner. In case the partitioner owned by the
752 * class is free, it is returned here. In case another thread has not
753 * released it yet, a new object is created. To free the partitioner
754 * again, return it by the release_one_partitioner() call.
755 */
756 std::shared_ptr<tbb::affinity_partitioner>
757 acquire_one_partitioner();
758
759 /**
760 * After using the partitioner in a tbb loop through
761 * acquire_one_partitioner(), this call makes the partitioner available
762 * again.
763 */
764 void
765 release_one_partitioner(
766 const std::shared_ptr<tbb::affinity_partitioner> &p);
767
768 private:
769 /**
770 * The stored partitioner that can accumulate knowledge over several
771 * runs of tbb::parallel_for
772 */
773 std::shared_ptr<tbb::affinity_partitioner> my_partitioner;
774
775 /**
776 * A flag to indicate whether the partitioner has been acquired but not
777 * released yet, i.e., it is in use somewhere else.
778 */
779 bool in_use;
780
781 /**
782 * A mutex to guard the access to the in_use flag.
783 */
784 Threads::Mutex mutex;
785 #endif
786 };
787 } // namespace internal
788 } // namespace parallel
789
790
791 namespace internal
792 {
793 namespace VectorImplementation
794 {
795 /**
796 * If we do computations on vectors in parallel (say, we add two vectors
797 * to get a third, and we do the loop over all elements in parallel), then
798 * this variable determines the minimum number of elements for which it is
799 * profitable to split a range of elements any further to distribute to
800 * different threads.
801 *
802 * This variable is available as a global writable variable in order to
803 * allow the testsuite to also test the parallel case. By default, it is
804 * set to several thousand elements, which is a case that the testsuite
805 * would not normally encounter. As a consequence, in the testsuite we set
806 * it to one -- a value that's hugely unprofitable but definitely tests
807 * parallel operations.
808 */
809 extern unsigned int minimum_parallel_grain_size;
810 } // namespace VectorImplementation
811
812
813 namespace SparseMatrixImplementation
814 {
815 /**
816 * Like internal::VectorImplementation::minimum_parallel_grain_size, but now
817 * denoting the number of rows of a matrix that should be worked on as a
818 * minimum.
819 */
820 extern unsigned int minimum_parallel_grain_size;
821 } // namespace SparseMatrixImplementation
822
823 } // end of namespace internal
824
825
826 /* --------------------------- inline functions ------------------------- */
827
828 namespace parallel
829 {
830 inline void
831 ParallelForInteger::apply_parallel(
832 const std::size_t begin,
833 const std::size_t end,
834 const std::size_t minimum_parallel_grain_size) const
835 {
836 #ifndef DEAL_II_WITH_TBB
837 // make sure we don't get compiler
838 // warnings about unused arguments
839 (void)minimum_parallel_grain_size;
840
841 apply_to_subrange(begin, end);
842 #else
843 internal::parallel_for(
844 begin,
845 end,
846 [this](const tbb::blocked_range<std::size_t> &range) {
847 apply_to_subrange(range.begin(), range.end());
848 },
849 minimum_parallel_grain_size);
850 #endif
851 }
852
853 } // end of namespace parallel
854
855 DEAL_II_NAMESPACE_CLOSE
856
857 #endif