22629945.基于mapreduce和gpu雙重并行層次下的關(guān)聯(lián)規(guī)則挖掘的探討

《22629945.基于mapreduce和gpu雙重并行層次下的關(guān)聯(lián)規(guī)則挖掘的探討》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、基于MapReduce和GPU雙重并行層次下的關(guān)聯(lián)規(guī)則挖掘的探討計(jì)算機(jī)學(xué)院2011級(jí)碩七班張宗禹21121276摘要：數(shù)據(jù)挖掘是指從巨量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過(guò)程。而關(guān)聯(lián)規(guī)則就是其中一種典型的例子,本論文主要關(guān)注關(guān)聯(lián)規(guī)則的挖掘。在許多情況下，將所有數(shù)據(jù)集中在一起進(jìn)行分析往往是不可行的。分布式數(shù)據(jù)挖掘系統(tǒng)則可以充分利用分布式計(jì)算的能力對(duì)相關(guān)的數(shù)據(jù)進(jìn)行分析與綜合，再加上可以節(jié)省大量的時(shí)間和空間開(kāi)銷(xiāo)，分布式數(shù)據(jù)挖掘應(yīng)運(yùn)而生。同時(shí)，隨著數(shù)據(jù)量的指數(shù)型增加以及對(duì)計(jì)算量的需求急切增長(zhǎng)，已有的數(shù)據(jù)挖掘軟件很難滿(mǎn)足應(yīng)用的實(shí)時(shí)性需要，人們對(duì)并行數(shù)據(jù)挖掘技術(shù)的

2、需求十分強(qiáng)烈。圖形處理器(GPU)的最新發(fā)展已經(jīng)能夠以低廉的成本提供高性能的通用計(jì)算。本文將在介紹當(dāng)前分布式數(shù)據(jù)挖掘的發(fā)展現(xiàn)狀和趨勢(shì)，以及當(dāng)前基于GPU的并行數(shù)據(jù)挖掘發(fā)展現(xiàn)狀的同時(shí)，從理論上以關(guān)聯(lián)規(guī)則挖掘?yàn)槔接懸环N將這兩種正火熱的技術(shù)結(jié)合的方法。關(guān)鍵字：數(shù)據(jù)挖掘、關(guān)聯(lián)規(guī)則、MapReduce、GPGPU、CUDA、HadoopStreaming1．研究背景和現(xiàn)狀1.1云計(jì)算框架Hadoop和MapReduce計(jì)算模型云計(jì)算的核心思想，是將大量用網(wǎng)絡(luò)連接的計(jì)算資源統(tǒng)一管理和調(diào)度，構(gòu)成一個(gè)計(jì)算資源池向用戶(hù)按需服務(wù)。提供資源的網(wǎng)絡(luò)被稱(chēng)為“云”。Hadoop是一個(gè)能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布

3、式處理的軟件框架。但是Hadoop是以一種可靠、高效、可伸縮的方式進(jìn)行處理的。Hadoop是可靠的，因?yàn)樗僭O(shè)計(jì)算元素和存儲(chǔ)會(huì)失敗，因此它維護(hù)多個(gè)工作數(shù)據(jù)副本，確保能夠針對(duì)失敗的節(jié)點(diǎn)重新分布處理。Hadoop是高效的，因?yàn)樗圆⑿械姆绞焦ぷ?，通過(guò)并行處理加快處理速度。Hadoop還是可伸縮的，能夠處理PB級(jí)數(shù)據(jù)。此外，Hadoop依賴(lài)于社區(qū)服務(wù)器，因此它的成本比較低，任何人都可以使用?！　adoop帶有用Java語(yǔ)言編寫(xiě)的框架，因此運(yùn)行在Linux生產(chǎn)平臺(tái)上是非常理想的。Hadoop上的應(yīng)用程序也可以使用其他語(yǔ)言編寫(xiě)，比如C++，當(dāng)然也自然可以用CUDA語(yǔ)言，之后會(huì)詳細(xì)說(shuō)明。H

