All-to-all-v¶

Grid all-to-all-v¶

template<grid_send_buffer SBuf, typename RBuf, is_execution_policy Exec, grid_compatible_output_layout Order = layout::unordered> requires grid_recv_buffer<RBuf, Order> && (!std::is_same_v<Order, layout::ordered_by_source> || std::indirectly_copyable<std::ranges::iterator_t<SBuf>, std::ranges::iterator_t<RBuf>>) kamping::v2::result<SBuf, RBuf> grid_alltoallv(SBuf &&sbuf, RBuf &&rbuf, grid_comm<Exec> const &grid, Order order = {})¶

All-to-all-v that routes the data through a grid of processes, combining messages on the way.

A flat alltoallv sends up to p−1 messages per process. On a grid_comm with dimensions s_0 × … × s_{k−1}, the data is instead exchanged in k phases, one per dimension, with up to s_i messages each: Σ s_i messages per process, about 2√p on a two-dimensional grid. This pays off for many small messages on many processes, at the cost of forwarding each element up to k times.

The call looks like kamping::v2::alltoallv, with a grid_comm instead of a communicator:

dstl::grid_comm grid{comm};
std::vector<int> recv;
dstl::grid_alltoallv(data | views::with_counts(counts) | views::auto_displs, recv | views::resize, grid);

With the default layout::unordered, rbuf receives the right elements, but grouped by routing path rather than by source rank. With layout::ordered_by_source, the result is identical to a flat alltoallv, including the per-source counts, which needs a variable-size receive buffer (see grid_recv_buffer) and some extra local work.

Parameters:

order – layout::unordered (default) or layout::ordered_by_source.

Returns:: The send and receive buffer, as from kamping::v2::alltoallv.

Defined in header <dstl/grid_alltoallv.hpp>

template<is_execution_policy Exec = execution_policy::par> class grid_comm¶

A communicator whose processes are arranged in a k-dimensional grid, for grid_alltoallv.

The grid dimensions s_0 × … × s_{k−1} (their product is the number of processes) are chosen by a factoring strategy, by default a balanced two-dimensional grid (dims_create), or given explicitly. Each dimension has a subcommunicator connecting the processes that differ only in that coordinate. Ranks are numbered row-major: the last dimension groups consecutive ranks, e.g. the processes of a compute node. Exec selects how the grid alltoallv uses threads (see execution_policy). The communicator accessors (rank(), size(), …) refer to the global communicator.

Defined in header <dstl/grid_comm.hpp>

explicit grid_comm(kamping::v2::comm_view global)¶ (1)

template<factoring Strategy> grid_comm(kamping::v2::comm_view global, Strategy strategy)¶ (2)

template<std::ranges::input_range R> requires std::convertible_to<std::ranges::range_value_t<R>, std::size_t> grid_comm(kamping::v2::comm_view global, R &&dims)¶ (3)

(1) Build a grid over global using the default factoring strategy (balanced 2-level grid).

(2) Build a grid over global using a factoring strategy.

(3) Build a grid over global with explicit dimensions. dims is any input range of values convertible to std::size_t; the product of dims must equal the size of global (a complete grid).

std::size_t num_dims() const noexcept¶

Returns:: The number of grid dimensions k.

std::size_t dim_size(std::size_t i) const¶

Returns:: The size s_i of dimension i.

kamping::v2::comm_view subcomm(std::size_t i) const¶

Returns:: A non-owning view of the subcommunicator for dimension i (size s_i).

template<std::ranges::output_range<std::size_t> R> std::ranges::borrowed_iterator_t<R> coords(int rank, R &&out) const¶ (1)

std::vector<std::size_t> coords(int rank) const¶ (2)

(1) Decompose a global rank into its mixed-radix coordinates (c_0 most significant), writing the num_dims() coordinates into the output range out. For a sized range, asserts it holds exactly num_dims() elements; for an unbounded sink (e.g. std::views::counted of a back-inserter) the caller is responsible for capacity.

(2)

Returns:

(1) The iterator one past the last written coordinate.
(2) The mixed-radix coordinates of a global rank as a vector.

