| 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 |