面向MIC的并行图算法负载平衡优化技术

摘要

图的遍历是一种基础的图形算法在社交网络、商业分析、高性能计算等领域有广泛应用的图形算法.在单节点上图的遍历已经被研究和优化的非常完善.目Intel的MIC(Many Integrated Core)是一种为高并行计算设计的众核协处理器,它拥有多达57个核.当用MIC来遍历图形时可能会存在很严重的负载不平衡现象,这会对系统的性能造成不利影响.提出了一种新颖用MIC加速并行宽度优先搜索算法(BFS)的方法为了使系统的性能达到最高，在CPU和MIC之间进行了任务划分，并通过实验找出使系统性能达到最高的最佳划分。通过这些优化措施,相较于未经优化的算法获得了非常高的性能提升.这一新颖的算法将会得到广泛的应用,特别是拥有多个MIC的大规模并行系统中.