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

1、基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行預(yù)計算和查詢（四）的論文第七章實驗在本章中通過實驗說明算法的有效性和可擴(kuò)展性。實驗的平臺是一臺有三個 計算 節(jié)點的刀片服務(wù)器，每個節(jié)點上的處理器主頻為，內(nèi)存容量為1gb,操作系統(tǒng)是linux,內(nèi)核版本，節(jié)點間采用千兆 網(wǎng)絡(luò) 連接。mpi運行環(huán)境為，C+編譯器g+版本為，mpi環(huán)境下C+ 編譯器mpicxx的版本為。數(shù)據(jù)描述在實驗中，使用了一個來自不同氣象站所收集的1985年9月的天氣數(shù)據(jù)hahn94。它包含了 1,015,367個元組，一共20維。在這次實驗中，所使用的是它前16維的數(shù)據(jù)，每個維度的依次如下表所示：維度維度名稱維度的勢1時間2402天空明亮度23緯

2、度38094經(jīng)度53595氣象站編號70376氣象站所處地點17當(dāng)前天氣情況1018云層覆蓋總量99低層云數(shù)量1010低層云高度1111低層云類型1312中層云類型1413高層云類型1114中層云數(shù)量X1002415高層云數(shù)量X1002416中層云數(shù)量10表天氣數(shù)據(jù)集預(yù)計算實驗在本實驗中，將討論基于數(shù)據(jù)分組方法的并行預(yù)計算程序?qū)τ诖蓄A(yù)計算程序在性能上 的提高，以及這兩種方法在不同規(guī)模數(shù)據(jù)集上進(jìn)行運算的性能表現(xiàn)。討論并行查詢程序的加速比。在預(yù)計算實驗中，在單節(jié)點環(huán)境下和三節(jié)點環(huán)境下分別對13個不同的數(shù)據(jù)進(jìn)行了串行和并行預(yù)計算。這 13個不同的數(shù)據(jù)的維度各不相同，從 4維到16維，分別是天氣數(shù)據(jù)

3、集 20維數(shù)據(jù)中的前4維到前16維等，元組條數(shù)都是 1,015,367條。三節(jié)點環(huán)境下的數(shù)據(jù)分割 采用平均分割，每個節(jié)點上收到的元組條數(shù)基本上是相等的。在單節(jié)點環(huán)境下的實驗使用串行的預(yù)計算程序。統(tǒng)計兩個時間：（1）程序進(jìn)行預(yù)計算寫入文件的時間。（2）程序運行時間。在三節(jié)點環(huán)境下的實驗使用并行的預(yù)計算程序。因為從機(jī)不需要等待主機(jī)完全讀入數(shù)據(jù)文件便可得到一部分?jǐn)?shù)據(jù)進(jìn)行預(yù)計算，使得從機(jī)預(yù)計算時間和主機(jī)讀取文件有交叉。因此在此實驗中，每臺機(jī)器都會統(tǒng)計三個時間：（1）主機(jī)從開始讀取數(shù)據(jù)文件到數(shù)據(jù)完全載入內(nèi)存 并發(fā)送出去的時間。（2）每臺機(jī)器進(jìn)行預(yù)計算的時間。（3）每臺機(jī)器總的運行時間。通過實驗發(fā)現(xiàn)，刀片

4、服務(wù)器的網(wǎng)絡(luò)效率非常高，在實驗中，幾乎所有的mpi點對點通信時間都可以在秒之內(nèi)完成，加上實驗中的mpi通信次數(shù)比較少，所以 mpi通信的時間可以忽略不計。預(yù)計算實驗結(jié)果分析圖所示是分別在兩種環(huán)境下的預(yù)計算時間，也就是程序生成立方體的計算時間。并行環(huán)境下的預(yù)計算時間是取三個節(jié)點預(yù)計算時間的平均值。如圖中所示，基于數(shù)據(jù)分組的并行預(yù)計算方法能夠有效地縮短預(yù)計算的時間。在數(shù)據(jù)維度少于或等于 9維時，預(yù)計算的時間增長顯得比較緩慢，在這個維度區(qū)間內(nèi)，預(yù)計算程序的性能始終保持著較高水平。但隨著數(shù)據(jù)維度的增多，預(yù)計算性能開始出現(xiàn)衰減。從11維數(shù)據(jù)開始，每增加一維數(shù)據(jù)，串行預(yù)計算時間便會增加約33%，而并行的預(yù)

