1、基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行預(yù)計算和查詢（四）        7.1   數(shù)據(jù)描述        在實驗中，使用了一個來自不同氣象站所收集的1985年9月的天氣數(shù)據(jù)Hahn94。它包含了1,015,367個元組，一共20維。在這次實驗中，所使用的是它前16維的數(shù)據(jù)，每個維度的依次如下表所示：維度維度名稱維度的勢1時間2402天空明亮度23緯度38094經(jīng)度53595氣象站編號70376氣象站所處地點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ù)計算實驗 在本實驗中，將討論基于數(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維，分別是

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

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

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

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

8、巨大額外的層次掃描使得查詢的時間急劇地增加，從而使得程序性能沒能達(dá)到預(yù)期的效果。盡管如此，在三臺機(jī)器上能夠?qū)崿F(xiàn)縮短一半的時間，并行查詢程序的性能還是令人滿意的。7.4   小結(jié) 由于硬件平臺條件的限制，實驗最多只能在三個節(jié)點上運行，無法進(jìn)行更多的實驗來驗證本文提出的基于數(shù)據(jù)分組的并行預(yù)計算和并行查詢方法的可擴(kuò)展性。1         在三個節(jié)點上進(jìn)行的預(yù)和查詢實驗的結(jié)果表明，基于數(shù)據(jù)分組方法的數(shù)據(jù)倉庫并行預(yù)計算和查詢方法是有效的，它能夠有效地提高數(shù)據(jù)倉庫預(yù)計算和查詢的性能，并得到正確的結(jié)果。 第

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

10、60;  該實現(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ù)計算和并行查詢方法存在的

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

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

13、果可以預(yù)先判斷出查詢不命中，則可以減少許多額外的層次掃描開銷，提高效率。預(yù)先的判斷應(yīng)該可以通過掃描本地預(yù)計算輸入基表里有沒有查詢語句覆蓋集內(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)速度。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     陳國良. 并行計算結(jié)構(gòu)·算法·編

15、程. 北京, 高等出版社, 1999Du01       都志輝. 高性能計算并行編程技術(shù)MPI并行程序設(shè)計. 北京, 清華大學(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. 張武, 毛國勇, 程海英 等譯. 并行計算導(dǎo)論. 北京, 機(jī)械出版社, 2005HPF06    High Performance Fortran ForumInm02    W. H. Inmon. Building the Data Warehouse (Third Edition), John Wiley & Sons, Inc. 2002. 王志海, 林友芳等譯. 數(shù)據(jù)倉庫. 北京, 機(jī)械工業(yè)出版社, 2003LAM07     LAM-MPI Parallel ComputingLPH02     L. Lakshmanan, J. Pei and J.Han. Quotient Cube: How to Summarize the Semantics of a Data