到時(shí)差計(jì)算中并行相關(guān)算法實(shí)驗(yàn)及性能分析

閆廣等

摘 要：針對(duì)震動(dòng)波波速成像過(guò)程中遇到的海量數(shù)據(jù)處理問(wèn)題，提出了分布式實(shí)現(xiàn)到時(shí)差相關(guān)運(yùn)算，提出了在MapReduce框架下到時(shí)差計(jì)算的程序設(shè)計(jì)思路，并在hadhoop環(huán)境下進(jìn)行測(cè)試。測(cè)試結(jié)果表明使用MapReduce作為海量傳感器數(shù)據(jù)的處理框架是可行的；在進(jìn)行并行的到時(shí)差相關(guān)運(yùn)算時(shí)，hadoop集群運(yùn)算所需時(shí)間受待計(jì)算數(shù)據(jù)量和data node個(gè)數(shù)的影響，待計(jì)算數(shù)據(jù)量越大，或data node個(gè)數(shù)越少，運(yùn)算所需時(shí)間越長(zhǎng)，但這兩組關(guān)系均非線性；平均Map時(shí)間與待計(jì)算數(shù)據(jù)量和data node個(gè)數(shù)無(wú)關(guān)，僅與Map函數(shù)的執(zhí)行內(nèi)容有關(guān)。

關(guān)鍵詞：到時(shí)差；分布式礦震監(jiān)測(cè)；MapReduce框架；hadoop集群；計(jì)算用時(shí)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）02-00-04

0 引 言

對(duì)于煤礦井下的地震勘探來(lái)說(shuō)，其探測(cè)的尺度相對(duì)于一般的地震勘探來(lái)說(shuō)要小得多，為了實(shí)現(xiàn)小尺寸地質(zhì)結(jié)構(gòu)的探測(cè)，傳感器的布置相對(duì)來(lái)說(shuō)要更密集些[1]。隨著傳感器布置密度的提高，地震勘探系統(tǒng)采集到的數(shù)據(jù)量將隨之增加，在使用單機(jī)進(jìn)行處理的情況下，到時(shí)差的計(jì)算及后續(xù)的反演計(jì)算用時(shí)將隨之延長(zhǎng)[2]，這對(duì)系統(tǒng)的實(shí)時(shí)性是極為不利的。

針對(duì)待處理數(shù)據(jù)量激增的情況，本文基于MapReduce并行計(jì)算系統(tǒng)引入數(shù)據(jù)處理過(guò)程，以實(shí)際的震動(dòng)數(shù)據(jù)為例，測(cè)試并分析了并行計(jì)算系統(tǒng)計(jì)算到時(shí)差的用時(shí)與待處理數(shù)據(jù)量、計(jì)算用時(shí)和集群節(jié)點(diǎn)之間的關(guān)系。本文的主要貢獻(xiàn)在于：

（1）提出了到時(shí)差計(jì)算中相關(guān)算法的并行實(shí)現(xiàn)思路。

（2）測(cè)試并分析了并行相關(guān)算法的性能及影響因素，給出了進(jìn)一步改進(jìn)的思路。

1 背景知識(shí)與問(wèn)題描述

1.1 煤炭井下震動(dòng)波波速成像原理

震動(dòng)波波速成像原理如圖1所示。

當(dāng)介質(zhì)均勻時(shí)，可以認(rèn)為震波沿直線傳播，此時(shí)，可以通過(guò)測(cè)量震波到達(dá)各傳感器的到時(shí)差來(lái)計(jì)算介質(zhì)的平均速度[3]。當(dāng)介質(zhì)不均勻時(shí)，認(rèn)為震波的傳播路徑將按照斯奈爾定律在不同介質(zhì)的分界面上發(fā)生改變，假設(shè)圖1中各方格速度為v1·vn，震動(dòng)波波速成像體現(xiàn)為尋找到一組最佳的v1·vn組合，使得通過(guò)射線追蹤方法計(jì)算得到的震波理論到時(shí)與實(shí)測(cè)到時(shí)之間的誤差最小[4]。

