本站小編為你精心準備了GPU加速數據挖掘論文參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1基于gpu的計算和編程

1.1GPUGPU之所以在某些應用中較CPU能夠獲得更高的性能，主要是因為GPU和CPU在硬件結構設計上存在很大差異。如圖1所示[10]，GPU將大量的晶體管用作ALU計算單元，從而適應密集且可并行的圖像渲染計算處理需要。相對GPU而言，CPU卻是將更多的晶體管用作復雜的控制單元和緩存等非計算功能，并以此來提高少量執行單元的執行效率。此外，存儲帶寬是另一個重要問題。存儲器到處理器的帶寬已經成為許多應用程序的瓶頸。目前GPU的芯片帶寬是CPU芯片帶寬的6倍左右。

1.2CPU/GPU協同并行計算在諸多適用于高性能計算的體系結構中，采用通用多核CPU與定制加速協處理器相結合的異構體系結構成為構造千萬億次計算機系統的一種可行途徑。而在眾多異構混合平臺中，基于CPU/GPU異構協同的計算平臺具有很大的發展潛力。在協同并行計算時，CPU和GPU應各取所長，即CPU承擔程序控制，而密集計算交由GPU完成。另外，除管理和調度GPU計算任務外，CPU也應當承擔一部分科學計算任務[12]。新型異構混合體系結構對大規模并行算法研究提出了新的挑戰，迫切需要深入研究與該體系結構相適應的并行算法。事實上，目前基于GPU加速的數據挖掘算法實現都有CPU參與協同計算，只是討論的重點多集中在為適應GPU而進行的并行化設計上。實踐中，需要找出密集計算部分并將其遷移到GPU中執行，剩余部分仍然由CPU來完成。

1.3CUDA為了加速GPU通用計算的發展，NVIDIA公司在2007年推出統一計算設備架構（ComputeUnifiedDeviceArchitecture，CUDA）[10,13]。CUDA編程模型將CPU作為主機，GPU作為協處理器，兩者協同工作，各司其職。CPU負責進行邏輯性強的事務處理和串行計算，GPU則專注于執行高度線程化的并行處理任務。CUDA采用單指令多線程（SIMT）執行模式，而內核函數（kernel）執行GPU上的并行計算任務，是整個程序中一個可以被并行執行的步驟。CUDA計算流程通常包含CPU到GPU數據傳遞、內核函數執行、GPU到CPU數據傳遞三個步驟。CUDA不需要借助于圖形學API，并采用了比較容易掌握的類C/C++語言進行開發，為開發人員有效利用GPU的強大性能提供了條件。CUDA被廣泛應用于石油勘探、天文計算、流體力學模擬、分子動力學仿真、生物計算和圖像處理等領域，在很多應用中獲得了幾倍、幾十倍，乃至上百倍的加速比[13]。

1.4并行編程語言和模型過去幾十年里，人們相繼提出了很多并行編程語言和模型，其中使用最廣泛的是為可擴展的集群計算設計的消息傳遞接口（MessagePassingInterface，MPI）和為共享存儲器的多處理器系統設計的OpenMP[14]。OpenMP最初是為CPU執行而設計的。OpenACC[15]是計算機廠商為異構計算系統提出的一種新編程模型，其主要優勢是為抽象掉許多并行編程細節提供了編譯自動化和運行時系統支持。這使得應用程序在不同廠商的計算機和同一廠商不同時代的產品中保持兼容性。然而，學習OpenACC需要理解所有相關的并行編程細節。在MPI編程模型中，集群中的計算節點之間相互不共享存儲器；節點之間的數據共享與交互都通過顯式傳遞消息的方式實現。MPI成功應用于高性能科學計算（HPC）領域。現在很多HPC集群采用的是異構的CPU/GPU節點。在集群層次上，開發人員使用MPI進行編程，但在節點層次上，CUDA是非常高效的編程接口。由于計算節點之間缺乏共享存儲器機制，要把應用程序移植到MPI中需要做大量針對性分析和分解工作。包括蘋果公司在內的幾大公司在2009年共同開發了一套標準編程接口，稱之為OpenCL[16]。與CUDA類似，OpenCL編程模型定義了語言擴展和運行時API，使程序員可以在大規模并行處理中進行并行管理和數據傳遞。與CUDA相比，OpenCL更多地依賴API，而不是語言的擴展，這允許廠商快速調整現有編譯器和工具來處理OpenCL程序。OpenCL和CUDA在關鍵概念和特性上有諸多相似之處，因此CUDA程序員可以很快掌握OpenCL。

