利于GPU计算具有线性并行度的P/G网SOR求解算法

• 作者: 唐亮 杨旭 赵国兴 骆祖莹
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 图形处理器 连续过松弛算法 统一计算设备架构 并行算法 电源线/地线网络(P/G网)
• 年，卷（期）: 2013,（7）
• 所属期刊栏目: 图形与图像处理
• 页码范围: 1491-1500
• 页数: 10页
• 分类号: TP391.7
• 字数: 6267字
• 语种: 中文

摘要

近年来电子设计自动化(EDA)研究人员尝试利用图形处理器(graphic processing unit,GPU)提供的高性能计算能力对IC参数分析进行加速研究.为了利用GPU进行电源线/地线网络(power/ground network,P/G网)快速分析,设计了一种基于经典的连续过松弛(successive over-relaxation,SOR)算法的高效P/G网分析并行算法.基于GPU并行计算加速原理,此算法进行了如下改进:1)采用红-黑次序的松弛策略.将所有的节点分为红黑两类,红色节点的所有邻点只有黑色节点、黑色节点的所有邻点只有红色节点,红色节点与黑色节点交替松弛,保证了GPU并行计算中的数据一致性.对于具有N个节点的P/G网而言,一次红色节点或黑色节点松弛可以同时对N/2个节点进行松弛操作,即理论上可以同时启动N/2个并行线程.2)优化数据结构.实现了对数据空间的合并访问,以保证对GPU全局存储空间的最优访问.3)在共享存储器内通过并行归约对松弛标记进行快速统计,同时利用zero-copy技术进行松弛标记的快速拷贝,以快速决定是否继续松弛.大量的实验结果表明:与单线程的CPU程序相比,此算法的加速倍数随GPU所提供物理线程的数目增加而线性增加,可以获得最大242倍的加速效果,是目前EDA研究领域中加速效果最好的GPU算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵国兴	北京师范大学信息科学与技术学院	8	39	4.0	6.0
2	骆祖莹	北京师范大学信息科学与技术学院	28	143	7.0	11.0
3	唐亮	北京师范大学信息科学与技术学院	7	37	4.0	6.0
4	杨旭	北京师范大学信息科学与技术学院	6	10	2.0	3.0