5、計算時間增長率為29%左右。圖所示是串行預(yù)計算時間和并行平均預(yù)計算時間的比值。在4到10維之間時，串行預(yù)計算時間一直維持在并行計算時間的倍左右。但在11維或更多維數(shù)據(jù)時，串行預(yù)計算時間的增長率開始大幅超過并行預(yù)計算時間，使得并行計算的加速比在11維時達(dá)到了理想狀態(tài)的3倍，并且呈線性增長的趨勢?？梢姡S著數(shù)據(jù)量的增大，dfs算法性能會相應(yīng)地下降，而減少元組條數(shù)可以繼續(xù)使得dfs算法保持高性能。圖預(yù)計算時間圖預(yù)計算加速比圖、和分別是預(yù)計算程序讀入數(shù)據(jù)文件時間、程序總運行時間和總運行時間的加速比。并行環(huán)境下程序總運行時間是指程序開始運行直到最后一個進(jìn)程完成計算退出為止。并行程序中數(shù)據(jù)讀入與數(shù)據(jù)發(fā)送是

6、結(jié)合在一起的， 數(shù)據(jù)讀入一部分之后即可將該部分?jǐn)?shù)據(jù)發(fā)送給相 應(yīng)的進(jìn)程進(jìn)行計算，但讀入數(shù)據(jù)文件這一部分不能達(dá)到完全的并行化，所以程序總運行時間但隨著維度的增多，預(yù)計算在高維度的預(yù)計算中，并4至13維的商立方體進(jìn)行單的加速比性能并沒有已經(jīng)完全并行化的預(yù)計算加速比那么可觀。 時間的增長，數(shù)據(jù)讀入時間所占的總運行時間比例也相應(yīng)地減少。 行的預(yù)計算程序最終還是可以達(dá)到3倍這個理想性能加速比。圖數(shù)據(jù)讀入時間圖總運行時間圖總運行時間加速比查詢實驗本實驗的主要內(nèi)容是在預(yù)計算生成的商立方體基礎(chǔ)上，對 節(jié)點串行和三節(jié)點并行點查詢實驗。討論并行查詢程序相對于單機(jī)查詢程序在性能上的提 高，計算并行查詢程序的加速比。首

7、先各個維度都隨機(jī)地生成了1000條點查詢。生成的點查詢是從基表中隨機(jī)抽取出1000條元組，并隨機(jī)地將元組中的某些屬性改為“ *。經(jīng)觀察，串行查詢程序與并行查詢程序所得到的查詢結(jié)果是一致的， 在本實驗中，主要討論并行查詢程序?qū)τ诖谐绦虻募铀俦龋?因此，查詢的具體結(jié)果便不再討論。串行查詢與并行查詢的程序運行時間如圖所示。圖查詢程序運行時間查詢實驗結(jié)果分析盡管在并行查詢中，每臺機(jī)器所查詢的立方體單元數(shù)目基本上只相當(dāng)于串行查詢中立方 體單元數(shù)目的三分之一，如圖所示，但通過實驗發(fā)現(xiàn)，并行查詢程序的性能加速比并未能夠達(dá)到理想的加速比， 如圖，只能達(dá)到2倍左右的性能加速。對其原因進(jìn)行分析，發(fā)現(xiàn)這是由 于查

8、詢語句未能直接命中，會造成額外開銷的問題（本文節(jié)中提到）所造成的。圖商立方體單元數(shù)圖程序加速比在基于數(shù)據(jù)分組方法的預(yù)計算中，經(jīng)過預(yù)計算的商立方體數(shù)據(jù)是分布式地存放各臺機(jī)器 上的。對于一條查詢語句 q，當(dāng)程序用q在a機(jī)器的商立方體中進(jìn)行查詢時，q的覆蓋集里面的所有元組在預(yù)計算時可能都沒有分配到a機(jī)器上。在這種情況下， q在a上的查詢便會產(chǎn)生巨大的額外開銷：首先會從q所在層次h1里的單元中開始查找，在h1找不到的情況下， 會繼續(xù)查找h1的下一層h2。但是由于q在a上是無法命中的，查詢程序會一層接著一層地 往下掃描下去，直到掃描完最后一層。隨機(jī)生成的1000條點查詢語句是根據(jù)基表中的元組生成的，這樣