1.5MATLAB因提供豐富的庫函數庫以及諸多其他研究者貢獻和共享的函數庫，MATLAB是研究人員實現算法的常用平臺。通過封裝的數據容器（GPUArrays）和函數，MATLAB允許沒有底層CUDA編程能力的研究人員可以較容易獲得GPU計算能力，因此MATLAB較OpenCL更容易上手。截止準備本文時，2014版本的MATLAB提供了226個內置的GPU版本的庫函數。對于有CUDA編程經驗的人員，MATLAB允許直接集成CUDA內核進MATLAB應用。本文第四節的實驗亦基于MATLAB實現。

1.6JACKET引擎JACKET[17]是一個由AccelerEyes公司開發專門用于以MATLAB為基礎的基于GPU的計算引擎，其最新版本已經包含了高層的接口，完全屏蔽了底層硬件的復雜性,并支持所有支持CUDA的GPU計算，降低了進行CUDA開發的門檻。JACKET是MATLAB代碼在GPU上運行的插件。JACKET允許標準的MATLAB代碼能夠在任何支持CUDA的GPU上運行，這使得廣大的MATLAB及C/C++用戶可以直接使用GPU強大的計算能力進行相關應用領域的快速原型開發。JACKET包含了一套運行于MATLAB環境中優化并行計算的基礎函數庫。并且支持MATLAB數據類型，可將任何存儲于MATLABCPU內存中的變量數據轉換為GPU上的數據類型，對以往的MATLAB程序來說，只需更改數據類型，就能遷移到GPU上運行。本文的第四節的實驗亦基于JACKET在MATLAB上實現。

2相關工作綜述

2.1基于CPU的數據挖掘算法實現數據挖掘算法的研究一直很活躍，許多成熟和經典的算法已經實現在諸多研究或商用軟件包/平臺，例如開源的Weka[18]和KNIME，以及商用的IBM公司的PASWModeler（即之前SPSS公司的Clementine®）。這些軟件默認都是單機版本，可運行在普通PC或高性能服務器上，基于CPU的計算能力。為了適應目前大規模的計算，出現了基于Google公司提出的MapReduce[19]計算框架實現的開源數據挖掘平臺Mahout[20]。相關的研究起源于斯坦福大學AndrewNg研究組2006年的經典論著[21]。由于現有的算法需要先找到可“遷移”到MapReduce的方式，因此目前Mahout平臺上僅有幾個能支持分布式部署的數據挖掘算法，包括用于分類的樸素貝葉斯、隨機森林，用于聚類的k-Means，基于項目的協同過濾等。目前Mahout仍然是基于CPU的計算能力。

