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.

The algorithm is the crystal router of Fox et al., "Solving Problems on Concurrent Processors, Volume 1", Prentice-Hall, 1988.

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 279 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 195 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 265 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 247 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 214 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 101 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 124 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 87 of file crystal_router.f90.