隨著高性能并行計(jì)算設(shè)備的日益普及,特別是高性能圖形處理器(GPU)的迅猛發(fā)展,基于GPU高性能計(jì)算平臺(tái)的并行優(yōu)化應(yīng)用服務(wù)解決方案引起國(guó)內(nèi)外研究學(xué)者的極大關(guān)注。由于傳統(tǒng)CPU、計(jì)算集群在計(jì)算資源以及能耗方面的限制,以及各類科學(xué)工程優(yōu)化問(wèn)題對(duì)于并行計(jì)算需求的不斷提升,基于高性能并行計(jì)算的擴(kuò)展模型、仿真計(jì)算、算法優(yōu)化以及數(shù)值計(jì)算已經(jīng)成為當(dāng)前高性能計(jì)算的研究熱點(diǎn)。高性能并行優(yōu)化算法作為銜接底層并行計(jì)算平臺(tái)及上層應(yīng)用服務(wù)的關(guān)鍵部分,在算法性能的優(yōu)化以及應(yīng)用空間的擴(kuò)展方面仍然存在嚴(yán)峻挑戰(zhàn)和亟需解決的問(wèn)題,需要對(duì)算法優(yōu)化和數(shù)值計(jì)算問(wèn)題的方法和技術(shù)不斷提高和完善。基于此,本文將重點(diǎn)進(jìn)行高性能并行計(jì)算隨機(jī)數(shù)生成、智能算法優(yōu)化和數(shù)值計(jì)算算法等方面的研究創(chuàng)新。針對(duì)隨機(jī)數(shù)生成器、蟻群算法、最小平方估計(jì)等問(wèn)題,采用GPU擴(kuò)展加速比模型、GPU局部?jī)?yōu)化等技術(shù),設(shè)計(jì)并提出三個(gè)關(guān)鍵的并行優(yōu)化解決方案。 主要研究?jī)?nèi)容和創(chuàng)新點(diǎn)如下： (1)針對(duì)傳統(tǒng)隨機(jī)數(shù)生成速度較慢及加速優(yōu)化模型擴(kuò)展性較差的問(wèn)題,通過(guò)對(duì)當(dāng)前可擴(kuò)展加速優(yōu)化模型及隨機(jī)數(shù)生成器機(jī)制的分析總結(jié),給出一種考慮存儲(chǔ)層次的GPU可擴(kuò)展加速比優(yōu)化模型,并基于該模型提出了一種簡(jiǎn)單的高性能并行計(jì)算隨機(jī)數(shù)生成算法(簡(jiǎn)稱為CUDA-RNG),該算法充分利用了GPU間的協(xié)同計(jì)算能力,最終可以生成高效率的隨機(jī)數(shù)序列。實(shí)驗(yàn)結(jié)果表明,CUDA-RNG算法能夠在連續(xù)計(jì)算運(yùn)行時(shí)達(dá)到189.32倍的生成速度,且具有很小的內(nèi)存負(fù)載開(kāi)銷。 (2)針對(duì)蟻群算法在大規(guī)模的最優(yōu)化問(wèn)題中難以得到最優(yōu)解的問(wèn)題,受蟻群算法在本質(zhì)上具有并行性特點(diǎn)的啟發(fā),著重研究如何在GPU并行計(jì)算環(huán)境下提高蟻群算法的性能及效率。通過(guò)對(duì)TSP(旅行商)問(wèn)題的蟻群算法建模,提出一種新的基于CUDA(統(tǒng)計(jì)算設(shè)備架構(gòu))的蟻群優(yōu)化算法,簡(jiǎn)稱為GACO。該算法結(jié)合了MMAS(MAX-MIN Ant System)和ACS(Ant Colony System)的共性特點(diǎn)進(jìn)行混合信息矩陣更新、動(dòng)態(tài)構(gòu)建最短鄰接路徑和多路蟻群分布等優(yōu)化策略。最后對(duì)GPU的性能優(yōu)化方案做了分析,通過(guò)使用這些優(yōu)化策略使得該算法跟同等類型的算法相比具有更高的速度和質(zhì)量。實(shí)驗(yàn)結(jié)果表明,本文提出的GACO算法性能在搜索加速度上分別比ACS、MMAS要高出40.1倍與35.7倍。 (3)針對(duì)在數(shù)據(jù)規(guī)模較大情況下利用奇異值分解求最小平方時(shí)的時(shí)間消耗和內(nèi)存空間代價(jià)過(guò)大的問(wèn)題,提出了一種基于GPU的迭代式分割與合并的奇異值分解最小平方估計(jì)法,簡(jiǎn)稱為IDMSVD。該算法可以有效的改善對(duì)于大型數(shù)據(jù)利用奇異值分解求最小平方問(wèn)題時(shí)的運(yùn)算時(shí)間和內(nèi)存空間。最后在GPU的CUDA計(jì)算架構(gòu)的中進(jìn)行了實(shí)現(xiàn),通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性。 本文所提出的算法具有普適意義,能夠輕松地轉(zhuǎn)移到其他的并行計(jì)算設(shè)備上,比如多核CPU或者大規(guī)模集群設(shè)備。更高性能的加速平臺(tái)如CPU和GPU混合構(gòu)架(或GPU集群)、GPU和FPGA(現(xiàn)場(chǎng)可編程門(mén)陣列)混合構(gòu)架等都有望應(yīng)用到高性能并行優(yōu)化算法的研究中。
【學(xué)位單位】：大連理工大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2014
【中圖分類】：TP332
【文章目錄】：
摘要
ABSTRACT
1 緒論
    1.1 研究背景與意義
    1.2 并行技術(shù)
        1.2.1 并行計(jì)算機(jī)體系結(jié)構(gòu)
        1.2.2 并行算法分類
        1.2.3 基于CUDA并行編程架構(gòu)
    1.3 國(guó)內(nèi)外研究現(xiàn)狀
        1.3.1 經(jīng)典優(yōu)化技術(shù)研究現(xiàn)狀
        1.3.2 現(xiàn)代智能優(yōu)化技術(shù)研究現(xiàn)狀
    1.4 本文的主要研究?jī)?nèi)容
    1.5 本文的組織結(jié)構(gòu)