圖1 震動(dòng)波波速成像原理

各傳感器間到時(shí)差的測(cè)量可以通過(guò)對(duì)不同傳感器接收到的震動(dòng)信號(hào)的相關(guān)計(jì)算來(lái)實(shí)現(xiàn)，實(shí)現(xiàn)的方法如下：

假設(shè)傳感器c1接收到的震動(dòng)信號(hào)為序列x（n），傳感器c2接收到的震動(dòng)信號(hào)序列為y（n），定義信號(hào)x（n）與信號(hào)y（n）的互相關(guān)函數(shù)為：，該式表示rxy（n）在時(shí)刻m時(shí)的值，等于將x（n）保持不動(dòng)而y（n）移動(dòng)m個(gè)采樣周期后兩個(gè)序列對(duì)應(yīng)相乘再相加的結(jié)果。從互相關(guān)函數(shù)的定義式可見(jiàn)，當(dāng)c1和c2接收到的為經(jīng)過(guò)同一路徑到達(dá)的震波，在不考慮不同頻率衰減的情況下，相關(guān)法測(cè)得的到時(shí)差精度僅取決于采樣周期。

1.2 分布式礦震監(jiān)測(cè)系統(tǒng)

分布式礦震監(jiān)測(cè)系統(tǒng)結(jié)構(gòu)如圖2所示：

系統(tǒng)工作過(guò)程如下：礦震傳感器通過(guò)授時(shí)子網(wǎng)保持各傳感器之間的高精度時(shí)鐘同步，經(jīng)測(cè)試，時(shí)鐘同步精度小于1μs。礦震傳感器在采集到震動(dòng)信號(hào)以后將震動(dòng)信號(hào)及接收到信號(hào)的時(shí)間通過(guò)數(shù)據(jù)傳輸子網(wǎng)發(fā)送到數(shù)據(jù)中心進(jìn)行處理，用戶通過(guò)因特網(wǎng)訪問(wèn)數(shù)據(jù)中心即可對(duì)采集到的震動(dòng)信號(hào)進(jìn)行查看[5]。

圖2 分布式礦震監(jiān)測(cè)系統(tǒng)

礦震傳感器使用ADI公司出品的AD7606芯片作為A/D轉(zhuǎn)換器，支持8通道同步采樣，采樣分辨率為16 b，最高采樣率可達(dá)200 kSPS。由于分布式礦震監(jiān)測(cè)系統(tǒng)以以太網(wǎng)作為數(shù)據(jù)傳輸通路，因此，在網(wǎng)絡(luò)帶寬允許的前提下，礦震傳感器的布置個(gè)數(shù)不受限制。

1.3 MapReduce框架

MapReduce框架的工作流程如圖3所示：

圖3 MapReduce框架的工作流程

在MapReduce框架中，用戶需指定Map和Reduce函數(shù)的工作內(nèi)容[6]。Map函數(shù)讀入輸入的鍵值對(duì)（Key/Value），然后根據(jù)用戶的需要完成指定的工作，處理完成后，Map函數(shù)將結(jié)果保存為一系列的中間鍵值對(duì)[7]。Reduce函數(shù)合并所有具有相同鍵值的中間鍵值對(duì)，按照用戶的需求完成指定工作后將結(jié)果輸出給用戶。

從MapReduce框架的工作流程中可以看出，Map函數(shù)之間和Reduce函數(shù)之間均是并行執(zhí)行的，因此，MapReduce模型的數(shù)據(jù)處理能力僅受限于Map和Reduce的個(gè)數(shù)，當(dāng)待處理數(shù)據(jù)量增大時(shí)，可以通過(guò)增加Map和Reduce的個(gè)數(shù)來(lái)提高集群的運(yùn)算能力。

1.4 問(wèn)題描述

