并行計(jì)算課程算法實(shí)踐教學(xué)的新工具CUDA編程模型

1、一一一文章編號(hào)：（）“并行計(jì)算課程算法實(shí)踐教學(xué)的新工具：編程模型王智廣，劉偉峰（中國(guó)石油大學(xué)（北隸）計(jì)算機(jī)科學(xué)與技術(shù)系，北京；中國(guó)石油化工股份有限公司石油勘探開(kāi)發(fā)研究院信息技術(shù)研究所，北京）摘要：本文首先從當(dāng)今多核微處理器的發(fā)展趨勢(shì)出發(fā)，介紹適用于多核微處理器的細(xì)粒度并行編程模型，以及其適用于“并行計(jì)算”課程教學(xué)的一系列優(yōu)勢(shì)，接著對(duì)當(dāng)前可用的幾種并行編程模型進(jìn)行分析和比較，最后給出采用編程模型的一個(gè)矩陣與矩陣相乘的教學(xué)實(shí)例。關(guān)鍵詞：并行計(jì)算；實(shí)踐教學(xué)；中圖分類(lèi)號(hào)：文獻(xiàn)標(biāo)識(shí)碼：引言年，教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)將“并行計(jì)算”課程定位在高等學(xué)校計(jì)算機(jī)專(zhuān)業(yè)高年級(jí)本科生或研究生以及面

2、向計(jì)算學(xué)科的非計(jì)算機(jī)專(zhuān)業(yè)的研究生層次上。“并行計(jì)算”課程一般主要包括以下四個(gè)層面：（）在算法理論層面主要講授可計(jì)算性與計(jì)算復(fù)雜性以及算法研究的數(shù)學(xué)基礎(chǔ)；（）在體系結(jié)構(gòu)層面主要講授并行計(jì)算機(jī)體系結(jié)構(gòu)；（）在算法設(shè)計(jì)層面主要講授計(jì)算機(jī)科學(xué)及其他科學(xué)計(jì)算領(lǐng)域中的非數(shù)值和數(shù)值并行算法；（）在算法實(shí)踐層面主要講授基于并行編程模型的并行算法編程。實(shí)際上，對(duì)于大多數(shù)學(xué)習(xí)“并行計(jì)算”課程的非并行計(jì)算研究方向的學(xué)生來(lái)講，第（）層面，即算法實(shí)踐是課程最具價(jià)值的組成部分。將并行算法實(shí)現(xiàn)成程序并投入大規(guī)?？茖W(xué)與工程計(jì)算生產(chǎn)應(yīng)用是課程的最主要學(xué)習(xí)目的之一。其中對(duì)于編程模型的選擇又是算法實(shí)踐教學(xué)的重要前提。以往“并行計(jì)算

3、”課程在算法實(shí)踐教學(xué)中大多采用作為編程模型，可的粗粒度特性不僅不足以滿(mǎn)足“并行計(jì)算”課程的實(shí)踐需要，還很難利用當(dāng)前多核微處理器的硬件細(xì)粒度優(yōu)勢(shì)。本文從當(dāng)今多核微處理器的發(fā)展趨勢(shì)出發(fā)，介紹適用于多核微處理器的編程模型，以及其適用于“并行計(jì)算”課程教學(xué)的一系列優(yōu)勢(shì)，并給出對(duì)幾種主流并行編程模型與的分析和比較，最后提供一個(gè)基于的矩陣與矩陣相乘程序作為教學(xué)實(shí)例。多核微處理器發(fā)展趨勢(shì)過(guò)去的年間，提高運(yùn)行頻率是性能提高的主要方式，然而，自年以來(lái)，這種趨勢(shì)發(fā)生了變化，不斷提高的頻率帶來(lái)了高功耗和高發(fā)熱量，使得主流頻率止步于，并向單芯片多處理器（，），即多核方向發(fā)展。年，和正式向主流消費(fèi)級(jí)市場(chǎng)推出了雙核心的產(chǎn)

