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

1、基于數(shù)據(jù)分組方法的數(shù)據(jù)倉(cāng)庫(kù)并行預(yù)計(jì)算和查詢（四）        7.1   數(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è)維度的依次如下表所示：維度維度名稱維度的勢(shì)1時(shí)間2402天空明亮度23緯度38094經(jīng)度53595氣象站編號(hào)70376氣象站所處地點(diǎn)17當(dāng)前天氣情況1018云層覆蓋總量

2、99低層云數(shù)量1010低層云高度1111低層云類型1312中層云類型1413高層云類型1114中層云數(shù)量×1002415高層云數(shù)量×1002416中層云數(shù)量10表7.1     天氣數(shù)據(jù)集7.2   預(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)。討論并行查詢程序的加速比。在預(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維，分別是

3、天氣數(shù)據(jù)集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ì)算寫入文件的時(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ī)從開始讀取數(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í)間都可以在0.2秒之內(nèi)完成，加上實(shí)驗(yàn)中的MPI通信次數(shù)比較少，所以MPI通信的時(shí)間可以忽略不計(jì)。圖7.2所示是串行預(yù)計(jì)算時(shí)間和并行平均預(yù)計(jì)算時(shí)間的比值。在4到10維之間時(shí)，串行預(yù)計(jì)算時(shí)間一直維持在并行計(jì)算時(shí)間的2.9倍左右。但在11維或更多維數(shù)據(jù)時(shí)，串行預(yù)計(jì)算時(shí)間的增長(zhǎng)率開始大幅超過(guò)并行預(yù)計(jì)算時(shí)間，使得并行計(jì)算的加速比在11維時(shí)達(dá)到了理想狀態(tài)的3倍，并且呈線性增長(zhǎng)的趨勢(shì)?？梢?jiàn)，隨著數(shù)據(jù)量的增大，DFS算法性能會(huì)相應(yīng)地下降，而減少元組條數(shù)可以繼續(xù)使得DFS算法保持高性能。圖7.1     預(yù)計(jì)算

5、時(shí)間圖7.2     預(yù)計(jì)算加速比圖7.3     數(shù)據(jù)讀入時(shí)間圖7.4     總運(yùn)行時(shí)間圖7.5     總運(yùn)行時(shí)間加速比7.3   查詢實(shí)驗(yàn)     本實(shí)驗(yàn)的主要內(nèi)容是在預(yù)計(jì)算生成的商立方體基礎(chǔ)上，對(duì)4至13維的商立方體進(jìn)行單節(jié)點(diǎn)串行和三節(jié)點(diǎn)并行點(diǎn)查詢實(shí)驗(yàn)。討論并行查詢程序相對(duì)于單機(jī)查詢程序在性能上的提高，計(jì)算并行查詢程序的加速比。首先各個(gè)維度都隨機(jī)地生成了1000條點(diǎn)查詢。生成的

6、點(diǎn)查詢是從基表中隨機(jī)抽取出1000條元組，并隨機(jī)地將元組中的某些屬性改為“*”。經(jīng)觀察，串行查詢程序與并行查詢程序所得到的查詢結(jié)果是一致的，在本實(shí)驗(yàn)中，主要討論并行查詢程序?qū)τ诖谐绦虻募铀俦?，因此，查詢的具體結(jié)果便不再討論。串行查詢與并行查詢的程序運(yùn)行時(shí)間如圖7.6所示。圖7.6     查詢程序運(yùn)行時(shí)間圖7.7     商立方體單元數(shù)圖7.8     程序加速比在基于數(shù)據(jù)分組方法的預(yù)計(jì)算中，經(jīng)過(guò)預(yù)計(jì)算的商立方體數(shù)據(jù)是分布式地存放各臺(tái)機(jī)器上的。對(duì)于一條查詢語(yǔ)句q，當(dāng)程序用q

7、在A機(jī)器的商立方體中進(jìn)行查詢時(shí)，q的覆蓋集里面的所有元組在預(yù)計(jì)算時(shí)可能都沒(méi)有分配到A機(jī)器上。在這種情況下，q在A上的查詢便會(huì)產(chǎn)生巨大的額外開銷：首先會(huì)從q所在層次h1里的單元中開始查找，在h1找不到的情況下，會(huì)繼續(xù)查找h1的下一層h2。但是由于q在A上是無(wú)法命中的，查詢程序會(huì)一層接著一層地往下掃描下去，直到掃描完最后一層。隨機(jī)生成的1000條點(diǎn)查詢語(yǔ)句是根據(jù)基表中的元組生成的，這樣在串行查詢中，較少會(huì)出現(xiàn)語(yǔ)句在某一層未能命中，需要掃描下一層的情況。然而在并行查詢中，由于元組的分布性，產(chǎn)生了較多的查詢不命中，使得程序必須進(jìn)行額外的層次掃描，而且這種額外的層次掃描的代價(jià)十分巨大。在并行查詢中，開銷