2.2聚類算法聚類是數據挖掘中用來發現數據分布和隱含模式的一種無監督學習，每個訓練元組的類標號是未知的，并且要學習的個數或集合也可能事先不知道。對于給定的數據集，聚類算法按照一定的度量，將數據對象分組為多個簇，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別很大[22-23]。k-Means算法是經典的基于距離/劃分的聚類分析算法，也是應用得最廣泛的算法之一，采用距離作為相似性的評價指標，即認為兩個對象距離越近，其相似度就越大。k-Means算法的流程如下[24]：輸入：簇的數目k和包含n個對象數據集D。輸出：k個簇的集合。方法：1)從D中任意選擇k個對象作為初始簇中心。計算每個數據對象到各簇中心的歐氏距離，將每個數據對象分配到最相似的簇中。2)重新計算每個簇中對象的均值。3)循環執行步驟2-3兩個步驟，直到各個簇內對象不再變化。上述算法步驟2屬于計算密度最大的部分，且具備并行化的條件。計算各個數據對象到各簇中心的歐氏距離和將數據對象分配到最近的簇的時候，數據對象之間都是相互獨立的，不需要進行交換，且沒有先后順序，后計算的對象不需要等待前一次計算的結果，僅在完成全部分配過程之后，才需要進行一次數據匯總。所以文獻[25]的作者們使用GPU并行優化了一維數據的k-Means算法的步驟2，并使用帶緩存機制的常數存儲器保存中心點數據，能獲得更好的讀取效率。文獻中還展示了實驗結果，在8600GT上取得了14倍左右的加速效果。DBSCAN屬于基于密度的聚類算法中最常被引用的，G-DBSCAN是它的一個GPU加速版本[26]。文獻[26]的實驗顯示較DBSCAN可以實現高達112倍的加速。BIRCH是經典的基于層次的聚類算法，文獻[27]中基于CUDA實現的GPU加速版本在實驗中獲得了高達154倍的加速。

2.3分類算法分類是數據挖掘中應用領域極其廣泛的重要技術之一，至今已經提出很多算法。分類算法[28]是一種監督學習，通過對已知類別訓練集的分析，從中發現分類規則，以此預測新數據的類別。分類算法是將一個未知樣本分到幾個已存在類的過程，主要包含兩個步驟：首先，根據類標號已知的訓練數據集，訓練并構建一個模型，用于描述預定的數據類集或概念集；其次，使用所獲得的模型對新的數據進行分類。近年來，許多研究已經轉向實現基于GPU加速分類算法，包括k-NN（k近鄰）分類算法[29]，支持向量機分類算法[30]，貝葉斯分類算法[31-32]等。kNN算法[33]是數據挖掘中應用最廣泛的一種分類算法，簡單易實現。它是一種典型的基于實例的學習法，將待判定的檢驗元組與所有的訓練元組進行比較，挑選與其最相似的k個訓練數據，基于相應的標簽和一定的選舉規則來決定其標簽。在ShenshenLiang等人的文章[34]指出，由于kNN算法是一種惰性學習法，對于每個待分類的樣本，它都需要計算其與訓練樣本庫中所有樣本的距離，然后通過排序，才能得到與待分類樣本最相鄰的k個鄰居。那么當遇到大規模數據并且是高維樣本時，kNN算法的時間復雜度和空間復雜度將會很高，造成執行效率低下，無法勝任大數據分析任務。所以加速距離的計算是提高kNN算法的核心問題。因為每個待分類的樣本都可以獨立地進行kNN分類，前后之間沒有計算順序上的相關性，因此可以采用GPU并行運算方法解決kNN算法串行復雜度高的問題。將計算測試集和訓練集中點與點之間的距離和排序一步采用GPU并行化完成，其余如判斷類標號一步難以在GPU上高效實現，由CPU完成。文獻[34]通過GPU并行化實現kNN算法，讓kNN算法時間復雜度大幅度減少，從而說明GPU對kNN算法的加速效果是非常明顯的。

2.4關聯分析算法關聯規則挖掘是數據挖掘中較成熟和重要的研究方法，旨在挖掘事務數據庫頻繁出現的項集。因此，挖掘關聯規則的問題可以歸結為挖掘頻繁項集[35]。關聯分析算法首先找出所有的頻繁項集，然后根據最小支持度和最小置信度從頻繁項集中產生強關聯規則。Apriori算法[36]是最有影響力的挖掘布爾關聯規則頻繁項目集的經典算法。Apriori算法使用逐層搜索的迭代方法產生頻繁項目集，即利用k頻繁項集來產生（k+1）項集，是一種基于生成候選項集的關聯規則挖掘方法。在劉瑩等人的文章[37]中指出，產生候選項和計算支持度，占據Apriori的大部分計算量。產生候選項的任務是連接兩個頻繁項集，而這個任務在不同線程之間是獨立的，所以這個過程適合在GPU上被并行化。通過掃描交易數據庫，計算支持度程序記錄一個候選項集出現的次數。由于每個候選項集的計數與其他項集的計數相對獨立，同樣適合于多線程并行。所以文獻[37]的作者們在實現Apriori時使用GPU并行化了產生候選項和計算支持度這兩個過程，取得了顯著的加速效果。文獻[38]是目前發現的對于在GPU上實現頻繁項集挖掘最全面細致的研究。他們使用的是早期的CUDA平臺，采用了bitmap和trie兩種數據結構來實現GPU的挖掘算法，并且根據不同數據集和支持度進行了算法性能的對比，均相對于CPU版本的算法獲得的一定的加速比。

