基于GPU的高性能并行優(yōu)化算法研究.pdf

1、博士學位論文基于GPU的高性能并行優(yōu)化算法研究HighPerformanceParallelOptimizationAlgorithmBasedonGPU學號：』幽鯉答辯日期：星Q!壘生12旦圣旦大連理工大學DalianUniversityofTechnology大連理工大學博士學位論文摘要隨著高性能并行計算設備的目益普及，特別是高性能圖形處理器(GPU)的迅猛發(fā)展，基于GPU高性能計算平臺的并行優(yōu)化應用服務解決方案引起國內外研究學者的

2、極大關注。由于傳統CPU、計算集群在計算資源以及能耗方面的限制，以及各類科學工程優(yōu)化問題對于并行計算需求的不斷提升，基于高性能并行計算的擴展模型、仿真計算、算法優(yōu)化以及數值計算已經成為當前高性能計算的研究熱點。高性能并行優(yōu)化算法作為銜接底層并行計算平臺及上層應用服務的關鍵部分，在算法性能的優(yōu)化以及應用空間的擴展方面仍然存在嚴峻挑戰(zhàn)和亟需解決的問題，需要對算法優(yōu)化和數值計算問題的方法和技術不斷提高和完善。基于此，本文將重點進行高性能并行計

3、算隨機數生成、智能算法優(yōu)化和數值計算算法等方面的研究創(chuàng)新。針對隨機數生成器、蟻群算法、最小平方估計等問題，采用GPU擴展加速比模型、GPU局部優(yōu)化等技術，設計并提出三個關鍵的并行優(yōu)化解決方案。主要研究內容和創(chuàng)新點如下：(1)針對傳統隨機數生成速度較慢及加速優(yōu)化模型擴展性較差的問題，通過對當前可擴展加速優(yōu)化模型及隨機數生成器機制的分析總結，給出一種考慮存儲層次的GPU可擴展加速比優(yōu)化模型，并基于該模型提出了一種簡單的高性能并行計算隨機數生

4、成算法f簡稱為CUDA—RNG)，該算法充分利用了GPU間的協同計算能力，最終可以生成高效率的隨機數序列。實驗結果表明，CUDARNG算法能夠在連續(xù)計算運行時達到189。32倍的生成速度，且具有很小的內存負載開銷。(2)針對蟻群算法在大規(guī)模的最優(yōu)化問題中難以得到最優(yōu)解的問題，受蟻群算法在本質上具有并行性特點的啟發(fā)，著重研究如何在GPU并行計算環(huán)境下提高蟻群算法的性能及效率。通過對TSP(旅行商)問題的蟻群算法建模，提出一種新的基于CUD

5、A(統一計算設備架構)的蟻群優(yōu)化算法，簡稱為GACO。該算法結合了MMAS(MAXMINAntSystem)禾HACS(AntColonySystem)l拘共性特點進行混合信息矩陣更新、動態(tài)構建最短鄰接路徑和多路蟻群分布等優(yōu)化策略。最后對GPU的性能優(yōu)化方案做了分析，通過使用這些優(yōu)化策略使得該算法跟同等類型的算法相比具有更高的速度和質量。實驗結果表明，本文提出的GACO算法性能在搜索加速度上分別比ACS、MMAS要高出401倍與357倍