基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行預計算和查詢（四）

基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行預計算和查詢（四）

第七章實驗

在本章中通過實驗說明算法的有效性和可擴展性。實驗的平臺是一臺有三個計算節(jié)點的刀片服務器，每個節(jié)點上的處理器主頻為1.8GHz，內(nèi)存容量為1GB，操作系統(tǒng)是Linux，內(nèi)核版本2.6.9，節(jié)點間采用千兆網(wǎng)絡連接。MPI運行環(huán)境為MPICH2.0，C++編譯器g++版本為3.4.3，MPI環(huán)境下C++編譯器MPICXX的版本為1.0.3。7.1數(shù)據(jù)描述

在實驗中，使用了一個來自不同氣象站所收集的1985年9月的天氣數(shù)據(jù)[Hahn94]。它包含了1，015，367個元組，一共20維。在這次實驗中，所使用的是它前16維的數(shù)據(jù)，每個維度的依次如下表所示：表7.1

天氣數(shù)據(jù)集7.2預計算實驗

在本實驗中，將討論基于數(shù)據(jù)分組方法的并行預計算程序?qū)τ诖蓄A計算程序在性能上的提高，以及這兩種方法在不同規(guī)模數(shù)據(jù)集上進行運算的性能表現(xiàn)。討論并行查詢程序的加速比。在預計算實驗中，在單節(jié)點環(huán)境下和三節(jié)點環(huán)境下分別對13個不同的數(shù)據(jù)進行了串行和并行預計算。這13個不同的數(shù)據(jù)的維度各不相同，從4維到16維，分別是天氣數(shù)據(jù)集20維數(shù)據(jù)中的前4維到前16維等，元組條數(shù)都是1，015，367條。三節(jié)點環(huán)境下的數(shù)據(jù)分割采用平均分割，每個節(jié)點上收到的元組條數(shù)基本上是相等的。在單節(jié)點環(huán)境下的實驗使用串行的預計算程序。統(tǒng)計兩個時間：(1)程序進行預計算寫入文件的時間。(2)程序運行時間。在三節(jié)點環(huán)境下的實驗使用并行的預計算程序。因為從機不需要等待主機完全讀入數(shù)據(jù)文件便可得到一部分數(shù)據(jù)進行預計算，使得從機預計算時間和主機讀取文件有交叉。因此在此實驗中，每臺機器都會統(tǒng)計三個時間：（1）主機從開始讀取數(shù)據(jù)文件到數(shù)據(jù)完全載入內(nèi)存并發(fā)送出去的時間。（2）每臺機器進行預計算的時間。（3）每臺機器總的運行時間。通過實驗發(fā)現(xiàn)，刀片服務器的網(wǎng)絡效率非常高，在實驗中，幾乎所有的MPI點對點通信時間都可以在0.2秒之內(nèi)完成，加上實驗中的MPI通信次數(shù)比較少，所以MPI通信的時間可以忽略不計。7.2.1預計算實驗結(jié)果分析

圖7.1所示是分別在兩種環(huán)境下的預計算時間，也就是程序生成立方體的計算時間。并行環(huán)境下的預計算時間是取三個節(jié)點預計算時間的平均值。如圖中所示，基于數(shù)據(jù)分組的并行預計算方法能夠有效地縮短預計算的時間。在數(shù)據(jù)維度少于或等于9維時，預計算的時間增長顯得比較緩慢，在這個維度區(qū)間內(nèi)，預計算程序的性能始終保持著較高水平。但隨著數(shù)據(jù)維度的增多，預計算性能開始出現(xiàn)衰減。從11維數(shù)據(jù)開始，每增加一維數(shù)據(jù)，串行預計算時間便會增加約33%，而并行的預計算時間增長率為29%左右。圖7.2所示是串行預計算時間和并行平均預計算時間的比值。在4到10維之間時，串行預計算時間一直維持在并行計算時間的2.9倍左右。但在11維或更多維數(shù)據(jù)時，串行預計算時間的增長率開始大幅超過并行預計算時間，使得并行計算的加速比在11維時達到了理想狀態(tài)的3倍，并且呈線性增長的趨勢?？梢姡S著數(shù)據(jù)量的增大，DFS算法性能會相應地下降，而減少元組條數(shù)可以繼續(xù)使得DFS算法保持高性能。圖7.1

