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

• 作者: 安虹 徐启泽 陈俊仕 韩文廷
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 广度优先搜索 众核架构 非均匀访存 向量化 性能优化
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 交叉与前沿
• 页码范围: 314-319
• 页数: 6页
• 分类号: TP302
• 字数: 6498字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2019.01.049

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	安虹	中国科学技术大学计算机科学与技术学院	65	224	7.0	12.0
2	陈俊仕	中国科学技术大学计算机科学与技术学院	10	25	3.0	5.0
3	徐启泽	中国科学技术大学计算机科学与技术学院	1	0	0.0	0.0
4	韩文廷	中国科学技术大学计算机科学与技术学院	6	7	1.0	2.0