1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//! Distributed computations in RLST
//!
//! RLST supports MPI distributed arrays and sparse matrices. Moreover,
//! it provides a number of utility routines for working with distributed data layouts.
//!
//! # Index Layouts
//!
//! The basic structure to store information about data distributions is the [IndexLayout](crate::distributed_tools::IndexLayout).
//! It stores an MPI communicator `comm` and a vector `scan` of length `1 + nprocs` where `nprocs` is the number of processes in the MPI
//! communicator. The range `scan[i]..scan[i + 1]` contains the indices on rank `i` (excluding the index `scan[i + 1]`).
//!
//! The easiest way to create an index layout is to use the function [IndexLayout::from_local_counts](crate::distributed_tools::IndexLayout::from_local_counts).
//! Each process calls this function with the number of local variables. They then communicate their local count to all other processes so that each process
//! can construct the complete `scan` vector.
//!
//! It is also possible to construct an index layout from [IndexLayout::from_equidistributed_chunks](crate::distributed_tools::IndexLayout::from_equidistributed_chunks). This expects the `nchunks` describing the overall number of chunks across all processes and a parameter `chunk_size` that specifies how many indices
//! are associated with each chunk. This is useful for example when we want to distribute n vectors with 3 elements each. Then `nchunks` is `n` and `chunk_size`
//! is 3. The resulting distribution will ensure that each process has a multiple of 3 local indices.
//!
//!
//!
//! # Distributed arrays
//!
//! RLST provides a [DistributedArray](crate::sparse::distributed_array::DistributedArray) type.
//! This consists of an [IndexLayout](crate::distributed_tools::IndexLayout) and a local [Array](crate::dense::array::Array) type.
//! Data is always distributed along the first dimension, meaning that for distributed matrices
//! each process owns consecutive rows. A distributed array stores its layout in an `Rc`, so callers
//! can cheaply clone the shared layout handle and use it independently while mutating local data.
//!
//! Distributed arrays support most operations from standard arrays whereas the result always refers to the global array, e.g. the method `inner` performs an inner product across all processes, or `shape` returns the global shape of the distributed array.
//!
//! For distributed arrays the following methods are available to distribute data to multiple processes or gather data on a single process.
//!
//! - [DistributedArray::gather_to_all](crate::sparse::distributed_array::DistributedArray::gather_to_all):
//! Gather the global array into local arrays on each process.
//! - [`DistributedArray::gather_to_one`](crate::sparse::distributed_array::DistributedArray::gather_to_one):
//! non-root side of a gather to `root`.
//! - [`DistributedArray::gather_to_one_root`](crate::sparse::distributed_array::DistributedArray::gather_to_one_root):
//! root side of the same gather.
//! - [`ScatterFromOne::scatter_from_one`](crate::traits::distributed::ScatterFromOne::scatter_from_one):
//! non-root side of scattering an array along its first dimension.
//! - [`ScatterFromOne::scatter_from_one_root`](crate::traits::distributed::ScatterFromOne::scatter_from_one_root):
//! root side of the same scatter.
//!
//! These paired methods still form one collective operation: every rank must call the appropriate
//! side with the same root and compatible layout. On the root, the source first dimension must
//! equal the layout's global size; all trailing dimensions are preserved.
//!
//! ## Empty partitions and migration
//!
//! An [`IndexLayout`](crate::distributed_tools::IndexLayout) may contain repeated
//! offsets, so a rank may own no indices and the entire layout may be empty. Every
//! rank must still call distributed operations in the same order; an empty local
//! slice is not a reason to skip a collective. Gather and redistribution routines
//! preserve empty slices, and sortedness of a globally empty sequence is `true`.
//!
//! `global_min` and `global_max` now return `Option<T>`: they return `None` when
//! the global input is empty. Callers that previously assumed a value must handle
//! this case explicitly. `communicate_back` returns the first value on the next
//! *nonempty* rank (or `None`), including when the calling rank is empty.
//! `parsort` accepts empty local input and can produce empty output ranks; it
//! preserves all records but promises only approximate output balance.
//!
//! Chunked ghost, mapping, and permutation operations require a positive,
//! communicator-consistent chunk size even when the local input is empty. Roots,
//! layouts, and other collective metadata must likewise agree on every rank.
//! RLST validates metadata before a payload phase where possible, but cannot
//! recover from ranks that do not enter the same collective sequence, mismatched
//! communicators, arbitrary user panics, allocation failure, or MPI runtime
//! failure. Empty subsets embedded with
//! [`IndexEmbedding`](crate::distributed_tools::index_embedding::IndexEmbedding) leave all
//! unselected output positions at `Default::default()`.
//!
//! # Distributed sparse matrices
//!
//! RLST supports distributed CSR matrices via the [DistributedCsrMatrix](crate::sparse::distributed_csr_mat::DistributedCsrMatrix)
//! that operate on distributed arrays. A distributed matrix is defined by a domain layout and a range layout.
//! The domain layout determines the distribution of vectors that are multiplied with the sparse matrix and the range layout determines the distribution of
//! the rows of the distributed sparse matrix. To create a distributed sparse matrix the method
//! [DistributedCsrMatrix::from_aij](crate::traits::sparse::FromAijDistributed::from_aij)
//! from the [FromAijDistributed](crate::traits::sparse::FromAijDistributed) trait. Each process can contribute arbitrary global elements, also for rows that
//! are not associated with the current rank. The constructor routines ensures that elements are communicated to the correct process. Multiple elements associated
//! with the same global row and column are summed up on creation. All ranks must participate,
//! including ranks contributing empty slices. The three local AIJ slices must have equal lengths;
//! global row indices are bounded by the range layout and columns by the domain layout.
//!
//! # Distributed communication patterns
//!
//! RLST has support routines for a number of distributed communication patterns.
//!
//! ## Tools for distributed arrays
//!
//! - [sort_to_bins](crate::distributed_tools::array_tools::sort_to_bins): Take a sorted sequence and distribute it into half-open bins. This is useful
//! for redistributing data across MPI ranks when the data distribution changes.
//! - [all_to_allv](crate::distributed_tools::array_tools::all_to_allv): A simplified MPI all_to_all communication routine.
//! - [scatterv](crate::distributed_tools::array_tools::scatterv): A simplified MPI scatter communication routine.
//! - [scatterv_root](crate::distributed_tools::array_tools::scatterv_root): A simplified MPI scatter communication routine. Call from root.
//!
//! ## Ghost communicators
//!
//! We are often in situations where we need data associated with indices on other processes. These indices are called ghost indices.
//! Underlying this is the pattern of a communication graph in which a process `j` receives data from all processes that are original owners of
//! ghost indices that `j` requires and in which `j` sends out data to all processes who have ghost indices from process `j`. A ghost communicator
//! is instantiated by calling [GhostCommunicator::new](crate::distributed_tools::ghost_communicator::GhostCommunicator::new) with the global indices
//! of the ghosts that the process needs and the owners of those indices. Once instantiated ghost data can be communicated with the following methods.
//!
//! - [GhostCommunicator::forward_send_values](crate::distributed_tools::ghost_communicator::GhostCommunicator::forward_send_values):
//! Each process forward sends data to the processes that require them.
//! - [GhostCommunicator::forward_send_values_by_chunks](crate::distributed_tools::ghost_communicator::GhostCommunicator::forward_send_values_by_chunks):
//! Forward send values by chunks. Use this if more than one data item is associated with an index.
//! - [GhostCommunicator::backward_send_values](crate::distributed_tools::ghost_communicator::GhostCommunicator::backward_send_values):
//! Send data from the ghost processes backwards to the owners.
//! - [GhostCommunicator::backward_send_values_by_chunks](crate::distributed_tools::ghost_communicator::GhostCommunicator::backward_send_values_by_chunks):
//! Send data from the ghost processes backwards to the owners by chunks. Use this if more than one data item is associated with an index.
//!
//! A complete worked out example for the use of the ghost communicator can be found in `examples/ghost_communicator.rs`.
//!
//! ## Mapping global to local data
//!
//! Imagine a global index set with indices from 0 to 9. The first process may need the indices `0, 1, 2, 3, 4, 5, 6`, and the second process
//! may need the indices `5, 6, 7, 8, 9`. Notice that 5 and 6 are repeated for both processes.
//! The [Global2LocalDataMapper](crate::distributed_tools::data_mapper::Global2LocalDataMapper) manages this communication
//! pattern. It is instantiated with [Global2LocalDataMapper::new](crate::distributed_tools::data_mapper::Global2LocalDataMapper) which takes the
//! index layout and the required global dofs.
//! The method [Global2LocalDataMapper::map_data](crate::distributed_tools::data_mapper::Global2LocalDataMapper::map_data) then maps a vector of global data
//! to the required local data. A chunk size can be given if each index is associated with multiple elements in the data vector.
//!
//! ## Data permutations
//!
//! Consider an index layout in which the first process owns indices `0, 1, 2, 3, 4` and the second process owns the indices `5, 6, 7, 8, 9`.
//! We want to create a new index layout in which the first process owns `0, 2, 4, 6, 8` and the second process owns `1, 3, 5, 7, 9`. Notice that this is
//! a permutation of the original layout. Each index still occurs exactly once. The [DataPermutation](crate::distributed_tools::permutation::DataPermutation)
//! type provides [forward_permute](crate::distributed_tools::permutation::DataPermutation::forward_permute) and a
//! [backward_permute](crate::distributed_tools::permutation::DataPermutation::backward_permute) method to map data from a given index layout to a custom
//! permutation and back.