9、在串行查詢中，較少 會出現(xiàn)語句在某一層未能命中，需要掃描下一層的情況。然而在并行查詢中，由于元組的分布性，產(chǎn)生了較多的查詢不命中，使得程序必須進(jìn)行額外的層次掃描，而且這種額外的層次掃描的代價十分巨大。在并行查詢中，開銷巨大額外的層次掃描使得查詢的時間急劇地增加， 從而使得程序性能沒能達(dá)到預(yù)期的效果。盡管如此，在三臺機(jī)器上能夠?qū)崿F(xiàn)縮短一半的時間，并行查詢程序的性能還是令人滿意的。小結(jié)由于硬件平臺條件的限制，實驗最多只能在三個節(jié)點上運行，無法進(jìn)行更多的實驗來驗證本文提出的基于數(shù)據(jù)分組的并行預(yù)計算和并行查詢方法的可擴(kuò)展性。在三個節(jié)點上進(jìn)行的預(yù) 計算和查詢實驗的結(jié)果表明，基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行

10、預(yù)計算和查詢方法是有效的，它能夠有效地提高數(shù)據(jù)倉庫預(yù)計算和查詢的性能，并得到正確的結(jié)果。第八章總結(jié)與展望在數(shù)據(jù)倉庫數(shù)據(jù)量急劇增長的今天，并行數(shù)據(jù)倉庫技術(shù)成為了解決海量數(shù)據(jù)預(yù)計算和存 儲問題的一種重要的、 有效的手段。本文主要研究了一種基于數(shù)據(jù)分組的并行數(shù)據(jù)倉庫預(yù)計 算和查詢技術(shù)，并在串行程序基礎(chǔ)上實現(xiàn)了并行預(yù)計算和查詢的程序。然后通過實驗數(shù)據(jù)來說明該方法的有效性和分析了這種方法的優(yōu)點和存在的缺陷。結(jié)論由于實驗平臺的限制， 使得各項實驗最多只能在三個節(jié)點的環(huán)境下運行，無法在更多節(jié)點的計算環(huán)境下進(jìn)行實驗，研究本文提出方法的可擴(kuò)展性。 通過實驗的觀察和分析，本文提 出的基于數(shù)據(jù)分組的數(shù)據(jù)倉庫并行預(yù)計

11、算和并行查詢方法有以下一些優(yōu)點：(1) 該實現(xiàn)方法的并行策略簡單，該方法可以經(jīng)過很少的修改，便可以將很多已經(jīng)實現(xiàn)的串行程序改為并行程序。使用mpi和C+進(jìn)行編程，使得程序具有良好的可移植性、面向?qū)ο笮浴?2) 可以更好地適用于大數(shù)據(jù)量場合。對于串行版本的預(yù)計算程序，在對于高維度數(shù)據(jù)集進(jìn)行預(yù)計算時，隨著數(shù)據(jù)量的增加，性能衰減得很厲害。并行預(yù)計算時的性能加速比十分 可觀，在數(shù)據(jù)量很大的情況下，甚至可以超過理想加速比。(3) 預(yù)計算后生成的商立方體數(shù)據(jù)以分布式方式存儲，在查詢時，各臺機(jī)器都可以同時對立方體數(shù)據(jù)進(jìn)行讀取，充分利用了各臺機(jī)器的磁盤i/o帶寬。同時本文提出的并行預(yù)計算和并行查詢方法存在的一

12、些不足：(1) 對于并行查詢，查詢的效率未能達(dá)到理想的加速比。這是由于數(shù)據(jù)元組的分布性與商立方體的特性所造成的，當(dāng)查詢語句覆蓋集中的元組沒被分配到某臺機(jī)器上時，該查詢語句在該臺機(jī)器上的查詢操作便無法命中。商立方體的特性使得查詢在某一層上界中找不到所覆蓋的上界的時候， 必須到下一層進(jìn)行查找， 如果一直找不到，便會一直找下去，直到全部都掃描過。查詢語句在某臺機(jī)器上無法命中的后果是會產(chǎn)生很多額外的層次文件掃描操作， 這樣一層層的掃描操作代價是十分巨大的，但這種情況在數(shù)據(jù)元組分布式存儲的情況下又是無法避免的，這樣便使得并行查詢程序的加速比未能達(dá)到理想狀態(tài)。(2) 基表元組的映射可以提高預(yù)計算和查詢的響

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

