在图处理领域，随着数据规模的爆炸式增长，如何高效地处理大规模图数据成为了一个重要的研究课题。现有的分布式图处理系统虽然能够处理大规模的图数据，但在性能上往往不如共享内存系统。为了解决这个问题，研究者们提出了 Gemini，一个以计算为中心的分布式图处理系统，旨在通过优化计算性能，在效率之上构建可扩展性。本文将深入探讨 Gemini 的设计理念、核心技术以及性能表现，并分析其在分布式图处理领域所做的贡献。
Gemini 的核心思想是在设计分布式图并行系统时，不仅要关注可扩展性，更要注重效率。这意味着需要在隐藏通信开销的同时，积极压缩计算时间。为了实现这一目标，Gemini 采用了多种优化策略，包括稀疏-稠密信号槽抽象、基于分块的划分方案、压缩结点索引访问的双重表示方案、NUMA 感知子划分以及局部感知分块和细粒度工作窃取等。
Gemini 图处理抽象：双重更新传播模型
Gemini 采用了 PowerGraph 的 master-mirror 概念，每个结点被分配给一个分区，成为 master 结点，负责维护结点状态数据的主副本。同时，同一结点在拥有其至少一个邻结点的节点/分区上拥有副本，称为 mirror 结点。Gemini 使用稀疏-稠密双模式引擎设计，并引入了信号-槽抽象，将结点状态（通信）与边处理（计算）分离。这种抽象方式使得 Gemini 能够灵活地处理不同类型的图计算任务。
在稀疏模式下，master 结点首先通过 sparseSignal 向 mirror 结点发送包含最新结点状态的消息，然后 mirror 结点通过 sparseSlot 沿出边依次更新其邻结点。这种模式适用于出度较低的结点，可以有效地减少通信开销。另一方面，在稠密模式下，mirror 结点首先沿入边根据邻结点状态执行本地计算，然后通过 denseSignal 将包含结果的更新消息发送给 master 结点，最后 master 结点通过 denseSlot 更新自身状态。这种模式适用于入度较高的结点，可以充分利用本地计算资源。
Gemini 能够自动启用消息组合，每个结点的每个激活的 master-mirror 对只需要一条消息，从而将消息数量从 O(|E|) 降低到 O(|V|)，进一步减少了通信开销。此外，Gemini 允许在本地执行计算以聚合传出更新，而无需采用额外的“组合过程(combining pass)”。
以下是 Gemini 的核心 API：
void sparseSignal(Vertex v, Graph g);
void sparseSlot(Vertex v, Graph g, Message m);
void denseSignal(Vertex v, Graph g);
void denseSlot(Vertex v, Graph g, Message m);并非所有的用户定义函数都是必须的，双模式处理也是可选的。以下是一个连通分量(Connected Components, CC)算法的示例：
class CC : public VertexProgram<VertexID> {
public:
void init(Vertex& v) {
v.data() = v.id();
}
void sparseSignal(Vertex& v,Graph& g) {
if (v.data() < v.min_neighbor_data()) {
signal(v,g,v.data());
}
}
void sparseSlot(Vertex& v,Graph& g, Message& m) {
if (m < v.data()) {
v.data() = m;
signal(v,g,v.data());
}
}
void denseSignal(Vertex& v, Graph& g) {
// 稠密模式下的信号发送
}
void denseSlot(Vertex& v, Graph& g, Message& m) {
// 稠密模式下的槽函数
}
};分布式图表示：轻量级、基于分块的多级划分方案
Gemini 提出了一种轻量级、基于分块的多级划分方案，并结合了图划分和内部表示的设计选择。这种方案旨在有效地保留局部性，并减少通信开销。
在 p 个节点的集群上，给定全局图 G=(V,E) 划分为 p 个子图 Gi=(V'i,Ei), i from 0 to (p-1)。其中，V'i 和 Ei 分别表示第 i 个分区的结点子集和边子集，Vi 表示第 i 个分区拥有的(master)结点子集。
Gemini 划分 G 使用一个简单的基于分块的方案，将 V 划分为 p 个连续的结点分块 (V0,V1,...,Vp-1)。每个分块 (Vi) 被分配给一个集群节点，该节点拥有该分块的所有结点。对于分区 i，其出边集（用于稀疏模式）为 ES_i = {(src,dst,value)∈E|dst∈Vi}，入边集（用于稠密模式）为 ED_i = {(src,dst,value)∈E|src∈Vi}。
双模式边表示：BCSR 与 DCSC
传统的 CSR/CSC 格式索引数组 idx 可能会成为扩展瓶颈。为了解决这个问题，Gemini 使用两种方案分别增强两种模式的索引数组：
- 位图辅助压缩稀疏行(Bitmap Assisted Compressed Sparse Row, BCSR): 针对稀疏模式的边，添加了一个标记每个结点在该分区是否有出边的存在位图
ext。 - 双压缩稀疏列(Doubly Compressed Sparse Column, DCSC): 针对稠密模式的边，仅存储具有入边的结点(
vtx)及其相应的边偏移(off,(off[i+1]-off[i])表示结点vtx[i]具有的本地入边数)。
局部性感知分块与 NUMA 感知子划分
为了进一步优化性能，Gemini 采用了一种在设置平衡标准时同时考虑拥有的(master)结点和稠密模式边的混合度量。划分结点数组 V 使得每个分区具有 α ⋅ ∣ V i ∣ + ∣ E i D ∣ \alpha\cdot|V_i|+|E^D_i| α⋅∣Vi∣+∣EiD∣ 的平衡值。其中，α 为可配置参数，实验中根据经验设置为 8 ⋅ ( p − 1 ) 8\cdot(p-1) 8⋅(p−1)。
Gemini 基于分块的图划分允许系统以相同的方式递归地应用子划分，并在每个特定级别都有适用不同的优化。在一个节点中，Gemini 在多个 socket 之间应用 NUMA 感知的子划分：对于每个包含 s 个 socket 的节点，结点分块 Vi 被进一步划分成 s 个子块，每个 socket 一个；边使用与节点间划分相同的规则分配给相应的 socket。
任务调度与细粒度工作窃取
Gemini 遵循批量同步并行(Bulk Synchronous Parallel, BSP)模型，并将集群节点组织成一个环，以平衡的循环方式协调消息发送和接收操作。在具有 c 个核的节点上，Gemini 维护一个具有 c 个线程的 OpenMP 线程池，用于并行边处理、执行 signal 和 slot 任务；每个线程使用 NUMA 感知的子划分绑定到特定 socket 上。每个节点创建两个助手线程用于通过 MPI 进行节点间的消息发送/接收操作。
每轮迭代分为 p (集群节点数)个 mini-step(小步骤)，每个 mini-step 中 node_i 按照从 node_{i+1} 到自己的顺序与每个对等节点通信。Gemini 利用共享内存采用细粒度的工作窃取调度程序进行节点内边处理。每个线程在 OpenMP 并行区域内仅获取待处理(signal / slot)结点的一小个分块(mini-chunk)，mini-chunk 大小默认设置为 64 个结点。每个线程首先完成自己所在核心的分区，然后开始从其他线程的分区中窃取 mini-chunk。
实现与评估
Gemini 使用约 2800 行 C++ 代码实现，使用 MPI 进行进程间通信，使用 libnuma 进行 NUMA 感知的内存分配。在图加载方面，每个节点并行读取其分配的连续部分，边按顺序分批加载到边缓冲区中。图划分方面，加载边时计算每个结点的度数并使用 AllReduce 收集，用于划分结点集。然后每个节点先进行本地划分，再从文件中重新加载边并分发到目标节点构建局部子图。
在内存分配方面，所有节点共享节点间消息传递的节点级分区边界，而 socket 级子分区信息保持节点私有。每个节点在共享内存中分配整个结点数组。Gemini 划分每个节点的结点分区为子分块，并置于相应的 socket 上。数据图的边和结点索引也采用 NUMA 感知的分配。对于模式选择，Gemini 首先调用一个(基于 ProcessVertices 接口的)内部操作获取激活边数，并由此确定处理模式(稀疏或稠密)。
Gemini 的性能评估表明，它在共享内存和分布式环境下均表现出色，并在扩展性方面具有优势。通过对设计选择的分析，可以深入了解 Gemini 各个优化策略的有效性。
结论
Gemini 作为一个以计算为中心的分布式图处理系统，通过稀疏-稠密信号槽抽象、双模式边表示(BCSR/DCSC)以及多级图划分等方法，显著提高了分布式图计算系统的计算性能。它在效率之上构建可扩展性的设计理念，为未来的分布式图处理系统提供了新的思路。Gemini 的成功经验表明，在设计分布式系统时，不仅要关注可扩展性，更要注重效率，才能获得更好的整体性能。