2.5時序分析由于越來越多的數據都與時間有著密切的關系，時序數據作為數據挖掘研究的重要分支之一，越來越受到人們的重視。其研究的目的主要包括以下兩個方面：一是學習待觀察過程過去的行為特征；二是預測未來該過程的可能狀態或表現。時序數據挖掘主要包含以下幾個主要任務：數據預處理，時序數據表示，分割，相似度度量，分類，聚類等。這些任務中很多都涉及到相當大的計算量。由于問題規模的不斷擴大，并且對于實時性能的要求，時序數據挖掘的任務就必須要求充分地提高計算速度或者通過優化減少計算量。時序數據的表示有時候會采取特征來表示，這就涉及到了特征提取問題，當特征數量龐大的時候就需要進行維數約簡，主要的方法有奇異值分解法，離散小波變換。這些計算都涉及到很大的時間復雜度，為了減少計算的時間消耗，SheetalLahabar等人使用GPU加速SVD的計算，獲得了60多倍的加速效果[39]。動態時間彎曲（DynamicTimeWarping，DTW）起初被應用于文本數據匹配和視覺模式識別的研究領域，是一種相似性度量算法。研究表明這種基于非線性彎曲技術的算法可以獲得很高的識別、匹配精度。Berndt和Clifford提出了將DTW的概念引入小型時間序列分析領域，在初步的實驗中取得了較好的結果[40]。隨著問題規模的擴大，對于DTW的計算成為了時序數據挖掘的首先要處理的問題。在DTW中，搜索需要找出與訓練數據最近距離的樣本，這就需要搜索與每個訓練樣本的距離，這就可以很好的利用GPU進行并行化處理。DorukSart等人在對DTW加速的處理中，獲得了兩個數量級的加速效果[41]。而對于分類和聚類任務的加速，上面已經提到，這里不再累贅。

2.6深度學習深度學習雖然隸屬機器學習，但鑒于機器學習和數據挖掘領域的緊密聯系，深度學習必定將在數據挖掘領域獲得越來越多的應用。從2006年Hinton和他的學生Salakhutdinov在《科學》上發表的文章[42]開始，深度學習在學術界持續升溫。深度學習的實質是通過構建具有很多隱層的機器學習模型和海量的訓練數據，來學習更有用的特征，從而最終提升分類預測的準確性[43]。如何在工程上利用大規模的并行計算平臺來實現海量數據訓練，是各個機構從事深度學習技術研發首先要解決的問題。傳統的大數據平臺如Hadoop，由于數據處理延遲太高而不適合需要頻繁迭代的深度學習。神經網絡一般基于大量相似的神經元，故本質上可以高度并行化訓練；通過映射到GPU，可以實現比單純依賴CPU顯著地提升。谷歌搭建的DistBelief是一個采用普通服務器的深度學習并行計算平臺，采用異步算法，由很多計算單元獨立更新同一個參數服務器的模型參數，實現了隨機梯度下降算法的并行化，加快了模型訓練速度。百度的多GPU并行計算平臺克服了傳統SGD訓練不能并行的技術難題，神經網絡的訓練已經可以在海量語料上并行展開。NVIDIA在2014年9月推出了深度學習GPU加速庫cuDNN，可以方便地嵌入高層級機器學習框架中使用，例如Caffe[45]。cuDNN支持NVIDIA的全系列GPU，包括低端的TegraK1和高端的TeslaK40，并承諾可向上支持未來的GPU。

