图数据格式对三角形计数算法影响的特性分析

张世茹，邓军勇

(西安邮电大学 电子工程学院，西安 710121)

1 引 言

图因其宜于表征不同实体间复杂的依赖关系而受到广泛应用[1-3]，社交网络分析、推荐系统、传染病防治等都紧密依赖于高性能、高能效的图计算系统[4,5].真实图的规模动辄有数十亿个顶点和上万亿条边，庞大的顶点和边以及附带的各类属性使得遍历、查找等图计算过程中无法预知相邻数据，造成存储访问的随机性强、局部性差，而图计算操作简单、实时性强的高“访存计算比”不仅带宽需求高，且带宽浪费严重[6,7].同时，图的组织形式包括邻接矩阵、关系矩阵、邻接表等，幂律分布的图数据往往组织成稀疏矩阵的形式[6]，图应用各式各样、图结构也千差万别，相同图应用处理不同图时性能差异巨大[8].经过不同压缩格式处理过的图数据，会对图计算加速器的性能造成不同的影响.因此，根据不同需求的应用算法来选择合适的压缩格式来提高图计算加速器的性能尤为重要.

本文通过对图计算中常用的稀疏矩阵存储方法COO(Coordinate List，按坐标表示)[6,9]、CSC(Compressed Sparse Column，压缩稀疏列)[6,10]、CSR(Compressed Sparse Row，压缩稀疏行)[6,11]、DCSC(Doubly Compressed Sparse Column，双压缩稀疏列)[12]和CSCI(Compressed Sparse Column Independently，独立稀疏列压缩)[13]5种图数据格式分别作为具有代表性的社交类应用的三角形计数算法TC(Triangle counting)的输入格式进行特性分析，性能参数包括执行时间(Exec.time)、计算量(compute)、数据移动量(Datamv)、每周期指令数(IPC)、各级cache的缺失率(MPKI)以及功耗(energy)，通过对这些特征数据的比较为不同需求的图计算加速器设计提供依据.

2 算法及图数据格式分析

2.1 三角形计数算法

三角形计数算法[14](TC，Triangle Counting)是一种统计算法，用于理解社交网络、图形分析和计算聚类系数.该算法伪代码如表1所示.TC算法计算给定图形中三角形的数目，当一个顶点有两个相邻的顶点，并且这两个相邻顶点也是相邻的，则判定存在三角形，其流程图如图1所示.计算三角形数目的技术如下：每个顶点与其每个邻居共享其邻居列表.然后每个顶点计算其邻居列表与其接收的邻居列表之间的交集对于给定的无循环有向图，交叉口的大小给出了图中三角形的数目.当图是无向图时，三角形中的每个顶点都贡献了计数，因此交点的大小正好是三角形数目的3倍.本文TC算法的基本思想：若k为源顶点，统计k的邻结点q，再按顺序统计q的邻结点m，再统计对两个顶点之间边计算交集，并找出交集中id大于前两个k和q结点id的结点v，最后对每个结点统计三角形总数.

表1 TC算法伪代码Table 1 TC algorithm pseudo code

图1 TC算法流程图Fig.1 TC algorithm flow chart

2.2 图数据格式

在实际问题中大规模矩阵基本上都是稀疏矩阵，稀疏矩阵是指矩阵中的元素大部分是0的矩阵.COO按坐标表示，每一个元素需要用一个三元组来表示，分别是行号、列号和数值.CSC由3个数组表示：指数、索引和数值，其中指数是行索引的数组，数值是对应非零值的数组，索引指向列的指数和数值.长度为n+1，最后一项是数据的总数.CSR与CSC类似，同样由3个数组来表示：列索引、行偏移和数值.DCSC它是CSC的扩展，由4个数组表示：列号，行号，列偏移，数值.CSCI由索引index的最高两位指示index其余位与数值value的含义.(ioc，index,value)，ioc为“1”，则表示index为列号，value表示该列非零元素的个数；若ioc为“0”，则表示index为当前列非零元素所在的行号，value表示该非零元素的值.如图2所示一个有向图以及它的邻接矩阵和5种图数据格式.

