Distributed algorithms¶

Each algorithm operates on a range that is distributed over the processes of a communicator: every process holds a contiguous part, and the global range is their concatenation in rank order.

Reductions¶

template<std::ranges::forward_range R, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class BinaryOp = std::plus<>> requires kamping::v2::has_mpi_type<R> std::ranges::range_value_t<R> reduce(R &&r, std::ranges::range_value_t<R> init = {}, BinaryOp const &op = {}, Comm const &comm = MPI_COMM_WORLD)¶

Reduces the globally distributed range to a scalar, available on all ranks.

Distributed equivalent of std::reduce applied to the concatenation of all local ranges. Returns op(init, in[0], in[1], …, in[N-1]) where N is the global element count.

R must be a forward_range with a deducible MPI element type (contiguous layout is not required; only the element type determines the MPI_Datatype for the scalar allreduce). Each rank computes its local reduction then participates in an allreduce. Empty ranks contribute T{} to the allreduce, so T{} must be the identity element for op when empty ranks are possible.

Precondition

op must be associative, commutative, and mappable to an MPI_Op.

Precondition

If any rank’s range is empty, T{} must be the identity element for op.

Defined in header <dstl/algorithm/reduce.hpp>

template<std::ranges::forward_range R, kamping::v2::rank Rank = int, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class BinaryOp = std::plus<>> requires kamping::v2::has_mpi_type<R> std::optional<std::ranges::range_value_t<R>> reduce_to_root(R &&r, std::ranges::range_value_t<R> init = {}, BinaryOp const &op = {}, Rank root = {}, Comm const &comm = MPI_COMM_WORLD)¶

Reduces the globally distributed range to a scalar on the root rank.

Distributed equivalent of std::reduce applied to the concatenation of all local ranges, but the result is returned only on the root rank. Non-root ranks receive std::nullopt. Returns std::optional containing op(init, in[0], …, in[N-1]) on root, and std::nullopt on all other ranks.

Precondition

op must be associative, commutative, and mappable to an MPI_Op.

Precondition

If any rank’s range is empty, T{} must be the identity element for op.

Defined in header <dstl/algorithm/reduce.hpp>

template<std::ranges::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> requires kamping::v2::has_mpi_type<R> && std::copy_constructible<std::ranges::range_value_t<R>> std::ranges::range_value_t<R> min(R &&r, Comp comp, Proj proj, Comm const &comm, std::ranges::range_value_t<R> sentinel)¶ (1)

template<std::ranges::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> requires kamping::v2::has_mpi_type<R> && std::numeric_limits<std::ranges::range_value_t<R>>::is_specialized && std::copy_constructible<std::ranges::range_value_t<R>> std::ranges::range_value_t<R> min(R &&r, Comp comp = {}, Proj proj = {}, Comm const &comm = MPI_COMM_WORLD)¶ (2)

(1) Returns the smallest element of the globally distributed range.

Distributed equivalent of std::ranges::min applied to the concatenation of all local ranges across the communicator. The result is available on every rank.

Each rank computes its local minimum under comp/proj (or sentinel if its local range is empty), then a single MPI_Allreduce combines the per-rank candidates. When comp/proj are the defaults and T is an MPI builtin arithmetic type, this dispatches straight to MPI_MIN (no MPI_Op_create involved); otherwise a custom MPI_Op is built from comp/proj via make_op, which requires them to be stateless (default-constructible, as they already must be to have default arguments here).

R must be a forward_range with a deducible MPI element type, and its value type T must be copy-constructible (std::copy_constructible<T>). Notably T need not be assignable, so this works directly on e.g. std::pair<const K, V> (the value type of iterating a std::map).

Precondition

sentinel must be an upper bound for every element under comp/proj.

Note

If every rank’s range is empty, the result is sentinel, unlike std::ranges::min, whose behavior on an empty range is undefined.

(2) Overload defaulting comp/proj/comm/sentinel; requires std::numeric_limits<T> to be specialized so std::numeric_limits<T>::max() is a meaningful sentinel. For T without a numeric_limits specialization, call the overload above with an explicit sentinel.

Parameters:

sentinel – Value contributed on behalf of a rank whose local range is empty; must compare not-less than every real element under comp/proj. Defaults to std::numeric_limits<T>::max() when std::numeric_limits<T> is specialized; for other T an explicit sentinel must be supplied.