從震動(dòng)波波速成像的過(guò)程可見(jiàn)，提高網(wǎng)格劃分密度將提高反演的精細(xì)度和質(zhì)量，而隨著網(wǎng)格劃分密度的提高，要使v1+vn能夠收斂到唯一解，則需要提高穿過(guò)網(wǎng)格的射線密度[8]。提高射線密度的方法有兩種思路，一是保持礦震傳感器數(shù)量不變，提高震動(dòng)的次數(shù)，二是保持震動(dòng)次數(shù)不變，提高礦震傳感器的數(shù)量。顯然，在實(shí)際情況下，當(dāng)震動(dòng)次數(shù)一定的時(shí)候，提高礦震傳感器的數(shù)量是唯一可行的方法。

礦震傳感器數(shù)量的提高意味著傳感器之間道間距的縮小，隨著道間距的縮小，震波到達(dá)傳感器的到時(shí)差也相應(yīng)縮小[9]，因此，各傳感器節(jié)點(diǎn)間到時(shí)差的測(cè)量精度也應(yīng)該相應(yīng)提高。從1.1中的分析可知，相關(guān)法的到時(shí)差測(cè)量精度取決于采樣周期，因此，若要實(shí)現(xiàn)高精度的時(shí)差測(cè)量，應(yīng)降低采樣周期亦即提高采樣頻率。

顯然，當(dāng)信號(hào)的采樣頻率提高時(shí)，在保持傳感器數(shù)量和采樣分辨率不變的前提下，信號(hào)所需要的傳輸帶寬將相應(yīng)提高，舉例如下：

假設(shè)某煤礦井下布設(shè)的單分量礦震傳感器數(shù)量為100個(gè)，信號(hào)的采樣頻率為1 kSPS，即到時(shí)差的測(cè)量精度為1 ms，則信號(hào)傳輸所需的最小帶寬可計(jì)算如下：

B=16/8×1 000×100=200 KB/s （1）

隨著道間距的縮小，需要提高采樣頻率，假設(shè)采樣頻率提高到1 MSPS，此時(shí)到時(shí)差的測(cè)量精度為1 μs，則信號(hào)傳輸所需的最小帶寬為：

B=16/8×1 000 000×100=200 KB/s （2）

可見(jiàn)，采樣頻率相較原來(lái)提高k倍，將導(dǎo)致信號(hào)傳輸所需的最小帶寬相應(yīng)提高k倍，存儲(chǔ)和處理這些數(shù)據(jù)所需的計(jì)算量將很容易超過(guò)單機(jī)的處理能力。

2 MapReduce框架下相關(guān)算法設(shè)計(jì)

從1.4中的分析可見(jiàn)，當(dāng)信號(hào)采樣頻率提高時(shí)，海量傳感器數(shù)據(jù)的處理將超出單機(jī)處理能力，而MapReduce框架作為一種并行處理方法，其處理能力可以隨著機(jī)器數(shù)的增加而增加[9]，因此，使用MapReduce作為海量傳感器數(shù)據(jù)的處理框架是可行的。

當(dāng)分布式礦震監(jiān)測(cè)系統(tǒng)中的數(shù)據(jù)中心接收到海量的傳感器數(shù)據(jù)后的數(shù)據(jù)處理過(guò)程分為如下幾個(gè)步驟：（1）數(shù)據(jù)被存儲(chǔ)到分布式文件系統(tǒng)中，在分布式文件系統(tǒng)中，為了保證存儲(chǔ)的可靠性，文件一般會(huì)被保存為N份副本；（2）識(shí)別礦震信號(hào)，并將有效的礦震信號(hào)取出；（3）針對(duì)某一次礦震，計(jì)算相鄰礦震傳感器節(jié)點(diǎn)之間的到時(shí)差；（4）根據(jù)到時(shí)差反演監(jiān)測(cè)區(qū)域的速度分布情況。

本文僅針對(duì)數(shù)據(jù)處理過(guò)程中的步驟（3），提出MapReduce框架下到時(shí)差計(jì)算的程序設(shè)計(jì)思路并在hadoop環(huán)境[10] 下對(duì)這種思路的性能進(jìn)行測(cè)試。