2.7小結并行化能帶來多少倍的加速取決于算法中可并行化的部分。例如，如果可并行部分的時間占整個應用程序執行時間的20%，那么即使將并行部分加速100倍，總執行時間也只能減少19.8%，整個應用程序的加速只有1.247倍；即使無限加速也只能減少約20%的執行時間，總加速不會超過1.25倍。對于一個數據挖掘（學習和預測）算法進行GPU加速實現，首先要思考是否存在可并行執行的部分，之后再結合GPU的架構特點進行針對性實現優化。然而，由于數據挖掘算法普遍是數據密集型計算，而GPU片內存儲容量有限，如何降低與內存交換數據集是一個要解決的關鍵問題。通過以上相關工作的分析，可以發現數據挖掘算法在GPU上的加速具有數據獨立，可并行化共同特征。本文提出數據挖掘算法在GPU上加速實現的一種解決思路：在大數據下，分析算法的性能瓶頸，從而確定算法中耗時大，時間復雜度高的部分，將此部分在GPU上執行，不耗時部分在CPU上串行執行，以達到加速效果。為了更充分利用GPU的并行計算的體系結構，可深入分析耗時大的部分，將具有數據獨立，可并行化的部分在GPU上并行執行，達到更進一步的加速效果。

3實踐和分析：協同過濾推薦

當前主要的協同過濾推薦算法有兩類：基于用戶(r-based)和基于項目(item-based)的協同過濾推薦算法。基于項目的協同過濾推薦算法[46-50]認為,項目間的評分具有相似性,可以通過用戶對目標項目的若干相似項目的評分來估計該項目的分值。基于用戶的協同過濾推薦算法認為,如果用戶對一些項目的評分比較相似,那么他們對其他項目的評分也比較相似。本文根據以上總結的算法特征圍繞兩種經典協同過濾算法的實現，通過大規模數據的實驗來驗證GPU相對于傳統CPU的優勢。

3.1算法實現

3.1.1基于CPU實現協同過濾推薦的兩類經典算法本文基于MATLAB實現CPU版本的基于用戶和基于項目的兩種經典協同過濾推薦算法。實現的步驟：1)數據表示：收集用戶的評分數據，并進行數據清理、轉換，最終形成一個mn的用戶-項目評分矩陣R，m和n分別代表矩陣中的用戶數和項目數，矩陣中的元素代表用戶對項目的評分值。2)最近鄰居搜索：主要完成對目標用戶/項目的最近鄰居的查找。通過計算目標用戶/項目與其他用戶/項目之間的相似度，算出與目標用戶/項目最相似的最近鄰居集。該過程分兩步完成：首先采用協同過濾推薦算法中運用較多的度量方法“Pearson相關系數”計算用戶/項目之間的相似度得到相應的相似度矩陣，其次是采用最近鄰方法找到目標用戶/項目的最近的K個鄰居，這些鄰居是由與目標相似度最高的一些用戶/項目組成的。3)產生推薦：根據之前計算好的用戶/項目之間的相似度，并使用相應的預測評分函數對用戶未打分的項目進行預測，得到預測評分矩陣，然后選擇預測評分最高的Top-n項推薦給目標用戶。4)性能評估：本研究擬采用平均絕對誤差MAE作為評價推薦系統預測質量的評價標準。MAE可以直觀地對預測質量進行度量，是最常用的一種方法。MAE通過計算預測的用戶評分與實際評分之間的偏差度量預測的準確性；MAE越小，預測質量越高。

