到時差計算中并行相關算法實驗及性能分析

閆廣等

摘 要：針對震動波波速成像過程中遇到的海量數據處理問題，提出了分布式實現到時差相關運算，提出了在MapReduce框架下到時差計算的程序設計思路，并在hadhoop環境下進行測試。測試結果表明使用MapReduce作為海量傳感器數據的處理框架是可行的；在進行并行的到時差相關運算時，hadoop集群運算所需時間受待計算數據量和data node個數的影響，待計算數據量越大，或data node個數越少，運算所需時間越長，但這兩組關系均非線性；平均Map時間與待計算數據量和data node個數無關，僅與Map函數的執行內容有關。

關鍵詞：到時差；分布式礦震監測；MapReduce框架；hadoop集群；計算用時

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2015）02-00-04

0 引 言

對于煤礦井下的地震勘探來說，其探測的尺度相對于一般的地震勘探來說要小得多，為了實現小尺寸地質結構的探測，傳感器的布置相對來說要更密集些[1]。隨著傳感器布置密度的提高，地震勘探系統采集到的數據量將隨之增加，在使用單機進行處理的情況下，到時差的計算及后續的反演計算用時將隨之延長[2]，這對系統的實時性是極為不利的。

針對待處理數據量激增的情況，本文基于MapReduce并行計算系統引入數據處理過程，以實際的震動數據為例，測試并分析了并行計算系統計算到時差的用時與待處理數據量、計算用時和集群節點之間的關系。本文的主要貢獻在于：

（1）提出了到時差計算中相關算法的并行實現思路。

（2）測試并分析了并行相關算法的性能及影響因素，給出了進一步改進的思路。

1 背景知識與問題描述

1.1 煤炭井下震動波波速成像原理

震動波波速成像原理如圖1所示。

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

圖1 震動波波速成像原理

各傳感器間到時差的測量可以通過對不同傳感器接收到的震動信號的相關計算來實現，實現的方法如下：

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

1.2 分布式礦震監測系統

分布式礦震監測系統結構如圖2所示：

系統工作過程如下：礦震傳感器通過授時子網保持各傳感器之間的高精度時鐘同步，經測試，時鐘同步精度小于1μs。礦震傳感器在采集到震動信號以后將震動信號及接收到信號的時間通過數據傳輸子網發送到數據中心進行處理，用戶通過因特網訪問數據中心即可對采集到的震動信號進行查看[5]。

圖2 分布式礦震監測系統

礦震傳感器使用ADI公司出品的AD7606芯片作為A/D轉換器，支持8通道同步采樣，采樣分辨率為16 b，最高采樣率可達200 kSPS。由于分布式礦震監測系統以以太網作為數據傳輸通路，因此，在網絡帶寬允許的前提下，礦震傳感器的布置個數不受限制。

1.3 MapReduce框架

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

圖3 MapReduce框架的工作流程

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

從MapReduce框架的工作流程中可以看出，Map函數之間和Reduce函數之間均是并行執行的，因此，MapReduce模型的數據處理能力僅受限于Map和Reduce的個數，當待處理數據量增大時，可以通過增加Map和Reduce的個數來提高集群的運算能力。

1.4 問題描述

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

礦震傳感器數量的提高意味著傳感器之間道間距的縮小，隨著道間距的縮小，震波到達傳感器的到時差也相應縮小[9]，因此，各傳感器節點間到時差的測量精度也應該相應提高。從1.1中的分析可知，相關法的到時差測量精度取決于采樣周期，因此，若要實現高精度的時差測量，應降低采樣周期亦即提高采樣頻率。

顯然，當信號的采樣頻率提高時，在保持傳感器數量和采樣分辨率不變的前提下，信號所需要的傳輸帶寬將相應提高，舉例如下：

假設某煤礦井下布設的單分量礦震傳感器數量為100個，信號的采樣頻率為1 kSPS，即到時差的測量精度為1 ms，則信號傳輸所需的最小帶寬可計算如下：

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

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

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

可見，采樣頻率相較原來提高k倍，將導致信號傳輸所需的最小帶寬相應提高k倍，存儲和處理這些數據所需的計算量將很容易超過單機的處理能力。

2 MapReduce框架下相關算法設計

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

當分布式礦震監測系統中的數據中心接收到海量的傳感器數據后的數據處理過程分為如下幾個步驟：（1）數據被存儲到分布式文件系統中，在分布式文件系統中，為了保證存儲的可靠性，文件一般會被保存為N份副本；（2）識別礦震信號，并將有效的礦震信號取出；（3）針對某一次礦震，計算相鄰礦震傳感器節點之間的到時差；（4）根據到時差反演監測區域的速度分布情況。

本文僅針對數據處理過程中的步驟（3），提出MapReduce框架下到時差計算的程序設計思路并在hadoop環境[10] 下對這種思路的性能進行測試。

根據1.1中相關計算的公式，信號x（n）與信號y（n）的互相關函數定義為：

（3）

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