根據(jù)1.1中相關(guān)計(jì)算的公式，信號(hào)x（n）與信號(hào)y（n）的互相關(guān)函數(shù)定義為：

（3）

假設(shè)兩信號(hào)的實(shí)際到時(shí)差為m'，則當(dāng)m=m'時(shí)rxy（m）將取得最大值，為了找到這個(gè)值，需要在m1≤m≤m2的范圍內(nèi)計(jì)算rxy（m）的值并找到其中的最大值，一般取，m1=-D12/V，m2=D12/V，其中D12為傳感器c1和傳感器c2間距，V為介質(zhì)中震波的平均速度。

顯然，當(dāng)m取不同的點(diǎn)時(shí)序列互相關(guān)值的計(jì)算是相互獨(dú)立的，可以設(shè)計(jì)為并行算法實(shí)現(xiàn)。因此，可將MapReduce框架下相關(guān)算法的實(shí)現(xiàn)思路設(shè)計(jì)如下[6]：

（1）根據(jù)待計(jì)算的序列值生成所有待計(jì)算的序列對(duì)或等價(jià)的計(jì)算式，比如，待計(jì)算序列為x（n）和y（n），則其所有待計(jì)算的序列對(duì)為x（n）·y（n+m1）…x（n）·y（n+m2）。

（2）Map函數(shù)將計(jì)算對(duì)作為Value讀入，并將計(jì)算結(jié)果作為Value輸出給Reduce函數(shù)。

（3）Reduce函數(shù)將計(jì)算結(jié)果輸出即得序列的相關(guān)結(jié)果。

本實(shí)驗(yàn)中，待計(jì)算序列保存為txt格式的單一文件，兩相鄰的序列用0X0D和0X0A間隔開(kāi)，同一行中的兩個(gè)序列x（n）與y（n+m）用0X21間隔開(kāi)。最終生成的文件格式如下：

（4）

應(yīng)注意的是，這樣生成的待計(jì)算序列將占用較大的存儲(chǔ)空間，不適用于實(shí)時(shí)或準(zhǔn)實(shí)時(shí)計(jì)算。

Map函數(shù)的執(zhí)行流程如圖4所示：

圖4 Map函數(shù)的執(zhí)行流程

Reduce函數(shù)將接收到的值不做處理直接輸出即可得互相關(guān)序列。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

由16臺(tái)普通PC組成集群，一臺(tái)機(jī)器作為name node，其余15臺(tái)機(jī)器作為data node，機(jī)器配置相同，具體配置如表1所示。

表1 PC集群的配置

CPU 內(nèi)存 硬盤 網(wǎng)卡 操作系統(tǒng) Hadoop版本 JDK版本

Intel Pentium E5300 DDR3

1 GB 500 GB 7 200轉(zhuǎn) SATA2 100 M Ubuntu 13.10 server 2.2.0 1.7.0_71-b14

實(shí)驗(yàn)數(shù)據(jù)為兩組實(shí)測(cè)的震動(dòng)數(shù)據(jù)，數(shù)據(jù)采樣率為1MSPS，數(shù)據(jù)位數(shù)16 b，時(shí)長(zhǎng)10 ms，每個(gè)序列的數(shù)據(jù)點(diǎn)數(shù)為104個(gè)，如圖5所示。

3.2 實(shí)驗(yàn)內(nèi)容與結(jié)果

3.2.1 運(yùn)算量與平均運(yùn)算速度

按照公式（4）所示格式，以100行為間隔，依次生成待計(jì)算數(shù)據(jù)，最終生成1 500行待計(jì)算數(shù)據(jù)，依次將數(shù)據(jù)傳入HDFS并啟動(dòng)互相關(guān)算法，多次實(shí)驗(yàn)，記錄作業(yè)完成時(shí)間的平均值，實(shí)驗(yàn)結(jié)果如圖6所示。

