crystal_router Module Reference

Crystal router: scalable all-to-some personalized exchange. More...

Functions/Subroutines
subroutine, public	crystal_router_pack (out, dest, body)
	Append one record to a packed crystal-router buffer.
subroutine, public	crystal_router_transfer (buf, n)
	Route packed records to their destination ranks.
subroutine	cr_check_dest (buf, n)
	Abort if any record destination falls outside \( [0, P) \).
subroutine	cr_partition (buf, n, mid, lower, keep, nkeep, snd, nsnd)
	Partition buf into records kept locally and records to be sent. A record is kept when the side of its destination (relative to mid) matches lower, i.e. it already belongs to our half.
subroutine	cr_exchange (sbuf, sn, dst, rbuf, rn, src)
	Size-negotiated bidirectional exchange with a partner. Either dst or src may be MPI_PROC_NULL to make that direction a no-op.
subroutine	cr_concat (buf, n, a, na, b, nb)
	Rebuild buf as the concatenation a(1:na) ++ b(1:nb).
subroutine	cr_append (buf, n, e, ne)
	Append e(1:ne) to buf(1:n) in place.

Variables
integer, parameter	cr_tag = 0
	Message tag used for all crystal-router exchanges. Stages are fully synchronised (blocking MPI_Sendrecv), so a single tag suffices.

Detailed Description

Routes a set of variable-length records, each tagged with a destination rank, from any source to any destination in \( \lceil \log_2 P \rceil \) communication stages. This replaces dense \( O(P) \)-round neighbour discovery / personalized exchange (which is \( O(P^2) \) globally and, under flat MPI at high rank counts, exhausts the MPI runtime's internal unexpected-message buffers) with a recursive-bisection routing that talks to at most one or two partners per stage.

Records are passed in a single packed integer(i8) buffer as a sequence of self-describing entries

     [ dest, len, payload(1), ..., payload(len) ]

where dest is the destination rank in \( [0, P) \) and len is the payload length. On return the buffer holds exactly the records whose dest equals pe_rank, in the same packed format (the dest/len headers are preserved so the caller can unpack uniformly).

Algorithm and correctness

The active rank range [lo, hi) always contains pe_rank; it starts as [0, P) and is halved each stage at mid = lo + (hi-lo)/2. A record is kept if its destination lies in the local half and otherwise shipped to a partner in the opposite half. Since a record is always moved into the half containing its destination, the range invariant "`dest in [lo, hi)`" is preserved, and when the range collapses to a single rank that rank is the destination – so every record is delivered exactly once and none is dropped.

For odd-sized ranges the upper half has exactly one more rank than the lower half, leaving one unpaired upper rank (hi-1). That rank still holds records destined for the lower half; it offloads them to rank lo, which performs one extra receive. All other ranks exchange with a single partner via MPI_Sendrecv, and the unpaired transfers use MPI_PROC_NULL for the idle direction, so every stage is fully matched and deadlock-free for any P (not only powers of two). Message sizes are negotiated per stage (a one-integer count exchange precedes each data exchange), so no global maximum buffer is ever allocated.

Function/Subroutine Documentation

cr_append()

subroutine crystal_router::cr_append ( integer(i8), dimension(:), intent(inout), allocatable  buf, integer, intent(inout)  n, integer(i8), dimension(:), intent(in), allocatable  e, integer, intent(in)  ne  )

private

Definition at line 276 of file crystal_router.f90.

Here is the caller graph for this function:

cr_check_dest()

subroutine crystal_router::cr_check_dest ( integer(i8), dimension(:), intent(in), allocatable  buf, integer, intent(in)  n  )

private

Definition at line 192 of file crystal_router.f90.

Here is the caller graph for this function:

cr_concat()

subroutine crystal_router::cr_concat ( integer(i8), dimension(:), intent(inout), allocatable  buf, integer, intent(out)  n, integer(i8), dimension(:), intent(in), allocatable  a, integer, intent(in)  na, integer(i8), dimension(:), intent(in), allocatable  b, integer, intent(in)  nb  )

private

Definition at line 262 of file crystal_router.f90.

Here is the caller graph for this function:

cr_exchange()

subroutine crystal_router::cr_exchange ( integer(i8), dimension(:), intent(in)  sbuf, integer, intent(in)  sn, integer, intent(in)  dst, integer(i8), dimension(:), intent(out), allocatable  rbuf, integer, intent(out)  rn, integer, intent(in)  src  )

private

Definition at line 244 of file crystal_router.f90.

Here is the caller graph for this function:

cr_partition()

subroutine crystal_router::cr_partition ( integer(i8), dimension(:), intent(in), allocatable  buf, integer, intent(in)  n, integer, intent(in)  mid, logical, intent(in)  lower, integer(i8), dimension(:), intent(out), allocatable  keep, integer, intent(out)  nkeep, integer(i8), dimension(:), intent(out), allocatable  snd, integer, intent(out)  nsnd  )

private

Definition at line 211 of file crystal_router.f90.

Here is the caller graph for this function:

crystal_router_pack()

subroutine, public crystal_router::crystal_router_pack	(	type(stack_i8_t), intent(inout)	out,
		integer, intent(in)	dest,
		integer(i8), dimension(:), intent(in)	body
	)

Writes the self-describing entry [dest, size(body), body...] that crystal_router_transfer consumes. Owning the record format here means call sites only supply a destination rank and a payload, and never encode the [dest, len, ...] envelope themselves.

Parameters

out	Stack accumulating the packed records.
dest	Destination rank for this record, in \( [0, P) \).
body	The record payload (its length becomes the len field).

Definition at line 98 of file crystal_router.f90.

Here is the caller graph for this function:

crystal_router_transfer()

subroutine, public crystal_router::crystal_router_transfer	(	integer(i8), dimension(:), intent(inout), allocatable	buf,
		integer, intent(inout)	n
	)

Parameters

buf	Packed records [dest, len, payload...] repeated. On entry, arbitrary destinations in \( [0, P) \); on exit, only the records addressed to pe_rank (may be reallocated).
n	Used length of buf (number of integer(i8) words). Updated on exit to the length of the received set.

Definition at line 121 of file crystal_router.f90.

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

cr_tag

integer, parameter crystal_router::cr_tag = 0

private

Definition at line 84 of file crystal_router.f90.