GPU編程模型中存儲(chǔ)體沖突的研究

原建偉，李愛國(guó)，李文宇

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

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

1 存儲(chǔ)體沖突分析

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

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

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

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

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

2 解決存儲(chǔ)體沖突的方法

2.1 一般性原則

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

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

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

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

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

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

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

2.2 實(shí)例分析

根據(jù)對(duì)本院學(xué)生訪問(wèn)在線學(xué)習(xí)系統(tǒng)的情況進(jìn)行數(shù)據(jù)挖掘，采用K均值（K-means）算法研究用戶訪問(wèn)行為，K均值算法是一種基于劃分的聚類算法，因?yàn)樗欣碚撋峡煽?、算法?jiǎn)單、速度快等優(yōu)點(diǎn)而被廣泛使用［6-9］。

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

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

這里采用平方誤差準(zhǔn)則，其定義為下式：

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

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

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

2）選擇任意k個(gè)對(duì)象作為初始聚類中心；

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

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

5）更新聚類均值，即計(jì)算每個(gè)（有變化）聚類的均值（中心對(duì)象）；

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

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

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

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

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

struct ClassicData｛

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

data＊attributes；

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

｝

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

表2 有無(wú)沖突的計(jì)算時(shí)間對(duì)比Tab.2 Comparison of computing time with or without Bank conflict

圖1 有無(wú)沖突計(jì)算時(shí)間曲線Fig.1 Computing time curve with or without Bank conflict

3 結(jié) 語(yǔ)

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

／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］.鄭州大學(xué)學(xué)報(bào)（理學(xué)版），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快速變換實(shí)現(xiàn)方法 ［J］.微電子學(xué)與計(jì)算機(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］姚 遠(yuǎn)，王 濤，張 丹，等.基于通用圖形處理器的Jacobi算法研究［J］.信息工程大學(xué)學(xué)報(bào)，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)濟(jì)發(fā)展研究中的應(yīng)用［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ò)評(píng)價(jià)中的應(yīng)用［J］.河北科技大學(xué)學(xué)報(bào)，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］張 娟，高克峰，張 曦.從文本中學(xué)習(xí)本體的系統(tǒng)設(shè)計(jì)［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ù)的教學(xué)測(cè)評(píng)［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ù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘［M］.北京：清華大學(xué)出版社，2005.AN Shuzhi.Data Warehouse and Data Mining［M］.Beijing：Tsinghua University Press，2005.