GPU編程模型中存儲體沖突的研究

原建偉，李愛國，李文宇

（陜西工業(yè)職業(yè)技術(shù)學院信息工程學院，陜西咸陽 712000）

隨著計算機技術(shù)的不斷發(fā)展，新技術(shù)層出不窮，不斷提高應用水平，近年來隨著GPU技術(shù)的不斷發(fā)展，其強大的浮點運算能力及并行運算處理能力協(xié)助CPU運算，甚至在某些領(lǐng)域成為了CPU有力的競爭對手［1］。GPU強大的并行計算能力被充分運用在很多領(lǐng)域，在信息處理領(lǐng)域里，文獻［2］中使用GPU實現(xiàn)了數(shù)據(jù)挖掘算法，文獻［3］在GPU上加速了DCT快速變換。越來越多的算法和應用在GPU上實現(xiàn)，編程模型也越來越成熟，但在基于GPU的編程模型中，影響并行效率的因素也很多，處理不好，不僅不能充分發(fā)揮GPU的并行能力，甚至會降低運算速度。這些因素中存儲體沖突（bank conflict）執(zhí)行效率的影響較大，本文針對存儲體沖突進行研究與探討，并提出解決方法。

1 存儲體沖突分析

在GPU結(jié)構(gòu)中，Bank是指共享內(nèi)存按照固定大小（通常為4Byte）劃分為若干存儲模塊。GPU進行并行運算過程中，線程對Bank的訪問通常以half-warp為組同時進行，無需以對齊的方式訪問，但要求線程與Bank一一對應。如果同時有多個線程對同一個Bank進行操作，就產(chǎn)生了訪問沖突，訪問時間將根據(jù)沖突的線程數(shù)量成倍增加。

由于共享存儲器位于芯片上，因而共享存儲器空間比本地和全局存儲器空間的速度都要快得多。實際上，對于Warp塊中的所有線程來說，只要線程間不存在存儲體沖突，訪問共享存儲器的速度與訪問寄存器一樣快。為了獲得較高的存儲器帶寬，共享存儲器被劃分為多個大小相等的存儲器模塊（Bank），這些存儲體可同步訪問。因此，對落入n個不同存儲體的n個地址的任何存儲器讀取或?qū)懭胝埱蠖伎赏綄崿F(xiàn)，得到更有效的帶寬，可達到單獨一個模塊的帶寬的n倍，但若一個存儲器請求的2個地址落入同一個存儲體內(nèi)，就會出現(xiàn)存儲體沖突［4］。

共享內(nèi)存沖突產(chǎn)生的根本原因來源于計算機本身的設(shè)計問題。引起存儲體沖突的誘因是并發(fā)存儲器訪問。內(nèi)存在工作的時候一次只能設(shè)置一個存取地址，因此其存取形式為串行，而GPU是多核結(jié)構(gòu)，其核心數(shù)量較多執(zhí)行線程數(shù)量更多，為了與GPU的眾多線程匹配，需要更大帶寬的共享內(nèi)存來提高效率。對于這樣的需求，可以通過多端口存儲器來加速訪問速度，但是對于作為共享內(nèi)存的Cache或者DRAM都只有一個端口，原因是制造多端口存儲器的成本非常高，為了實現(xiàn)這樣的模型，實際上采用將多個相同的單獨存儲器合并成內(nèi)存組即一個Bank，這樣就形成了相當于多端口的存儲，但在一個Bank內(nèi)依然采用順序存儲。

在CUDA的編程模型中，多處理器SIMT單元以32個并行線程為一組來創(chuàng)建、管理、調(diào)度和執(zhí)行線程，這樣的線程組稱為 Warp塊［4］。一個 Warp塊要去同時讀寫不同地址上的數(shù)據(jù)時，硬件不允許每個地址都設(shè)置一個存取端口，只能在一個跨距（以16個4Byte為單位）內(nèi)為每個地址設(shè)置不同的端口，即每一個地址都有自己獨立的讀寫端口，這就導致每過16個4Byte的跨距就會產(chǎn)生一次與當前地址發(fā)生讀寫沖突，訪問時間將根據(jù)沖突的線程數(shù)量成倍增加。

