现如今,以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。