基于GPU加速的细粒度并行模拟退火算法

摘要

模拟退火算法(Simulated.Annealing algorithm，SA)来源于固体退火原理，是一种通用概率算法，用来在一个大的搜寻空间内寻找问题的最优解。由于在解决大规模优化问题时，SA算法通常需要大量的计算时间，因此并行SA算法逐渐成为人们研究的热点。目前关于并行SA算法的研究主要在大型并行机上运行或利用多线程技术进行模拟，这些方法存在以下不足：进程间通信的消耗限制了线程规模；多线程技术是在CPU上用串行模拟并行，不能真正提高性能；大多数研究人员很少有机会使用上述并行机，而且并行机使用也比较复杂。
　　 近几年，图形处理器(Graphics processing unit，GPU)高速发展， 其高速浮点运算能力、并行计算和可编程功能为通用计算提供了良好的并行计算平台，NVIDIA公司推出的GPU编程的统一计算设备架构(Compute Unified Device Architecture，CUDA)，为研究人员利用GPU进行数据并行处理提供了更便捷的方法。
　　 本文针对传统并行SA算法在实际应用中的不足，利用GPU的高速并行性，提出了一种基于GPU加速的细粒度并行模拟退火算法(GPUSA)。该算法充分利用NVIDIAGPU的统一计算设备架构，将一条串行执行的Markov链拆分为若干个Markov链并行执行，即CUDA线程块并行计算过程，使等温状态下的重复抽样过程完全在GPU中加速执行，在取得较好优化解的同时，显著地提高了算法的运算速度。本文主要以Markov链的并行实现为例，详细描述了算法设计思想和程序实现过程，提供了应用于对称TSP问题的实验结果，与相应串行算法在相同计算环境下的实验结果做出比较，并针对实验结果分析了GPUSA算法的特点。实验结果表明本文算法在取得了较好的优化效果的同时，显著地提高了算法的运算速度。

目录

文摘

英文文摘

声明

引 言

1 模拟退火算法起源及其发展

1.1 TSP问题

1.2 模拟退火算法的起源

1.3 模拟退火算法的流程

1.4 模拟退火算法的研究现状

1.5 本文的主要工作

2 基于GPU的通用计算

2.1 GPU概述

2.2 GPU用于通用计算任务

2.3 GPU用于通用计算的限制

2.4 GPU通用计算的发展方向

3 基于GPU加速的细粒度并行SA算法的设计与实现

3.1 模型设计的难点分析及解决

3.1.1 CUDA简介

3.1.2 并行模型的设计

3.1.3 CUDA内存模型

3.1.4 生成的随机数处理

3.2 基于GPU的细粒度并行SA算法

3.2.1 SA算法求解TSP问题的数学模型

3.2.2 SA算法的GPU并行化模型

3.2.3 新路径的GPU并行生成

3.2.4 GPU芯片内存的优化使用

3.2.5 FGSA算法的GPU转换(GPUSA)

3.3 本章小结

4 实验结果以及结论分析

4.1 GPUSA的实验结果

4.2 实验结果分析

4.3 本章小结

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