并行計算課程算法實踐教學的新工具CUDA編程模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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