圖5 兩組實(shí)測(cè)震動(dòng)數(shù)據(jù)

圖6 實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出，隨著運(yùn)算量的增加，算法執(zhí)行的平均時(shí)間也隨之增加，但平均執(zhí)行時(shí)間與運(yùn)算量之間并非線性關(guān)系。

定義執(zhí)行時(shí)間的變化率為，則平均執(zhí)行時(shí)間的變化率如圖7所示。

圖7 平均執(zhí)行時(shí)間變化率

可見(jiàn)，當(dāng)待計(jì)算數(shù)據(jù)行數(shù)在100～600范圍內(nèi)的時(shí)候，平均執(zhí)行時(shí)間的變化率較小。通過(guò)hadoop日志分析發(fā)現(xiàn)，當(dāng)待計(jì)算數(shù)據(jù)行數(shù)超過(guò)600時(shí)系統(tǒng)出現(xiàn)Map任務(wù)排隊(duì)，說(shuō)明此時(shí)待執(zhí)行的總Map任務(wù)數(shù)超過(guò)系統(tǒng)最大并發(fā)任務(wù)數(shù)，因此平均執(zhí)行時(shí)間會(huì)延長(zhǎng)。

3.2.2 運(yùn)算量與平均Map時(shí)間

在3.2.1所述實(shí)驗(yàn)過(guò)程中，記錄每次互相關(guān)計(jì)算的每次Map任務(wù)執(zhí)行的平均時(shí)間，實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 實(shí)驗(yàn)結(jié)果

平均Map時(shí)間的變化率如圖9所示：

圖9 平均Map時(shí)間的變化率

對(duì)比平均Map時(shí)間變化率和平均執(zhí)行時(shí)間變化率可見(jiàn)，平均Map時(shí)間與運(yùn)算量之間無(wú)明顯關(guān)系。

3.2.3 節(jié)點(diǎn)數(shù)與平均運(yùn)算速度

按照公式（4）所示格式，生成1 100行待計(jì)算數(shù)據(jù)，將數(shù)據(jù)送入有6個(gè)data node的集群中，保持?jǐn)?shù)據(jù)量不變，依次增加data node的個(gè)數(shù)直至15個(gè)data node為止，多次實(shí)驗(yàn)，記錄作業(yè)完成的平均時(shí)間，實(shí)驗(yàn)結(jié)果如圖10所示：

圖10 1 100行數(shù)據(jù)平均執(zhí)行時(shí)間

1 100行數(shù)據(jù)平均執(zhí)行時(shí)間的變化率如圖11所示：

圖11 1 100行數(shù)據(jù)平均執(zhí)行時(shí)間變化率

顯然，對(duì)于相同的運(yùn)算量來(lái)說(shuō)，data node數(shù)的增加將降低平均執(zhí)行時(shí)間，加快執(zhí)行速度，但節(jié)點(diǎn)數(shù)和平均執(zhí)行時(shí)間的關(guān)系并非線性的，隨著節(jié)點(diǎn)數(shù)的增加，平均執(zhí)行時(shí)間的下降速率是減小的。

3.2.4 節(jié)點(diǎn)數(shù)與平均Map時(shí)間

在3.2.3的實(shí)驗(yàn)中平均Map時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系如圖12所示：

圖12 平均Map時(shí)間與節(jié)點(diǎn)數(shù)的關(guān)系

可見(jiàn)，平均Map時(shí)間不受節(jié)點(diǎn)數(shù)的影響，此外，比照3.2.2中的平均Map時(shí)間可以發(fā)現(xiàn)，兩次實(shí)驗(yàn)中的平均Map時(shí)間基本一致，這說(shuō)明平均Map時(shí)間與運(yùn)算量、節(jié)點(diǎn)數(shù)無(wú)關(guān)。

4 結(jié) 語(yǔ)