图2 一个有向图以及它的邻接矩阵和5种图数据格式Fig.2 Directed graph as well as its adjacency matrix and five graph data formats

3 实验环境建立与性能指标定义

3.1 硬件平台

本文的实验平台是hpe580 Intel(R)Xeon(R)Platinum 8164 CPU@2.00GHZ，该服务器具有208个物理核416线程，每个核心都有一个32KB的L1级数据cache，一个32KB的L1级指令cache，1024KB的L2级cache以及36608KB的L3级cache，内存大小为1TB，运行Linux内核4.15.0系统，所有代码均使用gcc5.3.0版本进行编译和运行，CPU平台的规格如表2表示.

表2 CPU平台的规格Table 2 Specifications of the CPU platform

3.2 数据集选取

本文的实验数据选自斯坦福大学的SNAP(Stanford Network Analysis Project)数据集中internet peer-to-peer networks的p2p-Gnutella04[15]、internet peer-to-peer networks的p2p-Gnutella06[16]以及Social networks的soc-Epinions1[17]，其各自的顶点个数、边数、类型以及描述如表3所示.

表3 实验所选的数据集Table 3 Data sets selected in the experiment

3.3 分析工具

常用的分析工具包括Perf[18]和Intel VTune[19].Perf是一个分析器工具，可以抽象出CPU硬件性能测量.VTune性能分析器用于基于x86的32位和64位的性能分析，它有助于各种代码分析，包括堆栈采样、线程分析和硬件事件采样.本文使用Perf和VTune来保证数据的可靠性.表4列出了与性能特征相关的可测量事件的子集[20,21].

表4 性能事件列表及描述Table 4 List and description of performance events

3.4 性能指标定义

根据统计的硬件性能事件，本文分析的性能指标如下：执行时间、IPC、数据移动量、功耗、计算量、L1、L2以及L3数据缓存MPKI.由于输入图数据规模差别较大的原因，本文将性能指标统一到每一条边的处理上.

3.4.1 执行时间

执行时间是计算机完成目标任务所需的总时间，包括硬盘访问、内存访问、I/O活动、操作系统开销和CPU执行时间等，单位为毫秒/边(ms/edges).根据下列公式计算3种图数据在不同压缩格式中的每条边的执行时间：

(1)

3.4.2 IPC

IPC(Instruction Per Clock)是CPU每一时钟周期内所执行的指令数，影响IPC的因素有算法、编程语言、编译器以及指令系统体系结构.根据下列公式计算3种图数据作为输入数据的TC算法的IPC：

(2)

3.4.3 数据移动量

数据移动量受延迟和带宽的限制，对于不同压缩格式的同一个数据集运行之后的数据移动量是远远不同的.本文统计了TC算法在每一种图数据格式下的数据移动次数，此处的数字表示数据移动操作.在等式(3)中所示负载和存储指令总数和表示数据移动，然后除以边数，根据下列公式计算每条边的数据移动量：

(3)

3.4.4 功 耗

功耗是图计算加速器的重要性能指标，在评价分析功耗时使用焦耳能量单位比瓦特功率单位更合理.本文用VTune性能分析器分别统计3种图数据在每种图数据格式下TC算法实现时所消耗的总功率.根据公式计算每条边的功耗：

(4)

3.4.5 MPKI

MPKI(Misses Per Kilo Instructions)是用来分析cache性能的通用指标，表示每千条指令的平均未命中数.cache缺失率越低，则cache性能越好，存储访存的速度就越快.根据下列公式计算各级cache的MPKI：

(5)

3.4.6 计算量

在程序执行的过程中，不同的图数据输入格式和使用的算法是影响计算量的主要原因.同一个算法处理同一个数据集的不同压缩格式时，计算量也是不尽相同的.根据下列公式计算每条边的计算量：

