众核平台上广度优先搜索算法的优化

摘要：

图算法在多个领域具有重要的应用价值.随着社会信息化程度的提高,需要处理的图数据量越来越大,图算法的性能已成为研究热点.广度优先搜索算法是一种重要的图算法,研究它的性能优化技术可以为其他图算法的性能优化提供借鉴.目前,在新一代Xeon Phi众核处理器上的工作均基于自顶向下算法且没有考虑到非均匀访存(NUMA)对性能的影响.文中以混合广度优先搜索算法为基础,结合NUMA拓扑结构,从任务分配、向量化和数据预处理3个方面展开优化,在Xeon Phi平台上设计并实现了高性能并行广度优先搜索算法.一系列实验结果表明,优化后的算法在不同规模的测试数据上与G raph500官方优化的算法相比取得了50％ ～145％ 的性能提升.

关键词：广度优先搜索、众核架构、非均匀访存、向量化、性能优化

所属期刊栏目：46

分类号：TP302(计算技术、计算机技术)

资助基金：国家重点研发计划2016YFB0201902

在线出版日期：2019-03-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：314-319