本文關(guān)鍵詞：分支密集應(yīng)用在GPU上的優(yōu)化方法研究

  更多相關(guān)文章： CUDA Control Divergence 基于線程交換優(yōu)化 延遲隱藏

【摘要】：現(xiàn)如今,以CPU+GPU為主的異構(gòu)模式被廣泛的使用,06年CUDA編程架構(gòu)的推出大大提高了GPU的可編程性,各領(lǐng)域內(nèi)使用CUDA進(jìn)行加速的應(yīng)用程序大量出現(xiàn)。CUDA的架構(gòu)中引入了STMD的概念。STMD中在提高硬件資源利用效率的同時(shí)也引入了一些問(wèn)題。STMD架構(gòu)中引入了Warp的概念,Warp是GPU創(chuàng)建,管理,執(zhí)行的最小單元,Warp有在一個(gè)周期內(nèi)其中所有線程必須執(zhí)行同一條指令的特性,因此在遇到分支等情況時(shí)會(huì)產(chǎn)生Control Divergence,嚴(yán)重影響程序的執(zhí)行效率。本文重點(diǎn)研究方向是如何最大程度上降低分支密集型應(yīng)用在執(zhí)行過(guò)程中產(chǎn)生的Control Divergence以提高程序性能。為了解決這個(gè)問(wèn)題,本文提出了一種基于線程交換的軟件優(yōu)化算法,可以在真實(shí)機(jī)器平臺(tái)上應(yīng)用于分支密集型應(yīng)用程序,并能夠有效的降低此類(lèi)程序中大量存在的Control Divergence,從而提高程序性能,縮短程序運(yùn)行時(shí)間。本文所做的工作以及成果有:1)深入分析了多個(gè)分支密集應(yīng)用產(chǎn)生Control Divergence的具體原理,并對(duì)程序按如下標(biāo)準(zhǔn)進(jìn)行分類(lèi)。(1)易獲得分支特性(Easy-Handled,EH)與不易獲得分支特性(Hard-Handled,HH),(2)線程編號(hào)相關(guān)(Thread-Index Dependent,TID)與線程數(shù)據(jù)相關(guān)(Thread-Data Dependent,TDD)。通過(guò)這種分類(lèi)將CUDA程序分為四類(lèi),可便于針對(duì)每一類(lèi)進(jìn)行不同的優(yōu)化。2)提出并設(shè)計(jì)一種基于線程交換的優(yōu)化算法框架,并進(jìn)一步細(xì)化,將其分成直接構(gòu)造映射表優(yōu)化算法(DIMA,Direct Index-Map Algorithm)以及預(yù)處理構(gòu)造映射表算法(PIMA,Pre-process Index-Map Algorithm)。實(shí)驗(yàn)結(jié)果表明,優(yōu)化之后程序的Control Divergence基本降至無(wú),使用線程交換優(yōu)化算法優(yōu)化之后相對(duì)與優(yōu)化之前運(yùn)行時(shí)間降低明顯。優(yōu)化之后Kernel的加速比平均有1.5左右,而總體運(yùn)行時(shí)間的加速比平均有1.2左右。3)DIMA與PIMA算法中參數(shù)的控制可能會(huì)對(duì)優(yōu)化結(jié)果產(chǎn)生影響。其中對(duì)于TID類(lèi)型的程序線程交換范圍會(huì)有影響,對(duì)于適用于PIMA算法的程序中,預(yù)處理的次數(shù)也是需要考慮的因素,因此對(duì)算法執(zhí)行過(guò)程中參數(shù)的控制進(jìn)行測(cè)試研究并得出結(jié)論。測(cè)試發(fā)現(xiàn),對(duì)于不同的程序,由于要進(jìn)行控制Control Divergence與控制不規(guī)則訪存之間的權(quán)衡,線程交換范圍的最優(yōu)解不同。同樣的,對(duì)于使用PIMA的程序,最優(yōu)的預(yù)處理次數(shù)也不同。4)通過(guò)分析算法執(zhí)行過(guò)程中的開(kāi)銷(xiāo)的產(chǎn)生情況并提出基于流水的延遲隱藏算法,這種算法利用CUDA中提供的異步數(shù)據(jù)傳輸函數(shù)Cuda Mem Cpy Asyc使得數(shù)據(jù)傳輸與Kernel執(zhí)行重疊,通過(guò)合理的控制傳輸數(shù)據(jù)的范圍以及執(zhí)行Kernel的時(shí)間使之盡可能相同,那么就可以在一定程度上隱藏傳輸開(kāi)銷(xiāo),提高程序性能。實(shí)驗(yàn)結(jié)果表明,相對(duì)于未優(yōu)化之前,加速比平均有1.1。
【關(guān)鍵詞】：CUDA Control Divergence 基于線程交換優(yōu)化 延遲隱藏
【學(xué)位授予單位】：國(guó)防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類(lèi)號(hào)】：TP391.41;TP332
【目錄】：

