基于并行計算的數(shù)據(jù)流處理方法研究.pdf

1、量大流速快的數(shù)據(jù)流挖掘已經(jīng)成為當今國際學術(shù)界大數(shù)據(jù)處理的研究熱點，與靜態(tài)存儲的數(shù)據(jù)相比，這些數(shù)據(jù)是連續(xù)實時獲得的單次掃描數(shù)據(jù)。對于快速時變的數(shù)據(jù)流，在有限的內(nèi)存資源下無法存儲全部的數(shù)據(jù)流數(shù)據(jù)，如何精確地增量挖掘其連續(xù)變化趨勢和發(fā)現(xiàn)隱藏的相關(guān)性對數(shù)據(jù)流的實時分析與處理帶來了巨大的挑戰(zhàn)，另一方面，數(shù)據(jù)流處理時滯也成為制約數(shù)據(jù)流挖掘的一個尖銳瓶頸問題。基于以上問題，本文研究了數(shù)據(jù)流趨勢和相關(guān)性分析的融合并行計算模型和算法，將數(shù)據(jù)流挖掘與基于C

2、PU(CentralProcess Unit)和GPU(Graphic Process Unit)的高性能計算有機地結(jié)合起來，實現(xiàn)動態(tài)連續(xù)的高效數(shù)據(jù)流處理方法。論文的主要研究內(nèi)容可歸納如下:
　　1、針對非線性非平穩(wěn)時間序列數(shù)據(jù)流的預測能力不足問題，研究了基于HHT(Hilbert-Huang Transform)的Online-HHT分析方法，進一步結(jié)合RBF(Radial BasisFunction)神經(jīng)網(wǎng)絡(luò)理論，研究了適合在

3、線預測的時間序列數(shù)據(jù)流模型。該方法通過引入CPU多線程的并行處理方法，設(shè)計了時間序列數(shù)據(jù)流鏈式可重寫滑動窗口的數(shù)據(jù)讀寫技術(shù)，實現(xiàn)了細粒度分段數(shù)據(jù)的并行預測分量和分段結(jié)果的合成算法。Online-HHT方法既能發(fā)揮其對時間序列數(shù)據(jù)流的時頻自適應(yīng)分析能力，又具有更快的計算處理速度，Online-HHT得到的數(shù)據(jù)流本征模分量也降低了RBF神經(jīng)網(wǎng)絡(luò)預測結(jié)構(gòu)的輸入復雜性，對時間序列數(shù)據(jù)流的趨勢預測能力起到很大地提高。實驗結(jié)果表明，通過與其他方法相

4、比較，本文提出的方法能夠處理數(shù)據(jù)流的短期趨勢預測，并且處理速度更快，可應(yīng)用于在線預測。
　　2、針對在數(shù)據(jù)流頻繁項挖掘中使用模式樹造成空間復雜度過大的問題，提出了一種嵌套滑動窗口遺傳算法NSWGA(Nested Sliding Window Genetic Algorithm)的數(shù)據(jù)流頻繁項挖掘方法。本算法在滑動窗口中的數(shù)據(jù)流上分割出嵌套窗口，利用基于MPI的遺傳算法并行處理嵌套窗口中的數(shù)據(jù)流，以及改進初始種群獲得方法，實現(xiàn)了嵌套

5、窗口中數(shù)據(jù)流的頻繁模式快速挖掘。在數(shù)據(jù)流動過程中，采用定期刪除過期數(shù)據(jù)的方法，更新滑動窗口中最新的頻繁項集，進而實現(xiàn)增量維護，提高執(zhí)行效率，快速發(fā)現(xiàn)數(shù)據(jù)流中的頻繁項。
　　3、針對由于資源約束造成的數(shù)據(jù)流處理時滯和效率問題，研究了最新超算技術(shù)GPU并行計算結(jié)構(gòu)，根據(jù)數(shù)據(jù)流數(shù)據(jù)屬性的特點和處理的高性能需求，提出了基于GPU的數(shù)據(jù)流通用處理模型。根據(jù)GPU并行計算結(jié)構(gòu)的SIMT模式，采用基本窗口技術(shù)的滑動窗口模型，給出了粗粒度和細粒度

6、兩個并行計算層面的數(shù)據(jù)流處理結(jié)構(gòu)，將數(shù)據(jù)流的數(shù)據(jù)劃分為粒度合適的數(shù)據(jù)塊，然后進行概要數(shù)據(jù)結(jié)構(gòu)和各種挖掘算法的并行處理。粗粒度并行主要負責任務(wù)分工并行化，而細粒度并行負責抽取數(shù)據(jù)流概要數(shù)據(jù)結(jié)構(gòu)的并行化，也負責在GPU上完成數(shù)據(jù)流挖掘和計算密集的線程網(wǎng)格，達到高效率的數(shù)據(jù)交換和高性能的并行算法。在這個通用數(shù)據(jù)流處理模型上，提出了基于GPU的數(shù)據(jù)流分位數(shù)并行計算方法GSQ(GPU Stream Quantiles)，調(diào)用GPU內(nèi)核程序，使用哈

7、希方法對數(shù)據(jù)流的數(shù)據(jù)塊并行計算生成概要數(shù)據(jù)直方圖，最后查詢得到數(shù)據(jù)流分位數(shù)，實驗驗證了從處理帶寬、響應(yīng)時間和加速比都有很大的提高。
　　4、針對在CPU上多條數(shù)據(jù)流相關(guān)性分析受到資源和執(zhí)行順序的實時性約束限制問題，本文研究提出了CPU和GPU協(xié)同處理的跨總線四層滑動窗口框架，用于處理多條數(shù)據(jù)流的并行計算，把多條數(shù)據(jù)流完全映射到GPU內(nèi)存空間，建立數(shù)據(jù)流SID索引，使用基本子窗口偏移量可以實現(xiàn)不同級別的并行操作。構(gòu)造了適合多數(shù)據(jù)流的

8、多級并行計算處理，使用s→Thread的細粒度并行計算和s→Block中粒度的方式，給出了單維多數(shù)據(jù)流的相關(guān)性分析并行算法GSSCCA(GPU Single-Dimensional Stream CanonicalCorrelation Analysis)，實驗驗證了算法有很好的準確度，極大提高了計算速度。
　　5、對由多數(shù)據(jù)屬性記錄實時復雜信息的高維多數(shù)據(jù)流來說，在計算準確性和性能會出現(xiàn)比單維多數(shù)據(jù)流處理更為復雜的資源和執(zhí)行順序