CnuasCCL Rank Bootstrap Design¶

Item	Value
Status	Design proposal, no implementation, awaiting a decision
Component	CnuasCCL
Roadmap	Epic 8, milestone 8.2
Blocks	CnuasCCL v0.1

Nothing here is implemented

This document exists so that the bootstrap protocol is chosen deliberately rather than invented while writing the first collective. Section 7 records the decisions that are still open. No code in the tree implements any of what follows.

1. What the problem is¶

A collective communication library needs every participant to agree, before any data moves, on four things.

Question	Meaning
Who is taking part	The membership of the communicator
What is my rank	A contiguous index in the range 0 to N-1
How do I reach rank r	The transport address of every other member
Are we all ready	A barrier, so nobody sends into an unready peer

Rank is not the same thing as identity. Identity is which accelerator a process is using, and rank is where that accelerator sits in one particular communicator. The same accelerator holds different ranks in different communicators, which is why NCCL separates ncclUniqueId from the rank argument to ncclCommInitRank.

2. Half of this is already solved¶

Cnuas is in an unusually good position, because accelerator identity is already assigned out of band and is already unique.

scripts/vm-manager.sh gives each emulated accelerator a gpu_id as it builds the QEMU command line, as base_id + i across the requested count. QEMU carries it as a device property, DEFINE_PROP_UINT32("gpu_id", ...) in qemu/hw/misc/cnuasgpu.c, and exposes it at register CNUASGPU_REG_GPU_ID. The control plane tracks the resulting inventory.

So the hard part of a general membership protocol, agreeing on unique names without a coordinator, does not arise. There is already an authoritative assigner and an authoritative inventory. What remains is narrower:

Decide which subset of the known accelerators forms this communicator.
Order that subset into ranks.
Exchange transport addressing.
Barrier.

A protocol that rediscovers identity from nothing would be solving a problem this platform does not have.

3. What the fabric can and cannot do today¶

These constraints come from reading the current implementation, not from the design documents, and they rule out the most obvious in band approach.

Constraint	Evidence
DISCOVERY frames are never forwarded	`src/cnuaslink/switch/src/cnuaslink_loop.c` returns immediately for `CNUASLINK_TYPE_DISCOVERY` and `CNUASLINK_TYPE_LINK_KEEPALIVE`, after learning the source mapping
Broadcast frames of other types are flooded	The same function floods to every port except the ingress port when `dst_gpu == CNUASLINK_GPU_BROADCAST`
The switch learns source to port mappings itself	`cnuaslink_fdb_learn` runs on any frame with a valid `src_gpu`
Unroutable frames are dropped silently	`rx_dropped_no_route` is counted and the frame discarded, with no notification to the sender
The usable identifier space is 1 to 0xFFFE	`CNUASLINK_GPU_INVALID` is 0x0000 and `CNUASLINK_GPU_BROADCAST` is 0xFFFF
A frame carries at most 64 KiB	`CNUASLINK_MAX_FRAME`, less the 12 byte header
Receive has one staging buffer under a mutex	`cnuasgpu_link_recv` in `src/cnuasgpu/driver/cnuasgpu.c` serialises on `link_rx_lock` against a single `link_rx_staging_off`
There are no per peer receive queues	Same, so an unexpected frame from peer B can be consumed by a thread waiting for peer A
Send blocks until the switch acknowledges	`cnuasgpu_link_send` waits on `link_tx_wq` and returns `ENOTCONN` when the link is down

Two consequences follow, and both are easy to get wrong.

First, a rank cannot announce itself to its peers with a DISCOVERY frame. That frame type trains the switch and stops there. Anything peers must actually see has to use a forwarded type.

Second, and more seriously, the receive path offers no demultiplexing, no ordering and no delivery guarantee. A bootstrap that assumes it can post a receive for a particular peer, or that a sent frame arrives, is assuming properties the fabric does not provide. Any in band design has to supply sequencing, retransmission and matching for itself.

4. Prior art¶

Every citation below was verified against the primary source. Where a detail could not be confirmed it is marked.

4.1 NCCL¶

NCCL has no published paper for its bootstrap; the implementation is the reference. Reading src/bootstrap.cc and src/include/bootstrap.h in NVIDIA/nccl, the design is as follows.

