Debian Codegraph @

include/deal.II/base/work_stream.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_work_stream_h
16 # define dealii_work_stream_h
17
18
19 # include <deal.II/base/config.h>
20
21 # include <deal.II/base/graph_coloring.h>
22 # include <deal.II/base/iterator_range.h>
23 # include <deal.II/base/multithread_info.h>
24 # include <deal.II/base/parallel.h>
25 # include <deal.II/base/std_cxx20/type_traits.h>
26 # include <deal.II/base/template_constraints.h>
27 # include <deal.II/base/thread_local_storage.h>
28 # include <deal.II/base/thread_management.h>
29
30 # ifdef DEAL_II_WITH_TBB
31 # ifdef DEAL_II_TBB_WITH_ONEAPI
32 # include <tbb/parallel_pipeline.h>
33 # else
34 # include <tbb/pipeline.h>
35 # endif
36 # include <tbb/blocked_range.h>
37 # endif
38
39 # ifdef DEAL_II_WITH_TASKFLOW
40 # include <taskflow/taskflow.hpp>
41 # endif
42
43 # include <functional>
44 # include <iterator>
45 # include <list>
46 # include <memory>
47 # include <utility>
48 # include <vector>
49
50 DEAL_II_NAMESPACE_OPEN
51
52
53
54 /**
55 * A namespace whose main template function supports running multiple threads
56 * each of which operates on a subset of the given range of objects. The class
57 * uses the Intel Threading Building Blocks (TBB) to load balance the
58 * individual subranges onto the available threads. For a lengthy discussion
59 * of the rationale of this class, see the
60 * @ref threads "Parallel computing with multiple processors"
61 * topic. It is used in the tutorial first in step-9, and again in step-13,
62 * step-14, step-32 and others.
63 *
64 * The class is built on the following premise: One frequently has some work
65 * that needs to be done on a sequence of objects; a prototypical example is
66 * assembling cell contributions to a system matrix or right hand side. In
67 * many such examples, part of the work can be done entirely independently and
68 * in parallel, possibly using several processor cores on a machine with
69 * shared memory. However, some other part of this work may need to be
70 * synchronized and be done in order. In the example of assembling a matrix,
71 * the computation of local contributions can be done entirely in parallel,
72 * but copying the local contributions into the global matrix requires some
73 * care: First, several threads can't write at the same time, but need to
74 * synchronize writing using a mutex; secondly, we want the order in which
75 * local contributions are added to the global matrix to be always the same
76 * because floating point addition is not commutative and adding local
77 * contributions to the global matrix in different orders leads to subtly
78 * different results that can affect the number of iterations for iterative
79 * solvers as well as the round-off error in the solution in random ways.
80 * Consequently, we want to ensure that only one thread at a time writes into
81 * the global matrix, and that results are copied in a stable and reproducible
82 * order.
83 *
84 * This class implements a framework for this work model. It works with a
85 * stream of objects given by an iterator range, runs a worker function in
86 * parallel on all of these objects and then passes each object to a
87 * postprocessor function that runs sequentially and gets objects in exactly
88 * the order in which they appear in the input iterator range. None of the
89 * synchronization work is exposed to the user of this class.
90 *
91 * Internally, the range given to the run() function of this class is split
92 * into a sequence of "items", which are then distributed according to some
93 * %internal algorithm onto the number of available threads. An item is an
94 * element of the range of iterators on which we are to operate; for example,
95 * for the purpose of assembling matrices or evaluating error indicators, an
96 * item could be a cell. The TBB library determines how many threads are
97 * created (typically as many as there are processor cores), but the number of
98 * items that may be active at any given time is specified by the argument to
99 * the constructor. It should be bigger or equal to the number of processor
100 * cores - the default is four times the number of cores on the current
101 * system.
102 *
103 * Items are created upon request by the TBB whenever one of the worker
104 * threads is idle or is expected to become idle. It is then handed off to a
105 * worker function, typically a member function of a main class. These worker
106 * functions are run in parallel on a number of threads, and there is no
107 * guarantee that they are asked to work on items in any particular order, in
108 * particular not necessarily in the order in which items are generated from
109 * the iterator range.
110 *
111 * Typically, worker functions need additional data, for example FEValues
112 * objects, input data vectors, etc, some of which can not be shared among
113 * threads. To this end, the run() function takes another template argument,
114 * ScratchData, which designates a type objects of which are stored with each
115 * item and which threads can use as private data without having to share them
116 * with other threads. The run() function takes an additional argument with an
117 * object of type ScratchData that is going to be copied for the arguments
118 * passed to each of the worker functions.
119 *
120 * In addition, worker functions store their results in objects of template
121 * type CopyData. These are then handed off to a separate function, called
122 * copier, that may use the stored results to transfer them into permanent
123 * storage. For example, it may copy the results of local contributions to a
124 * matrix computed by a worker function into the global matrix. In contrast to
125 * the worker function, however, only one instance of the copier is run at any
126 * given time; it can therefore safely copy local contributions into the
127 * global matrix without the need to lock the global object using a mutex or
128 * similar means. Furthermore, it is guaranteed that the copier is run with
129 * CopyData objects in the same order in which their associated items were
130 * created; consequently, even if worker threads may compute results in
131 * unspecified order, the copier always receives the results in exactly the
132 * same order as the items were created.
133 *
134 * Once an item is processed by the copier, it is deleted and the ScratchData
135 * and CopyData objects that were used in its computation are considered
136 * unused and may be re-used for the next invocation of the worker function,
137 * on this or another thread. However, the WorkStream functions make no
138 * attempt to reset these objects to any kind of pristine state -- a worker
139 * should assume that the CopyData object it gets handed has prior content
140 * and clear it first in whatever manner seems appropriate, before putting
141 * content into it that can later be processed again by the copier.
142 *
143 * The member variables in ScratchData and CopyData can be accessed
144 * independently of other concurrent uses of copies of these data structures.
145 * Therefore, it is perfectly fine to resize auxiliary data structures
146 * associated with ScratchData and CopyData to different lengths on each cell.
147 * For example, a vector holding densities at each quadrature point which is
148 * used with LocalIntegrators::L2::weighted_mass_matrix() to assemble the local
149 * matrix could be resized to the corresponding number of quadrature points of
150 * the current cell in DoFHandlers with hp-capabilities. Similarly, local
151 * stiffness matrix in CopyData can be resized in accordance with the number of
152 * local DoFs on the current cell.
153 *
154 * @note For integration over cells and faces, it is often useful to use
155 * methods more specific to the task than the current function (which doesn't
156 * care whether the iterators are over cells, vector elements, or any other
157 * kind of range). An implementation of an interface specifically suited to
158 * integration is the MeshWorker::mesh_loop() function.
159 *
160 * @note The functions in this namespace only really work in parallel when
161 * multithread mode was selected during deal.II configuration. Otherwise they
162 * simply work on each item sequentially.
163 *
164 * @ingroup threads
165 */
166 namespace WorkStream
167 {
168 /**
169 * The nested namespaces contain various implementations of the workstream
170 * algorithms.
171 */
172 namespace internal
173 {
174 /**
175 * A structure that contains a pointer to a scratch data object and a copy
176 * data object along with a flag that indicates whether this object is
177 * currently in use.
178 */
179 template <typename Iterator, typename ScratchData, typename CopyData>
180 struct ScratchAndCopyDataObjects
181 {
182 std::unique_ptr<ScratchData> scratch_data;
183 std::unique_ptr<CopyData> copy_data;
184 bool currently_in_use;
185
186 /**
187 * Default constructor.
188 */
189 ScratchAndCopyDataObjects()
190 : currently_in_use(false)
191 {}
192
193 ScratchAndCopyDataObjects(std::unique_ptr<ScratchData> &&p,
194 std::unique_ptr<CopyData> &&q,
195 const bool in_use)
196 : scratch_data(std::move(p))
197 , copy_data(std::move(q))
198 , currently_in_use(in_use)
199 {}
200
201 // Provide a copy constructor that actually doesn't copy the
202 // internal state. This makes handling ScratchAndCopyDataObjects
203 // easier to handle with STL containers.
204 ScratchAndCopyDataObjects(const ScratchAndCopyDataObjects &)
205 : currently_in_use(false)
206 {}
207 };
208
209 /**
210 * A structure that contains a pointer to a scratch data object
211 * along with a flag that indicates whether this object is currently
212 * in use.
213 */
214 template <typename ScratchData>
215 struct ScratchDataObject
216 {
217 std::unique_ptr<ScratchData> scratch_data;
218 bool currently_in_use;
219
220 /**
221 * Default constructor.
222 */
223 ScratchDataObject()
224 : currently_in_use(false)
225 {}
226
227 ScratchDataObject(std::unique_ptr<ScratchData> &&p, const bool in_use)
228 : scratch_data(std::move(p))
229 , currently_in_use(in_use)
230 {}
231
232 ScratchDataObject(ScratchData *p, const bool in_use)
233 : scratch_data(p)
234 , currently_in_use(in_use)
235 {}
236
237 // Provide a copy constructor that actually doesn't copy the
238 // internal state. This makes handling ScratchAndCopyDataObjects
239 // easier to handle with STL containers.
240 ScratchDataObject(const ScratchDataObject &)
241 : currently_in_use(false)
242 {}
243
244 ScratchDataObject(ScratchDataObject &&o) noexcept = default;
245 };
246
247 # ifdef DEAL_II_WITH_TBB
248 /**
249 * A namespace for the implementation of details of the WorkStream pattern
250 * and function. This namespace holds classes that deal with the second
251 * implementation described in the paper by Turcksin, Kronbichler and
252 * Bangerth (see
253 * @ref workstream_paper).
254 * Here, no coloring is provided, so copying is done sequentially using a
255 * TBB filter.
256 *
257 * Even though this implementation is slower than the third implementation
258 * discussed in that paper, we need to keep it around for two reasons: (i)
259 * a user may not give us a graph coloring, (ii) we want to use this
260 * implementation for colors that are just too small.
261 */
262 namespace tbb_no_coloring
263 {
264 /**
265 * A class that creates a sequence of items from a range of iterators.
266 */
267 template <typename Iterator, typename ScratchData, typename CopyData>
268 class IteratorRangeToItemStream
269 {
270 public:
271 /**
272 * A data type that we use to identify items to be worked on. This is
273 * the structure that is passed around between the different parts of
274 * the WorkStream implementation to identify what needs to be done by
275 * the various stages of the pipeline.
276 */
277 struct ItemType
278 {
279 /**
280 * Typedef to a list of scratch data objects. The rationale for this
281 * list is provided in the variables that use these lists.
282 */
283 using ScratchDataList = std::list<ScratchDataObject<ScratchData>>;
284
285 /**
286 * A list of iterators that need to be worked on. Only the first
287 * n_iterators are relevant.
288 */
289 std::vector<Iterator> iterators;
290
291 /**
292 * The CopyData objects that the Worker part of the pipeline fills
293 * for each work item. Again, only the first n_iterators elements are
294 * what we care about.
295 */
296 std::vector<CopyData> copy_datas;
297
298 /**
299 * Number of items identified by the iterators array that the
300 * Worker and Copier pipeline stage need to work on. The maximum
301 * value of this variable will be chunk_size.
302 */
303 unsigned int n_iterators;
304
305 /**
306 * Pointer to a thread local variable identifying the scratch data
307 * objects this thread will use. The initial implementation of this
308 * class using thread local variables provided only a single scratch
309 * object per thread. This doesn't work, because the worker
310 * functions may start tasks itself and then call
311 * Threads::TaskGroup::join_all() or a similar function, which the
312 * TBB scheduler may use to run something else on the current thread
313 * -- for example another instance of the worker function.
314 * Consequently, there would be two instances of the worker function
315 * that use the same scratch object if we only provided a single
316 * scratch object per thread. The solution is to provide a list of
317 * scratch objects for each thread, together with a flag indicating
318 * whether this scratch object is currently used. If a thread needs
319 * a scratch object, it walks this list until it finds an unused
320 * object, or, if there is none, creates one itself. Note that we
321 * need not use synchronization primitives for this process since
322 * the lists are thread-local and we are guaranteed that only a
323 * single thread accesses them as long as we have no yield point in
324 * between the accesses to the list.
325 *
326 * The pointers to scratch objects stored in each of these lists
327 * must be so that they are deleted on all threads when the thread
328 * local object is destroyed. This is achieved by using unique_ptr.
329 *
330 * Note that when a worker needs to create a scratch object, it
331 * allocates it using sample_scratch_data to copy from. This has the
332 * advantage of a first-touch initialization, i.e., the memory for
333 * the scratch data object is allocated and initialized by the same
334 * thread that will later use it.
335 */
336 Threads::ThreadLocalStorage<ScratchDataList> *scratch_data;
337
338 /**
339 * Pointer to a sample scratch data object, to be used to initialize
340 * the scratch data objects created for each individual thread.
341 */
342 const ScratchData *sample_scratch_data;
343
344 /**
345 * Flag is true if the buffer is used and false if the buffer can be
346 * used.
347 */
348 bool currently_in_use;
349
350
351 /**
352 * Default constructor. Initialize everything that doesn't have a
353 * default constructor itself.
354 */
355 ItemType()
356 : n_iterators(0)
357 , scratch_data(nullptr)
358 , sample_scratch_data(nullptr)
359 , currently_in_use(false)
360 {}
361 };
362
363
364 /**
365 * Constructor. Take an iterator range, the size of a buffer that can
366 * hold items, and the sample additional data object that will be
367 * passed to each worker and copier function invocation.
368 */
369 IteratorRangeToItemStream(const Iterator &begin,
370 const Iterator &end,
371 const unsigned int buffer_size,
372 const unsigned int chunk_size,
373 const ScratchData &sample_scratch_data,
374 const CopyData &sample_copy_data)
375 : remaining_iterator_range(begin, end)
376 , item_buffer(buffer_size)
377 , sample_scratch_data(sample_scratch_data)
378 , chunk_size(chunk_size)
379 {
380 // initialize the elements of the ring buffer
381 for (auto &item : item_buffer)
382 {
383 Assert(item.n_iterators == 0, ExcInternalError());
384
385 item.iterators.resize(chunk_size,
386 remaining_iterator_range.second);
387 item.scratch_data = &thread_local_scratch;
388 item.sample_scratch_data = &sample_scratch_data;
389 item.copy_datas.resize(chunk_size, sample_copy_data);
390 item.currently_in_use = false;
391 }
392 }
393
394
395 /**
396 * Create an item and return a pointer to it.
397 */
398 ItemType *
399 get_item()
400 {
401 // find first unused item. we know that there must be one
402 // because we have set the maximal number of tokens in flight
403 // and have set the ring buffer to have exactly this size. so
404 // if this function is called, we know that less than the
405 // maximal number of items in currently in flight
406 //
407 // note that we need not lock access to this array since
408 // the current stage is run sequentially and we can therefore
409 // enter the following block only once at any given time.
410 // thus, there can be no race condition between checking that
411 // a flag is false and setting it to true. (there may be
412 // another thread where we release items and set 'false'
413 // flags to 'true', but that too does not produce any
414 // problems)
415 ItemType *current_item = nullptr;
416 for (unsigned int i = 0; i < item_buffer.size(); ++i)
417 if (item_buffer[i].currently_in_use == false)
418 {
419 item_buffer[i].currently_in_use = true;
420 current_item = &item_buffer[i];
421 break;
422 }
423 Assert(current_item != nullptr,
424 ExcMessage("This can't be. There must be a free item!"));
425
426 // initialize the next item. it may
427 // consist of at most chunk_size
428 // elements
429 current_item->n_iterators = 0;
430 while ((remaining_iterator_range.first !=
431 remaining_iterator_range.second) &&
432 (current_item->n_iterators < chunk_size))
433 {
434 current_item->iterators[current_item->n_iterators] =
435 remaining_iterator_range.first;
436
437 ++remaining_iterator_range.first;
438 ++current_item->n_iterators;
439 }
440
441 if (current_item->n_iterators == 0)
442 // there were no items
443 // left. terminate the pipeline
444 return nullptr;
445 else
446 return current_item;
447 }
448
449 private:
450 /**
451 * The interval of iterators still to be worked on. This range will
452 * shrink over time.
453 */
454 std::pair<Iterator, Iterator> remaining_iterator_range;
455
456 /**
457 * A buffer that will store items.
458 */
459 std::vector<ItemType> item_buffer;
460
461 /**
462 * Pointer to a thread local variable identifying the scratch data
463 * objects this thread will use. The initial implementation of this
464 * class using thread local variables provided only a single scratch
465 * object per thread. This doesn't work, because the worker functions
466 * may start tasks itself and then call Threads::TaskGroup::join_all()
467 * or a similar function, which the TBB scheduler may use to run
468 * something else on the current thread -- for example another
469 * instance of the worker function. Consequently, there would be two
470 * instances of the worker function that use the same scratch object
471 * if we only provided a single scratch object per thread. The
472 * solution is to provide a list of scratch objects for each thread,
473 * together with a flag indicating whether this scratch object is
474 * currently used. If a thread needs a scratch object, it walks this
475 * list until it finds an unused object, or, if there is none, creates
476 * one itself. Note that we need not use synchronization primitives
477 * for this process since the lists are thread-local and we are
478 * guaranteed that only a single thread accesses them as long as we
479 * have no yield point in between the accesses to the list.
480 *
481 * The pointers to scratch objects stored in each of these lists must
482 * be so that they are deleted on all threads when the thread local
483 * object is destroyed. This is achieved by using unique_ptr.
484 *
485 * Note that when a worker needs to create a scratch object, it
486 * allocates it using sample_scratch_data to copy from. This has the
487 * advantage of a first-touch initialization, i.e., the memory for the
488 * scratch data object is allocated and initialized by the same thread
489 * that will later use it.
490 */
491 Threads::ThreadLocalStorage<typename ItemType::ScratchDataList>
492 thread_local_scratch;
493
494 /**
495 * A reference to a sample scratch data that will be used to
496 * initialize the thread-local pointers to a scratch data object each
497 * of the worker tasks uses.
498 */
499 const ScratchData &sample_scratch_data;
500
501 /**
502 * Number of elements of the iterator range that each thread should
503 * work on sequentially; a large number makes sure that each thread
504 * gets a significant amount of work before the next task switch
505 * happens, whereas a small number is better for load balancing.
506 */
507 const unsigned int chunk_size;
508 };
509
510
511
512 template <typename Worker,
513 typename Copier,
514 typename Iterator,
515 typename ScratchData,
516 typename CopyData>
517 void
518 run(const Iterator &begin,
519 const std_cxx20::type_identity_t<Iterator> &end,
520 Worker worker,
521 Copier copier,
522 const ScratchData &sample_scratch_data,
523 const CopyData &sample_copy_data,
524 const unsigned int queue_length,
525 const unsigned int chunk_size)
526 {
527 using ItemType = typename IteratorRangeToItemStream<Iterator,
528 ScratchData,
529 CopyData>::ItemType;
530
531 // Define the three stages of the pipeline:
532
533 //
534 // ----- Stage 1 -----
535 //
536 // The first stage is the one that provides us with chunks of data
537 // to work on (the stream of "items"). This stage will run sequentially.
538 IteratorRangeToItemStream<Iterator, ScratchData, CopyData>
539 iterator_range_to_item_stream(begin,
540 end,
541 queue_length,
542 chunk_size,
543 sample_scratch_data,
544 sample_copy_data);
545 auto item_generator = [&](tbb::flow_control &fc) -> ItemType * {
546 if (const auto item = iterator_range_to_item_stream.get_item())
547 return item;
548 else
549 {
550 fc.stop();
551 return nullptr;
552 }
553 };
554
555 //
556 // ----- Stage 2 -----
557 //
558 // The second stage is the one that does the actual work. This is the
559 // stage that runs in parallel
560 auto item_worker =
561 [worker =
562 std::function<void(const Iterator &, ScratchData &, CopyData &)>(
563 worker),
564 copier_exists =
565 static_cast<bool>(std::function<void(const CopyData &)>(copier))](
566 ItemType *current_item) {
567 // we need to find an unused scratch data object in the list that
568 // corresponds to the current thread and then mark it as used. if
569 // we can't find one, create one
570 //
571 // as discussed in the discussion of the documentation of the
572 // IteratorRangeToItemStream::scratch_data variable, there is no
573 // need to synchronize access to this variable using a mutex
574 // as long as we have no yield-point in between. this means that
575 // we can't take an iterator into the list now and expect it to
576 // still be valid after calling the worker, but we at least do
577 // not have to lock the following section
578 ScratchData *scratch_data = nullptr;
579 {
580 // see if there is an unused object. if so, grab it and mark
581 // it as used
582 for (auto &p : current_item->scratch_data->get())
583 if (p.currently_in_use == false)
584 {
585 scratch_data = p.scratch_data.get();
586 p.currently_in_use = true;
587
588 break;
589 }
590
591 // if no object was found, create one and mark it as used
592 if (scratch_data == nullptr)
593 {
594 scratch_data =
595 new ScratchData(*current_item->sample_scratch_data);
596 current_item->scratch_data->get().emplace_back(scratch_data,
597 true);
598 }
599 };
600
601 // then call the worker function on each element of the chunk we
602 // were given. since these worker functions are called on separate
603 // threads, nothing good can happen if they throw an exception and
604 // we are best off catching it and showing an error message
605 for (unsigned int i = 0; i < current_item->n_iterators; ++i)
606 {
607 try
608 {
609 if (worker)
610 worker(current_item->iterators[i],
611 *scratch_data,
612 current_item->copy_datas[i]);
613 }
614 catch (const std::exception &exc)
615 {
616 Threads::internal::handle_std_exception(exc);
617 }
618 catch (...)
619 {
620 Threads::internal::handle_unknown_exception();
621 }
622 }
623
624 // finally mark the scratch object as unused again. as above, there
625 // is no need to lock anything here since the object we work on
626 // is thread-local
627 for (auto &p : current_item->scratch_data->get())
628 if (p.scratch_data.get() == scratch_data)
629 {
630 Assert(p.currently_in_use == true, ExcInternalError());
631 p.currently_in_use = false;
632
633 break;
634 }
635
636 // if there is no copier, mark current item as usable again
637 if (copier_exists == false)
638 current_item->currently_in_use = false;
639
640
641 // Then return the original pointer
642 // to the now modified object. The copier will work on it next.
643 return current_item;
644 };
645
646 //
647 // ----- Stage 3 -----
648 //
649 // The last stage is the one that copies data from the CopyData objects
650 // to the final destination. This stage runs sequentially again.
651 auto item_copier = [copier = std::function<void(const CopyData &)>(
652 copier)](ItemType *current_item) {
653 if (copier)
654 {
655 // Initiate copying data. For the same reasons as in the worker
656 // class above, catch exceptions rather than letting them
657 // propagate into unknown territories:
658 for (unsigned int i = 0; i < current_item->n_iterators; ++i)
659 {
660 try
661 {
662 copier(current_item->copy_datas[i]);
663 }
664 catch (const std::exception &exc)
665 {
666 Threads::internal::handle_std_exception(exc);
667 }
668 catch (...)
669 {
670 Threads::internal::handle_unknown_exception();
671 }
672 }
673 }
674 // mark current item as usable again
675 current_item->currently_in_use = false;
676 };
677
678
679 // Now we just have to set up the pipeline and run it:
680 auto tbb_item_stream_filter = tbb::make_filter<void, ItemType *>(
681 # ifdef DEAL_II_TBB_WITH_ONEAPI
682 tbb::filter_mode::serial_in_order,
683 # else
684 tbb::filter::serial,
685 # endif
686 item_generator);
687
688 auto tbb_worker_filter = tbb::make_filter<ItemType *, ItemType *>(
689 # ifdef DEAL_II_TBB_WITH_ONEAPI
690 tbb::filter_mode::parallel,
691 # else
692 tbb::filter::parallel,
693 # endif
694 item_worker);
695
696 auto tbb_copier_filter = tbb::make_filter<ItemType *, void>(
697 # ifdef DEAL_II_TBB_WITH_ONEAPI
698 tbb::filter_mode::serial_in_order,
699 # else
700 tbb::filter::serial,
701 # endif
702 item_copier);
703
704 tbb::parallel_pipeline(queue_length,
705 tbb_item_stream_filter & tbb_worker_filter &
706 tbb_copier_filter);
707 }
708
709 } // namespace tbb_no_coloring
710 # endif // DEAL_II_WITH_TBB
711
712
713
714 # ifdef DEAL_II_WITH_TASKFLOW
715 /**
716 * Mostly a copy of the 2nd implementation of the Workstream paper taking
717 * advantage of thread local lists for re-use. Uses taskflow for task
718 * scheduling rather than TBB. Currently does not support chunking.
719 */
720
721
722 namespace taskflow_no_coloring
723 {
724 /**
725 * The main run function for the taskflow colorless implementation. The
726 * last two arguments in this function are for chunking support which
727 * currently does not exist but ideally will later. For now they are
728 * ignored but still here to permit existing programs to function
729 */
730 template <typename Worker,
731 typename Copier,
732 typename Iterator,
733 typename ScratchData,
734 typename CopyData>
735 void
736 run(const Iterator &begin,
737 const std_cxx20::type_identity_t<Iterator> &end,
738 Worker worker,
739 Copier copier,
740 const ScratchData &sample_scratch_data,
741 const CopyData &sample_copy_data,
742 const unsigned int /*queue_length*/ = 2 *
743 MultithreadInfo::n_threads(),
744 const unsigned int chunk_size = 8)
745
746 {
747 tf::Executor &executor = MultithreadInfo::get_taskflow_executor();
748 tf::Taskflow taskflow;
749
750 using ScratchDataList = std::list<ScratchDataObject<ScratchData>>;
751
752 Threads::ThreadLocalStorage<ScratchDataList>
753 thread_safe_scratch_data_list;
754
755 tf::Task last_copier;
756
757
758 // A collection of chunk_size copy objects which each represent the
759 // contribution of a single worker. Chunk_size workers are thus chunked
760 // together by having their outputs stored in this object in a single
761 // task.
762 struct CopyChunk
763 {
764 std::vector<CopyData> copy_datas;
765
766 CopyChunk(const unsigned int chunk_size,
767 const CopyData &sample_copy_data)
768 : copy_datas(chunk_size, sample_copy_data)
769 {}
770 };
771
772 // idx is used to connect each worker to its copier as communication
773 // between tasks is not supported. It does this by providing a unique
774 // index in the vector of pointers copy_datas at which the copy data
775 // object where the work done by work task #idx is stored
776 unsigned int idx = 0;
777
778 // A collection of handles to a CopyChunk object for each chunk. The
779 // actual data will be allocated only when a worker arrives at this
780 // chunk and will be freed as soon as the result has been copied.
781 std::vector<std::unique_ptr<CopyChunk>> copy_chunks;
782
783 std::vector<Iterator> chunk;
784 chunk.reserve(chunk_size);
785
786 unsigned int total_chunks = 0;
787 unsigned int chunk_counter = 0;
788
789 // Generate a static task graph. Here we generate a task for each cell
790 // that will be worked on. The tasks are not executed until all of them
791 // are created, this code runs sequentially.
792 for (Iterator it = begin; it != end;)
793 {
794 for (; (chunk_counter < chunk_size) && (it != end);
795 ++it, ++chunk_counter)
796 chunk.emplace_back(it);
797 ++total_chunks;
798 // Create a worker task.
799 auto worker_task =
800 taskflow
801 .emplace([chunk,
802 idx,
803 chunk_counter,
804 &thread_safe_scratch_data_list,
805 &sample_scratch_data,
806 &sample_copy_data,
807 &copy_chunks,
808 &worker]() {
809 ScratchData *scratch_data = nullptr;
810
811 ScratchDataList &scratch_data_list =
812 thread_safe_scratch_data_list.get();
813 // We need to find an unused scratch data object in the list
814 // that corresponds to the current thread and then mark it as
815 // used. if we can't find one, create one. There is no need to
816 // synchronize access to this variable using a mutex since
817 // each object is local to its own thread.
818 for (auto &p : scratch_data_list)
819 {
820 if (p.currently_in_use == false)
821 {
822 scratch_data = p.scratch_data.get();
823 p.currently_in_use = true;
824 break;
825 }
826 }
827 // If no element in the list was found, create
828 // one and mark it as used.
829 if (scratch_data == nullptr)
830 {
831 scratch_data_list.emplace_back(
832 std::make_unique<ScratchData>(sample_scratch_data),
833 true);
834 scratch_data =
835 scratch_data_list.back().scratch_data.get();
836 }
837
838 // Create a unique copy chunk object where this
839 // worker's work will be stored.
840 copy_chunks[idx] =
841 std::make_unique<CopyChunk>(chunk_counter,
842 sample_copy_data);
843 auto copy_chunk = copy_chunks[idx].get();
844 unsigned int i = 0;
845 for (auto &it : chunk)
846 {
847 worker(it, *scratch_data, copy_chunk->copy_datas[i]);
848 ++i;
849 }
850
851 // Find our currently used scratch data and
852 // mark it as unused.
853 for (auto &p : scratch_data_list)
854 {
855 if (p.scratch_data.get() == scratch_data)
856 {
857 Assert(p.currently_in_use == true,
858 ExcInternalError());
859 p.currently_in_use = false;
860 }
861 }
862 })
863 .name("worker");
864
865 // Create a copier task. This task is a separate object from the
866 // worker task.
867 tf::Task copier_task =
868 taskflow
869 .emplace([idx, &copy_chunks, &copier]() {
870 auto copy_chunk = copy_chunks[idx].get();
871 for (auto &copy_data : copy_chunk->copy_datas)
872 {
873 copier(copy_data);
874 }
875 // Finally free the memory.
876 copy_chunks[idx].reset();
877 })
878 .name("copy");
879
880 // Ensure the copy task runs after the worker task.
881 worker_task.precede(copier_task);
882
883 // Ensure that only one copy task can run at a time. The code
884 // below makes each copy task wait until the previous one has
885 // finished before it can start
886 if (!last_copier.empty())
887 last_copier.precede(copier_task);
888
889 // Keep a handle to the last copier. Tasks in taskflow are
890 // basically handles to internally stored data, so this does not
891 // perform a copy:
892 last_copier = copier_task;
893 ++idx;
894 chunk_counter = 0;
895 chunk.clear();
896 }
897 copy_chunks.resize(total_chunks);
898 // Now we run all the tasks in the task graph. They will be run in
899 // parallel and are eligible to run when their dependencies established
900 // above are met.
901 executor.run(taskflow).wait();
902 }
903 } // namespace taskflow_no_coloring
904 # endif
905
906 /**
907 * A reference implementation without using multithreading to be used if we
908 * don't have multithreading support or if the user requests to run things
909 * sequentially. This is more efficient than using TBB or taskflow if we
910 * only have a single thread.
911 */
912 namespace sequential
913 {
914 /**
915 * Sequential version without colors.
916 */
917 template <typename Worker,
918 typename Copier,
919 typename Iterator,
920 typename ScratchData,
921 typename CopyData>
922 void
923 run(const Iterator &begin,
924 const std_cxx20::type_identity_t<Iterator> &end,
925 Worker worker,
926 Copier copier,
927 const ScratchData &sample_scratch_data,
928 const CopyData &sample_copy_data)
929 {
930 // need to copy the sample since it is marked const
931 ScratchData scratch_data = sample_scratch_data;
932 CopyData copy_data = sample_copy_data; // NOLINT
933
934 // Optimization: Check if the functions are not the zero function. To
935 // check zero-ness, create a C++ function out of it:
936 const bool have_worker =
937 (static_cast<const std::function<
938 void(const Iterator &, ScratchData &, CopyData &)> &>(worker)) !=
939 nullptr;
940 const bool have_copier =
941 (static_cast<const std::function<void(const CopyData &)> &>(
942 copier)) != nullptr;
943
944 // Finally loop over all items and perform the necessary work:
945 for (Iterator i = begin; i != end; ++i)
946 {
947 if (have_worker)
948 worker(i, scratch_data, copy_data);
949 if (have_copier)
950 copier(copy_data);
951 }
952 }
953
954
955
956 /**
957 * Sequential version with colors
958 */
959 template <typename Worker,
960 typename Copier,
961 typename Iterator,
962 typename ScratchData,
963 typename CopyData>
964 void
965 run(const std::vector<std::vector<Iterator>> &colored_iterators,
966 Worker worker,
967 Copier copier,
968 const ScratchData &sample_scratch_data,
969 const CopyData &sample_copy_data)
970 {
971 // need to copy the sample since it is marked const
972 ScratchData scratch_data = sample_scratch_data;
973 CopyData copy_data = sample_copy_data; // NOLINT
974
975 // Optimization: Check if the functions are not the zero function. To
976 // check zero-ness, create a C++ function out of it:
977 const bool have_worker =
978 (static_cast<const std::function<
979 void(const Iterator &, ScratchData &, CopyData &)> &>(worker)) !=
980 nullptr;
981 const bool have_copier =
982 (static_cast<const std::function<void(const CopyData &)> &>(
983 copier)) != nullptr;
984
985 // Finally loop over all items and perform the necessary work:
986 for (unsigned int color = 0; color < colored_iterators.size(); ++color)
987 if (colored_iterators[color].size() > 0)
988 for (auto &it : colored_iterators[color])
989 {
990 if (have_worker)
991 worker(it, scratch_data, copy_data);
992 if (have_copier)
993 copier(copy_data);
994 }
995 }
996
997 } // namespace sequential
998
999
1000
1001 # ifdef DEAL_II_WITH_TBB
1002 /**
1003 * A namespace for the implementation of details of the WorkStream pattern
1004 * and function. This namespace holds classes that deal with the third
1005 * implementation described in the paper by Turcksin, Kronbichler and
1006 * Bangerth (see
1007 * @ref workstream_paper).
1008 */
1009 namespace tbb_colored
1010 {
1011 /**
1012 * A class that manages calling the worker and copier functions. Unlike
1013 * the other implementations, parallel_for is used instead of a
1014 * pipeline.
1015 */
1016 template <typename Iterator, typename ScratchData, typename CopyData>
1017 class WorkerAndCopier
1018 {
1019 public:
1020 /**
1021 * Constructor.
1022 */
1023 WorkerAndCopier(
1024 const std::function<void(const Iterator &, ScratchData &, CopyData &)>
1025 &worker,
1026 const std::function<void(const CopyData &)> &copier,
1027 const ScratchData &sample_scratch_data,
1028 const CopyData &sample_copy_data)
1029 : worker(worker)
1030 , copier(copier)
1031 , sample_scratch_data(sample_scratch_data)
1032 , sample_copy_data(sample_copy_data)
1033 {}
1034
1035
1036 /**
1037 * The function that calls the worker and the copier functions on a
1038 * range of items denoted by the two arguments.
1039 */
1040 void
1041 operator()(const tbb::blocked_range<
1042 typename std::vector<Iterator>::const_iterator> &range)
1043 {
1044 // we need to find an unused scratch and corresponding copy
1045 // data object in the list that corresponds to the current
1046 // thread and then mark it as used. If we can't find one,
1047 // create one as discussed in the discussion of the documentation
1048 // of the IteratorRangeToItemStream::scratch_data variable,
1049 // there is no need to synchronize access to this variable
1050 // using a mutex as long as we have no yield-point in between.
1051 // This means that we can't take an iterator into the list
1052 // now and expect it to still be valid after calling the worker,
1053 // but we at least do not have to lock the following section.
1054 ScratchData *scratch_data = nullptr;
1055 CopyData *copy_data = nullptr;
1056 {
1057 ScratchAndCopyDataList &scratch_and_copy_data_list = data.get();
1058
1059 // see if there is an unused object. if so, grab it and mark
1060 // it as used
1061 for (typename ScratchAndCopyDataList::iterator p =
1062 scratch_and_copy_data_list.begin();
1063 p != scratch_and_copy_data_list.end();
1064 ++p)
1065 if (p->currently_in_use == false)
1066 {
1067 scratch_data = p->scratch_data.get();
1068 copy_data = p->copy_data.get();
1069 p->currently_in_use = true;
1070 break;
1071 }
1072
1073 // if no element in the list was found, create one and mark it as
1074 // used
1075 if (scratch_data == nullptr)
1076 {
1077 Assert(copy_data == nullptr, ExcInternalError());
1078
1079 scratch_and_copy_data_list.emplace_back(
1080 std::make_unique<ScratchData>(sample_scratch_data),
1081 std::make_unique<CopyData>(sample_copy_data),
1082 true);
1083 scratch_data =
1084 scratch_and_copy_data_list.back().scratch_data.get();
1085 copy_data = scratch_and_copy_data_list.back().copy_data.get();
1086 }
1087 }
1088
1089 // then call the worker and copier functions on each
1090 // element of the chunk we were given.
1091 for (typename std::vector<Iterator>::const_iterator p = range.begin();
1092 p != range.end();
1093 ++p)
1094 {
1095 try
1096 {
1097 if (worker)
1098 worker(*p, *scratch_data, *copy_data);
1099 if (copier)
1100 copier(*copy_data);
1101 }
1102 catch (const std::exception &exc)
1103 {
1104 Threads::internal::handle_std_exception(exc);
1105 }
1106 catch (...)
1107 {
1108 Threads::internal::handle_unknown_exception();
1109 }
1110 }
1111
1112 // finally mark the scratch object as unused again. as above, there
1113 // is no need to lock anything here since the object we work on
1114 // is thread-local
1115 {
1116 ScratchAndCopyDataList &scratch_and_copy_data_list = data.get();
1117
1118 for (typename ScratchAndCopyDataList::iterator p =
1119 scratch_and_copy_data_list.begin();
1120 p != scratch_and_copy_data_list.end();
1121 ++p)
1122 if (p->scratch_data.get() == scratch_data)
1123 {
1124 Assert(p->currently_in_use == true, ExcInternalError());
1125 p->currently_in_use = false;
1126 }
1127 }
1128 }
1129
1130 private:
1131 using ScratchAndCopyDataObjects = typename internal::
1132 ScratchAndCopyDataObjects<Iterator, ScratchData, CopyData>;
1133
1134 /**
1135 * Typedef to a list of scratch data objects. The rationale for this
1136 * list is provided in the variables that use these lists.
1137 */
1138 using ScratchAndCopyDataList = std::list<ScratchAndCopyDataObjects>;
1139
1140 Threads::ThreadLocalStorage<ScratchAndCopyDataList> data;
1141
1142 /**
1143 * Pointer to the function that does the assembling on the sequence of
1144 * cells.
1145 */
1146 const std::function<void(const Iterator &, ScratchData &, CopyData &)>
1147 worker;
1148
1149 /**
1150 * Pointer to the function that does the copying from local
1151 * contribution to global object.
1152 */
1153 const std::function<void(const CopyData &)> copier;
1154
1155 /**
1156 * References to sample scratch and copy data for when we need them.
1157 */
1158 const ScratchData &sample_scratch_data;
1159 const CopyData &sample_copy_data;
1160 };
1161
1162 /**
1163 * The colored run function using TBB.
1164 */
1165 template <typename Worker,
1166 typename Copier,
1167 typename Iterator,
1168 typename ScratchData,
1169 typename CopyData>
1170 void
1171 run(const std::vector<std::vector<Iterator>> &colored_iterators,
1172 Worker worker,
1173 Copier copier,
1174 const ScratchData &sample_scratch_data,
1175 const CopyData &sample_copy_data,
1176 const unsigned int chunk_size)
1177 {
1178 // loop over the various colors of what we're given
1179 for (unsigned int color = 0; color < colored_iterators.size(); ++color)
1180 if (colored_iterators[color].size() > 0)
1181 {
1182 using WorkerAndCopier = internal::tbb_colored::
1183 WorkerAndCopier<Iterator, ScratchData, CopyData>;
1184
1185 WorkerAndCopier worker_and_copier(worker,
1186 copier,
1187 sample_scratch_data,
1188 sample_copy_data);
1189
1190 parallel::internal::parallel_for(
1191 colored_iterators[color].begin(),
1192 colored_iterators[color].end(),
1193 [&worker_and_copier](
1194 const tbb::blocked_range<
1195 typename std::vector<Iterator>::const_iterator> &range) {
1196 worker_and_copier(range);
1197 },
1198 chunk_size);
1199 }
1200 }
1201
1202 } // namespace tbb_colored
1203 # endif // DEAL_II_WITH_TBB
1204
1205
1206
1207 # ifdef DEAL_II_WITH_TASKFLOW
1208 /**
1209 * Mostly a copy of the 3rd implementation of the Workstream paper taking
1210 * advantage of thread local lists for re-use. Uses taskflow for task
1211 * scheduling rather than TBB. Currently does not support chunking.
1212 */
1213 namespace taskflow_colored
1214 {
1215 /**
1216 * The main run function for the taskflow colored implementation. The
1217 * last two arguments in this function are for chunking support which
1218 * currently does not exist but ideally will later. For now they are
1219 * ignored but still here to permit existing programs to function.
1220 */
1221 template <typename Worker,
1222 typename Copier,
1223 typename Iterator,
1224 typename ScratchData,
1225 typename CopyData>
1226 void
1227 run(const std::vector<std::vector<Iterator>> &colored_iterators,
1228 Worker worker,
1229 Copier copier,
1230 const ScratchData &sample_scratch_data,
1231 const CopyData &sample_copy_data,
1232 const unsigned int /*queue_length*/ = 2 *
1233 MultithreadInfo::n_threads(),
1234 const unsigned int chunk_size = 8)
1235
1236 {
1237 tf::Executor &executor = MultithreadInfo::get_taskflow_executor();
1238 using ScratchAndCopyDataObjects = typename internal::
1239 ScratchAndCopyDataObjects<Iterator, ScratchData, CopyData>;
1240
1241 using ScratchAndCopyDataList = std::list<ScratchAndCopyDataObjects>;
1242
1243 Threads::ThreadLocalStorage<ScratchAndCopyDataList>
1244 thread_safe_scratch_and_copy_data_list;
1245
1246 tf::Taskflow taskflow;
1247
1248 // Create a "future" object which eventually contains the execution
1249 // result of a taskflow graph and can be used to yield execution
1250 tf::Future<void> execution_future;
1251
1252 const bool have_worker =
1253 (static_cast<const std::function<
1254 void(const Iterator &, ScratchData &, CopyData &)> &>(worker)) !=
1255 nullptr;
1256 const bool have_copier =
1257 (static_cast<const std::function<void(const CopyData &)> &>(
1258 copier)) != nullptr;
1259
1260 std::vector<Iterator> chunk;
1261 chunk.reserve(chunk_size);
1262
1263 unsigned int chunk_counter = 0;
1264 // Generate a static task graph. Here we generate a task for each cell
1265 // that will be worked on. The tasks are not executed until all of them
1266 // are created, this code runs sequentially. Cells have been grouped
1267 // into "colors" data from cells in the same color are safe to copy in
1268 // parallel so copying need not be sequential.
1269 for (unsigned int color = 0; color < colored_iterators.size(); ++color)
1270 // Ignore color blocks which are empty.
1271 if (colored_iterators[color].size() > 0)
1272 {
1273 // For each cell queue up a combined worker and copier task. These
1274 // are not yet run.
1275 for (auto it = colored_iterators[color].begin();
1276 it != colored_iterators[color].end();)
1277 {
1278 for (; (chunk_counter < chunk_size) &&
1279 (it != colored_iterators[color].end());
1280 ++it, ++chunk_counter)
1281 chunk.emplace_back(*it);
1282 taskflow
1283 .emplace([chunk,
1284 have_worker,
1285 have_copier,
1286 &thread_safe_scratch_and_copy_data_list,
1287 &sample_scratch_data,
1288 &sample_copy_data,
1289 &worker,
1290 &copier]() {
1291 ScratchData *scratch_data = nullptr;
1292 CopyData *copy_data = nullptr;
1293
1294 ScratchAndCopyDataList &scratch_and_copy_data_list =
1295 thread_safe_scratch_and_copy_data_list.get();
1296 // See if there is an unused object. if so, grab it
1297 // and mark it as used.
1298 for (typename ScratchAndCopyDataList::iterator p =
1299 scratch_and_copy_data_list.begin();
1300 p != scratch_and_copy_data_list.end();
1301 ++p)
1302 {
1303 if (p->currently_in_use == false)
1304 {
1305 scratch_data = p->scratch_data.get();
1306 copy_data = p->copy_data.get();
1307 p->currently_in_use = true;
1308 break;
1309 }
1310 }
1311 // If no element in the list was found, create one and
1312 // mark it as used.
1313 if (scratch_data == nullptr)
1314 {
1315 Assert(copy_data == nullptr, ExcInternalError());
1316 scratch_and_copy_data_list.emplace_back(
1317 std::make_unique<ScratchData>(sample_scratch_data),
1318 std::make_unique<CopyData>(sample_copy_data),
1319 true);
1320 scratch_data = scratch_and_copy_data_list.back()
1321 .scratch_data.get();
1322 copy_data =
1323 scratch_and_copy_data_list.back().copy_data.get();
1324 }
1325
1326 for (const Iterator &it : chunk)
1327 {
1328 if (have_worker)
1329 worker(it, *scratch_data, *copy_data);
1330 if (have_copier)
1331 copier(*copy_data);
1332 }
1333
1334 // Mark objects as free to be used again.
1335 for (typename ScratchAndCopyDataList::iterator p =
1336 scratch_and_copy_data_list.begin();
1337 p != scratch_and_copy_data_list.end();
1338 ++p)
1339 {
1340 if (p->scratch_data.get() == scratch_data)
1341 {
1342 Assert(p->currently_in_use == true,
1343 ExcInternalError());
1344 p->currently_in_use = false;
1345 }
1346 }
1347 })
1348 .name("worker_and_copier");
1349 chunk.clear();
1350 chunk_counter = 0;
1351 }
1352
1353 if (color > 0)
1354 // Wait for the previous color to finish executing
1355 execution_future.wait();
1356 execution_future = executor.run(std::move(taskflow));
1357 }
1358 // Wait for our final execution to finish
1359 if (colored_iterators.size() > 0)
1360 execution_future.wait();
1361 }
1362 } // namespace taskflow_colored
1363 # endif // DEAL_II_WITH_TASKFLOW
1364
1365
1366 } // namespace internal
1367
1368
1369
1370 /**
1371 * This is one of two main functions of the WorkStream concept, doing work
1372 * as described in the introduction to this namespace. It corresponds to
1373 * implementation 3 of the paper by Turcksin, Kronbichler and Bangerth, see
1374 * @ref workstream_paper.
1375 * As such, it takes not a range of iterators described by a begin and end
1376 * iterator, but a "colored" graph of iterators where each color represents
1377 * cells for which writing the cell contributions into the global object
1378 * does not conflict (in other words, these cells are not neighbors). Each
1379 * "color" is represented by std::vectors of cells. The first argument to
1380 * this function, a set of sets of cells (which are represent as a vector of
1381 * vectors, for efficiency), is typically constructed by calling
1382 * GraphColoring::make_graph_coloring(). See there for more information.
1383 *
1384 * This function that can be used for worker and copier objects that are
1385 * either pointers to non-member functions or objects that allow to be
1386 * called with an operator(), for example objects created by lambda functions
1387 * or std::bind.
1388 *
1389 * The two data types <tt>ScratchData</tt> and <tt>CopyData</tt> need to
1390 * have a working copy constructor. <tt>ScratchData</tt> is only used in the
1391 * <tt>worker</tt> function, while <tt>CopyData</tt> is the object passed
1392 * from the <tt>worker</tt> to the <tt>copier</tt>.
1393 *
1394 * The @p queue_length argument indicates the number of items that can be
1395 * live at any given time. Each item consists of @p chunk_size elements of
1396 * the input stream that will be worked on by the worker and copier
1397 * functions one after the other on the same thread.
1398 *
1399 * @note If your data objects are large, or their constructors are
1400 * expensive, it is helpful to keep in mind that <tt>queue_length</tt>
1401 * copies of the <tt>ScratchData</tt> object and
1402 * <tt>queue_length*chunk_size</tt> copies of the <tt>CopyData</tt> object
1403 * are generated.
1404 *
1405 * @note In case the copier does not do anything, pass
1406 * `std::function<void(const CopyData &)>()` as @p copier to make sure
1407 * a more efficient algorithm is used internally. It is important, however,
1408 * to recognize that the empty function object created above is *not*
1409 * the same as a lambda function with an empty body,
1410 * `[](const CopyData &) {}` -- from the perspective of this function,
1411 * there is no way to recognize whether a lambda function provided as
1412 * a copier does something or does not do something in its body,
1413 * and so it needs to be copied. On the other hand, a default-constructed
1414 * `std::function` object *can* be recognized, and is then used to select
1415 * a more efficient algorithm.
1416 */
1417 template <typename Worker,
1418 typename Copier,
1419 typename Iterator,
1420 typename ScratchData,
1421 typename CopyData>
1422 void
1423 run(const std::vector<std::vector<Iterator>> &colored_iterators,
1424 Worker worker,
1425 Copier copier,
1426 const ScratchData &sample_scratch_data,
1427 const CopyData &sample_copy_data,
1428 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1429 const unsigned int chunk_size = 8);
1430
1431
1432 /**
1433 * This is one of two main functions of the WorkStream concept, doing work
1434 * as described in the introduction to this namespace. It corresponds to
1435 * implementation 2 of the paper by Turcksin, Kronbichler and Bangerth (see
1436 * @ref workstream_paper).
1437 *
1438 * This function that can be used for worker and copier objects that are
1439 * either pointers to non-member functions or objects that allow to be
1440 * called with an operator(), for example lambda functions
1441 * or objects created by std::bind. If the copier is an empty function, it is
1442 * ignored in the pipeline. (However, a lambda function with an empty body is
1443 * *not* equivalent to an empty `std::function` object and will, consequently,
1444 * not be ignored.
1445 *
1446 * The argument passed as @p end must be convertible to the same type as @p
1447 * begin, but doesn't have to be of the same type itself. This allows to
1448 * write code like <code>WorkStream().run(dof_handler.begin_active(),
1449 * dof_handler.end(), ...</code> where the first is of type
1450 * DoFHandler::active_cell_iterator whereas the second is of type
1451 * DoFHandler::raw_cell_iterator.
1452 *
1453 * The two data types <tt>ScratchData</tt> and <tt>CopyData</tt> need to
1454 * have a working copy constructor. <tt>ScratchData</tt> is only used in the
1455 * <tt>worker</tt> function, while <tt>CopyData</tt> is the object passed
1456 * from the <tt>worker</tt> to the <tt>copier</tt>.
1457 *
1458 * The @p queue_length argument indicates the number of items that can be
1459 * live at any given time. Each item consists of @p chunk_size elements of
1460 * the input stream that will be worked on by the worker and copier
1461 * functions one after the other on the same thread.
1462 *
1463 * @note If your data objects are large, or their constructors are
1464 * expensive, it is helpful to keep in mind that <tt>queue_length</tt>
1465 * copies of the <tt>ScratchData</tt> object and
1466 * <tt>queue_length*chunk_size</tt> copies of the <tt>CopyData</tt> object
1467 * are generated.
1468 *
1469 * @note In case the copier does not do anything, pass
1470 * `std::function<void(const CopyData &)>()` as @p copier to make sure
1471 * a more efficient algorithm is used internally. It is important, however,
1472 * to recognize that the empty function object created above is *not*
1473 * the same as a lambda function with an empty body,
1474 * `[](const CopyData &) {}` -- from the perspective of this function,
1475 * there is no way to recognize whether a lambda function provided as
1476 * a copier does something or does not do something in its body,
1477 * and so it needs to be copied. On the other hand, a default-constructed
1478 * `std::function` object *can* be recognized, and is then used to select
1479 * a more efficient algorithm.
1480 */
1481 template <typename Worker,
1482 typename Copier,
1483 typename Iterator,
1484 typename ScratchData,
1485 typename CopyData>
1486 void
1487 run(const Iterator &begin,
1488 const std_cxx20::type_identity_t<Iterator> &end,
1489 Worker worker,
1490 Copier copier,
1491 const ScratchData &sample_scratch_data,
1492 const CopyData &sample_copy_data,
1493 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1494 const unsigned int chunk_size = 8)
1495 {
1496 Assert(queue_length > 0,
1497 ExcMessage("The queue length must be at least one, and preferably "
1498 "larger than the number of processors on this system."));
1499 (void)queue_length; // removes -Wunused-parameter warning in optimized mode
1500 Assert(chunk_size > 0, ExcMessage("The chunk_size must be at least one."));
1501 (void)chunk_size; // removes -Wunused-parameter warning in optimized mode
1502
1503 // If no work then skip. (only use operator!= for iterators since we may
1504 // not have an equality comparison operator)
1505 if (!(begin != end))
1506 return;
1507
1508 if (MultithreadInfo::n_threads() > 1)
1509 {
1510 # if defined(DEAL_II_WITH_TBB) || defined(DEAL_II_WITH_TASKFLOW)
1511 if (static_cast<const std::function<void(const CopyData &)> &>(copier))
1512 {
1513 // If we have a copier, run the algorithm:
1514 # if defined(DEAL_II_WITH_TASKFLOW)
1515 internal::taskflow_no_coloring::run(begin,
1516 end,
1517 worker,
1518 copier,
1519 sample_scratch_data,
1520 sample_copy_data,
1521 queue_length,
1522 chunk_size);
1523 # elif defined(DEAL_II_WITH_TBB)
1524 internal::tbb_no_coloring::run(begin,
1525 end,
1526 worker,
1527 copier,
1528 sample_scratch_data,
1529 sample_copy_data,
1530 queue_length,
1531 chunk_size);
1532 # endif
1533 }
1534 else
1535 {
1536 // There is no copier function. in this case, we have an
1537 // embarrassingly parallel problem where we can
1538 // essentially apply parallel_for. because parallel_for
1539 // requires subdividing the range for which operator- is
1540 // necessary between iterators, it is often inefficient to
1541 // apply it directly to cell ranges and similar iterator
1542 // types for which operator- is expensive or, in fact,
1543 // nonexistent. rather, in that case, we simply copy the
1544 // iterators into a large array and use operator- on
1545 // iterators to this array of iterators.
1546 //
1547 // instead of duplicating code, this is essentially the
1548 // same situation we have in the colored implementation below, so we
1549 // just defer to that place
1550 std::vector<std::vector<Iterator>> all_iterators(1);
1551 for (Iterator p = begin; p != end; ++p)
1552 all_iterators[0].push_back(p);
1553
1554 run(all_iterators,
1555 worker,
1556 copier,
1557 sample_scratch_data,
1558 sample_copy_data,
1559 queue_length,
1560 chunk_size);
1561 }
1562
1563 // exit this function to not run the sequential version below:
1564 return;
1565 # endif
1566 }
1567
1568 // no TBB or Taskflow installed or we are requested to run sequentially:
1569 internal::sequential::run(
1570 begin, end, worker, copier, sample_scratch_data, sample_copy_data);
1571 }
1572
1573
1574
1575 /**
1576 * Same as the function above, but for iterator ranges and C-style arrays.
1577 * A class that fulfills the requirements of an iterator range defines the
1578 * functions `IteratorRangeType::begin()` and `IteratorRangeType::end()`,
1579 * both of which return iterators to elements that form the bounds of the
1580 * range.
1581 */
1582 template <
1583 typename Worker,
1584 typename Copier,
1585 typename IteratorRangeType,
1586 typename ScratchData,
1587 typename CopyData,
1588 typename = std::enable_if_t<
1589 has_begin_and_end<IteratorRangeType> &&
1590 !std::is_same_v<IteratorRangeType,
1591 IteratorRange<typename IteratorRangeType::iterator>>>>
1592 void
1593 run(IteratorRangeType iterator_range,
1594 Worker worker,
1595 Copier copier,
1596 const ScratchData &sample_scratch_data,
1597 const CopyData &sample_copy_data,
1598 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1599 const unsigned int chunk_size = 8)
1600 {
1601 // Call the function above
1602 run(iterator_range.begin(),
1603 iterator_range.end(),
1604 worker,
1605 copier,
1606 sample_scratch_data,
1607 sample_copy_data,
1608 queue_length,
1609 chunk_size);
1610 }
1611
1612
1613
1614 /**
1615 * Same as the function above, but for deal.II's IteratorRange.
1616 */
1617 template <typename Worker,
1618 typename Copier,
1619 typename Iterator,
1620 typename ScratchData,
1621 typename CopyData>
1622 void
1623 run(const IteratorRange<Iterator> &iterator_range,
1624 Worker worker,
1625 Copier copier,
1626 const ScratchData &sample_scratch_data,
1627 const CopyData &sample_copy_data,
1628 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1629 const unsigned int chunk_size = 8)
1630 {
1631 // Call the function above
1632 run(iterator_range.begin(),
1633 iterator_range.end(),
1634 worker,
1635 copier,
1636 sample_scratch_data,
1637 sample_copy_data,
1638 queue_length,
1639 chunk_size);
1640 }
1641
1642
1643
1644 template <typename Worker,
1645 typename Copier,
1646 typename Iterator,
1647 typename ScratchData,
1648 typename CopyData>
1649 void
1650 run(const std::vector<std::vector<Iterator>> &colored_iterators,
1651 Worker worker,
1652 Copier copier,
1653 const ScratchData &sample_scratch_data,
1654 const CopyData &sample_copy_data,
1655 const unsigned int queue_length,
1656 const unsigned int chunk_size)
1657 {
1658 Assert(queue_length > 0,
1659 ExcMessage("The queue length must be at least one, and preferably "
1660 "larger than the number of processors on this system."));
1661 (void)queue_length; // removes -Wunused-parameter warning in optimized mode
1662 Assert(chunk_size > 0, ExcMessage("The chunk_size must be at least one."));
1663 (void)chunk_size; // removes -Wunused-parameter warning in optimized mode
1664
1665
1666 if (MultithreadInfo::n_threads() > 1)
1667 {
1668 # ifdef DEAL_II_WITH_TASKFLOW
1669 internal::taskflow_colored::run(colored_iterators,
1670 worker,
1671 copier,
1672 sample_scratch_data,
1673 sample_copy_data,
1674 chunk_size);
1675
1676 // exit this function to not run the sequential version below:
1677 return;
1678 # elif defined(DEAL_II_WITH_TBB)
1679 internal::tbb_colored::run(colored_iterators,
1680 worker,
1681 copier,
1682 sample_scratch_data,
1683 sample_copy_data,
1684 chunk_size);
1685
1686 // exit this function to not run the sequential version below:
1687 return;
1688 # endif
1689 }
1690
1691 // run all colors sequentially:
1692 {
1693 internal::sequential::run(colored_iterators,
1694 worker,
1695 copier,
1696 sample_scratch_data,
1697 sample_copy_data);
1698 }
1699 }
1700
1701
1702
1703 /**
1704 * This is a variant of one of the two main functions of the WorkStream
1705 * concept, doing work as described in the introduction to this namespace.
1706 * It corresponds to implementation 2 of the paper by Turcksin, Kronbichler
1707 * and Bangerth (see
1708 * @ref workstream_paper).
1709 *
1710 * This is the function that can be used for worker and copier functions
1711 * that are member functions of a class. If the copier is an empty function,
1712 * it is ignored in the pipeline.
1713 *
1714 * The argument passed as @p end must be convertible to the same type as @p
1715 * begin, but doesn't have to be of the same type itself. This allows to
1716 * write code like <code>WorkStream().run(dof_handler.begin_active(),
1717 * dof_handler.end(), ...</code> where the first is of type
1718 * DoFHandler::active_cell_iterator whereas the second is of type
1719 * DoFHandler::raw_cell_iterator.
1720 *
1721 * The @p queue_length argument indicates the number of items that can be
1722 * live at any given time. Each item consists of @p chunk_size elements of
1723 * the input stream that will be worked on by the worker and copier
1724 * functions one after the other on the same thread.
1725 *
1726 * @note If your data objects are large, or their constructors are
1727 * expensive, it is helpful to keep in mind that <tt>queue_length</tt>
1728 * copies of the <tt>ScratchData</tt> object and
1729 * <tt>queue_length*chunk_size</tt> copies of the <tt>CopyData</tt> object
1730 * are generated.
1731 *
1732 * @note In case the copier does not do anything, pass
1733 * `std::function<void(const CopyData &)>()` as @p copier to make sure
1734 * a more efficient algorithm is used internally. It is important, however,
1735 * to recognize that the empty function object created above is *not*
1736 * the same as a lambda function with an empty body,
1737 * `[](const CopyData &) {}` -- from the perspective of this function,
1738 * there is no way to recognize whether a lambda function provided as
1739 * a copier does something or does not do something in its body,
1740 * and so it needs to be copied. On the other hand, a default-constructed
1741 * `std::function` object *can* be recognized, and is then used to select
1742 * a more efficient algorithm.
1743 */
1744 template <typename MainClass,
1745 typename Iterator,
1746 typename ScratchData,
1747 typename CopyData>
1748 void
1749 run(const Iterator &begin,
1750 const std_cxx20::type_identity_t<Iterator> &end,
1751 MainClass &main_object,
1752 void (MainClass::*worker)(const Iterator &, ScratchData &, CopyData &),
1753 void (MainClass::*copier)(const CopyData &),
1754 const ScratchData &sample_scratch_data,
1755 const CopyData &sample_copy_data,
1756 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1757 const unsigned int chunk_size = 8)
1758 {
1759 // forward to the other function
1760 run(
1761 begin,
1762 end,
1763 [&main_object, worker](const Iterator &iterator,
1764 ScratchData &scratch_data,
1765 CopyData &copy_data) {
1766 (main_object.*worker)(iterator, scratch_data, copy_data);
1767 },
1768 [&main_object, copier](const CopyData &copy_data) {
1769 (main_object.*copier)(copy_data);
1770 },
1771 sample_scratch_data,
1772 sample_copy_data,
1773 queue_length,
1774 chunk_size);
1775 }
1776
1777
1778 template <typename MainClass,
1779 typename Iterator,
1780 typename ScratchData,
1781 typename CopyData>
1782 void
1783 run(const IteratorOverIterators<Iterator> &begin,
1784 const IteratorOverIterators<std_cxx20::type_identity_t<Iterator>> &end,
1785 MainClass &main_object,
1786 void (MainClass::*worker)(const Iterator &, ScratchData &, CopyData &),
1787 void (MainClass::*copier)(const CopyData &),
1788 const ScratchData &sample_scratch_data,
1789 const CopyData &sample_copy_data,
1790 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1791 const unsigned int chunk_size = 8)
1792 {
1793 // forward to the other function
1794 run(
1795 begin,
1796 end,
1797 [&main_object, worker](const Iterator &iterator,
1798 ScratchData &scratch_data,
1799 CopyData &copy_data) {
1800 (main_object.*worker)(iterator, scratch_data, copy_data);
1801 },
1802 [&main_object, copier](const CopyData &copy_data) {
1803 (main_object.*copier)(copy_data);
1804 },
1805 sample_scratch_data,
1806 sample_copy_data,
1807 queue_length,
1808 chunk_size);
1809 }
1810
1811
1812
1813 /**
1814 * Same as the function above, but for iterator ranges and C-style arrays.
1815 * A class that fulfills the requirements of an iterator range defines the
1816 * functions `IteratorRangeType::begin()` and `IteratorRangeType::end()`,
1817 * both of which return iterators to elements that form the bounds of the
1818 * range.
1819 */
1820 template <
1821 typename MainClass,
1822 typename IteratorRangeType,
1823 typename ScratchData,
1824 typename CopyData,
1825 typename = std::enable_if_t<
1826 has_begin_and_end<IteratorRangeType> &&
1827 !std::is_same_v<IteratorRangeType,
1828 IteratorRange<typename IteratorRangeType::iterator>>>>
1829 void
1830 run(
1831 IteratorRangeType iterator_range,
1832 MainClass &main_object,
1833 void (MainClass::*worker)(
1834 const typename std_cxx20::type_identity_t<IteratorRangeType>::iterator &,
1835 ScratchData &,
1836 CopyData &),
1837 void (MainClass::*copier)(const CopyData &),
1838 const ScratchData &sample_scratch_data,
1839 const CopyData &sample_copy_data,
1840 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1841 const unsigned int chunk_size = 8)
1842 {
1843 // Call the function above
1844 run(std::begin(iterator_range),
1845 std::end(iterator_range),
1846 main_object,
1847 worker,
1848 copier,
1849 sample_scratch_data,
1850 sample_copy_data,
1851 queue_length,
1852 chunk_size);
1853 }
1854
1855
1856
1857 /**
1858 * Same as the function above, but for deal.II's IteratorRange.
1859 */
1860 template <typename MainClass,
1861 typename Iterator,
1862 typename ScratchData,
1863 typename CopyData>
1864 void
1865 run(IteratorRange<Iterator> iterator_range,
1866 MainClass &main_object,
1867 void (MainClass::*worker)(const Iterator &, ScratchData &, CopyData &),
1868 void (MainClass::*copier)(const CopyData &),
1869 const ScratchData &sample_scratch_data,
1870 const CopyData &sample_copy_data,
1871 const unsigned int queue_length = 2 * MultithreadInfo::n_threads(),
1872 const unsigned int chunk_size = 8)
1873 {
1874 // Call the function above
1875 run(std::begin(iterator_range),
1876 std::end(iterator_range),
1877 main_object,
1878 worker,
1879 copier,
1880 sample_scratch_data,
1881 sample_copy_data,
1882 queue_length,
1883 chunk_size);
1884 }
1885
1886 } // namespace WorkStream
1887
1888
1889
1890 DEAL_II_NAMESPACE_CLOSE
1891
1892
1893
1894 //---------------------------- work_stream.h ---------------------------
1895 // end of #ifndef dealii_work_stream_h
1896 #endif
1897 //---------------------------- work_stream.h ---------------------------