图数据压缩格式对广度优先搜索算法影响的特性化分析

作者：任含; 邓军勇^*

来源：郑州大学学报(理学版）, 2021, 53(02): 26-33.

DOI：10.13705/j.issn.1671-6841.2020260

• 压缩格式
• 图计算
• 广度优先搜索
• 性能分析

随着图计算需求的快速增长,同一种图算法在处理不同压缩格式的数据时会对访存、性能等方面产生不同的影响。将两种图数据的5种不同数据压缩格式COO、CSC、CSR、DCSC和CSCI分别作为广度优先搜索算法的输入进行性能分析和对比,根据性能特征选择不同的压缩格式的数据以达到最佳结果。针对BFS处理5种不同数据压缩格式进行性能分析,参数主要包括执行时间、数据移动量、计算量以及功耗等,并面向性能和功耗进行了相关性分析。实验结果表明,BFS算法在处理不同的数据压缩格式时性能指标各不相同,其中:从数据移动量、计算操作量、执行时间和功耗方面来看,CSR与CSC两种数据压缩格式相对较优;在有效提高缓存命中率指标中,DCSC压缩格式最优;从占用内存来看,DCSC压缩格式内存占用相对较小。该结论为BFS算法中如何根据不同性能特征选择不同的压缩格式提供了依据。

• 单位
  电子工程学院; 西安邮电大学