基于CUDA模型的GPU會在必要的時候自行解決沖突，采取的方法是將存在存儲體沖突的存儲器請求分割為多個不沖突的請求，此時有效帶寬將降低為原帶寬除以分離后的存儲器請求的數(shù)量。

2 解決存儲體沖突的方法

2.1 一般性原則

在CUDA中，為了盡可能提高計算性能，應該盡量最小化存儲體沖突。可以通過以下方式在程序設(shè)計過程中做相應處理以減少存儲體沖突的產(chǎn)生。根據(jù)存儲體的組織方式，將Warp塊的共享存儲器請求分割為上下兩部分，屬于Warp塊第1部分的線程和屬于Warp塊第2部分的線程之間不可能出現(xiàn)存儲體沖突。

一種常見的情況是各線程訪問數(shù)組中的32位字，使用線程ID tid進行索引，步幅為s：

只要s＊n是存儲體m數(shù)量的倍數(shù)，或者說只要n是m／d的倍數(shù)（其中d是m和s的最大公約數(shù)），線程tid和（tid＋n）訪問的就是同一個存儲體。因而，只有在 Warp塊的一半大小小于等于m／d時，才不會存在存儲體沖突。對于計算能力是1.x的設(shè)備，可以說只有在d等于1時，或者說只有在s是奇數(shù)時，才不會存在存儲體沖突［4］。

另一種情況就是，當一個half-warp的所有16個線程同時訪問同一個Bank的32bit數(shù)據(jù)時，該Bank以廣播的方式將數(shù)據(jù)發(fā)送給所有線程，因此不會產(chǎn)生訪問沖突。

矩陣運算由于其計算量巨大、耗時長，往往通過并行算法提高執(zhí)行效率。同樣在基于圖形處理器的并行運算環(huán)境中矩陣的運算也常常出現(xiàn)。通常情況下，矩陣元素可以存儲在Bank里，第i個數(shù)據(jù)存儲在第16個Bank中，即劃分子矩陣時每個Block處理矩陣的寬度為16的整數(shù)倍。如果線程訪問Bank是對齊的就不會有沖突。

在CUDA中一個Block中線程數(shù)量的最大值為512，如果矩陣規(guī)模小于512時，矩陣按行劃分，并將塊對應的數(shù)據(jù)映射到處理單元上，當矩陣規(guī)模大于512時，可以將矩陣分成二維塊，每個塊的大小為16×16，二維塊的線程數(shù)為256，為了減少計算過程中對全局存儲器的訪問，將計算過程中經(jīng)常使用的x（k），x（k＋1）存儲在共享存儲器內(nèi)［5］。

由于不同數(shù)據(jù)類型的數(shù)據(jù)占用存儲單元的差別，設(shè)計不合理時也會帶來存儲體沖突。當使用Char型數(shù)據(jù)時，由于其每個數(shù)據(jù)長度是8bit，因此每個Bank中就包含了4個數(shù)據(jù)。線程在順序訪問內(nèi)存時就會出現(xiàn)4個線程訪問同一個Bank的情況，即產(chǎn)生了4路訪問沖突［5］。對于結(jié)構(gòu)體賦值將在必要時編譯為針對結(jié)構(gòu)體中各成員的多個存儲器請求，因此結(jié)構(gòu)體內(nèi)部成員的這種并行存儲請求也會導致存儲體沖突。

2.2 實例分析

根據(jù)對本院學生訪問在線學習系統(tǒng)的情況進行數(shù)據(jù)挖掘，采用K均值（K-means）算法研究用戶訪問行為，K均值算法是一種基于劃分的聚類算法，因為它有理論上可靠、算法簡單、速度快等優(yōu)點而被廣泛使用［6-9］。

