图广度优先搜索算法面向图形处理器的优化方法研究

• 作者: 刘谷 吴石磊 安虹 李小强
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 图形处理器 图广度优先算法 不规则程序 并行性剖析 优化方法
• 年，卷（期）: 2014,（5）
• 所属期刊栏目: 计算机体系结构研究
• 页码范围: 1074-1079
• 页数: 6页
• 分类号: TP303
• 字数: 7667字
• 语种: 中文

摘要

近年来,图形处理器(GPU)以其丰富的计算资源和低廉的成本逐渐在高性能计算领域取得一席之地,对于具有规则访存特性的并行程序具有明显的加速作用.但是以图广度优先搜索(BFS)算法为代表的某些不规则应用,在图形处理器上性能表现平平.为了解决不规则程序在图形处理器上的性能瓶颈问题必须分析其行为特征,面向特定体系结构提出有针对性的程序优化方法.本文通过分析图广度优先搜索算法的在GPU上的并行性模式,访存特性以及工作负载,提出了基于并行性剖析与反馈的计算资源重配置方法,动态队列的层次优化方法,以及线程级负载平衡方法.实验表明以上优化方法能够显著提高图广度优先搜索算法为代表的不规则程序在GPU上的性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	安虹	中国科学技术大学计算机科学与技术学院	65	224	7.0	12.0
5	李小强	中国科学技术大学计算机科学与技术学院	40	553	14.0	23.0
6	刘谷	中国科学技术大学计算机科学与技术学院	3	8	2.0	2.0
7	吴石磊	中国科学技术大学计算机科学与技术学院	4	9	2.0	3.0