Defined in header <dstl/algorithm/min.hpp>

template<std::ranges::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> requires kamping::v2::has_mpi_type<R> && std::copy_constructible<std::ranges::range_value_t<R>> std::ranges::range_value_t<R> max(R &&r, Comp comp, Proj proj, Comm const &comm, std::ranges::range_value_t<R> sentinel)¶ (1)

template<std::ranges::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> requires kamping::v2::has_mpi_type<R> && std::numeric_limits<std::ranges::range_value_t<R>>::is_specialized && std::copy_constructible<std::ranges::range_value_t<R>> std::ranges::range_value_t<R> max(R &&r, Comp comp = {}, Proj proj = {}, Comm const &comm = MPI_COMM_WORLD)¶ (2)

(1) Returns the largest element of the globally distributed range.

Distributed equivalent of std::ranges::max applied to the concatenation of all local ranges across the communicator. The result is available on every rank.

Each rank computes its local maximum under comp/proj (or sentinel if its local range is empty), then a single MPI_Allreduce combines the per-rank candidates. When comp/proj are the defaults and T is an MPI builtin arithmetic type, this dispatches straight to MPI_MAX (no MPI_Op_create involved); otherwise a custom MPI_Op is built from comp/proj via make_op, which requires them to be stateless (default-constructible, as they already must be to have default arguments here).

Precondition

sentinel must be a lower bound for every element under comp/proj.

Note

If every rank’s range is empty, the result is sentinel, unlike std::ranges::max, whose behavior on an empty range is undefined.

(2) Overload defaulting comp/proj/comm/sentinel; requires std::numeric_limits<T> to be specialized so std::numeric_limits<T>::lowest() is a meaningful sentinel. For T without a numeric_limits specialization, call the overload above with an explicit sentinel.

Parameters:

sentinel – Value contributed on behalf of a rank whose local range is empty; must compare not-greater than every real element under comp/proj. Defaults to std::numeric_limits<T>::lowest() when std::numeric_limits<T> is specialized; for other T an explicit sentinel must be supplied.

Defined in header <dstl/algorithm/max.hpp>

template<kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> bool all_of(bool value, Comm const &comm = MPI_COMM_WORLD)¶ (1)
template<std::input_iterator I, std::sentinel_for<I> S, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class Proj = std::identity, std::indirect_unary_predicate<std::projected<I, Proj>> Pred> bool all_of(I first, S last, Pred pred, Comm const &comm = MPI_COMM_WORLD, Proj proj = {})¶ (2)
template<std::ranges::input_range R, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class Proj = std::identity, std::indirect_unary_predicate<std::projected<std::ranges::iterator_t<R>, Proj>> Pred> bool all_of(R &&r, Pred pred, Comm const &comm = MPI_COMM_WORLD, Proj proj = {})¶ (3): Defined in header <dstl/algorithm/all_of.hpp>

template<std::ranges::bidirectional_range R, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less> requires kamping::v2::has_mpi_type<R> bool is_sorted(R &&r, Comm const &comm = MPI_COMM_WORLD, Comp comp = {}, Proj proj = {})¶

Tests whether the globally distributed range is sorted.

Distributed equivalent of std::ranges::is_sorted. Returns true iff:

Each rank’s local slice is sorted under comp and proj, and
For every adjacent pair of non-empty ranks, the last element of the left rank is not greater than the first element of the right rank.

R must be a bidirectional_range (to access the last element in O(1) via std::prev) with a deducible MPI element type. The range itself is never passed to MPI; only a single stack-allocated boundary element is exchanged.

Empty ranks are skipped via with_subset: the sub-communicator of non-empty ranks checks their pair-wise boundaries with a single shift_right exchange.

Defined in header <dstl/algorithm/is_sorted.hpp>

Prefix sums¶

template<std::ranges::forward_range R, kamping::v2::recv_buffer O, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class BinaryOp = std::plus<>> requires kamping::v2::has_mpi_type<R> void inclusive_scan(R &&r, O &&out, BinaryOp const &op = {}, Comm const &comm = MPI_COMM_WORLD)¶

Inclusive prefix scan over the globally distributed range.

Distributed equivalent of std::inclusive_scan applied to the concatenation of all local ranges across the communicator. The element at global position i in the output is op(in[0], …, in[i]).