聚類算法處理的數(shù)據(jù)量都很大，且大量的計算都是在同一數(shù)據(jù)結(jié)構(gòu)上的不同部分進行操作，數(shù)據(jù)在處理期間是分布式存放，因此很適合采用數(shù)據(jù)并行方法編程。

K均值算法在處理大數(shù)據(jù)集時相對可伸縮且效率高，該算法的復雜度是O（nkt），其中n是所有對象的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。通常情況下k?n，且t?n。當n非常大的時候，K均值算法時間主要耗費在距離計算過程中，且距離計算完全可以分成相同的塊同時進行計算，可以根據(jù)GPU中流處理器的數(shù)量將n個數(shù)據(jù)分成一定的份數(shù)分別進行計算，然后根據(jù)每一個流處理器計算出各自子數(shù)據(jù)集中數(shù)據(jù)與k個類的中心距離從而得到局部聚類結(jié)果，然后再匯總得到全局聚類結(jié)果［3］。

這里采用平方誤差準則，其定義為下式：

式中：E是數(shù)據(jù)中所有對象的平方誤差的總和；p是空間中的點，表示給定的數(shù)據(jù)對象；m是簇Ci的平均值［10］。

算法實現(xiàn)如下：

1）先將數(shù)據(jù)分成若干塊存入共享內(nèi)存；

2）選擇任意k個對象作為初始聚類中心；

3）分別在GPU的運算單元中，根據(jù)每個聚類中所有對象的均值（中心對象）計算樣本集中每個對象與這些中心對象的歐幾里德距離；

4）將各個計算單元中的數(shù)據(jù)進行匯總，并根據(jù)最小距離重新對相應對象進行劃分；

5）更新聚類均值，即計算每個（有變化）聚類的均值（中心對象）；

6）重復步驟3）到步驟5）直到每個聚類不再發(fā)生變化為止。

很多K均值算法中的數(shù)據(jù)結(jié)構(gòu)都是采用數(shù)組來存儲分類元素，但聚類算法的特殊性決定了每一次計算之前都不能確定每一分類的元素數(shù)目，為了避免這個問題，往往采用比較大的數(shù)組進行存儲，但是GPU的存儲容量有限，為了提高效率，可以采用結(jié)構(gòu)體并設(shè)置一個域來區(qū)分元素屬于哪一個分類。但由于結(jié)構(gòu)體成員定義的差異會出現(xiàn)不同的存儲體沖突。

如果結(jié)構(gòu)體內(nèi)部成員使用奇數(shù)個32位字作為步幅訪問存儲器就不會出現(xiàn)存儲體沖突，相反采用偶數(shù)個32位字作為步幅訪問存儲器就會產(chǎn)生存儲體沖突，不同類型沖突情況見表1。

表1 不同類型沖突情況Tab.1 Bank conflict because of different type of data

本例中使用以下的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)分類元素的存儲，用于避免存儲體沖突的發(fā)生。

struct ClassicData｛

unsigned int num；／／定義數(shù)據(jù)大小

data＊attributes；

unsigned int＊belongTo；／／確定數(shù)據(jù)屬于哪一個聚類

｝

本文的實驗平臺為NVIDIA 8800GT GPU，內(nèi)建24個流處理器，INTEL E8400 3.0GHz CPU，數(shù)據(jù)來源為校園網(wǎng)中學生對在線學習系統(tǒng)訪問情況的相關(guān)日志，根據(jù)學生訪問該系統(tǒng)不同內(nèi)容頁面，分析學生在線學習的行為特征。原始數(shù)據(jù)在經(jīng)過數(shù)據(jù)清洗、用戶識別等步驟之后，得到5 327個用戶對《計算機應用基礎(chǔ)》課程在線教學網(wǎng)站的訪問數(shù)據(jù)（訪問時間，閱讀時長等）。對上述數(shù)據(jù)進行聚類分析研究學生對該網(wǎng)站不同內(nèi)容的頁面訪問的行為特征。表2顯示了有存儲體沖突與沒有存儲體沖突的兩種情況下不同用戶量訪問數(shù)據(jù)進行聚類分析的用時，有沖突情況下計算時間約是無沖突情況下的56～190倍，并且隨著數(shù)據(jù)量的增大，存儲沖突帶來的低效率也就越明顯，有無沖突計算時間曲線見圖1。