• 摘要9-11
• ABSTRACT11-13
• 第一章 緒論13-26
• 1.1 研究背景與意義13-18
• 1.1.1 GPU的結(jié)構(gòu)與發(fā)展13-18
• 1.2 CUDA編程模型18-24
• 1.2.1 編程橋梁?jiǎn)栴}18-19
• 1.2.2 CUDA編程架構(gòu)19-20
• 1.2.3 CUDA執(zhí)行模型20
• 1.2.4 控制流問(wèn)題的產(chǎn)生與影響20-24
• 1.3 本文目標(biāo)與主要工作24-25
• 1.3.1 課題目標(biāo)24
• 1.3.2 課題主要工作24-25
• 1.3.3 課題來(lái)源25
• 1.4 本文結(jié)構(gòu)安排25-26
• 第二章 CUDA及控制流優(yōu)化研究現(xiàn)狀26-34
• 2.1 CUDA的研究現(xiàn)狀26-27
• 2.2 控制流的優(yōu)化研究現(xiàn)狀27-33
• 2.2.1 硬件優(yōu)化方法27-30
• 2.2.2 軟件優(yōu)化方法30-33
• 2.3 本章小結(jié)33-34
• 第三章 線程交換優(yōu)化34-51
• 3.1 線程交換的基本思想34-37
• 3.1.1 CUDA Kernel的抽象表示34-36
• 3.1.2 線程交換的概念36-37
• 3.2 線程交換方法37-39
• 3.2.1 Control Divergence分類(lèi)37
• 3.2.2 交換映射表37-39
• 3.3 映射表的直接構(gòu)造39-45
• 3.3.1 DIMA基本框架39-42
• 3.3.2 DIMA正確性證明42-45
• 3.4 映射表的預(yù)處理構(gòu)造45-47
• 3.4.1 PIMA基本框架45-46
• 3.4.2 交換數(shù)據(jù)方法46-47
• 3.5 設(shè)計(jì)參數(shù)優(yōu)化探究47-49
• 3.5.1 預(yù)處理構(gòu)造映射表法的參數(shù)選擇47-49
• 3.5.2 非TDD的參數(shù)選擇49
• 3.6 本章小結(jié)49-51
• 第四章 延遲隱藏優(yōu)化51-57
• 4.1 延遲隱藏技術(shù)概述51-53
• 4.2 數(shù)據(jù)交換的延遲隱藏53-56
• 4.2.1 延遲隱藏流水線的設(shè)計(jì)54-56
• 4.3 本章小結(jié)56-57
• 第五章 性能評(píng)價(jià)57-84
• 5.1 實(shí)驗(yàn)環(huán)境57-60
• 5.2 算法性能測(cè)試60-79
• 5.2.1 使用DIMA算法進(jìn)行優(yōu)化的程序60-70
• 5.2.2 使用PIMA算法進(jìn)行優(yōu)化的程序70-79
• 5.3 延遲隱藏性能評(píng)價(jià)79-83
• 5.3.1 Bitonic sort的優(yōu)化79-80
• 5.3.2 Reduction的優(yōu)化80-81
• 5.3.3 Needle-Wunch的優(yōu)化81-82
• 5.3.4 Marching cubes的優(yōu)化82-83
• 5.3.5 Hotspots的優(yōu)化83
• 5.4 本章小結(jié)83-84
• 第六章 結(jié)束語(yǔ)84-86
• 6.1 全文總結(jié)84-85
• 6.2 研究展望85-86
• 致謝86-88
• 參考文獻(xiàn)88-92
• 作者在學(xué)期間取得的學(xué)術(shù)成果92

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 ;An Object-Oriented Multi-Thread Dialog Model[J];The Journal of China Universities of Posts and Telecommunications;1998年01期