4、品，年推出了核心的，按照各廠商的發(fā)展路線(xiàn)圖，今后大約每年單上的核心數(shù)將翻番。但由于市場(chǎng)變化和研制成本的原因，多核的每個(gè)核都基于以往的單核設(shè)計(jì)，保留了如亂序執(zhí)行等很多單核時(shí)代的復(fù)雜執(zhí)行方式，使得其對(duì)于科學(xué)計(jì)算等問(wèn)題的計(jì)算能力提高非常有限。此時(shí)，以游戲加速和圖形處理為初衷設(shè)計(jì)的（，圖形處理器）以超出摩爾定律的速度發(fā)展，并開(kāi)始在非圖形的高性能計(jì)算領(lǐng)域被大量使用。圖為近年來(lái)同等市場(chǎng)價(jià)格和的浮點(diǎn)運(yùn)算速度對(duì)比圖。作者簡(jiǎn)介：王智廣（），男，教授，高級(jí)會(huì)員，主要研究方向?yàn)榉植际接?jì)算和并行計(jì)算；劉偉峰（一），男，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)科學(xué)與技術(shù)系屆碩士，工程師，會(huì)員，主要研究方向?yàn)閳D形處理器架構(gòu)，高性能計(jì)算

5、可視化。萬(wàn)方數(shù)據(jù)”卜一而磊蕊墨圈隧蕊鑲鑭啪乏享啪“亂。一拋。羅廠：御?。豪谳铮阂?。圖和的理論峰值由圖可見(jiàn)，的浮點(diǎn)運(yùn)算速度可以達(dá)到的倍以上。帶來(lái)這種數(shù)據(jù)處理能力差別的主要原因在于最早為并行處理大量三維計(jì)算機(jī)圖形學(xué)中的頂點(diǎn)和像素?cái)?shù)據(jù)而設(shè)計(jì)，近年來(lái)為通用計(jì)算又進(jìn)行了一系列改進(jìn)。其天生并行的體系結(jié)構(gòu)決定了非常擅長(zhǎng)以并行的方式運(yùn)行高運(yùn)算強(qiáng)度的應(yīng)用。以為例，與體系結(jié)構(gòu)相比，體系結(jié)構(gòu)的優(yōu)勢(shì)主要有：（）單芯片上的更多處理器（核）與核心包含的個(gè)核心相比，目前最高僅達(dá)到核，雖然每個(gè)核的運(yùn)算能力高于上的單核，但后者憑借更多核的并行在計(jì)算能力上高出很多；（）將更多的晶體管用于計(jì)算單元運(yùn)算能力遠(yuǎn)高于的重要原因是將更多的

6、晶體管用于計(jì)算單元。目前將約的晶體管用于；而晶體管的以上是計(jì)算單元；（）超多活動(dòng)線(xiàn)程能夠保持個(gè)活動(dòng)線(xiàn)程的上下文，與此相比，通過(guò)線(xiàn)程池管理的線(xiàn)程不過(guò)數(shù)十個(gè)。超多活動(dòng)線(xiàn)程可以隱藏大量計(jì)算單元的訪(fǎng)存延遲，在處理數(shù)據(jù)敏感的應(yīng)用時(shí)要比的方式更加有效；（）高顯存帶寬與其顯示設(shè)備內(nèi)存間的帶寬超過(guò)與內(nèi)存的帶寬倍以上。配合超多活動(dòng)線(xiàn)程，使十分適合大規(guī)模并行處理高運(yùn)算強(qiáng)度的應(yīng)用。正是由于這些原因，在國(guó)際高性能計(jì)算研究領(lǐng)域，針對(duì)以為代表的硬件細(xì)粒度并行計(jì)算的研究是近年來(lái)的一個(gè)新的熱點(diǎn)。并誕生了大量基于的科學(xué)計(jì)算改進(jìn)算法，其領(lǐng)域涵蓋各類(lèi)數(shù)值模擬方法，包括計(jì)算天體物理、計(jì)算流體力學(xué)、計(jì)算量子化學(xué)，甚至計(jì)算金融學(xué)在內(nèi)的眾