顯然，當m取不同的點時序列互相關值的計算是相互獨立的，可以設計為并行算法實現。因此，可將MapReduce框架下相關算法的實現思路設計如下[6]：

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

（2）Map函數將計算對作為Value讀入，并將計算結果作為Value輸出給Reduce函數。

（3）Reduce函數將計算結果輸出即得序列的相關結果。

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

（4）

應注意的是，這樣生成的待計算序列將占用較大的存儲空間，不適用于實時或準實時計算。

Map函數的執行流程如圖4所示：

圖4 Map函數的執行流程

Reduce函數將接收到的值不做處理直接輸出即可得互相關序列。

3 實驗結果與分析

3.1 實驗環境

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

表1 PC集群的配置

CPU 內存 硬盤 網卡 操作系統 Hadoop版本 JDK版本

Intel Pentium E5300 DDR3

1 GB 500 GB 7 200轉 SATA2 100 M Ubuntu 13.10 server 2.2.0 1.7.0_71-b14

實驗數據為兩組實測的震動數據，數據采樣率為1MSPS，數據位數16 b，時長10 ms，每個序列的數據點數為104個，如圖5所示。

3.2 實驗內容與結果

3.2.1 運算量與平均運算速度

按照公式（4）所示格式，以100行為間隔，依次生成待計算數據，最終生成1 500行待計算數據，依次將數據傳入HDFS并啟動互相關算法，多次實驗，記錄作業完成時間的平均值，實驗結果如圖6所示。

圖5 兩組實測震動數據

圖6 實驗結果

從實驗結果可以看出，隨著運算量的增加，算法執行的平均時間也隨之增加，但平均執行時間與運算量之間并非線性關系。

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

圖7 平均執行時間變化率

可見，當待計算數據行數在100～600范圍內的時候，平均執行時間的變化率較小。通過hadoop日志分析發現，當待計算數據行數超過600時系統出現Map任務排隊，說明此時待執行的總Map任務數超過系統最大并發任務數，因此平均執行時間會延長。

3.2.2 運算量與平均Map時間

在3.2.1所述實驗過程中，記錄每次互相關計算的每次Map任務執行的平均時間，實驗結果如圖8所示。

圖8 實驗結果

平均Map時間的變化率如圖9所示：

圖9 平均Map時間的變化率

對比平均Map時間變化率和平均執行時間變化率可見，平均Map時間與運算量之間無明顯關系。

3.2.3 節點數與平均運算速度

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

圖10 1 100行數據平均執行時間

1 100行數據平均執行時間的變化率如圖11所示：

圖11 1 100行數據平均執行時間變化率

顯然，對于相同的運算量來說，data node數的增加將降低平均執行時間，加快執行速度，但節點數和平均執行時間的關系并非線性的，隨著節點數的增加，平均執行時間的下降速率是減小的。

3.2.4 節點數與平均Map時間

在3.2.3的實驗中平均Map時間與節點數的關系如圖12所示：

圖12 平均Map時間與節點數的關系

可見，平均Map時間不受節點數的影響，此外，比照3.2.2中的平均Map時間可以發現，兩次實驗中的平均Map時間基本一致，這說明平均Map時間與運算量、節點數無關。

4 結 語

本文針對震動波波速成像過程中遇到的海量數據處理問題，提出在分布式條件下實現到時差相關運算的思路并以此思路為基礎完成相關實驗，從實驗結果來看，可以得到以下幾點結論：

（1）到時差相關運算的并行實現可分成兩個步驟實現，首先將待計算序列轉化為待計算序列對，然后將所有待計算序列對送入并行計算系統即可得計算結果。但是在具體實現時應注意的是，如果直接將待計算序列按照本文所述方法進行轉化的話會造成待計算序列對體積的急劇膨脹，不利于提高計算的速度。

（2）在進行并行的到時差相關運算時，hadoop集群運算所需時間受待計算數據量和data node個數的影響，待計算數據量越大，或data node個數越少，運算所需時間越長，但這兩組關系均非線性。對于某一次具體運算來說，當待計算數據量小于集群最大并行計算量時運算所需時間最小。

（3）平均Map時間與待計算數據量和data node個數無關，僅與Map函數的執行內容有關。

參考文獻

[1] 左國平. 地震記錄初至拾取方法對比和研究 [D].北京：中國地質大學， 2006.

[2] 張凌云. 高密度電阻率勘探反演的非線性方法研究 [D].太原：太原理工大學，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]. 計算機科學與探索，2013（2）：160-167.

[5] 賈寶新. 礦震監測的理論與應用研究 [D]. 阜新：遼寧工程技術大學，2013.

[6] 劉義， 景寧， 陳犖，等. MapReduce框架下基于R-樹的k-近鄰連接算法[J]. 軟件學報. 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] 顧漢明， 周鴻秋， 張學強. 初至時間的自動拾取[J]. 物探與化探. 1992（2）：120-128.

[9] 黃翼堅. 多井源距VSP速度分析及逆時偏移 [D].西安：長安大學，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.