分支密集应用在GPU上的优化方法研究

发布时间：2017-09-27 09:33

  本文关键词：分支密集应用在GPU上的优化方法研究

  更多相关文章： CUDA Control Divergence 基于线程交换优化 延迟隐藏

【摘要】：现如今,以CPU+GPU为主的异构模式被广泛的使用,06年CUDA编程架构的推出大大提高了GPU的可编程性,各领域内使用CUDA进行加速的应用程序大量出现。CUDA的架构中引入了STMD的概念。STMD中在提高硬件资源利用效率的同时也引入了一些问题。STMD架构中引入了Warp的概念,Warp是GPU创建,管理,执行的最小单元,Warp有在一个周期内其中所有线程必须执行同一条指令的特性,因此在遇到分支等情况时会产生Control Divergence,严重影响程序的执行效率。本文重点研究方向是如何最大程度上降低分支密集型应用在执行过程中产生的Control Divergence以提高程序性能。为了解决这个问题,本文提出了一种基于线程交换的软件优化算法,可以在真实机器平台上应用于分支密集型应用程序,并能够有效的降低此类程序中大量存在的Control Divergence,从而提高程序性能,缩短程序运行时间。本文所做的工作以及成果有:1)深入分析了多个分支密集应用产生Control Divergence的具体原理,并对程序按如下标准进行分类。(1)易获得分支特性(Easy-Handled,EH)与不易获得分支特性(Hard-Handled,HH),(2)线程编号相关(Thread-Index Dependent,TID)与线程数据相关(Thread-Data Dependent,TDD)。通过这种分类将CUDA程序分为四类,可便于针对每一类进行不同的优化。2)提出并设计一种基于线程交换的优化算法框架,并进一步细化,将其分成直接构造映射表优化算法(DIMA,Direct Index-Map Algorithm)以及预处理构造映射表算法(PIMA,Pre-process Index-Map Algorithm)。实验结果表明,优化之后程序的Control Divergence基本降至无,使用线程交换优化算法优化之后相对与优化之前运行时间降低明显。优化之后Kernel的加速比平均有1.5左右,而总体运行时间的加速比平均有1.2左右。3)DIMA与PIMA算法中参数的控制可能会对优化结果产生影响。其中对于TID类型的程序线程交换范围会有影响,对于适用于PIMA算法的程序中,预处理的次数也是需要考虑的因素,因此对算法执行过程中参数的控制进行测试研究并得出结论。测试发现,对于不同的程序,由于要进行控制Control Divergence与控制不规则访存之间的权衡,线程交换范围的最优解不同。同样的,对于使用PIMA的程序,最优的预处理次数也不同。4)通过分析算法执行过程中的开销的产生情况并提出基于流水的延迟隐藏算法,这种算法利用CUDA中提供的异步数据传输函数Cuda Mem Cpy Asyc使得数据传输与Kernel执行重叠,通过合理的控制传输数据的范围以及执行Kernel的时间使之尽可能相同,那么就可以在一定程度上隐藏传输开销,提高程序性能。实验结果表明,相对于未优化之前,加速比平均有1.1。
【关键词】：CUDA Control Divergence 基于线程交换优化 延迟隐藏
【学位授予单位】：国防科学技术大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP391.41;TP332
【目录】：

