原建偉，李愛國，李文宇

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

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

1 存儲體沖突分析

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

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

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

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

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

2 解決存儲體沖突的方法

2.1 一般性原則

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

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

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

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

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

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

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

2.2 實例分析

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

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

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

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

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

算法實現如下：

1）先將數據分成若干塊存入共享內存；

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

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

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

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

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

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

如果結構體內部成員使用奇數個32位字作為步幅訪問存儲器就不會出現存儲體沖突，相反采用偶數個32位字作為步幅訪問存儲器就會產生存儲體沖突，不同類型沖突情況見表1。

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

本例中使用以下的數據結構實現分類元素的存儲，用于避免存儲體沖突的發(fā)生。

struct ClassicData｛

unsigned int num；／／定義數據大小

data＊attributes；

unsigned int＊belongTo；／／確定數據屬于哪一個聚類

｝

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

通過研究可見，CUDA編程模型中存儲體沖突的根本原因在于目前計算機體系中并發(fā)存儲器訪問的機制，因此在不能改變硬件的情況下，通過算法改良解決存儲體沖突是行之有效的方法，通過多種手段對算法進行優(yōu)化，可防止存儲體沖突的產生，進一步提高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加速數據挖掘算法的研究［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快速變換實現方法 ［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］孟海東，李秉秋.聚類分析在縣域經濟發(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］李冬梅，陳軍霞.聚類分析法在公交網絡評價中的應用［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)設計［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］葉若芬，孫書明.基于數據挖掘技術的教學測評［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］安淑芝.數據倉庫與數據挖掘［M］.北京：清華大學出版社，2005.AN Shuzhi.Data Warehouse and Data Mining［M］.Beijing：Tsinghua University Press，2005.