Paper Slides Code

Gemini是发表在OSDI16的一篇关于图计算系统的文章。

之前写过一个Gemini论文笔记的blog：Gemini论文笔记，最近又重新看了下代码实现，在这里简单记录下Gemini的图结构和通信的设计与实现。

图结构

stage 1

  • Partition Graph along out_degrees fllow by (edges + nodes * alpha), alpha = alpha = 12 * (partitions + 1);
  • eache partitions vertices num is dive by PAGESIZE (1024)
  • read edge, compute outdegree, determine partition_offset

image-20230222203418793

Stage 2： Numa-Aware sub-chunking

  • outgoing_structure: each socket hold the edges tha dst belongs to and these edges partition by src.
  • incoming_structure: each socket hold the edges tha src belongs to and these edges partition by dst.
  • each worker read partial edge file and send edge to corresponding worker according to dst (outgoing) and src (incoming).

image-20230222203455887

通信

Stage1: Eacher partition send socket’s msg to other partitions

Stage2: each socket in the partition will handle all the message recv from other partition

image-20230222203812970

代码

下面以SSSP算法在sparse模式下为例子，介绍下图结构和通信的实现细节。

图结构

确定每个分区的节点：

image-20230222211124934

每个分区再进行一次numa-awre的划分，即确定每个socket负责的节点范围：

image-20230222211222604

接下来是决定outgoing structure，gemini的图结构存储是站在mirror的角度考虑的。

首先是标记每个socket的入邻居（有哪些mirror指向我这个socket里面的节点）。

image-20230222212002231

outgoing对应CSR结构，首先是获取offset数据（src指向本地点的偏移量）

image-20230222212215425

有了offset之后，然后获取对应的dst点。

image-20230222212326121

incomming的结构类似，这里就不再说明了。

tune_chunks函数的作用是对每个socket存储的图结构，再进行一次thread粒度的划分。
image-20230222212832368

image-20230222212908947

通信

每个worker创建发送和接收的buffer：

image-20230222204048137

每个分区将本地活跃节点，通过sparse_signal产生一个消息，这个消息先是会到线程的buffer里面，然后再到socket对应的buffer里面。

image-20230222204325107

image-20230222204744262

通过MPI完成消息的发送和接收。

image-20230222204617892

在GeminiPush模式下，Master首先将消息同步到Mirror端，然后mirror更新自己本地的出邻居（outgoing）。

image-20230222205110269

在sparse-signal函数中，对于活跃点的产生消息这一步骤，是由多个线程并行完成的。

image-20230222205246481

接收端处理消息时，对于发来的socket消息，本地的每个socket都会对这个消息进行处理，这样就确保图结构的完整性。

image-20230222205641659

这个地方可能有点绕，举个例子：

image-20230222210953416