图计算中压缩格式对单源最短路径算法影响的特性化分析

针对在单源最短路径(Single Source Shortest Path,SSSP)算法实现中如何根据性能特征选择压缩格式以达到性能最优的问题,基于Kaby Lake架构处理器上的硬件性能计数器对不同数据集的按坐标表示(Coordinate,COO)、按列压缩(Compressed Sparse Column,CSC)、按行压缩(Compressed Sparse Row,CSR)、双压缩稀疏列(Doubly Compressed Sparse Column,DCSC)和独立稀疏列压缩(Compressed Sparse Column Independently,CSCI)五种压缩格式在单源最短路径算法处理时的执行时间、数据移动量、计算量以及功耗等相关性能指标进行分析。实验结果表明,CSR压缩格式是适合单源最短路径算法的数据结构,在减少算法的执行时间、计算操作量以及数据移动量的同时降低功耗;使用CSC压缩格式可以有效提高缓存命中率;使用DCSC压缩格式内存占用最小;使用COO和CSCI压缩格式性能较差。该结论对于遍历类应用SSSP算法输入数据集的压缩格式选择提供了依据。