template<std::ranges::input_range R> requires std::convertible_to<std::ranges::range_value_t<R>, std::size_t> int rank_of(R &&coords) const¶: Compose mixed-radix coordinates (c_0 most significant) back into a global rank. coords is any input range of exactly num_dims() values yielding the coordinates in dimension order.

bool is_complete() const noexcept¶

Returns:: Whether the product of the dimensions equals the number of processes. Always true: incomplete grids are rejected at construction.

std::size_t stride(std::size_t i) const¶

Returns:: The row-major stride of dimension i (product of all later dimensions; 1 for i==k-1).

int rank() const¶

Returns:: The rank of the calling process in this communicator.

int size() const¶

Returns:: The number of processes in this communicator.

kamping::v2::group group() const¶

Extract the group associated with this communicator.

The returned group is owned by the caller.

Throws:

mpi_error – if MPI_Comm_group fails.

comm dup() const¶

Collective: duplicate this communicator (MPI_Comm_dup).

All processes in the communicator must call this collectively. Delegates to the free function kamping::v2::dup.

Throws:

mpi_error – if MPI_Comm_dup fails.

comm split(int color, int key = 0) const¶

Collective: split this communicator by color and key (MPI_Comm_split).

Processes with the same color form a sub-communicator ordered by key. Pass MPI_UNDEFINED as color to opt out — result is MPI_COMM_NULL. Delegates to the free function kamping::v2::split.

Throws:

mpi_error – if MPI_Comm_split fails.

template<typename SBuf> concept grid_send_buffer¶

template<typename SBuf>
concept grid_send_buffer = kamping::v2::send_buffer_v<SBuf> && std::ranges::contiguous_range<SBuf>
                           && detail::grid_element<std::ranges::range_value_t<SBuf>>

A send buffer for grid_alltoallv: a variable-size send buffer that is also a contiguous range, e.g. data | views::with_counts(counts) | views::auto_displs. Its elements must be default-initializable and copyable.

Defined in header <dstl/grid_alltoallv.hpp>

template<typename RBuf, typename Order> concept grid_recv_buffer¶

template<typename RBuf, typename Order>
concept grid_recv_buffer = std::ranges::contiguous_range<RBuf>
                           && ((std::is_same_v<Order, layout::ordered_by_source> && kamping::v2::recv_buffer_v<RBuf>)
                               || (!std::is_same_v<Order, layout::ordered_by_source> && kamping::v2::recv_buffer<RBuf>))
                           && detail::grid_element<std::ranges::range_value_t<RBuf>>

A receive buffer for grid_alltoallv with receive layout Order, a contiguous range of default-initializable, copyable elements. With layout::ordered_by_source it must be a variable-size receive buffer, which receives the per-source counts (e.g. views::auto_recv_v); with layout::unordered any receive buffer will do (e.g. a presized std::vector<T> or views::resize).

Send and receive element types may differ. With layout::unordered, as for a plain MPI_Alltoallv, only their datatype signatures have to match; with layout::ordered_by_source, the send elements must also be copyable to the receive elements.

Defined in header <dstl/grid_alltoallv.hpp>

Factoring the grid¶

template<typename T> concept factoring¶

template<typename T>
concept factoring = requires(T const& strategy, kamping::v2::comm_view global) {
    { strategy(global) } -> std::convertible_to<std::vector<std::size_t>>;
}

A factoring strategy: a callable that maps the global communicator to the grid dimensions, e.g. dims_create.

Defined in header <dstl/factoring.hpp>

struct dims_create¶

A balanced grid with levels dimensions (default 2), computed with MPI_Dims_create: the dimensions multiply to the number of processes and are as close to each other as possible.

Defined in header <dstl/factoring.hpp>

struct explicit_dims¶

Dimensions given by the caller, used as they are; their product must equal the number of processes.

Defined in header <dstl/factoring.hpp>

struct topology_aware¶

One dimension per hardware level: a two-dimensional grid of nodes × processes per node, derived from MPI_Comm_split_type(MPI_COMM_TYPE_SHARED). Falls back to dims_create{2} if the nodes have different numbers of processes.

Defined in header <dstl/factoring.hpp>

Execution policies¶

struct seq¶

Sequential: one thread regroups the elements between phases and issues all MPI calls. Works with any MPI thread level.