TL;DR:使用RDMA单边操作，解决计算不平衡和通信不平衡问题
对于计算不平衡，通过对发送数据进行细粒度的切分进一步隐藏计算和通信延迟
对于通信不平衡 通过单边通信和主动get

基于Gemini，发现gemini中存在节点间计算不平衡和通信不平衡的问题
计算不平衡：通用的划分策略只能平衡每个节点在每次迭代中的总计算成本，而不能平衡它们在每轮中的计算成本。（每轮即gemini在一次迭代中通过循环通信来进行计算和通信，每一轮表示处理一个分区）
通信不平衡：每个节点连接到另一个节点的边数不平衡会导致每轮发送数据量不均匀
image.png

IV. DESIGN OF SHMEMGRAPH

image.png
单边通信基本设计如上图所示，每个节点只有一个通信线程，使用put将数据写到其他节点上的接收缓冲区。

准备工作完成并填充发送缓冲区后，发送方线程对接收方节点上相应的长度数组进行原子比较和交换（CAS）操作。这个单一的 CAS 有三个目的：通知数据到达、通知数据大小以及锁定接收缓冲区。冲突是指另一个 CAS 之前修改了同一位置。接收器检查长度数组以了解接收数据的到达和长度。接收数据在有效数据部分末尾有一个完成标志，以确认传输完成。虽然每个接收缓冲区与某个发送方唯一关联，但由于通信平衡，仍然需要使用锁来避免竞争条件，这将在稍后讨论。

即先CAS长度数组对应的某个元素，将数据大小写到长度数组，并且锁定了该接受缓冲区，其他节点CAS失败就知道先写下一个，传输数据的末尾有传输完成标志，接受节点检查后就知道是否接受完成了。

为了最大化计算/通信重叠，SHMEMGraph 还采用了类似于原始 Gemini 的循环节点间通信程序。然而，SHMEMGraph 的处理阶段是无序的，以避免不平衡的综合影响。接收节点不会阻塞自己等待来自预期节点的数据。相反，当接收方没有从预期节点的缓冲区中获取数据时，它会继续检查后续缓冲区。接收节点收到数据后继续处理，下次会跳过相应的接收缓冲区。如果来自最预期节点的数据被处理，它将把下一个未处理的节点标记为新的预期节点。

在基本的单侧通信通道之上，SHMEMGraph 通过将准备、通信和处理阶段的不平衡且较长的数据服务过程全部划分为更细粒度的部分，进一步解决了计算不平衡问题。
image.png
如上图所示，要发送的数据被分为细粒度的chunk，准备阶段完成后，每个单独的块将（1）写入发送缓冲区，（2）发送到远程接收缓冲区，以及（3）接收后由远程节点进行处理。

即准备好一部分就发，准备好一部分就发

如果当前轮次存在显著的计算不平衡，才启用细粒度的数据服务
件是（1）相应发送/接收对的划分权重显着超过同一节点上其他对的划分权重，或者（2）与相应发送/接收对关联的传出边的数量数据显着超过当前迭代的平均数量。
image.png
此外，由于我们无法通过创建另一个计算阶段来计算权重和边，这会增加大量开销，因此我们在准备阶段收集这些值，并将它们用作下一次迭代的预测值（Eavg 可用于所有节点）当前迭代结束）。对于第一次迭代，我们使用在初始化阶段收集的值。我们不会简单地对所有情况应用细粒度模式，因为只有不平衡的计算才会导致显着的延迟。此外，我们发现，由于增加的操作开销和资源争用，积极地划分数据服务过程可能会导致不良的性能行为。
此外，当启用细粒度数据服务时，长度数组将扩展为二维数组。每个原始数组条目进一步扩展为长度数组。

image.png
通信不平衡的解决原理：获取发送缓冲区或获取未处理的顶点

即通信默认用put，如果不平衡就主动get发送的数据或者get要处理的顶点（负载均衡）

当一个通信线程发送完所有数据后，它开始从另一个尚未向该节点发送任何数据的节点远程读取数据。如果该节点当前正在从另一个节点接收数据，即该节点对应的长度数组已被锁定，它将跳过该节点。因此，在取之前，通信线程也会进行一次CAS尝试锁定相应长度的数组项。这可以防止写入同一缓冲区时发生冲突，并避免不必要地传输重复数据。（相当于暂停接受数据）

平衡时，节点首先检查目标节点上的发送缓冲区是否有可用数据。它通过检查目标节点上相应的长度数组来实现这一点。然后，如果有相应的数据，该节点就会获取相应的数据。如果没有，则该节点检查是否可以获取目标节点上的活动顶点。活动顶点由目标节点在每次迭代开始时准备并存储在全局内存空间中。为了避免昂贵的通信开销和计算成本可能会抵消通信平衡的好处，我们设置了一个阈值 sT ，它是值得获取的活动顶点数量的上限。对于 Gemini，我们将 sT 设置为 Vi/10 ，其中 Vi 是节点 i 拥有的顶点总数。该值是根据 Gemini 中稀疏模式和密集模式的总体性能差异来选择的。在这里，SHMEMGraph 有效地利用了 Gemini 在单次迭代中的自适应模式切换：即使在拉模型中也推送更新。