(6)

4 图数据格式的内存占用及特性分析

本节介绍了在所选的5种图数据格式的内存占用情况以及在TC应用下的性能特征，并通过对比不同的性能指标列出了一些图计算加速器设计建议.

4.1 图数据格式内存占用情况

图3表示了3种图数据在不同的图数据格式下的内存占用情况.由于COO格式与原数据格式相似，因此为了更好的对比分析5种图数据格式内存占用情况，图3中将其他4种图数据格式归一化到COO格式.从图3可以看出，COO格式占用的内存最大，因为COO格式采用三元组的形式来存储原始数据的所有边和顶点的信息；DCSC格式对数据的压缩程度最大，占用的内存最小，这是因为DCSC在CSC的基础上对列偏移量再次进行压缩，只存储非零元素个数大于等于1的列，输出4个压缩数组，分别是压缩后的非零列、非零列的偏移值，非零列元素值对应的非零行以及非零元素，所以对于足够稀疏的图数据来说存储效率最高；CSR与CSC的压缩结果二者相差不大，CSC和CSR需要用两个数组来存储每个顶点所有边的个数、边的源顶点(CSC)或者目标顶点(CSR)，因此当稀疏矩阵的行列数相近时，内存占用大小也相近，对原始数据的压缩程度相对较大；CSCI格式是将邻接稀疏矩阵表示的图数据转换成独立稀疏列压缩的图数据，每列单独压缩后的图数据包括列标识数据对和非零元素数据对，每个数据对包括索引和数值，故与DCSC、CSR和CSC格式相比较内存占用较大.

图3 3种图数据5种图数据格式下的内存占用情况(归一化到COO格式)Fig.3 Memory usage of three graph data and five graph data formats(normalized to COO format)

4.2 5种图数据格式的特性分析

为了对5种图数据格式的相同算法处理的性能特征进行系统性的分析，本文通过雷达图的形式显示了COO、CSC、CSR、DCSC和CSCI5种图数据格式在TC算法应用中的性能，如图4所示，在每一幅图中，包括每个图数据下5种图数据格式实现的IPC、数据移动量、执行时间、功耗以及L1、L2和L3三级数据缓存MPKI.其中，每个度量标准的最大值视为100%.

图4 3种图数据下5种图数据格式的性能指标Fig.4 Performance indicators of five graph data formats under three graph data

4.2.1 执行时间

3种图数据在5种图数据格式下每条边的执行时间如表5所示.将每个图数据下的最大执行时间归一化，在图数据p2p-Gnutella04下COO占CSCI的35.81%，CSC占CSCI的0.04%，CSR占CSCI的0.15%，DCSC占CSCI的9.69%；在图数据p2p-Gnutella06下COO占CSCI的34.06%，CSC占CSCI的0.05%，CSR占CSCI的0.18%，DCSC占CSCI的9.76%；在图数据soc-Epinions1下COO占CSCI的9.49%，CSC占CSCI的0.92%，CSR占CSCI的0.99%，DCSC占CSCI的9.10%.可以看出，3种图数据下CSC格式边的执行时间最短，CSR格式相比CSC较短，DCSC的执行时间和COO的执行时间相近居中，CSCI的执行时间最大.因此，在考虑边的执行时间时，图计算应用优先选择CSC格式.

表5 3种图数据5种图数据格式下的执行时间(ms)Table 5 Execution time(ms)of three graph data and five graph data formats

4.2.2 数据移动量

