Graph500 Benchmarks

1 Benchmark

1.1 Overall

Graph 500是针对数据密集型计算问题设计的一个基准测试。该基准测试包括一个生成器，生成无向图给后两个内核使用，不允许修改使特定内核受益。后两个内核分别为广度优先搜索和单源最短路计算。三个内核都会计时。

基准测试执行步骤如下：

  • 生成边
  • 构造图(kernel1，计时)
  • 随机抽样64个度数为1的key，不包括自循环
  • 对每个搜索键
    • 计算父数组(kernel2，计时)
    • 验证父数组是否为正确的BFS搜索树
  • 对每个搜索键：
    • 计算父数组和距离数组(kernel3，计时)
    • 验证父数组和距离向量是否为正确的单源最短路径搜索树
  • 计算输出性能信息

性能信息是通过计时部分计算的。允许使用伪随机数抽样。后两个内核是分别单独进行的，而不是连续离开同一初始顶点。

1.2 Generating the Edge List

数据生成器会生成边的列表。每个边为元组(StartVertex，EndVertex，Weight)。如果只运行kernel2，可以不生成权重。生成的输入元组列表不得表现出任何可被计算内核利用的位置性。因此，顶点必须是随机的，并且必须将元组的随机排序呈现给kernel1。weight是单精度浮点[0,1]，顶点数为N。

Benchmark接受的唯一参数是SCALE，是顶点数的以二为底的对数，决定了N=2^SCALE。edgefactor为16，是边与顶点数的比率。M是边的数量，为edgefactor*N。

图的生成器是一种类似R-MAT的生成器。以邻接矩阵描述R-MAT，实现可以使用任何输出等效边元组列表的替代方法。R-MAT递归将图形邻接矩阵分为四个大小相等的分区A B C D，每次添加一条边，边选择概率为四个分区之一，概率为A = 0.57 B = 0.19 C = 0.19 D = 0.05。

图生成器在两个顶点之间创建少量的重复边以及自循环。在后续kernel中，可以忽略重复边、自循环和孤立的顶点，但必须将其包含在提供给第一个kernel的边缘列表中。该算法还生成具有高度局部性的数据元组。因此，作为最后一步，顶点数必须随机置换，然后shuffle边元组。

允许并行运行数据生成器。在这种情况下，必须确保顶点是全局命名的，并且生成的数据在本地内存中或跨处理器的全局位置不具有任何位置性。数据可以存储到RAM或磁盘，如果存储到磁盘，可以在启动kernel1前读取数据。生成和读取都是不计时的。

数据规模有五档：

1.3 Kernel 1 – Graph Construction

kernel 1可以将边列表转换为任何数据结构，但数据结构不能被后续kernel修改或在后续kernel之间修改。稀疏图有多种表示方式。生成图时仅有边列表和边列表大小，其他信息必须通过计算得出，例如顶点数。该过程计时。

1.4 Sampling 64 Search Keys

搜索键必须从图中的顶点中随机抽样。为避免琐碎的搜索，仅从连接到其他顶点的顶点中采样。他们的度数，不包括自循环，必须至少为一个。如果此类顶点少于 64 个，则运行少于 64 个搜索。此基准测试中的图形大小不应发生这种情况，但生成微不足道或几乎微不足道的图形的可能性不为零。使用的搜索键数包含在输出中，但此步骤是不计时的。

BFS的输入和输出是指定的，并有一定的约束，但是具体的算法并不限制，只要能产生正确的搜索树。每次搜索必须是单独进行的。

对于每个搜索键，例程必须返回一个数组，其中包含有效的广度优先搜索父信息（每个顶点）。搜索键的父级是其自身(?)，树中未包含的任何顶点的父级是 -1。

1.6 Kernel 3 – Single Source Shortest Paths

类似BFS，具体算法不做限制，只要能产生正确的距离向量。不能使用kernel2的结果，只能从一个初始顶点开始进行计算。

对于每个初始顶点，例程必须返回每个顶点与初始顶点之间的距离，以及有效的单源最短路径树中每个顶点的父顶点的距离。初始顶点的父项是其自身，而树中未包含的任何顶点的父项是 -1。

1.7 Validation

验证时不要求与标准结果完全精确相同。也不要求使用最大SCALE进行验证。而是在适合被评估机器的最大数据集上执行这些算法并验证。

1.8 输出及性能指标

为了衡量Graph 500性能，定义一个称为每秒遍历边数(TEPS)的指标。TEPS(n)=M/time(n)，M为无向边数。

输出包含SCALE edgefactor NBFS(搜索数)以及BFS和SSSP执行的时间，中位时间，TEPS的调和平均值等指标。

2 Reference code

Reference code的核心代码在src当中。为MPI并行。默认情况下processors per node应该为2的幂次方，如果不是，则需要定义-DPROCS_PER_NODE_NOT_POWER_OF_TWO。

2.1 AML(active message lib)

2.1.1 overall

AML是基于MPI的通信库，支持异步小消息传递，将多个小消息合并发送，减小通信开销。消息是异步传递的，传递后需要进行同步。使用时需要首先调用aml_init初始化，然后通过以下函数注册消息处理程序：

1
2
3
4
//消息处理程序应该为以下格式：
void handler(int fromPE, void* data, int dataSize); //fromPE为发送方rank
//注册消息处理程序
aml_register_handler(handler, handlerid);

然后使用aml_send发送消息到其他节点，发送后调用aml_barrier确保消息处理完毕，最后调用aml_finalize结束使用。

1
aml_send(data, handlerid, dataSize, destPE)

2.1.2 implemention

AML首先在初始化中，对通信域进行了分隔：

  • comm_intra：根据主机名将一个主机的进程划分在一个通信域内
  • comm：在各个主机上有相同rank的进程划分在一个通信域内

划分后进行亲和性绑定，将进程绑定在和local_rank对应的核上，通过pthread_setaffinity_np绑定。

接下来AML使用了MPI_Recv_init初始化几个异步接收操作。这是MPI-3引入的，不需要指定消息来源和标签，更加灵活。初始化的异步接收操作包括节点内的和跨节点的，还开辟了sendbuf，acks，nbuf。然后启动节点内部的异步接收，并初始化几个发送请求。这实际上是在实现One-sided communication。

1
2
3
4
5
6
7
8
9
10
//节点内部通信域也采取类似的初始化和启动
	for ( j = 0; j < num_groups; j++ ) {
		sendsize[j] = 0; nbuf[j] = j;  acks[j]=0;
	}
	for(i=0;i<NRECV;i++)
		MPI_Start( rqrecv+i );
	for ( j = 0; j < NSEND; j++ ) {
		MPI_Isend( NULL, 0, MPI_CHAR, MPI_PROC_NULL, 0, comm, rqsend+j );
		activebuf[j]=num_groups+j;
	}

utils.c

封装了一个set_global函数，初始化MPI环境，并封装了一个MPI数据类型packed_edge_mpi_type，该MPI数据类型是以下数据类型的封装：

1
2
3
4
5
typedef struct packed_edge {
  uint32_t v0_low;
  uint32_t v1_low;
  uint32_t high; /* v1 in high half, v0 in low half */
} packed_edge;

封装了一个MPI_Alloc_mem。定义了一个取第一个大于等于x的2的幂次方的对数的函数。

common.h

定义了一组用于处理进程编号的宏。lgsize是节点进程数的对数。顶点是交错分布在节点上的，即若有4个顶点0 1 2 3，两个节点，则0 2在节点1，1 3在节点2。以及定义了边列表数据结构tuple_graph，边的数据可在文件中也可在内存中。还定义了一组宏，用于并行读入边列表的数据。