預計算時間圖7.2

預計算加速比圖7.3、7.4和7.5分別是預計算程序讀入數(shù)據(jù)文件時間、程序總運行時間和總運行時間的加速比。并行環(huán)境下程序總運行時間是指程序開始運行直到最后一個進程完成計算退出為止。并行程序中數(shù)據(jù)讀入與數(shù)據(jù)發(fā)送是結(jié)合在一起的，數(shù)據(jù)讀入一部分之后即可將該部分數(shù)據(jù)發(fā)送給相應的進程進行計算，但讀入數(shù)據(jù)文件這一部分不能達到完全的并行化，所以程序總運行時間的加速比性能并沒有已經(jīng)完全并行化的預計算加速比那么可觀。但隨著維度的增多，預計算時間的增長，數(shù)據(jù)讀入時間所占的總運行時間比例也相應地減少。在高維度的預計算中，并行的預計算程序最終還是可以達到3倍這個理想性能加速比。圖7.3

數(shù)據(jù)讀入時間圖7.4

總運行時間圖7.5

總運行時間加速比7.3查詢實驗

本實驗的主要內(nèi)容是在預計算生成的商立方體基礎上，對4至13維的商立方體進行單節(jié)點串行和三節(jié)點并行點查詢實驗。討論并行查詢程序相對于單機查詢程序在性能上的提高，計算并行查詢程序的加速比。首先各個維度都隨機地生成了1000條點查詢。生成的點查詢是從基表中隨機抽取出1000條元組，并隨機地將元組中的某些屬性改為“*”。經(jīng)觀察，串行查詢程序與并行查詢程序所得到的查詢結(jié)果是一致的，在本實驗中，主要討論并行查詢程序?qū)τ诖谐绦虻募铀俦龋虼?，查詢的具體結(jié)果便不再討論。串行查詢與并行查詢的程序運行時間如圖7.6所示。圖7.6

查詢程序運行時間7.3.1查詢實驗結(jié)果分析

盡管在并行查詢中，每臺機器所查詢的立方體單元數(shù)目基本上只相當于串行查詢中立方體單元數(shù)目的三分之一，如圖7.7所示，但通過實驗發(fā)現(xiàn)，并行查詢程序的性能加速比并未能夠達到理想的加速比，如圖7.8，只能達到2倍左右的性能加速。對其原因進行分析，發(fā)現(xiàn)這是由于查詢語句未能直接命中，會造成額外開銷的問題（本文4.3節(jié)中提到）所造成的。圖7.7

商立方體單元數(shù)圖7.8

程序加速比在基于數(shù)據(jù)分組方法的預計算中，經(jīng)過預計算的商立方體數(shù)據(jù)是分布式地存放各臺機器上的。對于一條查詢語句q，當程序用q在A機器的商立方體中進行查詢時，q的覆蓋集里面的所有元組在預計算時可能都沒有分配到A機器上。在這種情況下，q在A上的查詢便會產(chǎn)生巨大的額外開銷：首先會從q所在層次h1里的單元中開始查找，在h1找不到的情況下，會繼續(xù)查找h1的下一層h2。但是由于q在A上是無法命中的，查詢程序會一層接著一層地往下掃描下去，直到掃描完最后一層。隨機生成的1000條點查詢語句是根據(jù)基表中的元組生成的，這樣在串行查詢中，較少會出現(xiàn)語句在某一層未能命中，需要掃描下一層的情況。然而在并行查詢中，由于元組的分布性，產(chǎn)生了較多的查詢不命中，使得程序必須進行額外的層次掃描，而且這種額外的層次掃描的代價十分巨大。在并行查詢中，開銷巨大額外的層次掃描使得查詢的時間急劇地增加，從而使得程序性能沒能達到預期的效果。盡管如此，在三臺機器上能夠?qū)崿F(xiàn)縮短一半的時間，并行查詢程序的性能還是令人滿意的。7.4小結(jié)