ncclUniqueId is a 128 byte opaque blob holding a ncclBootstrapHandle, which carries only three fields: a random 64 bit magic token, the socket address of a root listener, and a rank count. It carries no topology and no keys.

One process calls ncclGetUniqueId, which binds an ephemeral TCP port and spawns a detached root thread. The user is responsible for broadcasting that identifier to every participant, by MPI or any other means; NCCL deliberately does not do this. Each rank then connects to the root and sends a record containing its rank, the total rank count, and the address on which it is listening for its ring predecessor. The root stitches the ring by telling each rank where its successor listens, then exits. It takes no part in later collectives.

Once the ring exists, bootstrapAllGather performs a ring allgather over those TCP sockets to distribute the full membership table in one step. The bootstrap sockets are used only for setup; the actual collectives run over a separate high performance transport.

Later additions are worth noting. ncclCommInitRankScalable accepts several unique identifiers so that ranks spread across multiple roots instead of hot spotting one listener, and there is a stagger delay above 256 ranks for the same reason. ncclCommSplit derives a new communicator from an existing one without any fresh out of band step.

The lesson is the separation: an out of band exchange of one small rendezvous token, a throwaway coordinator, a ring allgather for bulk membership, and a completely separate data transport.

4.2 UCC, the callback pattern¶

UCC does not implement a bootstrap at all. It defines the interface and makes the caller supply it, through ucc_oob_coll:

struct ucc_oob_coll {
    ucc_status_t (*allgather)(void *src_buf, void *recv_buf, size_t size,
                              void *allgather_info, void **request);
    ucc_status_t (*req_test)(void *request);
    ucc_status_t (*req_free)(void *request);
    void    *coll_info;
    uint32_t n_oob_eps;
    uint32_t oob_ep;
};

Each participant contributes size bytes, which land at offset oob_ep * size in every participant's recv_buf. UCC calls this during team creation to distribute packed transport addresses.

This is the cleanest of the designs surveyed. One asynchronous allgather is sufficient to bootstrap a collective library, and pushing it to the caller means the library never grows a rendezvous implementation of its own.

4.3 Gloo, the store pattern¶

Gloo bootstraps through a key value store interface with several implementations, including a TCP store where rank 0 serves, a file store on a shared filesystem, and an in process store. Ranks publish their endpoints and read everyone else's, then build connections directly. This decouples agreement on membership from communication entirely. The exact interface was reported by search rather than read from source, so treat the details as indicative.

4.4 PMI and PMIx¶

The generalisation of the store pattern for HPC launchers. Processes publish business cards into a key value space with put, get and fence operations, and the launcher supplies the implementation.

Ralph H. Castain, Joshua Hursey, Aurelien Bouteiller, David Solt. "PMIx: Process management for exascale environments." Parallel Computing, volume 79, pages 9 to 29, November 2018. doi:10.1016/j.parco.2018.08.002

4.5 Algorithm selection, once bootstrapped¶

Relevant because the datasheet also records ring versus tree selection as unspecified, and because bootstrap output shapes what algorithms are available.

Pitch Patarasuk and Xin Yuan. "Bandwidth optimal all-reduce algorithms for clusters of workstations." Journal of Parallel and Distributed Computing, volume 69, number 2, pages 117 to 124, 2009. doi:10.1016/j.jpdc.2009.04.008

The ring allreduce result: a reduce scatter followed by an allgather around a ring moves 2(N-1)/N times the buffer per node, which is bandwidth optimal and independent of N. This is why ring is the default for large payloads.

Rajeev Thakur, Rolf Rabenseifner, William Gropp. "Optimization of Collective Communication Operations in MPICH." International Journal of High Performance Computing Applications, volume 19, number 1, pages 49 to 66, 2005. doi:10.1177/1094342005051521

Algorithm choice depends on message size and process count: recursive doubling wins on latency for small messages, reduce scatter plus allgather wins on bandwidth for large ones. A bootstrap that yields a ring only is therefore already a policy decision, and one that yields a full membership table leaves both families open.

