Routing plan for the crystal router gather-scatter comm. backends. More...
Data Types | |
| type | gs_crystal_plan_t |
| The full routing plan for one gather-scatter schedule. More... | |
| type | gs_crystal_stage_t |
| One active communication stage of the routing plan. More... | |
Functions/Subroutines | |
| subroutine | gs_crystal_plan_init (this, send_pe, recv_pe, send_dof, recv_dof) |
| Work out the routing plan for a gather-scatter schedule. | |
| subroutine | cr_final_dofs (this, rdest, rorig, rlen, nrec, recv_pe, recv_dof) |
| Turn the records left at the end of the routing into the reduction order of the delivered words. | |
| subroutine | cr_meta_exchange (sbuf, nsrec, dst, rbuf, nrrec, src) |
| Size-negotiated bidirectional exchange of record metadata with a partner. Either dst or src may be -1 to make that direction a no-op, which is how the unpaired ranks of an odd sized range are kept matched and deadlock free. | |
| subroutine | gs_crystal_plan_free (this) |
| Release the routing plan. | |
Variables | |
| integer, parameter | cr_rec = 3 |
| Metadata words per in-flight record in the symbolic pass: destination rank, originating rank, payload length. | |
| integer, parameter | cr_plan_tag = 0 |
Message tag for the symbolic pass. Setup only, and every exchange in it is a fully synchronised MPI_Sendrecv, so one tag suffices. | |
Detailed Description
The crystal router (see crystal_router) delivers records to arbitrary destinations in \( \lceil \log_2 P \rceil \) recursive-bisection stages, talking to at most one partner per stage instead of to every peer at once. For the halo exchange the peer set is fixed by the gather-scatter schedule, so the routing is the same for every gs operation and can be worked out once, here, rather than re-derived from the payload on every call.
The algorithm is the crystal router of Fox et al., "Solving Problems on Concurrent Processors, Volume 1", Prentice-Hall, 1988.
What this module computes is that plan: for each stage, the partner ranks, the exact word counts to send and receive, and the index lists that move the words which stay put. The runtime is then a fixed sequence of Isend/Irecv of known size plus indexed gathers – no destination scan, no size negotiation, and no allocation, none of which the setup-phase router avoids because it cannot.
What the aggregation buys, and what it costs
One gs operation goes from \( k \) messages to \( k \) peers to at most one message per active stage. Because a partition's peers are close in rank index, most stages have nothing to send or receive and are dropped from the plan entirely, so the active stage count is set by the largest rank distance among the peers rather than by \( \log_2 P \). The price is store and forward: a word bound for a peer several stages away crosses the network once per stage it survives, and is copied locally each time. This trades bandwidth for message count and is worth it only where per-message overhead dominates – few elements per rank, coarse multigrid levels, or a runtime that handles many concurrent peers badly. Which is why the backends built on it are candidates for the runtime autotuning rather than a default.
Record identity
A record is the whole slab of shared dofs one rank sends to one peer, and it is routed intact. Its payload length and its originating rank are all a relay needs; the destination's local dof indices are never shipped, since the destination already knows them as recv_dof(origin). Contributions are therefore reduced at the destination only, exactly as in the pairwise backends. Folding contributions to the same dof at intermediate hops would cut the \( O(k^2) \) traffic of a multiplicity \( k \) vertex to \( O(k \log k) \), but needs the destination's dof identity at the relay and is deliberately left out here.
Function/Subroutine Documentation
◆ cr_final_dofs()
|
private |
- Parameters
-
rdest,rorig,rlen the delivered records nrec number of delivered records recv_pe ranks this process receives from recv_dof per-rank lists of shared dofs to reduce into
Definition at line 455 of file gs_crystal_plan.f90.
◆ cr_meta_exchange()
|
private |
- Parameters
-
sbuf packed metadata of the records to hand over nsrec number of records in sbuf dst rank to send to, or -1 rbuf allocated here, holds the metadata taken in nrrec number of records in rbuf src rank to receive from, or -1
Definition at line 513 of file gs_crystal_plan.f90.
◆ gs_crystal_plan_free()
|
private |
Definition at line 538 of file gs_crystal_plan.f90.
◆ gs_crystal_plan_init()
| subroutine gs_crystal_plan::gs_crystal_plan_init | ( | class(gs_crystal_plan_t), intent(inout) | this, |
| integer, dimension(:), intent(in) | send_pe, | ||
| integer, dimension(:), intent(in) | recv_pe, | ||
| type(stack_i4_t), dimension(0:), intent(inout) | send_dof, | ||
| type(stack_i4_t), dimension(0:), intent(inout) | recv_dof | ||
| ) |
Runs the recursive bisection of the crystal router over record metadata alone – three integers per slab rather than the payload – so the partner ranks, word counts and index lists of every stage are known before a single gs operation runs.
- Parameters
-
send_pe ranks this process sends to recv_pe ranks this process receives from send_dof per-rank lists of shared dofs to send recv_dof per-rank lists of shared dofs to reduce into
- Note
- Collective over NEKO_COMM, as the bisection is.
Definition at line 167 of file gs_crystal_plan.f90.
Variable Documentation
◆ cr_plan_tag
Definition at line 89 of file gs_crystal_plan.f90.
◆ cr_rec
Definition at line 85 of file gs_crystal_plan.f90.
