模拟退火算法(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算法的特点。实验结果表明本文算法在取得了较好的优化效果的同时,显著地提高了算法的运算速度。