7、多領(lǐng)域已經(jīng)從計(jì)算中獲益。萬(wàn)方數(shù)據(jù)由此可見(jiàn)，相對(duì)于多核而言，的高度并行體系結(jié)構(gòu)天然地適合進(jìn)行并行計(jì)算的研究和教學(xué)。而在年以前，的并行程序設(shè)計(jì)還主要是通過(guò)或這種圖形來(lái)完成，入門(mén)難度較高。所以在高性能計(jì)算的研究者們對(duì)于利用進(jìn)行并行計(jì)算的迫切需求下，編程模型誕生了。編程模型（，統(tǒng)一計(jì)算設(shè)備架構(gòu)）是年由推出的一套并行編程模型。其推出的最初目的是為解決通用計(jì)算的易用性問(wèn)題。至今已有眾多研究者利用的高度并行性特點(diǎn)將科學(xué)計(jì)算算法遷移至編程模型并在上獲得了相對(duì)于平均數(shù)十倍的性能提升。隨著編程模型被越來(lái)越多的研究者接受，的研究人員利用源源的解決方案設(shè)計(jì)了（），使程序也可以運(yùn)行在多核上，且運(yùn)行效率要高于多數(shù)原生的優(yōu)

8、化方法。使的應(yīng)用范圍基本覆蓋了包括和在內(nèi)的當(dāng)今主流多核微處理器?？梢哉f(shuō)，并行編程模型的出現(xiàn)和迅速發(fā)展標(biāo)志著細(xì)粒度并行程序設(shè)計(jì)已經(jīng)逐漸為主流程序設(shè)計(jì)人員所接受。編程模型有和顯式數(shù)據(jù)調(diào)用個(gè)主要特點(diǎn)。運(yùn)行方式與以往和的并行計(jì)算常用指令和數(shù)據(jù)流運(yùn)行方式相比，程序的運(yùn)行方式被稱(chēng)為（，單指令多線(xiàn)程），其意義是可以讓程序設(shè)計(jì)人員把編程的硬件對(duì)象作為若干個(gè)標(biāo)量處理器調(diào)用，即沒(méi)有固定的矢量寬度，并允許每一條線(xiàn)程占據(jù)各自路徑，在不受可編程性制約的前提下保證每個(gè)處理器核心一直處于完全被利用狀態(tài)。這樣在并行程序設(shè)計(jì)上就可以將精力專(zhuān)注于程序線(xiàn)程的拆分，達(dá)到提高并行化效果并且降低程序編寫(xiě)難度的目的。顯式數(shù)據(jù)調(diào)用的訪(fǎng)存指令

9、與語(yǔ)言相同，但增加了一項(xiàng)重要特性，即對(duì)共享內(nèi)存（）的顯式操作。共享內(nèi)存是芯片內(nèi)的一塊分為個(gè)的存儲(chǔ)器，主要作用是作為并發(fā)線(xiàn)程間的共享數(shù)據(jù)存放空間，另外也可以顯式地將其當(dāng)成使用，存放并發(fā)線(xiàn)程其需要多卜囊豳豳霹里里型塑型！一斕鑭鑭次存取的數(shù)據(jù)。當(dāng)每個(gè)線(xiàn)程訪(fǎng)問(wèn)不同的時(shí)候，共享內(nèi)存的存取延遲與寄存器的存取延遲一樣低，即數(shù)百倍地低于片外顯示內(nèi)存或主存的存取延遲，所以對(duì)共享內(nèi)存的有效顯式操作是提高并行程序運(yùn)行效率的關(guān)鍵。本文第節(jié)會(huì)給出一個(gè)使用共享內(nèi)存的教學(xué)實(shí)例?？傮w來(lái)講，編程模型中基于多核的細(xì)粒度并行方式和對(duì)存儲(chǔ)器的顯式操作是十分理想的課程教學(xué)工具，有助于學(xué)生設(shè)計(jì)既貼近硬件體系結(jié)構(gòu)又獨(dú)立于運(yùn)行平臺(tái)的并行程序