表2 有無沖突的計算時間對比Tab.2 Comparison of computing time with or without Bank conflict

圖1 有無沖突計算時間曲線Fig.1 Computing time curve with or without Bank conflict

3 結(jié) 語

通過研究可見，CUDA編程模型中存儲體沖突的根本原因在于目前計算機體系中并發(fā)存儲器訪問的機制，因此在不能改變硬件的情況下，通過算法改良解決存儲體沖突是行之有效的方法，通過多種手段對算法進行優(yōu)化，可防止存儲體沖突的產(chǎn)生，進一步提高GPU并行運算的效率。

／References：

［1］KENNETH M，EDWARD A.The FFT on a GPU［A］.Proceedings of the ACM Siggraph／Eurographics Conference on Graphics Hardware［C］.San Diego：［s.n.］，2003.112-119.

［2］劉 琳，何劍鋒，王紅玲.GPU加速數(shù)據(jù)挖掘算法的研究［J］.鄭州大學學報（理學版），2010，42（2）：31-34.LIU Lin，HE Jianfeng，WANG Hongling.Study of the data mining algorithm with GPU acceleration［J］.Journal of Zhengzhou University（Natural Science Edition），2010，42 （2）：31-34.

［3］阮 軍，韓定定.基于CUDA的DCT快速變換實現(xiàn)方法 ［J］.微電子學與計算機，2009，26（8）：201-205.RUAN Jun，HAN Dingding.An efficient implementation of fast DCT using CUDA［J］.Microelectronics &Computer，2009，26（8）：201-205.

［4］NVIDIA.Corporation CUDA2.0編程指南［EB／OL］.http：／／down.csdn.net／detail／gaopengpian／2788197，2010-10-27.NVIDIA.Corporation CUDA2.0programming guide［EB／OL］.http：／／down.csdn.net／ detail／gaopengpian／2788197，2010-10-27.

［5］姚 遠，王 濤，張 丹，等.基于通用圖形處理器的Jacobi算法研究［J］.信息工程大學學報，2010，11（3）：336-338.YAO Yuan，WANG Tao，ZHANG Dan，et al.Research on Jacobi algorithm based on general purpose graphical processing unit［J］.Journal of Information Engineering University，2010，11（3）：336-338.

［6］孟海東，李秉秋.聚類分析在縣域經(jīng)濟發(fā)展研究中的應用［J］.河北工業(yè)科技，2012，29（2）：116-119.MENG Haidong，LI Bingqiu.Application of cluster analysis in regional economy research［J］.Hebei Journal of Industrial Science and Technology，2012，29（2）：116-119.

［7］李冬梅，陳軍霞.聚類分析法在公交網(wǎng)絡(luò)評價中的應用［J］.河北科技大學學報，2012，33（3）：279-282.LI Dongmei，CHEN Junxia.Application of cluster analysis in evaluation of public traffic network［J］.Journal of Hebei University of Science and Technology，2012，33（3）：279-282.

［8］張 娟，高克峰，張 曦.從文本中學習本體的系統(tǒng)設(shè)計［J］.河北工業(yè)科技，2011，28（3）：160-163.ZHANG Juan，GAO Kefeng，ZHANG Xi.Design of system of learning ontology from texts［J］.Hebei Journal of Industrial Science and Technology，2011，28（3）：160-163.

［9］葉若芬，孫書明.基于數(shù)據(jù)挖掘技術(shù)的教學測評［J］.河北工業(yè)科技，2011，28（6）：383-385.YE Ruofen，SUN Shuming.Teaching evaluation based on data mining technology［J］.Hebei Journal of Industrial Science and Technology，2011，28（6）：383-385.

［10］安淑芝.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘［M］.北京：清華大學出版社，2005.AN Shuzhi.Data Warehouse and Data Mining［M］.Beijing：Tsinghua University Press，2005.