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

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

第七章實(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)上的處理器主頻為1.8GHz，內(nèi)存容量為1GB，操作系統(tǒng)是Linux，內(nèi)核版本2.6.9，節(jié)點(diǎn)間采用千兆網(wǎng)絡(luò)連接。MPI運(yùn)行環(huán)境為MPICH2.0，C++編譯器g++版本為3.4.3，MPI環(huán)境下C++編譯器MPICXX的版本為1.0.3。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è)維度的依次如下表所示：表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維，分別是天氣數(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ì)算寫(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)，刀片服務(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.1預(yù)計(jì)算實(shí)驗(yàn)結(jié)果分析

圖7.1所示是分別在兩種環(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ù)計(jì)算時(shí)間增長(zhǎng)率為29%左右。圖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)率開(kāi)始大幅超過(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ì)算時(shí)間圖7.2

預(yù)計(jì)算加速比圖7.3、7.4和7.5分別是預(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ā)送是結(jié)合在一起的，數(shù)據(jù)讀入一部分之后即可將該部分?jǐn)?shù)據(jù)發(fā)送給相應(yīng)的進(jìn)程進(jìn)行計(jì)算，但讀入數(shù)據(jù)文件這一部分不能達(dá)到完全的并行化，所以程序總運(yùn)行時(shí)間的加速比性能并沒(méi)有已經(jīng)完全并行化的預(yù)計(jì)算加速比那么可觀。但隨著維度的增多，預(yù)計(jì)算時(shí)間的增長(zhǎng)，數(shù)據(jù)讀入時(shí)間所占的總運(yùn)行時(shí)間比例也相應(yīng)地減少。在高維度的預(yù)計(jì)算中，并行的預(yù)計(jì)算程序最終還是可以達(dá)到3倍這個(gè)理想性能加速比。圖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)查詢。生成的點(diǎn)查詢是從基表中隨機(jī)抽取出1000條元組，并隨機(jī)地將元組中的某些屬性改為“*”。經(jīng)觀察，串行查詢程序與并行查詢程序所得到的查詢結(jié)果是一致的，在本實(shí)驗(yàn)中，主要討論并行查詢程序?qū)τ诖谐绦虻募铀俦?，因此，查詢的具體結(jié)果便不再討論。串行查詢與并行查詢的程序運(yùn)行時(shí)間如圖7.6所示。圖7.6

查詢程序運(yùn)行時(shí)間7.3.1查詢實(shí)驗(yàn)結(jié)果分析

盡管在并行查詢中，每臺(tái)機(jī)器所查詢的立方體單元數(shù)目基本上只相當(dāng)于串行查詢中立方體單元數(shù)目的三分之一，如圖7.7所示，但通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，并行查詢程序的性能加速比并未能夠達(dá)到理想的加速比，如圖7.8，只能達(dá)到2倍左右的性能加速。對(duì)其原因進(jìn)行分析，發(fā)現(xiàn)這是由于查詢語(yǔ)句未能直接命中，會(huì)造成額外開(kāi)銷的問(wèn)題（本文4.3節(jié)中提到）所造成的。圖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在A機(jī)器的商立方體中進(jìn)行查詢時(shí)，q的覆蓋集里面的所有元組在預(yù)計(jì)算時(shí)可能都沒(méi)有分配到A機(jī)器上。在這種情況下，q在A上的查詢便會(huì)產(chǎn)生巨大的額外開(kāi)銷：首先會(huì)從q所在層次h1里的單元中開(kāi)始查找，在h1找不到的情況下，會(huì)繼續(xù)查找h1的下一層h2。但是由于q在A上是無(wú)法命中的，查詢程序會(huì)一層接著一層地往下掃描下去，直到掃描完最后一層。隨機(jī)生成的1000條點(diǎn)查詢語(yǔ)句是根據(jù)基表中的元組生成的，這樣在串行查詢中，較少會(huì)出現(xiàn)語(yǔ)句在某一層未能命中，需要掃描下一層的情況。然而在并行查詢中，由于元組的分布性，產(chǎn)生了較多的查詢不命中，使得程序必須進(jìn)行額外的層次掃描，而且這種額外的層次掃描的代價(jià)十分巨大。在并行查詢中，開(kāi)銷巨大額外的層次掃描使得查詢的時(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ò)展性。第八章總結(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ì)算和查詢技術(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)該實(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ī)器的磁盤(pán)I/O帶寬。同時(shí)本文提出的并行預(yù)計(jì)算和并行查詢方法存在的一些不足：(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)基表元組的映射可以提高預(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ī)上命中查詢。如果可以預(yù)先判斷出查詢不命中，則可以減少許多額外的層次掃描開(kāi)銷，提高效率。預(yù)先的判斷應(yīng)該可以