10、。雖然學(xué)生在算法實(shí)踐初期會(huì)覺(jué)得細(xì)粒度的并行程序設(shè)計(jì)較難接受，但就我們的教學(xué)經(jīng)驗(yàn)來(lái)看，具有計(jì)算機(jī)體系結(jié)構(gòu)和編程語(yǔ)言基礎(chǔ)的學(xué)生大約在周內(nèi)可以對(duì)的并行編程模型基本熟悉，況且在算法實(shí)踐中獲得數(shù)十倍性能提升帶來(lái)的成就感也會(huì)促使學(xué)生逐漸克服學(xué)習(xí)的困難。幾種弗行編程模型的分析和比較目前國(guó)內(nèi)外一般教材和課程教學(xué)選用的并行編程模型主要有種：消息傳遞接口、線(xiàn)程接口和基于指令的。這三種編程模型各有比較鮮明的特點(diǎn)。本節(jié)將它們和本文選用的編程模型一并進(jìn)行分析和比較。（，可移植操作系統(tǒng)接口）線(xiàn)程接口也稱(chēng)，年被通過(guò)成為被絕大多數(shù)廠商支持的線(xiàn)程。它提供了處理諸如死鎖和競(jìng)態(tài)條件這類(lèi)問(wèn)題的工具，但沒(méi)有限定線(xiàn)程的具體工作方式，對(duì)于

11、如何編制線(xiàn)程并行的程序留有很大的余地?；诖?，被認(rèn)為過(guò)于底層和編程難度較高，所以目前多數(shù)“并行計(jì)算”課程不將作為主要的算法實(shí)踐工具。作為共享存儲(chǔ)標(biāo)準(zhǔn)而在年問(wèn)世的是為在多處理機(jī)上編寫(xiě)可移植的多線(xiàn)程應(yīng)用程序而設(shè)計(jì)的一個(gè)應(yīng)用編程接口。編程模型包括一套平臺(tái)無(wú)關(guān)的編譯指導(dǎo)（）、編譯命令（）和一個(gè)用來(lái)支持它們的函數(shù)庫(kù)。顯示地指導(dǎo)編譯器如何利用應(yīng)用程序的并行性，而開(kāi)發(fā)人員不需要關(guān)心實(shí)現(xiàn)細(xì)節(jié)，這使得的學(xué)習(xí)入門(mén)難度相對(duì)較低，但同時(shí)也很難完成并萬(wàn)方數(shù)據(jù)行算法的課程教學(xué)要求，所以一般也不將作為主要的算法實(shí)踐工具。年由政府、學(xué)術(shù)界、產(chǎn)業(yè)界共同制定的（，消息傳遞接口）是根據(jù)并行應(yīng)用程序?qū)τ谙鬟f的需求而定義的一組標(biāo)準(zhǔn)

12、接口說(shuō)明和不同廠商提供的相應(yīng)方法實(shí)現(xiàn)。吸收了等眾多消息傳遞模型的優(yōu)點(diǎn)，在集群型高性能計(jì)算機(jī)的流行化趨勢(shì)下成為了目前最流行的并行編程模型。雖說(shuō)的學(xué)習(xí)曲線(xiàn)較長(zhǎng)，但大多數(shù)“并行計(jì)算”教科書(shū)還是主要使用作為并行算法教學(xué)實(shí)踐的工具。種并行編程模型比較表是種并行編程模型主要特性比較表。表種并行編程模型主要特性比較表釁特征低級(jí)原語(yǔ)共享存儲(chǔ)消息傳遞單指令多線(xiàn)程并行粒度細(xì)粒度細(xì)粒度粗粒度細(xì)粒度存儲(chǔ)模式共享存儲(chǔ)共享存儲(chǔ)分布存儲(chǔ)共享存儲(chǔ)數(shù)據(jù)調(diào)用方式顯式隱式顯式顯式學(xué)習(xí)難度難容易較難一般可擴(kuò)展性較好較差好較好矩陣與矩陣相乘并行算法教學(xué)實(shí)例矩陣與矩陣相乘并行算法是最常用也最具代表性的并行算法之一，十分適合作為學(xué)生對(duì)并行