本文針對(duì)震動(dòng)波波速成像過(guò)程中遇到的海量數(shù)據(jù)處理問(wèn)題，提出在分布式條件下實(shí)現(xiàn)到時(shí)差相關(guān)運(yùn)算的思路并以此思路為基礎(chǔ)完成相關(guān)實(shí)驗(yàn)，從實(shí)驗(yàn)結(jié)果來(lái)看，可以得到以下幾點(diǎn)結(jié)論：

（1）到時(shí)差相關(guān)運(yùn)算的并行實(shí)現(xiàn)可分成兩個(gè)步驟實(shí)現(xiàn)，首先將待計(jì)算序列轉(zhuǎn)化為待計(jì)算序列對(duì)，然后將所有待計(jì)算序列對(duì)送入并行計(jì)算系統(tǒng)即可得計(jì)算結(jié)果。但是在具體實(shí)現(xiàn)時(shí)應(yīng)注意的是，如果直接將待計(jì)算序列按照本文所述方法進(jìn)行轉(zhuǎn)化的話會(huì)造成待計(jì)算序列對(duì)體積的急劇膨脹，不利于提高計(jì)算的速度。

（2）在進(jìn)行并行的到時(shí)差相關(guān)運(yùn)算時(shí)，hadoop集群運(yùn)算所需時(shí)間受待計(jì)算數(shù)據(jù)量和data node個(gè)數(shù)的影響，待計(jì)算數(shù)據(jù)量越大，或data node個(gè)數(shù)越少，運(yùn)算所需時(shí)間越長(zhǎng)，但這兩組關(guān)系均非線性。對(duì)于某一次具體運(yùn)算來(lái)說(shuō)，當(dāng)待計(jì)算數(shù)據(jù)量小于集群最大并行計(jì)算量時(shí)運(yùn)算所需時(shí)間最小。

（3）平均Map時(shí)間與待計(jì)算數(shù)據(jù)量和data node個(gè)數(shù)無(wú)關(guān)，僅與Map函數(shù)的執(zhí)行內(nèi)容有關(guān)。

參考文獻(xiàn)

[1] 左國(guó)平. 地震記錄初至拾取方法對(duì)比和研究 [D].北京：中國(guó)地質(zhì)大學(xué)， 2006.

[2] 張凌云. 高密度電阻率勘探反演的非線性方法研究 [D].太原：太原理工大學(xué)，2011.

[3] Xiang Z， Ce Y. Fast n-point correlation function approximation with recursive convolution for scalar fields[C]. IEEE 3rd International Conference on Cloud Computing Technology and Science （CloudCom 2011）， Los Alamitos， USA： IEEE Computer Society，2011.

[4] 靳朋飛， 曹菡， 余婧，等. MapReduce模型下Voronoi圖柵格生成算法[J]. 計(jì)算機(jī)科學(xué)與探索，2013（2）：160-167.

[5] 賈寶新. 礦震監(jiān)測(cè)的理論與應(yīng)用研究 [D]. 阜新：遼寧工程技術(shù)大學(xué)，2013.

[6] 劉義， 景寧， 陳犖，等. MapReduce框架下基于R-樹(shù)的k-近鄰連接算法[J]. 軟件學(xué)報(bào). 2013，24（8）：1836-1851.

[7] Afrati F N， Ullman J D. Optimizing joins in a map-reduce environment[C]. 13th International Conference on Extending Database Technology： Advances in Database Technology， Lausanne， Switzerland： Association for Computing Machinery，2010.

[8] 顧漢明， 周鴻秋， 張學(xué)強(qiáng). 初至?xí)r間的自動(dòng)拾取[J]. 物探與化探. 1992（2）：120-128.

[9] 黃翼堅(jiān). 多井源距VSP速度分析及逆時(shí)偏移 [D].西安：長(zhǎng)安大學(xué)，2010.

[10] Joshi S B.Apache hadoop performance-tuning methodologies and best practices[C]. 3rd Joint WOSP/SIPEW International Conference on Performance Engineering， Boston， United states： Association for Computing Machinery，2012.