2 基于GPU的并行隨機(jī)數(shù)生成優(yōu)化算法
    2.1 引言
    2.2 相關(guān)工作
    2.3 算法描述
        2.3.1 加速比擴(kuò)展模型
        2.3.2 隨機(jī)序列遞推公式
        2.3.3 數(shù)據(jù)類型轉(zhuǎn)換
        2.3.4 并行隨機(jī)數(shù)生成器
    2.4 實(shí)驗(yàn)及結(jié)果分析
        2.4.1 隨機(jī)數(shù)生成實(shí)驗(yàn)
        2.4.2 加速比實(shí)驗(yàn)
    2.5 本章小結(jié)
3 基于GPU的并行蟻群優(yōu)化算法
    3.1 引言
    3.2 相關(guān)工作
        3.2.1 智能優(yōu)化算法
        3.2.2 蟻群算法原理
    3.3 算法描述
        3.3.1 TSP問(wèn)題蟻群算法建模
        3.3.2 混合信息矩陣更新
        3.3.3 動(dòng)態(tài)構(gòu)建最短鄰接路徑
        3.3.4 多蟻群分布
        3.3.5 GPU局部性優(yōu)化
    3.4 實(shí)驗(yàn)及結(jié)果分析
        3.4.1 算法實(shí)驗(yàn)
        3.4.2 性能優(yōu)化實(shí)驗(yàn)
    3.5 本章小結(jié)
4 基于GPU的并行迭代式分割與合并優(yōu)化算法
    4.1 引言
    4.2 相關(guān)工作
        4.2.1 最小平方估計(jì)問(wèn)題
        4.2.2 解最小平方估計(jì)問(wèn)題
    4.3 算法描述
        4.3.1 迭代式分割與合并
        4.3.2 復(fù)雜度分析
        4.3.3 矩陣轉(zhuǎn)化
    4.4 實(shí)驗(yàn)及結(jié)果分析
        4.4.1 測(cè)試用例及平臺(tái)
        4.4.2 實(shí)驗(yàn)結(jié)果
    4.5 本章小結(jié)
5 結(jié)論與展望
    5.1 結(jié)論
    5.2 創(chuàng)新點(diǎn)摘要
    5.3 展望
參考文獻(xiàn)
攻讀博士學(xué)位期間科研項(xiàng)目及科研成果
致謝
作者簡(jiǎn)介

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 吳恩華;圖形處理器用于通用計(jì)算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)[J];軟件學(xué)報(bào);2004年10期

本文編號(hào)：2838348