2 陳希超;王健;;基于RT-Thread的嵌入式網(wǎng)絡(luò)通信系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J];電聲技術(shù);2012年12期

3 成淑萍;;C#實(shí)現(xiàn)簡(jiǎn)易WEB服務(wù)器[J];中國(guó)西部科技;2009年01期

4 管莉;鄒汝平;朱斌;郝重陽(yáng);;An HLA/RTI Architecture Based on Multi-thread Processing[J];Journal of China Ordnance;2010年03期

5 閆澤華;李芳;;Thread Labeling for News Event[J];Journal of Shanghai Jiaotong University(Science);2013年04期

6 郭宇;蔣信予;陳意云;;Certification of Thread Context Switching[J];Journal of Computer Science & Technology;2010年04期

7 朱志國(guó);;RT-Thread操作系統(tǒng)在STM32中移植的研究[J];計(jì)算機(jī)光盤(pán)軟件與應(yīng)用;2012年22期

8 涂撰;趙標(biāo);;RT-Thread在LPC2378上的移植與應(yīng)用[J];上海船舶運(yùn)輸科學(xué)研究所學(xué)報(bào);2013年01期

9 shxf;;今日話題[J];飛碟探索;2010年09期

10 吳宇翔;李鑫;劉清;;基于RT-Thread和STM32的數(shù)碼相框的設(shè)計(jì)[J];電子世界;2013年18期

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前2條

1 本報(bào)記者 張哲;網(wǎng)絡(luò)互動(dòng)工具助MBA課程實(shí)踐、學(xué)術(shù)雙向發(fā)展[N];中國(guó)社會(huì)科學(xué)報(bào);2012年

2 上海大學(xué) 孫淵磊;PB中消息對(duì)話框的居中顯示[N];計(jì)算機(jī)世界;2001年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 王振運(yùn);基于RT-Thread和STM32的雙輪自平衡機(jī)器人的設(shè)計(jì)與實(shí)現(xiàn)[D];中北大學(xué);2016年

2 馮曙光;基于Real-Time Maude的AADL Thread構(gòu)件的形式化建模與驗(yàn)證[D];華東師范大學(xué);2016年

3 錢(qián)程;分支密集應(yīng)用在GPU上的優(yōu)化方法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2014年

4 郭聚建;基于RT-Thread的智能開(kāi)關(guān)設(shè)計(jì)[D];西安電子科技大學(xué);2014年

5 葉思超;基于RT-Thread的手持式高性能RFID讀寫(xiě)器設(shè)計(jì)[D];電子科技大學(xué);2015年

6 蔡曙光;基于RT-Thread的便攜式健康監(jiān)測(cè)儀的設(shè)計(jì)與實(shí)現(xiàn)[D];安徽大學(xué);2015年

7 曹成;嵌入式實(shí)時(shí)操作系統(tǒng)RT-Thread原理分析與應(yīng)用[D];山東科技大學(xué);2011年

8 邱yN;嵌入式實(shí)時(shí)操作系統(tǒng)RT-Thread的設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2007年

9 涂撰;基于RT-Thread的嵌入式CAN-Ethernet網(wǎng)關(guān)設(shè)計(jì)與實(shí)現(xiàn)[D];上海交通大學(xué);2014年

10 司夢(mèng)如;基于RT-Thread的NANDFLASH文件系統(tǒng)中間層的設(shè)計(jì)與實(shí)現(xiàn)[D];安徽大學(xué);2012年

，

本文編號(hào)：928937