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

摘要

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