• 摘要9-11
• ABSTRACT11-13
• 第一章 绪论13-26
• 1.1 研究背景与意义13-18
• 1.1.1 GPU的结构与发展13-18
• 1.2 CUDA编程模型18-24
• 1.2.1 编程桥梁问题18-19
• 1.2.2 CUDA编程架构19-20
• 1.2.3 CUDA执行模型20
• 1.2.4 控制流问题的产生与影响20-24
• 1.3 本文目标与主要工作24-25
• 1.3.1 课题目标24
• 1.3.2 课题主要工作24-25
• 1.3.3 课题来源25
• 1.4 本文结构安排25-26
• 第二章 CUDA及控制流优化研究现状26-34
• 2.1 CUDA的研究现状26-27
• 2.2 控制流的优化研究现状27-33
• 2.2.1 硬件优化方法27-30
• 2.2.2 软件优化方法30-33
• 2.3 本章小结33-34
• 第三章 线程交换优化34-51
• 3.1 线程交换的基本思想34-37
• 3.1.1 CUDA Kernel的抽象表示34-36
• 3.1.2 线程交换的概念36-37
• 3.2 线程交换方法37-39
• 3.2.1 Control Divergence分类37
• 3.2.2 交换映射表37-39
• 3.3 映射表的直接构造39-45
• 3.3.1 DIMA基本框架39-42
• 3.3.2 DIMA正确性证明42-45
• 3.4 映射表的预处理构造45-47
• 3.4.1 PIMA基本框架45-46
• 3.4.2 交换数据方法46-47
• 3.5 设计参数优化探究47-49
• 3.5.1 预处理构造映射表法的参数选择47-49
• 3.5.2 非TDD的参数选择49
• 3.6 本章小结49-51
• 第四章 延迟隐藏优化51-57
• 4.1 延迟隐藏技术概述51-53
• 4.2 数据交换的延迟隐藏53-56
• 4.2.1 延迟隐藏流水线的设计54-56
• 4.3 本章小结56-57
• 第五章 性能评价57-84
• 5.1 实验环境57-60
• 5.2 算法性能测试60-79
• 5.2.1 使用DIMA算法进行优化的程序60-70
• 5.2.2 使用PIMA算法进行优化的程序70-79
• 5.3 延迟隐藏性能评价79-83
• 5.3.1 Bitonic sort的优化79-80
• 5.3.2 Reduction的优化80-81
• 5.3.3 Needle-Wunch的优化81-82
• 5.3.4 Marching cubes的优化82-83
• 5.3.5 Hotspots的优化83
• 5.4 本章小结83-84
• 第六章 结束语84-86
• 6.1 全文总结84-85
• 6.2 研究展望85-86
• 致谢86-88
• 参考文献88-92
• 作者在学期间取得的学术成果92

【相似文献】

中国期刊全文数据库 前10条

1 ;An Object-Oriented Multi-Thread Dialog Model[J];The Journal of China Universities of Posts and Telecommunications;1998年01期

2 陈希超;王健;;基于RT-Thread的嵌入式网络通信系统的设计与实现[J];电声技术;2012年12期

3 成淑萍;;C#实现简易WEB服务器[J];中国西部科技;2009年01期

4 管莉;邹汝平;朱斌;郝重阳;;An HLA/RTI Architecture Based on Multi-thread Processing[J];Journal of China Ordnance;2010年03期

5 闫泽华;李芳;;Thread Labeling for News Event[J];Journal of Shanghai Jiaotong University(Science);2013年04期

6 郭宇;蒋信予;陈意云;;Certification of Thread Context Switching[J];Journal of Computer Science & Technology;2010年04期

7 朱志国;;RT-Thread操作系统在STM32中移植的研究[J];计算机光盘软件与应用;2012年22期

8 涂撰;赵标;;RT-Thread在LPC2378上的移植与应用[J];上海船舶运输科学研究所学报;2013年01期

9 shxf;;今日话题[J];飞碟探索;2010年09期

10 吴宇翔;李鑫;刘清;;基于RT-Thread和STM32的数码相框的设计[J];电子世界;2013年18期

中国重要报纸全文数据库 前2条

1 本报记者 张哲;网络互动工具助MBA课程实践、学术双向发展[N];中国社会科学报;2012年

2 上海大学 孙渊磊;PB中消息对话框的居中显示[N];计算机世界;2001年

中国硕士学位论文全文数据库 前10条

1 王振运;基于RT-Thread和STM32的双轮自平衡机器人的设计与实现[D];中北大学;2016年

2 冯曙光;基于Real-Time Maude的AADL Thread构件的形式化建模与验证[D];华东师范大学;2016年

3 钱程;分支密集应用在GPU上的优化方法研究[D];国防科学技术大学;2014年

4 郭聚建;基于RT-Thread的智能开关设计[D];西安电子科技大学;2014年

5 叶思超;基于RT-Thread的手持式高性能RFID读写器设计[D];电子科技大学;2015年

6 蔡曙光;基于RT-Thread的便携式健康监测仪的设计与实现[D];安徽大学;2015年

7 曹成;嵌入式实时操作系统RT-Thread原理分析与应用[D];山东科技大学;2011年

8 邱yN;嵌入式实时操作系统RT-Thread的设计与实现[D];电子科技大学;2007年

9 涂撰;基于RT-Thread的嵌入式CAN-Ethernet网关设计与实现[D];上海交通大学;2014年

10 司梦如;基于RT-Thread的NANDFLASH文件系统中间层的设计与实现[D];安徽大学;2012年

，

本文编号：928937