The paper aims to address load imbalance caused by high in-degree
distribution in graphs by applying the idea of rhizome to vertex-centric
message-driven graph processing. Rhizome construction of the graph creates
multiple named vertex address for any number of single large in-degree
vertices. It then allows other vertices to point to any of the named addresses
thus sharing the in-degree load. The rhizomes internally communicate and remain
consistent to provide a unified and correct view of the vertex. Simulated
experimental results show performance speed ups for BFS graph traversal on
large chip sizes for the tested input graph datasets containing highly skewed
in-degree distribution. The improvements come from sharing the in-degree
compute workload among memory-processing elements and also lowering contention
on the network-on-chip.

通过应用根茎的概念到以顶点为中心的消息驱动图处理，本文旨在解决由图中高入度分布所引起的负载不平衡问题。通过构建图的根茎，为任意数量的单个大入度顶点创建多个命名顶点地址。然后允许其他顶点指向任何命名地址，从而共享入度负载。模拟实验结果表明，在包含高度偏斜的入度分布的测试输入图数据集上，BFS 图遍历在大型芯片尺寸上的性能提升。这些改进来自于在内存处理元素之间共享入度计算工作负载，同时降低芯片内网络的争用。

平衡偏倚度分布的根茎

Rhizomes to Load Balance Skewed In-Degree Distributions

The Mixtures-of-Experts (MoE) model is a widespread distributed and
integrated learning method for large language models (LLM), which is favored
due to its ability to sparsify and expand models efficiently. However, the
performance of MoE is limited by load imbalance and high latency of All-To-All
communication, along with relatively redundant computation owing to large
expert capacity. Load imbalance may result from existing routing policies that
consistently tend to select certain experts. The frequent inter-node
communication in the All-To-All procedure also significantly prolongs the
training time. To alleviate the above performance problems, we propose a novel
routing strategy that combines load balance and locality by converting partial
inter-node communication to that of intra-node. Notably, we elucidate that
there is a minimum threshold for expert capacity, calculated through the
maximal angular deviation between the gating weights of the experts and the
assigned tokens. We port these modifications on the PanGu-Sigma model based on
the MindSpore framework with multi-level routing and conduct experiments on
Ascend clusters. The experiment results demonstrate that the proposed LocMoE
reduces training time per epoch by 12.68% to 22.24% compared to classical
routers, such as hash router and switch router, without impacting the model
accuracy.

通过转换部分节点间通信为节点内通信的路由策略，我们提出了一种新颖的负载均衡和局部性相结合的路由策略，并在 PanGu-Sigma 模型上进行了改进，实验证明该路由策略减少了每轮训练时间约 12.68% 至 22.24%，而不影响模型的准确性。

LocMoE：一种用于大型语言模型训练的低开销 MoE

LocMoE: A Low-overhead MoE for Large Language Model Training

Load imbalance pervasively exists in distributed deep learning training
systems, either caused by the inherent imbalance in learned tasks or by the
system itself. Traditional synchronous Stochastic Gradient Descent (SGD)
achieves good accuracy for a wide variety of tasks, but relies on global
synchronization to accumulate the gradients at every training step. In this
paper, we propose eager-SGD, which relaxes the global synchronization for
decentralized accumulation. To implement eager-SGD, we propose to use two
partial collectives: solo and majority. With solo allreduce, the faster
processes contribute their gradients eagerly without waiting for the slower
processes, whereas with majority allreduce, at least half of the participants
must contribute gradients before continuing, all without using a central
parameter server. We theoretically prove the convergence of the algorithms and
describe the partial collectives in detail. Experimental results on
load-imbalanced environments (CIFAR-10, ImageNet, and UCF101 datasets) show
that eager-SGD achieves 1.27x speedup over the state-of-the-art synchronous
SGD, without losing accuracy.

本文提出了一种基于分布式深度学习的负载平衡问题的解决方法 ——eager-SGD，并使用两个部分集合（solo 和 majority）来实现其分散的梯度累积，理论上证明了算法的收敛性，实验证明在负载不均衡的环境下，它比同步 SGD 获得了 1.27 倍的加速，而不会失去准确性。