由于硬件平臺條件的限制，實驗最多只能在三個節(jié)點上運行，無法進行更多的實驗來驗證本文提出的基于數(shù)據(jù)分組的并行預計算和并行查詢方法的可擴展性。第八章總結(jié)與展望

在數(shù)據(jù)倉庫數(shù)據(jù)量急劇增長的今天，并行數(shù)據(jù)倉庫技術(shù)成為了解決海量數(shù)據(jù)預計算和存儲問題的一種重要的、有效的手段。本文主要研究了一種基于數(shù)據(jù)分組的并行數(shù)據(jù)倉庫預計算和查詢技術(shù)，并在串行程序基礎上實現(xiàn)了并行預計算和查詢的程序。然后通過實驗數(shù)據(jù)來說明該方法的有效性和分析了這種方法的優(yōu)點和存在的缺陷。8.1

結(jié)論

由于實驗平臺的限制，使得各項實驗最多只能在三個節(jié)點的環(huán)境下運行，無法在更多節(jié)點的計算環(huán)境下進行實驗，研究本文提出方法的可擴展性。通過實驗的觀察和分析，本文提出的基于數(shù)據(jù)分組的數(shù)據(jù)倉庫并行預計算和并行查詢方法有以下一些優(yōu)點：(1)該實現(xiàn)方法的并行策略簡單，該方法可以經(jīng)過很少的修改，便可以將很多已經(jīng)實現(xiàn)的串行程序改為并行程序。使用MPI和C++進行編程，使得程序具有良好的可移植性、面向?qū)ο笮浴?2)可以更好地適用于大數(shù)據(jù)量場合。對于串行版本的預計算程序，在對于高維度數(shù)據(jù)集進行預計算時，隨著數(shù)據(jù)量的增加，性能衰減得很厲害。并行預計算時的性能加速比十分可觀，在數(shù)據(jù)量很大的情況下，甚至可以超過理想加速比。(3)預計算后生成的商立方體數(shù)據(jù)以分布式方式存儲，在查詢時，各臺機器都可以同時對立方體數(shù)據(jù)進行讀取，充分利用了各臺機器的磁盤I/O帶寬。同時本文提出的并行預計算和并行查詢方法存在的一些不足：(1)對于并行查詢，查詢的效率未能達到理想的加速比。這是由于數(shù)據(jù)元組的分布性與商立方體的特性所造成的，當查詢語句覆蓋集中的元組沒被分配到某臺機器上時，該查詢語句在該臺機器上的查詢操作便無法命中。商立方體的特性使得查詢在某一層上界中找不到所覆蓋的上界的時候，必須到下一層進行查找，如果一直找不到，便會一直找下去，直到全部都掃描過。查詢語句在某臺機器上無法命中的后果是會產(chǎn)生很多額外的層次文件掃描操作，這樣一層層的掃描操作代價是十分巨大的，但這種情況在數(shù)據(jù)元組分布式存儲的情況下又是無法避免的，這樣便使得并行查詢程序的加速比未能達到理想狀態(tài)。(2)基表元組的映射可以提高預計算和查詢的響應效率，但是對于映射這個步驟還不能完全地并行化處理。8.2未來的改進

對于本文提出的并行預計算和并行查詢方法存在的一些不足和缺點，可以存在這樣一些補充和改進的地方：(1)預計算算法還需要做出一些修改以適應立方體分布式存儲環(huán)境，如聚集操作中的平均操作，除了對該維度量值做平均值計算之外，還應該同時加上計算總和的計算。這樣才能保證元組條數(shù)的信息不至于丟失，在主進程最終做統(tǒng)計運算的時候才能得到正確的結(jié)果。(2)對于基于順序查詢方法的并行查詢，可以預先判斷一下是否在該機上命中查詢。如果可以預先判斷出查詢不命中，則可以減少許多額外的層次掃描開銷，提高效率。預先的判斷應該可以