4、adoop最有趣的方面之一是MapandReduce流程，它受到Google開(kāi)發(fā)的啟發(fā)。MapReduce本身就是用于并行處理大數(shù)據(jù)集的軟件框架。MapReduce的根源是函數(shù)性編程中的map和reduce函數(shù)。它由兩個(gè)可能包含有許多實(shí)例（許多Map和Reduce）的操作組成。Map函數(shù)接受一組數(shù)據(jù)并將其轉(zhuǎn)換為一個(gè)鍵/值對(duì)列表，輸入域中的每個(gè)元素對(duì)應(yīng)一個(gè)鍵/值對(duì)。Reduce函數(shù)接受Map函數(shù)生成的列表，然后根據(jù)它們的鍵（為每個(gè)鍵生成一個(gè)鍵/值對(duì)）縮小鍵/值對(duì)列表。1.2GPGPU以及CUDA編程GPGPU全稱(chēng)GeneralPurposeGPU，即通用計(jì)算圖形處理器。這個(gè)GPU可

5、以分擔(dān)CPU的處理任務(wù)，一般集成在CPU上。近年來(lái)，計(jì)算機(jī)圖形處理器（GPU，GraphicsProcessingUnit）正在以大大超過(guò)摩爾定律的速度高速發(fā)展，極大的提高了計(jì)算機(jī)圖形處理的速度和質(zhì)量，不但促進(jìn)了圖像處理、虛擬現(xiàn)實(shí)、計(jì)算機(jī)仿真等相關(guān)應(yīng)用領(lǐng)域的快速發(fā)展，同時(shí)也為人們利用GPU進(jìn)行圖形處理以外的通用計(jì)算提供了良好的運(yùn)行平臺(tái)。GPU應(yīng)用領(lǐng)域的拓寬與其硬件發(fā)展有著極大關(guān)系。GPU自1999年首先由NVIDIA公司提出后，就其發(fā)展的速度而言，是CPU更新速度的三倍。從1993年開(kāi)始，GPU的性能以每年2.8倍的速度增長(zhǎng)。目前，圖形處理器已經(jīng)經(jīng)歷了五代發(fā)展，平均每半年就有新一

6、代的GPU問(wèn)世。GPU具有四大優(yōu)勢(shì)：分別是眾多的處理單元(ALU)，高數(shù)據(jù)帶寬的運(yùn)算，高效的并行性，超長(zhǎng)圖形流水線。在3D領(lǐng)域，GPU的用途很簡(jiǎn)單，就是為拉更好的渲染3D場(chǎng)景，減輕CPU在圖形運(yùn)算方面的負(fù)擔(dān)。時(shí)下剛剛出臺(tái)的GPGPU，是將應(yīng)用范圍擴(kuò)展到圖形之外，無(wú)論是科研教育，財(cái)務(wù)計(jì)算，還是在工業(yè)領(lǐng)域，GPGPU都得到拉廣泛的使用，關(guān)于它的科研成果和新應(yīng)用模式也層出不窮。CUDA(ComputeUnifiedDeviceArchitecture)，是顯卡廠商N(yùn)Vidia推出的運(yùn)算平臺(tái)。CUDA是一種由NVIDIA推出的通用并行計(jì)算架構(gòu)，該架構(gòu)使GPU能夠解決復(fù)雜的計(jì)算問(wèn)題。它包含

7、了CUDA指令集架構(gòu)（ISA）以及GPU內(nèi)部的并行計(jì)算引擎。開(kāi)發(fā)人員現(xiàn)在可以使用C語(yǔ)言來(lái)為CUDA架構(gòu)編寫(xiě)程序，C語(yǔ)言是應(yīng)用最廣泛的一種高級(jí)編程語(yǔ)言。所編寫(xiě)出的程序于是就可以在支持CUDA的處理器上以超高性能運(yùn)行。將來(lái)還會(huì)支持其它語(yǔ)言，包括FORTRAN以及C++。1.3并行數(shù)據(jù)挖掘并行數(shù)據(jù)挖掘技術(shù)不同于其它并行算法的地方在于它需要處理的數(shù)據(jù)的規(guī)模很大。人們知道，對(duì)于并行而言，交互之間的消耗（即內(nèi)存的使用）是比執(zhí)行時(shí)間（計(jì)算階段）重要得多的因素。串行數(shù)據(jù)挖掘算法對(duì)于規(guī)模很小的數(shù)據(jù)