基于數(shù)據(jù)分組方法的數(shù)據(jù)倉(cāng)庫(kù)并行預(yù)計(jì)算和查詢(xún)四的論文

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

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

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

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

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

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

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

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

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

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

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

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

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

14、沒(méi)有查詢(xún)語(yǔ)句覆蓋集內(nèi)的元組進(jìn)行。(3) 改進(jìn)查詢(xún)程序的算法。順序查詢(xún)是最簡(jiǎn)單、易行的查詢(xún)方法，但這種方法的效率確 實(shí)不高。(4) 改進(jìn)立方體數(shù)據(jù)結(jié)構(gòu)，商立方體存在著查詢(xún)效率不高的問(wèn)題，對(duì)此人們提出了各種基于商立方體的改善型立方體數(shù)據(jù)結(jié)構(gòu)，如qc-treelpz03和semi-closed cubelw05，基于此類(lèi)型的立方體結(jié)構(gòu)應(yīng)該能夠改善查詢(xún)的響應(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陳國(guó)良.并行計(jì)算一一結(jié)構(gòu)算法 編程.北京，高等 教育 出版社，1999du01都志輝.高性能計(jì)算并行編程技術(shù)一一mpi并行程序設(shè)計(jì).北京，清華大學(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.張武，毛國(guó)勇，程海英 等譯.并行計(jì)算導(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ù)倉(cāng)庫(kù).北京，機(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é)斌，莫?jiǎng)t堯，李若.并行計(jì)算導(dǎo)論.北京，清華大學(xué)出版社， 2006附錄時(shí)間（秒）維