8、巨大額外的層次掃描使得查詢的時(shí)間急劇地增加，從而使得程序性能沒(méi)能達(dá)到預(yù)期的效果。盡管如此，在三臺(tái)機(jī)器上能夠?qū)崿F(xiàn)縮短一半的時(shí)間，并行查詢程序的性能還是令人滿意的。7.4   小結(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ì)算和并行查詢方法的可擴(kuò)展性。1         在三個(gè)節(jié)點(diǎn)上進(jìn)行的預(yù)和查詢實(shí)驗(yàn)的結(jié)果表明，基于數(shù)據(jù)分組方法的數(shù)據(jù)倉(cāng)庫(kù)并行預(yù)計(jì)算和查詢方法是有效的，它能夠有效地提高數(shù)據(jù)倉(cāng)庫(kù)預(yù)計(jì)算和查詢的性能，并得到正確的結(jié)果。 第

9、八章  與展望 在數(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ì)算和查詢技術(shù)，并在串行程序基礎(chǔ)上實(shí)現(xiàn)了并行預(yù)計(jì)算和查詢的程序。然后通過(guò)實(shí)驗(yàn)數(shù)據(jù)來(lái)說(shuō)明該方法的有效性和分析了這種方法的優(yōu)點(diǎn)和存在的缺陷。8.1    結(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ì)算和并行查詢方法有以下一些優(yōu)點(diǎn)：(1)

10、60;  該實(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ǔ)，在查詢時(shí)，各臺(tái)機(jī)器都可以同時(shí)對(duì)立方體數(shù)據(jù)進(jìn)行讀取，充分利用了各臺(tái)機(jī)器的磁盤I/O帶寬。同時(shí)本文提出的并行預(yù)計(jì)算和并行查詢方法存在的

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

12、0; 基表元組的映射可以提高預(yù)計(jì)算和查詢的響應(yīng)效率，但是對(duì)于映射這個(gè)步驟還不能完全地并行化處理。8.2   未來(lái)的改進(jìn) 對(duì)于本文提出的并行預(yù)計(jì)算和并行查詢方法存在的一些不足和缺點(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ì)于基于順序查詢方法的并行查詢，可以預(yù)先判斷一下是否在該機(jī)上命中查詢。如

13、果可以預(yù)先判斷出查詢不命中，則可以減少許多額外的層次掃描開銷，提高效率。預(yù)先的判斷應(yīng)該可以通過(guò)掃描本地預(yù)計(jì)算輸入基表里有沒(méi)有查詢語(yǔ)句覆蓋集內(nèi)的元組進(jìn)行。(3)   改進(jìn)查詢程序的算法。順序查詢是最簡(jiǎn)單、易行的查詢方法，但這種方法的效率確實(shí)不高。(4)   改進(jìn)立方體數(shù)據(jù)結(jié)構(gòu)，商立方體存在著查詢效率不高的問(wèn)題，對(duì)此人們提出了各種基于商立方體的改善型立方體數(shù)據(jù)結(jié)構(gòu)，如QC-TreeLPZ03和Semi-Closed CubeLW05，基于此類型的立方體結(jié)構(gòu)應(yīng)該能夠改善查詢的響應(yīng)速度。Beo07    B: T

14、he Beowulf Cluster SiteCCS93a     E. Codd, S. Codd, C. Salley. Beyond decision support. Computer World, 27(30): 87-89, 1993CCS93b   E. Codd, S. Codd, C. Salley. Providing OLAP to User-Analysts. PC World, (9), 1993Chen99     陳國(guó)良. 并行計(jì)算結(jié)構(gòu)·算法·編

15、程. 北京, 高等出版社, 1999Du01       都志輝. 高性能計(jì)算并行編程技術(shù)MPI并行程序設(shè)計(jì). 北京, 清華大學(xué)出版社, 2001Fly72      M. Flynn. Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers, C21(9), 1972GCB+97     J. Gray, S. Chaudhuri,

16、A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow and H. Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. Journal of Data Mining and Knowledge Discovery, 1(1): 29-53, 1997GGKK03     A. Grama, A. Gupta, G. Karypis,

17、 V. Kumar. Introduction to Parallel Computing (Second Edition). Pearson Education, 2003. 張武, 毛國(guó)勇, 程海英 等譯. 并行計(jì)算導(dǎo)論. 北京, 機(jī)械出版社, 2005HPF06    High Performance Fortran 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 ComputingLPH02     L. Lakshmanan, J. Pei and J.Han. Quotient Cube: How to Summarize the Semantics of a Data