3.1.2基于GPU實現協同過濾推薦的兩類經典算法在大數據下，協同過濾算法中主要的時間消耗在于相似度計算模塊，占了整個算法的大部分時間，且每個用戶/項目之間的相似度可以被獨立計算,不依靠其他用戶/項目，具備并行化的條件，所以在以下的實驗中，將相似度計算模塊在GPU上執行，其他部分在CPU上執行，進而提高整個算法的執行效率。使用MATLAB編程技術和JACKET編程技術在GPU上分別實現基于用戶和基于項目的兩種經典協同過濾推薦算法。實現步驟如下：1)數據表示：收集用戶的評分數據，并進行數據清理、轉換，最終形成用戶-項目評分矩陣。2)將收集的數據從CPU傳輸至GPU。3)對傳輸到GPU上的數據執行GPU操作，調用相關函數庫，采用公式（1）和（2）分別計算并獲取用戶/項目間的相似度矩陣。4)將GPU計算結果返回CPU中以便后續操作。5)采用公式（3）和（4）在CPU上分別獲取兩種經典算法的評分預測矩陣。6)選擇預測評分最高的Top-n項推薦給目標用戶。7)采用公式（5）求兩種經典算法的平均絕對誤差MAE。

3.2實驗結果與分析

3.2.1實驗環境本實驗所用的CPU是IntelXeonE52687W，核心數量是八核，主頻率是3.1GHz，內存大小是32GB；所使用的GPU是NVIDIAQuadroK4000，顯存容量是3GB,顯存帶寬是134GB/s核心頻率是811MHz，流處理器數是768個。使用Windows764位操作系統，編程環境使用最新的CUDA。

3.2.2實驗數據本實驗使用目前比較常用的MovieLens[56]數據集作為測試數據，該數據集從MovieLens網站采集而來，由美國Minnesota大學的GroupLens研究小組提供，數據集1包含943個用戶對1682部電影約10萬的評分數據，數據集2包含6040個用戶對3952部電影約100萬的評分數據，其中每個用戶至少對20部電影進行了評分。評分的范圍是1～5，1表示“很差”，5表示“很好”。實驗需要將每個數據集劃分為一個訓練集和一個測試集，每次隨機選出其中80％的評分數據用作訓練集，另20％用作測試集。

3.2.3實驗結果與分析本文采用加速比來比較算法的CPU實現和GPU實現的運行效率。計算加速比的方法如式（6）所示：在公式中，TimeCPU表示算法在CPU上的平均運行時間，TimeGPU表示算法在GPU上的平均運行時間。所有實驗中均取最近鄰居數為20，且各實驗結果均為5次獨立測試的平均值。圖2是關于兩個算法核心步驟的加速效果，而圖3則展示了算法整體加速效果。可以看出，（1）整體加速效果取決于核心步驟的加速效果，（2）GPU版本的算法在性能上較CPU版本有較顯著地優勢，且面對大數據集的加速效果更為明顯。例如在基于100萬條數據集時，Item-based的整體算法的加速比達到了14倍左右，而面對10萬條數據集時，加速比不到8倍。這可以解釋為GPU的多核優勢在面對大數據集時被更為充分地得到釋放；（3）算法對r-based和Item-based兩種算法的加速比相近。圖4是關于算法預測效果的評估，可以看出基于GPU加速的兩類經典協同過濾算法與基于CPU的兩類經典協同過濾算法在預測效果上相近。如果結合圖2和圖3，可獲得結論-能夠基于GPU獲得得可觀的計算加速而不犧牲應用效果。

3.3小結

本文通過使用JACKET加快開發過程。目前國內還缺少對JACKET的了解和應用，JACKET的出現為科學領域進行大規模計算仿真提供了新的研究方法，并使得研究人員可以在熟悉的MATLAB平臺上實現相關算法。

4結束語

本文既對基于GPU加速經典數據挖掘的研究進行了分類回顧和小結，也實踐了基于GPU加速協同過濾計算，通過和基于CPU的版本對比，確實可以實現可觀的效率提升。這對我們深入研究將GPU應用到大數據處理場景可以積累寶貴的一手經驗，并在已知的尚未基于GPU加速的數據挖掘算法有的放矢。

作者：戴春娥陳維斌傅順開李志強單位：華僑大學計算機科學與技術學院