Zixian Cai, Zhengyang Liu, Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Jacob Nelson, Olli Saarikivi. "Synthesizing Optimal Collective Algorithms." PPoPP 2021, pages 62 to 75. doi:10.1145/3437801.3441620, arXiv:2008.08708

Aashaka Shah, Vijay Chidambaram, Meghan Cowan, Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Jacob Nelson, Olli Saarikivi, Rachee Singh. "TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches." NSDI 2023, pages 593 to 612. arXiv:2111.04867

Both synthesise schedules from a topology description rather than picking from a fixed menu. Cnuas is well suited to this later, because the topology is declared rather than discovered, but neither is in scope for v0.1.

4.6 Membership protocols, and why they do not apply¶

Abhinandan Das, Indranil Gupta, Ashish Motivala. "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol." DSN 2002, pages 303 to 312. IEEE document 1029751, DOI reported as 10.1109/DSN.2002.1029751 but not confirmed by direct fetch.

Gossip based membership solves failure detection and eventual agreement without a coordinator, at large scale. It is the right tool when membership is large, dynamic and has no authority. Cnuas has an authority, a control plane with the inventory, and collectives need exact rather than eventual agreement, since a communicator with a disputed member is not usable. Recorded here so the option is visibly considered and set aside, not overlooked.

4.7 RDMA connection establishment¶

The classic verbs pattern creates a queue pair, then exchanges local identifier, queue pair number, global identifier and packet sequence number with the peer over a side channel, then transitions the queue pair to ready to receive and ready to send. RDMA-CM is the alternative that hides this behind connect and listen, resolving addresses through the subnet manager.

The parallel matters because CnuasLink is an emulated fabric with the same shape. Either the bootstrap carries opaque per rank transport handles, which is what NCCL does, or a fabric manager resolves them on demand, which is what RDMA-CM does.

5. Options¶

Option A, an out of band callback supplied by the caller¶

Follow UCC. CnuasCCL defines an allgather callback and refuses to implement one. The launcher, an MPI job, or the Cnuas control plane provides it.

Advantages: no rendezvous code in the library, works with whatever the site already runs, testable with a trivial in process implementation, and it sidesteps every fabric constraint in section 3 because bootstrap traffic does not touch CnuasLink.

Disadvantages: the caller cannot simply run a program, so it is unfriendly on its own. NCCL has the same property and answers it with ncclCommInitAll for the single process case.

Option B, a control plane rendezvous¶

Follow Gloo, using the Cnuas control plane as the store. It already knows the inventory and already exposes a REST API.

Advantages: works out of the box with no launcher integration, and the control plane is the natural authority for which accelerators exist and who may use them. It is a natural default implementation of the option A callback rather than a competitor to it.

Disadvantages: a hard dependency on the control plane being reachable from every participant, and a component that is not otherwise on the data path becoming a job startup dependency.

Option C, in band over CnuasLink¶

Bootstrap over the fabric itself, with a broadcast announcement and a rank ordered by identifier.

Advantages: no external dependency at all.

Disadvantages: severe, and they are the reason this document exists. Section 3 shows the receive path has a single staging buffer with no per peer demultiplexing, no ordering and no delivery guarantee, and that the obvious announcement frame type is never forwarded. Bootstrapping here means first building sequencing, retransmission, timeout and matching on top of a lossy datagram service, which is a transport project rather than a bootstrap. It also cannot express membership smaller than the whole fabric without an extra agreement step.

6. Recommendation¶

Adopt option A as the interface and option B as the default implementation of it, and do not pursue option C for v0.1.

This mirrors what the surveyed libraries converged on independently, keeps the rendezvous out of the library, and lets the first CnuasCCL be tested with an in process allgather with no fabric and no control plane. It also keeps the door open: a later in band bootstrap becomes one more implementation of the same callback rather than a rewrite.

The sketch below is deliberately close to ucc_oob_coll, since matching a known interface is worth more than a novel one.

/* Supplied by the caller. Contributes send_bytes from send_buf and fills
 * recv_buf, which is n_ranks * send_bytes long, with every rank's
 * contribution in rank order. Blocking in v0.1. */
typedef cnuasccl_status_t (*cnuasccl_oob_allgather_fn)(
        const void *send_buf, void *recv_buf, size_t send_bytes,
        void *context);