3种图数据在5种图数据格式下每条边的数据移动量如表6所示.将每个图数据下的最大数据移动量归一化，在图数据p2p-Gnutella04下COO占CSCI的74.93%，CSC占CSCI的3.71%，CSR占CSCI的4.49%，DCSC占CSCI的59.12%；在图数据p2p-Gnutella06下CSCI占COO的13.43%，CSC占COO的6.48%，CSR占COO的8.10%，DCSC占COO的27.37%；在图数据soc-Epinions1下COO占CSCI的97.07%，CSC占CSCI的42.93%，CSR占CSCI的42.94%，DCSC占CSCI的86.37%.可以看出，3种图数据下CSC和CSR格式每条边的数据移动量相接近，其中CSC格式的数据移动量最小，DCSC格式相对较小，COO格式相对CSC、CSR较大，CSCI格式的数据移动量最大.因此，在考虑边的数据移动量时，图计算应用优先选择CSC格式.

表6 3种图数据5种图数据格式下每条边的数据移动量(指令数/边)Table 6 Data movement amount of each side in the three graph data five graph data formats(number of instructions/edge)

4.2.3 功耗

3种图数据在5种图数据格式下每条边的功耗如表7所示.将每个图数据下的最大功耗归一化，在图数据p2p-Gnutella04下CSCI占COO的75.28%，CSC占COO的57.39%，CSR占COO的47.73%，DCSC占COO的33.24%；在图数据p2p-Gnutella06下COO占CSCI的37.03%，CSC占CSCI的84.71%，CSR占CSCI的40.79%，DCSC占CSCI的43.44%；在图数据soc-Epinions1下CSCI占COO的86.00%，CSC占COO的34.77%，CSR占COO的29.01%，DCSC占COO的28.39%.可以看出，图数据p2p-Gnutella04和soc-Epinions1下DCSC格式的功耗最小，COO格式的功耗最大；图数据p2p-Gnutella6下COO格式的功耗最小，CSCI格式的功耗最大,对于3种图数据在5种图数据下的功耗，DCSC格式总体偏小.因此，考虑到边的功耗时，图计算应用优先选择DCSC格式.

表7 3种图数据5种图数据格式下每条边的功耗(J)Table 7 Power consumption of each side of the three graph data and five graph data formats(J)

4.2.4 MPKI

3种图数据在5种图数据格式的L1、L2和L3级cache MPKI分别如表8、表9和表10所示.将每个图数据下的最大的各级cache缺失率归一化，在图数据p2p-Gnutella 04下L1级cache缺失率CSCI占COO的90.44%，CSC占COO的58.13%，CSR占COO的60.36%，DCSC占COO的16.46%，L2级cache缺失率CSCI占COO的35.48%，CSC占COO的3.71%，CSR占COO的0.10%，DCSC占COO的0.68%，L3级cache缺失率COO占CSC的2.41%，CSR占CSC的1.19%，CSCI占CSC的3.22%，DCSC占CSC的3.47%；在图数据p2p-Gnutella06下L1级cache缺失率CSCI占COO的95.84%，CSC占COO的58.86%，CSR占COO的64.77%，DCSC占COO的12.47%，L2级cache缺失率CSCI占COO的52.14%，CSC占COO的12.78%，CSR占COO的4.22%，DCSC占COO的0.14%，L3级cache缺失率COO占CSC的2.22%，CSR占CSC的17.99%，CSCI占CSC的3.33%，DCSC占CSC的1.92%；在图数据soc-Epinions1下L1级cache缺失率CSCI占COO的54.38%，CSC占COO的10.56%，CSR占COO的10.22%，DCSC占COO的9.89%，L2级cache缺失率CSCI占COO的64.68%，CSC占COO的7.02%，CSR占COO的4.68%，DCSC占COO的0.05%，L3级cache缺失率CSC占COO的2.07%，CSR占COO的2.57%，CSCI占COO的47.56%，DCSC占CSC的1.05%.可以看出，在所有图数据格式下，L1级cache MPKI都小于5，L1级cache MPKI与L2级cache MPKI和L3级cache MPKI相比普遍偏高，综合各级cache MPKI对比可以发现DCSC格式具有更小的各级cache MPKI，COO格式具有较高的cache缺失率，较低的缺失率可有效减少时间损耗.因此，考虑各级cache缺失率时，图计算应用优先选择DCSC格式.