R must be a forward_range (for consistency; only one pass is made) with a deducible MPI element type. O must be a contiguous mutable buffer (recv_buffer).

Algorithm:

Local std::inclusive_scan; the last element of out is the local total.
MPI exscan of local totals across non-empty ranks → per-rank prefix.
For ranks with a predecessor: apply op(rank_prefix, out[i]) to every local output.

Empty ranks are excluded from the exscan via dstl::with_subset, so no identity element for op is required.

Precondition

out must have the same element count as r on each rank.

Precondition

op must be associative and mappable to an MPI_Op.

Defined in header <dstl/algorithm/inclusive_scan.hpp>

template<std::ranges::forward_range R, kamping::v2::recv_buffer O, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm, class BinaryOp = std::plus<>> requires kamping::v2::has_mpi_type<R> void exclusive_scan(R &&r, O &&out, std::ranges::range_value_t<R> init, BinaryOp const &op = {}, Comm const &comm = MPI_COMM_WORLD)¶

Exclusive prefix scan over the globally distributed range.

Distributed equivalent of std::exclusive_scan applied to the concatenation of all local ranges across the communicator. The element at global position i in the output is op(init, in[0], …, in[i-1]).

R must be a forward_range (two passes are made: one to compute the local total, one for std::exclusive_scan) with a deducible MPI element type. The MPI element type is needed for the scalar exscan across ranks. O must be a contiguous mutable buffer.

Algorithm:

Compute local_total via a fold over r (first pass).
MPI exscan of local totals across non-empty ranks → per-rank prefix.
std::exclusive_scan over r into out with the rank-adjusted init (second pass).

Empty ranks are excluded from the exscan via dstl::with_subset; no identity element for op is required.

Precondition

out must have the same element count as r on each rank.

Precondition

op must be associative and mappable to an MPI_Op.

Defined in header <dstl/algorithm/exclusive_scan.hpp>

Shifting¶

template<std::ranges::contiguous_range R, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> requires kamping::v2::send_recv_buffer<R> std::ranges::borrowed_subrange_t<R> shift_left(R &&r, std::ranges::range_difference_t<R> n, Comm const &comm = MPI_COMM_WORLD)¶

Shifts the distributed range left by n positions globally.

Distributed equivalent of std::shift_left applied to the concatenation of all local ranges across the communicator. Elements at global position i are moved to global position i - n. The last n elements of the last rank are value-initialized.

For the regular case (n <= local size on every rank), each rank performs a blocking sendrecv with its right neighbor to exchange the n boundary elements, then applies a local std::shift_left.

For the irregular case (n exceeds the local size on at least one rank), the first n elements are stripped from the global send distribution and dstl::redistribute is called with the truncated send view and a correspondingly smaller recv count on the trailing ranks. This ensures total send == total recv so redistribute operates without holes.

Returns:: Per-rank subrange of r indicating the locally valid portion after the shift. On ranks where all output elements originate from the original global array this is [begin, end). On the rightmost affected rank(s) it covers only the elements with a valid source; the remainder are value-initialized.

Defined in header <dstl/algorithm/shift.hpp>

template<std::ranges::contiguous_range R, kamping::v2::convertible_to_mpi_handle<MPI_Comm> Comm = MPI_Comm> requires kamping::v2::send_recv_buffer<R> std::ranges::borrowed_subrange_t<R> shift_right(R &&r, std::ranges::range_difference_t<R> n, Comm const &comm = MPI_COMM_WORLD)¶

Shifts the distributed range right by n positions globally.

Distributed equivalent of std::shift_right applied to the concatenation of all local ranges across the communicator. Elements at global position i are moved to global position i + n. The first n elements of rank 0 are value-initialized.

For the regular case (n <= local size on every rank), each rank performs a blocking sendrecv with its left neighbor to exchange the n boundary elements, then applies a local std::shift_right.

For the irregular case, the last n elements are stripped from the global send distribution and dstl::redistribute is called with the truncated send view and each rank’s recv buffer pointing into the non-zero suffix of the output staging vector. The zero prefix is provided by value-initialization.

Returns:: Per-rank subrange of r indicating the locally valid portion after the shift. On ranks where all output elements originate from the original global array this is [begin, end). On the leftmost affected rank(s) it starts after begin(); the preceding elements are value-initialized.

Defined in header <dstl/algorithm/shift.hpp>