struct cnuasccl_bootstrap {
        cnuasccl_oob_allgather_fn allgather;
        void       *context;
        int         n_ranks;
        int         rank;        /* this participant, in 0 .. n_ranks-1 */
};

cnuasccl_status_t cnuasccl_comm_init_rank(cnuasccl_comm_t *comm,
                                          const struct cnuasccl_bootstrap *boot,
                                          uint16_t gpu_id);

One allgather of a small fixed record per rank, carrying the gpu_id and whatever addressing the transport needs, is enough to build the full membership table. Rank order is given by the caller rather than derived, which is what makes several communicators over the same accelerators possible.

7. Decisions taken¶

Settled for v0.1 as follows. Each is recorded with the reason, because the cost of a bootstrap decision is paid later, when changing it means changing every caller.

Question	Decision	Why
Adopt the recommendation in section 6	Yes. Option A is the interface, option B is one implementation of it, option C is out of scope	Keeps the rendezvous outside the library, so the first CnuasCCL is testable with no fabric and no control plane
Is the control plane a permitted job startup dependency	No	Making it optional costs nothing here, and a library that cannot run without a daemon cannot be unit tested
Blocking or asynchronous callback	Blocking	Sufficient for v0.1 and far simpler. The signature can gain a non blocking variant later without breaking callers
Does rank order have to match `gpu_id` order	No, the caller supplies rank	Forcing the orders to match would make several communicators over the same accelerators impossible, which is what communicator splitting needs
Ring only, or full membership table	Full membership table	Costs one small record per rank at this scale and leaves both algorithm families of section 4.5 open. A ring is derived from the table, not baked into it
Failure and timeout behaviour	Return a status, never abort	The surveyed libraries mostly abort the process. A library that kills its caller cannot be tested for its failure paths, and the accelerator is virtual, so a stuck peer is a normal event rather than a catastrophe

The last one is the only place this departs from the surveyed prior art, and it is deliberate. cnuasccl_comm_init_rank reports a duplicate rank, a missing rank or a gpu_id collision to its caller and leaves the communicator uninitialised.

7.1 What follows from the table decision¶

Because the table is materialised rather than reduced to a ring at bootstrap, cnuasccl_comm_rank_of, cnuasccl_comm_gpu_of and the ring neighbour helpers are all views over the same array. Selecting a tree or recursive doubling schedule later needs no change to the bootstrap and no second allgather.

8. Prerequisite, now satisfied¶

Independent of which option is chosen, CnuasCCL needs a supported userspace CnuasLink transport. When this document was first written there was none: the fabric was reachable only through raw ioctls, with frames hand built inside a driver test, and cnuaslink_proto.h lived in the switch tree rather than anywhere a library could include it.

Roadmap milestone 8.2a has since closed that gap. CnuasDev now exports cnuasdev_link_id, cnuasdev_link_status, cnuasdev_link_send and cnuasdev_link_recv, plus a frame layer in cnuaslink_frame.h that carries no device dependency and is therefore tested on the build host. The transport is described in section 2a of the CnuasDev datasheet.

Nothing in that work presumed an answer to the questions in section 7. The transport moves frames between named identifiers and takes no view on how a rank learns its rank, which peers exist, or when everyone is ready. Those remain open, and they are now the only thing between CnuasCCL and a first implementation.

9. References¶

Source	Where
NCCL bootstrap implementation	github.com/NVIDIA/nccl, `src/bootstrap.cc`
NCCL communicator documentation	docs.nvidia.com
UCC out of band collective	openucx.github.io/ucc
PMIx	doi:10.1016/j.parco.2018.08.002
Ring allreduce bandwidth optimality	doi:10.1016/j.jpdc.2009.04.008
MPICH collective optimisation	doi:10.1177/1094342005051521
SCCL	arXiv:2008.08708
TACCL	arXiv:2111.04867
SWIM	DSN 2002, IEEE document 1029751
CnuasLink wire format	`src/cnuaslink/switch/include/cnuaslink_proto.h`
CnuasLink switch forwarding	`src/cnuaslink/switch/src/cnuaslink_loop.c`
Receive path	`src/cnuasgpu/driver/cnuasgpu.c`, `cnuasgpu_link_recv`