13、算法實(shí)踐的入門(mén)教學(xué)。本節(jié)描述一個(gè)基于編程模型和塊矩陣算法的矩陣與矩陣相乘并行算法教學(xué)實(shí)例。串行算法對(duì)于兩個(gè)胛×稠密矩陣與相乘得到乘積矩陣×的算法，易寫(xiě)出其串行實(shí)現(xiàn)的偽代碼如下：（，）：一：一，：一，：，×，；工¨努弋而蕊蕊暖圈酲峨塊算法針對(duì)粗粒度的并行機(jī)制，一般采用基于塊矩陣運(yùn)算矩：；：？；？；斕碉鑭陣與矩陣相乘算法，即將整個(gè)矩陣分成矩陣塊大小為（喲）（的塊矩陣，把原矩陣的代數(shù)運(yùn)算轉(zhuǎn)換成對(duì)這些塊矩陣中元素的代數(shù)運(yùn)算，進(jìn)而通過(guò)消息傳遞實(shí)現(xiàn)粗粒度的并行。塊算法的偽代碼如下：一？：鼠，×，；（，）；，。；：一，：一其；語(yǔ)句表示在開(kāi)始下一步操作之前：對(duì)

14、線(xiàn)程塊內(nèi)的線(xiàn)程進(jìn)行同步。和是二維線(xiàn)程塊中線(xiàn)程的編號(hào)，通過(guò)它們也容易理解編程模型的單指令多線(xiàn)程的工作方式。同時(shí)可以算出，為計(jì)算每個(gè)塊，若不使用共享內(nèi)存，。，；塊算法的并行實(shí)現(xiàn)的細(xì)粒度并行機(jī)制要求從每個(gè)線(xiàn)程的角度考慮整個(gè)矩陣相乘，同時(shí)的三級(jí)線(xiàn)程管理結(jié)構(gòu)也要求對(duì)線(xiàn)程進(jìn)行適當(dāng)?shù)膲K劃分，本實(shí)例中對(duì)線(xiàn)程塊的劃分可以與塊矩陣運(yùn)算思想直接對(duì)應(yīng)起來(lái)。首先，根據(jù)需要?jiǎng)澐謨蓚€(gè)胛×聹稠密矩陣彳與為口需要訪(fǎng)問(wèn)存放塊矩陣，和取，的全局內(nèi)存（響）次，反之僅需訪(fǎng)存（，吻）次。通過(guò)以這種方式分塊計(jì)算，可以有效利用快速的共享內(nèi)存，進(jìn)而節(jié)省許多全局內(nèi)存帶寬。由于篇幅所限，本實(shí)例僅包括塊矩陣相乘的代碼主體部分，對(duì)代碼的調(diào)用

15、方式等其他內(nèi)容請(qǐng)參考編程指南。塊大小為（毗）×（確）的塊矩陣，根據(jù)的體系結(jié)構(gòu)，結(jié)束語(yǔ)本文在介紹多核微處理器發(fā)展趨勢(shì)和編程模型的基礎(chǔ)上，對(duì)和以往其他種并行編程模型進(jìn)行了比較，最后給出了一個(gè)矩陣與矩陣相乘的教學(xué)實(shí)例對(duì)編程模型進(jìn)行進(jìn)一步詳述。能夠看出，作為近兩年新出現(xiàn)的并行編程模型可以很好地利用新一代及芯片上數(shù)量眾多的核進(jìn)行細(xì)粒度并行計(jì)算，再結(jié)合相對(duì)易于學(xué)習(xí)掌握的特點(diǎn)，可以得出結(jié)論，編程模型可以與粗粒度的互為補(bǔ)充，為學(xué)生帶來(lái)更豐富的算法實(shí)踐經(jīng)驗(yàn)，并且完全可以作為“并行計(jì)算”課程算法實(shí)踐教學(xué)的工具使用。圈取以便每線(xiàn)程塊的線(xiàn)程數(shù)是（上個(gè)線(xiàn)程組成的線(xiàn)程簇）大小的倍數(shù)，且低于每線(xiàn)程塊的最大線(xiàn)程數(shù)。然后，計(jì)算的每個(gè)塊，其執(zhí)行過(guò)程是：（）使用每線(xiàn)程加載塊矩陣抽和圾，的一個(gè)元素，將爿城和瞰，從全局內(nèi)存加載到共享內(nèi)存；（）每個(gè)線(xiàn)程計(jì)算結(jié)果塊矩陣的一個(gè)元素，其中