面向高性能图计算的高效高层次综合方法

汤嘉武 郑 龙 廖小飞 金 海

(华中科技大学计算机科学与技术学院 武汉 430074) (大数据技术与系统国家地方联合工程研究中心(华中科技大学) 武汉 430074) (服务计算技术与系统教育部重点实验室(华中科技大学) 武汉 430074) (集群与网格计算湖北省重点实验室(华中科技大学) 武汉 430074)

(jiawut@hust.edu.cn)

最近10年来随着生物信息网络、社交网络、网页图等大数据分析问题的出现，图应用变得越来越重要，图是大数据关联属性的最佳表达方式，图计算则是基于图模式进行巨量、稀疏、超维关联的挖掘和分析过程，当前大数据的机器学习和深度学习都依赖于图计算，图计算已经成为大数据处理的主流模式之一.

图计算的复杂特性对当前硬件提出了新的挑战，CPU和面向吞吐量的架构都有各自的局限性[1].对于通用的CPU，大量研究表明,即使对于最优的图算法实现其指令级并行度仍然异常的低，绝大多数低于1.0，许多低于0.5[2].对于面向吞吐量的架构，比如GPU，按照单指令多数据(single-instruction multiple-data, SIMD)的方式执行，通过调度数以千计的线程来掩盖耗时的内存访问[3]，虽然性能较高但是功耗巨大，图数据的幂律分布和图算法的不规则性天然对SIMD模式不友好，存在负载不均和低带宽利用率问题，研究表明只有低于16%的时间GPU得到完全利用，主要性能瓶颈在于访存单元在流水线中的停滞[4].

对于可重构硬件，例如现场可编程门阵列(field-programmable gate array， FPGA)，由于其低功耗和可重构特性得到很大关注，研究人员在FPGA上针对图计算设计了诸多高效……