14、沒有查詢語句覆蓋集內(nèi)的元組進(jìn)行。(3) 改進(jìn)查詢程序的算法。順序查詢是最簡單、易行的查詢方法，但這種方法的效率確 實不高。(4) 改進(jìn)立方體數(shù)據(jù)結(jié)構(gòu)，商立方體存在著查詢效率不高的問題，對此人們提出了各種基于商立方體的改善型立方體數(shù)據(jù)結(jié)構(gòu)，如qc-treelpz03和semi-closed cubelw05，基于此類型的立方體結(jié)構(gòu)應(yīng)該能夠改善查詢的響應(yīng)速度。參考文獻(xiàn)beo07: the beowulf cluster siteccs93a e. codd, s. codd, c. salley. bey ond decisi on support. computer world, 27(30):

15、 87-89, 1993ccs93b e. codd, s. codd, c. salley. providi ng olap to user-a nalysts. pc world, (9), 1993chen99陳國良.并行計算一一結(jié)構(gòu)算法 編程.北京，高等 教育 出版社，1999du01都志輝.高性能計算并行編程技術(shù)一一mpi并行程序設(shè)計.北京，清華大學(xué)出版社，2001fly72 m. flynn. some computer organizations and their effectiveness. ieee transactions on computers, c21(9), 19

16、72gcb+97 j. gray, s. chaudhuri, a. bosworth, a. layma n, d. reichart, m. ven katrao, f. pellow and h. pirahesh. data cube: a relational aggregation operator generalizing group-by, cross-tab, and sub-totals. jo urnal of data mining and kno wledge discovery, 1(1): 29-53, 1997ggkk03 a. grama, a. gupta,

17、 g. karypis, v. kumar. i ntroduct ion to parallel comput ing (sec ond edition). pearson education, 2003.張武，毛國勇，程海英 等譯.并行計算導(dǎo)論.北京，機(jī) 械工業(yè)出版社,2005hah n94 c. hah n et. al. edited syn optic cloud reports from ships and land stati ons over the globe, 1982-1991. /ftp/ndp026b/, 1994.hpf06 high performa nee fo

18、rtra n foruminm02 w. h. inmon. building the data warehouse (third edition), john wiley & sons, inc. 2002.王志海，林友芳等譯.數(shù)據(jù)倉庫.北京，機(jī)械工業(yè)出版社，2003lam07 lam-mpi parallel comput inglph02 l. lakshma nan, j. pei and quotie nt cube: how to summarize the sema ntics of a data cube. in vldb ' 02lpz03 l. lakshm

19、anan, j. pei and y. zhao. qc-trees: an efficient summary structure for sema ntic olap. in proceedi ngs of the 2003 acm sigmod intern ati onal conference on man ageme nt of data, acm, 2003lw05 s. li and s. wang. semi-closed cube: an effective approach to trad ing off data cube size and query resp ons

20、e time. jo urnal of computer scie nee and tech no logy, , , , 2005mpi03a mpi: a message-pass ing in terface sta ndard.mpi03b mpi-2: exte nsions to the message-pass ing in terface.mpi07 mpich2 home pageomp07 ope nmp: simple, portable, scalable smp program mingptp06 posix thread program mingpvm07 para

21、llel virtual mach ine web sitesrd02 y. sismanis, n. roussopoulos, a. deligiannakis and y. kotidis. dwarf: shrinking the petacube. in proceedi ngs of the 2002 acm sigmod intern ati onal conference on man ageme nt of data, acm, 2002st98 d. skillicorn and d. talia. models and Ianguages for parallel com

22、putation. acm computi ng surveys, 30(2): 123-169, 1998wlfy02 w. wang, h. lu, j. feng and j. yu. conden sed cube: an effective approach to reduc ing data cube size. in proceedings of the 18th international conference on data engineering, ieee computer society, 2002.zcml06張林波，遲學(xué)斌，莫則堯，李若.并行計算導(dǎo)論.北京，清華大學(xué)出版社， 2006附錄時間（秒）維