文章摘要:图计算由当前图应用与输入图数据驱动，而图应用各式各样、图结构也千差万别，相同图应用处理不同图时性能差异巨大。为探究图数据格式对图算法的性能影响，本文选取五种常用的图数据格式COO、CSC、CSR、DCSC和CSCI以及社区发现算法三角形计数在图数据p2p-Gnutella04、p2p-Gnutella06、soc-Epinions1上的应用作为分析对象，定义了图数据格式对图计算系统影响的性能指标，包括执行时间、数据移动量、计算量、功耗和各级cache MPKI等，基于Skylake Xeon（R） Platinum 8164处理器进行性能事件采集。实验结果表明，TC在COO、CSC、CSR、DCSC和CSCI格式下运行p2p-Gnutella04/06、soc-Epinions1图数据的执行时间（归一化到最长执行时间）之比为35.7%、0.04%、0.15%、9.7%、100%与34.1%、0.05%、1.81%、9.76%、100%和9.49%、0.92%、0.99%、9.1%、100%，数据移动量（归一化到最大数据移动量）之比为74.9%、3.7%、4.5%、20.32%、100%与100%、0.65%、0.81%、27.37%、13.43%和97.08%、42.94%、42.95%、86.38%、100%，计算量（归一化到最大计算量）之比为39.36%、6.5%、8.62%、10.68%、100%与31.6%、6.97%、8.64%、8.67%、100%和100%、0.9%、0.89%、28.09%、33.07%，功耗（归一化到最大功耗）之比为100%、57.39%、47.73%、33.24%、75.28%与37.03%、84.7%、40.8%、43.4%、100%和100%、34.77%、29.01%、28.39%、86%。实验结果对于为TC应用的输入图数据格式选择提供了依据。

文章关键词:

项目基金: