Debian Codegraph @

include/deal.II/matrix_free/task_info.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2018 - 2023 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
16 #ifndef dealii_matrix_free_task_info_h
17 #define dealii_matrix_free_task_info_h
18
19
20 #include <deal.II/base/config.h>
21
22 #include <deal.II/base/exceptions.h>
23 #include <deal.II/base/memory_consumption.h>
24 #include <deal.II/base/mpi_stub.h>
25 #include <deal.II/base/tensor.h>
26 #include <deal.II/base/vectorization.h>
27
28
29 DEAL_II_NAMESPACE_OPEN
30
31
32 // forward declaration
33 #ifndef DOXYGEN
34 class DynamicSparsityPattern;
35 #endif
36
37
38 namespace internal
39 {
40 /**
41 * An interface for the worker object that runs the various operations we
42 * want to perform during the matrix-free loop.
43 */
44 struct MFWorkerInterface
45 {
46 public:
47 virtual ~MFWorkerInterface() = default;
48
49 /// Starts the communication for the update ghost values operation
50 virtual void
51 vector_update_ghosts_start() = 0;
52
53 /// Finishes the communication for the update ghost values operation
54 virtual void
55 vector_update_ghosts_finish() = 0;
56
57 /// Starts the communication for the vector compress operation
58 virtual void
59 vector_compress_start() = 0;
60
61 /// Finishes the communication for the vector compress operation
62 virtual void
63 vector_compress_finish() = 0;
64
65 /// Zeros part of the vector according to a given range as stored in
66 /// DoFInfo
67 virtual void
68 zero_dst_vector_range(const unsigned int range_index) = 0;
69
70 virtual void
71 cell_loop_pre_range(const unsigned int range_index) = 0;
72
73 virtual void
74 cell_loop_post_range(const unsigned int range_index) = 0;
75
76 /// Runs the cell work specified by MatrixFree::loop or
77 /// MatrixFree::cell_loop
78 virtual void
79 cell(const std::pair<unsigned int, unsigned int> &cell_range) = 0;
80
81 /// Runs the cell work specified by MatrixFree::loop or
82 /// MatrixFree::cell_loop
83 virtual void
84 cell(const unsigned int range_index) = 0;
85
86 /// Runs the body of the work on interior faces specified by
87 /// MatrixFree::loop
88 virtual void
89 face(const unsigned int range_index) = 0;
90
91 /// Runs the body of the work on boundary faces specified by
92 /// MatrixFree::loop
93 virtual void
94 boundary(const unsigned int range_index) = 0;
95 };
96
97
98
99 namespace MatrixFreeFunctions
100 {
101 /**
102 * A struct that collects all information related to parallelization with
103 * threads: The work is subdivided into tasks that can be done
104 * independently.
105 */
106 struct TaskInfo
107 {
108 // enum for choice of how to build the task graph. Odd add versions with
109 // preblocking and even versions with postblocking. partition_partition
110 // and partition_color are deprecated but kept for backward
111 // compatibility.
112 enum TasksParallelScheme
113 {
114 none,
115 partition_partition,
116 partition_color,
117 color
118 };
119
120 /**
121 * Constructor.
122 */
123 TaskInfo();
124
125 /**
126 * Clears all the data fields and resets them
127 * to zero.
128 */
129 void
130 clear();
131
132 /**
133 * Runs the matrix-free loop.
134 */
135 void
136 loop(MFWorkerInterface &worker) const;
137
138 /**
139 * Make the number of cells which can only be treated in the
140 * communication overlap divisible by the vectorization length.
141 */
142 void
143 make_boundary_cells_divisible(std::vector<unsigned int> &boundary_cells);
144
145 /**
146 * Sets up the blocks for running the cell loop based on the options
147 * controlled by the input arguments.
148 *
149 * @param cells_with_comm A list of cells that need to exchange data
150 * prior to performing computations. These will be given a certain id in
151 * the partitioning to make sure cell loops that overlap communication
152 * with communication have the ghost data ready.
153 *
154 * @param dofs_per_cell Gives an expected value for the number of degrees
155 * of freedom on a cell, which is used to determine the block size for
156 * interleaving cell and face integrals.
157 *
158 * @param categories_are_hp Defines whether
159 * `cell_vectorization_categories` is originating from a hp-adaptive
160 * computation with variable polynomial degree or a user-defined
161 * variant.
162 *
163 * @param cell_vectorization_categories This set of categories defines
164 * the cells that should be grouped together inside the lanes of a
165 * vectorized array. This can be the polynomial degree in an hp-element
166 * or a user-provided grouping.
167 *
168 * @param cell_vectorization_categories_strict Defines whether the
169 * categories defined by the previous variables should be separated
170 * strictly or whether it is allowed to insert lower categories into the
171 * next high one(s).
172 *
173 * @param parent_relation This data field is used to specify which cells
174 * have the same parent cell. Cells with the same ancestor are grouped
175 * together into the same batch(es) with vectorization across cells.
176 *
177 * @param renumbering When leaving this function, the vector contains a
178 * new numbering of the cells that aligns with the grouping stored in
179 * this class.
180 *
181 * @param incompletely_filled_vectorization Given the vectorized layout
182 * of this class, some cell batches might have components in the
183 * vectorized array (SIMD lanes) that are not used and do not carray
184 * valid data. This array indicates the cell batches where this occurs
185 * according to the renumbering returned by this function.
186 */
187 void
188 create_blocks_serial(
189 const std::vector<unsigned int> &cells_with_comm,
190 const unsigned int dofs_per_cell,
191 const bool categories_are_hp,
192 const std::vector<unsigned int> &cell_vectorization_categories,
193 const bool cell_vectorization_categories_strict,
194 const std::vector<unsigned int> &parent_relation,
195 std::vector<unsigned int> &renumbering,
196 std::vector<unsigned char> &incompletely_filled_vectorization);
197
198 /**
199 * First step in the block creation for the task-parallel blocking setup.
200 *
201 * @param boundary_cells A list of cells that need to exchange data prior
202 * to performing computations. These will be given a certain id in the
203 * partitioning.
204 *
205 * @param renumbering When leaving this function, the vector contains a
206 * new numbering of the cells that aligns with the grouping stored in
207 * this class (before actually creating the tasks).
208 *
209 * @param incompletely_filled_vectorization Given the vectorized layout
210 * of this class, some cell batches might have components in the
211 * vectorized array (SIMD lanes) that are not used and do not carray
212 * valid data. This array indicates the cell batches where this occurs
213 * according to the renumbering returned by this function.
214 */
215 void
216 initial_setup_blocks_tasks(
217 const std::vector<unsigned int> &boundary_cells,
218 std::vector<unsigned int> &renumbering,
219 std::vector<unsigned char> &incompletely_filled_vectorization);
220
221 /**
222 * This helper function determines a block size if the user decided not
223 * to force a block size through MatrixFree::AdditionalData. This is
224 * computed based on the number of hardware threads on the system and
225 * the number of cell batches that we should work on.
226 */
227 void
228 guess_block_size(const unsigned int dofs_per_cell);
229
230 /**
231 * This method goes through all cells that have been filled into @p
232 * dof_indices and finds out which cells can be worked on independently
233 * and which ones are neighboring and need to be done at different times
234 * when used in parallel.
235 *
236 * The strategy is based on a two-level approach. The outer level is
237 * subdivided into partitions similar to the type of neighbors in
238 * Cuthill-McKee, and the inner level is subdivided via colors (for
239 * chunks within the same color, can work independently). One task is
240 * represented by a chunk of cells. The cell chunks are formed before
241 * subdivision into partitions and colors.
242 *
243 * @param connectivity (in/out) Determines whether cells `i` and `j` are
244 * conflicting, expressed by an entry in position (i,j).
245 *
246 * @param renumbering (in/out) At output, the element j of this variable
247 * gives the original number of the cell that is reordered to place j by
248 * the ordering due to the thread graph.
249 *
250 * @param irregular_cells (in/out) Informs the current function whether
251 * some SIMD lanes in VectorizedArray would not be filled for a given
252 * cell batch index.
253 *
254 * @param hp_bool Defines whether we are in hp-mode or not
255 */
256 void
257 make_thread_graph_partition_color(
258 DynamicSparsityPattern &connectivity,
259 std::vector<unsigned int> &renumbering,
260 std::vector<unsigned char> &irregular_cells,
261 const bool hp_bool);
262
263 /**
264 * This function goes through all cells that have been filled into @p
265 * dof_indices and finds out which cells can be worked on independently
266 * and which ones are neighboring and need to be done at different times
267 * when used in parallel.
268 *
269 * The strategy is based on a two-level approach. The outer level is
270 * subdivided into partitions similar to the type of neighbors in
271 * Cuthill-McKee, and the inner level is again subdivided into
272 * Cuthill-McKee-like partitions (partitions whose level differs by more
273 * than 2 can be worked on independently). One task is represented by a
274 * chunk of cells. The cell chunks are formed after subdivision into the
275 * two levels of partitions.
276 *
277 * @param cell_active_fe_index The active FE index corresponding to the
278 * individual indices in the list of all cell indices, in order to be
279 * able to not place cells with different indices into the same cell
280 * batch with vectorization.
281 *
282 * @param connectivity (in/out) Determines whether cells `i` and `j` are
283 * conflicting, expressed by an entry in position (i,j).
284 *
285 * @param renumbering (in/out) At output, the element j of this variable
286 * gives the original number of the cell that is reordered to place j by
287 * the ordering due to the thread graph.
288 *
289 * @param irregular_cells (in/out) Informs the current function whether
290 * some SIMD lanes in VectorizedArray would not be filled for a given
291 * cell batch index.
292 *
293 * @param hp_bool Defines whether we are in hp-mode or not
294 */
295 void
296 make_thread_graph_partition_partition(
297 const std::vector<unsigned int> &cell_active_fe_index,
298 DynamicSparsityPattern &connectivity,
299 std::vector<unsigned int> &renumbering,
300 std::vector<unsigned char> &irregular_cells,
301 const bool hp_bool);
302
303 /**
304 * Either calls make_thread_graph_partition_color() or
305 * make_thread_graph_partition_partition() accessible from the outside,
306 * depending on the setting in the data structure.
307 *
308 * @param cell_active_fe_index The active FE index corresponding to the
309 * individual indices in the list of all cell indices, in order to be
310 * able to not place cells with different indices into the same cell
311 * batch with vectorization.
312 *
313 * @param connectivity (in/out) Determines whether cells `i` and `j` are
314 * conflicting, expressed by an entry in position (i,j).
315 *
316 * @param renumbering (in/out) At output, the element j of this variable
317 * gives the original number of the cell that is reordered to place j by
318 * the ordering due to the thread graph.
319 *
320 * @param irregular_cells (in/out) Informs the current function whether
321 * some SIMD lanes in VectorizedArray would not be filled for a given
322 * cell batch index.
323 *
324 * @param hp_bool Defines whether we are in hp-mode or not
325 */
326 void
327 make_thread_graph(const std::vector<unsigned int> &cell_active_fe_index,
328 DynamicSparsityPattern &connectivity,
329 std::vector<unsigned int> &renumbering,
330 std::vector<unsigned char> &irregular_cells,
331 const bool hp_bool);
332
333 /**
334 * This function computes the connectivity between blocks of cells from
335 * the connectivity between the individual cells.
336 */
337 void
338 make_connectivity_cells_to_blocks(
339 const std::vector<unsigned char> &irregular_cells,
340 const DynamicSparsityPattern &connectivity_cells,
341 DynamicSparsityPattern &connectivity_blocks) const;
342
343 /**
344 * %Function to create coloring on the second layer within each
345 * partition.
346 */
347 void
348 make_coloring_within_partitions_pre_blocked(
349 const DynamicSparsityPattern &connectivity,
350 const unsigned int partition,
351 const std::vector<unsigned int> &cell_partition,
352 const std::vector<unsigned int> &partition_list,
353 const std::vector<unsigned int> &partition_size,
354 std::vector<unsigned int> &partition_color_list);
355
356 /**
357 * %Function to create partitioning on the second layer within each
358 * partition.
359 */
360 void
361 make_partitioning_within_partitions_post_blocked(
362 const DynamicSparsityPattern &connectivity,
363 const std::vector<unsigned int> &cell_active_fe_index,
364 const unsigned int partition,
365 const unsigned int cluster_size,
366 const bool hp_bool,
367 const std::vector<unsigned int> &cell_partition,
368 const std::vector<unsigned int> &partition_list,
369 const std::vector<unsigned int> &partition_size,
370 std::vector<unsigned int> &partition_partition_list,
371 std::vector<unsigned char> &irregular_cells);
372
373 /**
374 * This function creates partitions according to the provided connectivity
375 * graph.
376 *
377 * @param connectivity Connectivity between (blocks of cells)
378 *
379 * @param cluster_size The number of cells in each partition should be a
380 * multiple of cluster_size (for blocking later on)
381 *
382 * @param cell_partition Saves of each (block of cells) to which
383 * partition the block belongs
384 *
385 * @param partition_list partition_list[j] gives the old number of the
386 * block that should be renumbered to j due to the partitioning
387 *
388 * @param partition_size Vector pointing to start of each partition (on
389 * output)
390 *
391 * @param partition number of partitions created
392 */
393 void
394 make_partitioning(const DynamicSparsityPattern &connectivity,
395 const unsigned int cluster_size,
396 std::vector<unsigned int> &cell_partition,
397 std::vector<unsigned int> &partition_list,
398 std::vector<unsigned int> &partition_size,
399 unsigned int &partition) const;
400
401 /**
402 * Update fields of task info for task graph set up in
403 * make_thread_graph.
404 */
405 void
406 update_task_info(const unsigned int partition);
407
408 /**
409 * Creates a task graph from a connectivity structure.
410 */
411 void
412 create_flow_graph();
413
414 /**
415 * Returns the memory consumption of the class.
416 */
417 std::size_t
418 memory_consumption() const;
419
420 /**
421 * Prints minimum, average, and maximal memory consumption over the MPI
422 * processes.
423 */
424 template <typename StreamType>
425 void
426 print_memory_statistics(StreamType &out, std::size_t data_length) const;
427
428 /**
429 * Number of physical cells in the mesh, not cell batches after
430 * vectorization
431 */
432 unsigned int n_active_cells;
433
434 /**
435 * Number of physical ghost cells in the mesh which are subject to
436 * special treatment and should not be included in loops
437 */
438 unsigned int n_ghost_cells;
439
440 /**
441 * Number of lanes in the SIMD array that are used for vectorization
442 */
443 unsigned int vectorization_length;
444
445 /**
446 * Block size information for multithreading
447 */
448 unsigned int block_size;
449
450 /**
451 * Number of blocks for multithreading
452 */
453 unsigned int n_blocks;
454
455 /**
456 * Parallel scheme applied by multithreading
457 */
458 TasksParallelScheme scheme;
459
460 /**
461 * The blocks are organized by a vector-of-vector concept, and this data
462 * field @p partition_row_index stores the distance from one 'vector' to
463 * the next within the linear storage of all data to the two-level
464 * partitioning.
465 */
466 std::vector<unsigned int> partition_row_index;
467
468 /**
469 * This is a linear storage of all partitions, building a range of
470 * indices of the form cell_partition_data[idx] to
471 * cell_partition_data[idx+1] within the integer list of all cells in
472 * MatrixFree, subdivided into chunks by @p partition_row_index.
473 */
474 std::vector<unsigned int> cell_partition_data;
475
476 /**
477 * Like cell_partition_data but with precomputed subranges for each
478 * active fe index. The start and end point of a partition is given
479 * by cell_partition_data_hp_ptr.
480 */
481 std::vector<unsigned int> cell_partition_data_hp;
482
483 /**
484 * Pointers within cell_partition_data_hp, indicating the start and end
485 * of a partition.
486 */
487 std::vector<unsigned int> cell_partition_data_hp_ptr;
488
489 /**
490 * This is a linear storage of all partitions of inner faces, building a
491 * range of indices of the form face_partition_data[idx] to
492 * face_partition_data[idx+1] within the integer list of all interior
493 * faces in MatrixFree, subdivided into chunks by @p
494 * partition_row_index.
495 */
496 std::vector<unsigned int> face_partition_data;
497
498 /**
499 * Like face_partition_data but with precomputed subranges for each
500 * active fe index pair. The start and end point of a partition is given
501 * by face_partition_data_hp_ptr.
502 */
503 std::vector<unsigned int> face_partition_data_hp;
504
505 /**
506 * Pointers within face_partition_data_hp, indicating the start and end
507 * of a partition.
508 */
509 std::vector<unsigned int> face_partition_data_hp_ptr;
510
511 /**
512 * This is a linear storage of all partitions of boundary faces,
513 * building a range of indices of the form boundary_partition_data[idx]
514 * to boundary_partition_data[idx+1] within the integer list of all
515 * boundary faces in MatrixFree, subdivided into chunks by @p
516 * partition_row_index.
517 */
518 std::vector<unsigned int> boundary_partition_data;
519
520 /**
521 * Like boundary_partition_data but with precomputed subranges for each
522 * active fe index. The start and end point of a partition is given
523 * by boundary_partition_data_hp_ptr.
524 */
525 std::vector<unsigned int> boundary_partition_data_hp;
526
527 /**
528 * Pointers within boundary_partition_data_hp, indicating the start and
529 * end of a partition.
530 */
531 std::vector<unsigned int> boundary_partition_data_hp_ptr;
532
533 /**
534 * This is a linear storage of all partitions of interior faces on
535 * boundaries to other processors that are not locally used, building a
536 * range of indices of the form ghost_face_partition_data[idx] to
537 * ghost_face_partition_data[idx+1] within the integer list of all such
538 * faces in MatrixFree, subdivided into chunks by @p
539 * partition_row_index.
540 */
541 std::vector<unsigned int> ghost_face_partition_data;
542
543 /**
544 * This is a linear storage of all partitions of faces for multigrid
545 * levels that have a coarser neighbor and are only included in certain
546 * residual computations but not in smoothing, building a range of
547 * indices of the form refinement_edge_face_partition_data[idx] to
548 * refinement_edge_face_partition_data[idx+1] within the integer list of
549 * all such faces in MatrixFree, subdivided into chunks by @p
550 * partition_row_index.
551 */
552 std::vector<unsigned int> refinement_edge_face_partition_data;
553
554 /**
555 * Thread information (which chunk to start 'even' partitions from) to
556 * be handed to the dynamic task scheduler
557 */
558 std::vector<unsigned int> partition_evens;
559
560 /**
561 * Thread information (which chunk to start 'odd' partitions from) to be
562 * handed to the dynamic task scheduler
563 */
564 std::vector<unsigned int> partition_odds;
565
566 /**
567 * Thread information regarding the dependencies for partitions handed
568 * to the dynamic task scheduler
569 */
570 std::vector<unsigned int> partition_n_blocked_workers;
571
572 /**
573 * Thread information regarding the dependencies for partitions handed
574 * to the dynamic task scheduler
575 */
576 std::vector<unsigned int> partition_n_workers;
577
578 /**
579 * Number of even partitions accumulated over the field @p
580 * partition_evens
581 */
582 unsigned int evens;
583
584 /**
585 * Number of odd partitions accumulated over the field @p
586 * partition_odds
587 */
588 unsigned int odds;
589
590 /**
591 * Number of blocked workers accumulated over the field @p
592 * partition_n_blocked_workers
593 */
594 unsigned int n_blocked_workers;
595
596 /**
597 * Number of workers accumulated over the field @p partition_n_workers
598 */
599 unsigned int n_workers;
600
601 /**
602 * Stores whether a particular task is at an MPI boundary and needs data
603 * exchange
604 */
605 std::vector<unsigned char> task_at_mpi_boundary;
606
607 /**
608 * MPI communicator
609 */
610 MPI_Comm communicator;
611
612 /**
613 * Shared-memory MPI communicator
614 */
615 MPI_Comm communicator_sm;
616
617 /**
618 * Assert that vectors passed to the MatrixFree loops are not ghosted.
619 */
620 bool allow_ghosted_vectors_in_loops;
621
622 /**
623 * Rank of MPI process
624 */
625 unsigned int my_pid;
626
627 /**
628 * Number of MPI rank for the current communicator
629 */
630 unsigned int n_procs;
631 };
632
633 } // end of namespace MatrixFreeFunctions
634 } // end of namespace internal
635
636 DEAL_II_NAMESPACE_CLOSE
637
638 #endif