表8 3种图数据5种图数据格式下L1级cache MPKI(misses/kilo_instructions)Table 8 L1 level cache MPKI(misses/kilo_instructions)under three typesof graph data and five types of graph data formats

表9 3种数据集5种图数据格式下L2级cache MPKI(misses/kilo_instructions)Table 9 L2 level cache MPKI(misses/kilo_instructions)in three data sets and five image data formats

表10 3种数据集5种图数据格式下L3级cache MPKI(misses/kilo_instructions)Table 10 L3 level cache MPKI(misses/kilo_instructions)in three data sets and five image data formats

4.2.5 计算量

3种图数据在5种图数据格式下每条边的计算量如表11所示.将每个图数据下的最大计算量归一化，在图数据p2p-Gnutella04下COO占CSCI的39.36%，CSC占CSCI的6.50%，CSR占CSCI的8.62%，DCSC占CSCI的10.68%；在图数据p2p-Gnutella06下COO占CSCI的31.64%，CSC占CSCI的6.97%，CSR占CSCI的8.64%，DCSC占CSCI的8.67%；在图数据soc-Epinions1下CSCI占COO的33.07%，CSC占COO的8.95%，CSR占COO的8.94%，DCSC占COO的28.09%.可以看出，3种图数据下CSC格式的计算量最少，CSR格式相对较少，DCSC格式的计算操作量居中，COO格式的计算操作相对较多，CSCI格式的计算量最多.因此在计算量受限制的情况下，图计算应用优先选择CSC格式.

表11 3种图数据5种图数据格式下每条边的计算量(指令数/边)Table 11 Calculation amount of each side of the three graph data and five graph data formats(number of instructions/edge)

4.3 实验结果

分析结果可以看出5种图数据格式在不同的图数据下有着各自的特点.TC算法在相同图数据不同图数据格式下，性能指标执行时间、计算量和数据移动量在CSC格式下表现最好，性能指标功耗和各级cache缺失率在DCSC格式下表现最好；TC算法在不同图数据相同图数据格式下，具有较多的边和顶点的图数据性能指标数据偏大.相同的图数据不同的图数据格式对TC算法性能的影响是因为不同的图数据格式对图数据存储的方式不同.COO格式采用三元组的形式直观的存储图数据中非零元素的信息，访问全部的顶点和顶点的的邻接边，故而COO格式对图数据的查询及访问效率较低；CSC和CSR格式占用内存相比于CSCI和COO较小，其中CSC格式是按列压缩存储图数据，CSR格式是按行压缩存储图数据的，它们存储的信息是当前活动顶点的偏移量，和偏移值对应的行列索引值，占用内存较小，存储率较高；DCSC格式是CSC的扩展，它通过删除零(空)列来进一步压缩矩阵，从而避免数组中重复的元素，因为删除了零列，所以需要间接指向以索引保留的非零列，对于稀疏图数据来说存储效率最高；CSCI格式是将邻接稀疏矩阵表示的图数据转换成独立稀疏列压缩的图数据，每列单独压缩后的图数据包括列标识数据对和非零元素数据对，每个数据对包括索引和数值，由索引的最高两位指示其余位与数值的含义，可以精确的找到顶点，但占用内存相比较其他的压缩格式较大，而具有较大边和顶点的图数据会增加算法访问难度.

5 结束语

本文通过分析3种图数据的5种图数据格式(COO、CSC、CSR、DCSC和CSCI)在TC算法的性能数据，发现：对于TC算法，同一种图数据下考虑执行时间、数据移动量和计算量时，优先选择CSC格式；当考虑缓存命中率和功耗时，优先选择DCSC格式作；当内存受限时，优先选择DCSC格式.因此，在面对不同的应用环境和不同的性能要求时，根据实际需求以上述结论为依据进行调整可有效提高图计算加速器的性能.