《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》是中國石油天然氣集團公司、中國石油集團東方地球物理勘探有限責任公司於2012年9月28日申請的專利，該專利的公布號為CN103698809A，申請公布日為2014年4月2日，發明人是王獅虎、趙波、王成祥、寇芹、羅國安、祝寬海、錢忠平。該發明涉及石油地球物理勘探地震數據的處理技術。
《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》將輸出空間細分為線號、炮檢距等四維，根據最小炮檢距、最大炮檢距、炮檢距增量參數計算炮檢距個數，把所有參與計算的節點進行分組，每組內的節點數目均勻，同一組內的節點在節點名的順序連續，每一組節點一次計算一個炮檢距組分的疊前時間偏移。該發明實現地震數據最小量網路傳遞，徹底解決了克希霍夫疊前時間偏移的網路傳遞密集型問題，可以使計算硬體規模擴展，使疊前時間偏移地計算周期縮短。
2017年12月11日，《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》獲得第十九屆中國專利優秀獎。
（概述圖為《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》摘要附圖）
基本介紹
- 中文名：一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法
- 申請人：中國石油天然氣集團公司、中國石油集團東方地球物理勘探有限責任公司
- 申請日：2012年9月28日
- 申請號：2012103676727
- 公布號：CN103698809A
- 公布日：2014年4月2日
- 發明人：王獅虎、趙波、王成祥、寇芹、羅國安、祝寬海、錢忠平
- 地址：北京市東城區東直門北大街9號中國石油大廈
- 代理機構：北京市中實友智慧財產權代理有限責任公司
- 代理人：劉天語、湯琦
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,權利要求,實施方式,榮譽表彰,
專利背景
克希霍夫疊前時間偏移技術是地球物理勘探地震數據處理過程中最重要的一種時間域成像方法，該方法不但具有成像質量高、對速度模型要求低、不受野外數據觀測方式的限制等優點，另外它還能輸出基於炮檢距的共成像點道集，這類道集又是進一步速度分析重要的信息。
在水平地表情況下，Kirchhoff積分法偏移公式為：
其中成像點ξ=（xξ，yξ，zξ），對於時間偏移為ξ＝（xξ，yξ，τξ），I（ξ）是成像結果，D[t，m，h]是野外觀測的地震數據，m是共中心點，h是半炮檢距，Ωξ是偏移孔徑。疊前偏移過程就是對一系列觀測數據進行加權求和，W（ξ，m，h）是加權因子。tD（ξ，m，h）是由炮點到成像點再到接收點的旅行時間。
克希霍夫疊前時間偏移方法的數學表達雖然較為抽象，但其物理實現過程可簡單描述為：地震道從等待偏移數據空間到偏移結果數據空間多對多的映射，映射關係為雙平方根旅行時計算公式，在不考慮時變孔徑的條件下，克希霍夫疊前時間偏移就是把每一道等待偏移地震數據（炮檢距為h）映射到偏移結果數據集中的一個橢圓柱體中，圓柱體的軸心是當前等待偏移地震道按大地坐標在偏移結果空間中的投影位置。若偏移孔徑採用圓形且孔徑值為300，則一個等待偏移地震採樣點將要映射到282600（3.14*300*300）個偏移結果地震採樣點上。
在水平地表情況下，克希霍夫積分法偏移用公式為前面所述公式⑴。⑴式可以進行深度偏移，也可以完成時間偏移，當完成時間偏移式時，旅行時用圖1圖示，⑵式是計算公式。
公式中變數參看圖1。
結合公式⑴和⑵可以看出，完成一個地震樣點的疊前時間偏移要包括旅行時計算、振幅加權、積分求和等計算，另外還有反假頻濾波沒有在公式中表示出來。一般地，一個地震道包含幾千個地震樣點、一個工區包含幾千萬至幾億個地震道，所以一個工區疊前時間偏移的計算量是極其龐大的，傳統計算機的計算能力無法滿足疊前時間偏移計算量的要求。直到計算機集群集成技術的發展和普及後，地球物理勘探才開始研究並行克希霍夫疊前時間偏移方法，現在已形成了以下兩類算法：
一是輸入道並行算法，這種方法以觀測面上包含的面元總數為單位把整個偏移結果數據空間平均分配到參與計算的各個節點的記憶體中，待偏移數據空間中的每一道地震數據都要傳送到各個計算節點上，所有等待偏移的地震數據都偏移完成後，再把各個節點記憶體中的偏移結果合併成完整的偏移結果。主要缺點是網路間數據的傳輸量和節點個數成正比，對硬體的可擴展性受到了限制。
二是輸出道並行算法，這類方法一次完成輸出空間沿觀測線方向一條線（Inline）的偏移，因為一條Inline線的數據量不算太大，因此可以在每一個參與計算節點的記憶體中為整條線申請空間。把等待偏移數據空間中對當前Inline線有貢獻的所有數據按參與計算的節點個數進行平均分割，一個節點完成其中的一份數據的偏移計算任務。偏移結束後把各個節點記憶體中的偏移結果做求和操作並輸出，當前Inline線偏移結束，再轉入下一條輸出線偏移。主要缺點是地震數據的讀取量、網路傳輸數量和輸出空間inline線的個數以及參與並行計算的節點個數成一定的比例關係，隨著偏移工區增大、節點個數增大，地震數據的網路流量快速增長。
2012年前實際生產中疊前時間偏移會按照兩種方式運行，一種是目標線偏移，目的是最佳化偏移速度和偏移參數試驗等，另一種是體偏移，其目的是得到最終的疊前時間偏移結果。目標線偏移計算量較小採用輸出道並行算法效率較高，體偏移計算量較大採用輸入道並行算法效率較高。
不管是輸入道並行算法還是輸出道並行算法，隨著計算節點個數增加地震數據網路流量將隨之增大。當計算機集群頻寬不能滿足疊前時間偏移程式地震數據的網路流量要求時，疊前時間偏移程式就會遇到加速比瓶頸，這時再增加計算的節點個數，偏移程式的運行時間反而會增加、運行效率降低。上述兩種方法都存在加速比瓶頸，國際權威機構統計的疊前時間偏移程式加速比瓶頸會在節點個數90附近出現。
發明內容
專利目的
該發明的目的是提供一種硬體可擴展、無加速比瓶頸的克希霍夫疊前時間偏移並行方法。
技術方案
《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》通過以下具體步驟實現：
1）野外採集得到的地震數據，進行靜校正、去噪、反褶積後對該數據進行預處理；
步驟1）所述的預處理過程是：
（1）收集每一道數據的炮點位置X坐標、炮點位置Y坐標、檢波點位置X坐標、檢波點位置Y坐標、沿測線方向（Inline）線號，垂直測線方向（Xline）線號信息；
（2）把等待偏移地震數據按照炮檢距（offset）、測線方向線號、垂直測線方向線號按照三級關鍵字分選，將每一個炮檢距數據保存為一個獨立的地震數據檔案；
（3）建立（1）中的道頭字信息和（2）中地震數據檔案相互對應關係。
2）根據最小炮檢距、最大炮檢距、炮檢距增量參數，按下式計算炮檢距個數：炮檢距個數=（最大炮檢距-最小炮檢距）/炮檢距增量；
3）把所有參與計算的節點進行分組，每組內的節點數目均勻，每組內的節點個數不小於4，同一組內的節點在節點名的順序連續；
4）根據炮檢距個數和節點個數進行並行計算分配，每一組節點一次計算一個炮檢距組分的疊前時間偏移；
步驟4）所述的任務分配按以下三種情況進行：
（1）當計算節點的分組個數等於疊前時間偏移的炮檢距個數，每一組節點計算一個炮檢距疊前時間偏移，當某一組節點完成計算後，其組內節點自動加入到當前進度最慢的一組協同計算；
（2）當計算節點的分組個數小於疊前時間偏移的炮檢距個數，每一組節點計算一個炮檢距疊前時間偏移，當某一組節點完成計算後，申請下一個炮檢距的計算；
（3）當計算節點的分組個數大於疊前時間偏移輸出的炮檢距個數，每一組節計算一個炮檢距疊前時間偏移，剩餘節點組依次分配加入其它組協同計算。
5）將步驟3）分組的第一個節點確定為組長（master）節點，組內其它節點作為組員（worker）節點；
6）根據偏移孔徑確定當前成像區間所需要的待偏移地震數距的範圍，具體方法為：待偏移地震數距的最小沿測線方向線號=當前成像區間的最小沿測線方向線號-（垂直測線方向的最大孔徑/線間距）；待偏移地震數距的最大沿測線方向線號=當前成像區間的最大沿測線方向線號+（垂直測線方向的最大孔徑/線間距）；
7）每一組的組長節點逐道讀取本炮檢距待偏移地震數據並按需分發到該組所有組員組長和組員節點；
8）每一個節點獨立完成各自分配到的克希霍夫疊前時間偏移計算任務；
9）重複步驟7）~8）完成一個炮檢距的克希霍夫疊前時間偏移；
10）每一組的組長節點回收該組組員節點的疊前時間偏移結果並進行疊加完成該組炮檢距數據的克希霍夫疊前時間偏移。
改善效果
《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》有以下特點：
⑴地震數據網路流量小，解決了傳統方法存在的加速比瓶頸問題，可以使並行規模無限制擴大。
⑵由於引入了共炮檢距數據集的概念，從數據流方面考慮疊前時間偏移和常用的疊後時間偏移的概念比較接近，使疊前時間偏移的並行任務分配方式變得非常簡單。
⑶將平均任務分配模式變為“能者多勞”式任務分配模式，更適合於異步通訊機制，從而解決了慢節點或故障節點對整體計算性能的影響。
該發明預先把地震數據按炮檢距進行分組，使各組地震數據之間沒有依賴關係，因此減少了傳統並行克希霍夫疊前時間偏移方法地震數據在網路上大量的冗餘傳遞，從而解決了網路傳遞密集型問題，可以使計算硬體規模擴展，使疊前時間偏移地計算周期縮短。
附圖說明
圖1水平地表旅行時計算圖；
圖2該發明並行任務分配圖；
圖3該發明的脈衝回響圖；
圖4輸入道並行方法的脈衝回響圖；
圖5該發明和輸入道並行方法地震數據網路流量對比圖；
圖6目標線偏移、體偏移運行效率對比測試結果圖，
左上：目標線偏移運行時間圖、右上：目標線偏移加速比曲線圖；左下：體偏移運行時間圖、右下：體偏移加速比曲線圖。
權利要求
1.《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》特點是通過以下具體步驟實現：
1）野外採集得到的地震數據，進行靜校正、去噪、反褶積後對該數據進行預處理；
2）根據最小炮檢距、最大炮檢距、炮檢距增量參數，按下式計算炮檢距個數：炮檢距個數=（最大炮檢距-最小炮檢距）/炮檢距增量；
3）把所有參與計算的節點進行分組，每組內的節點數目均勻，每組內的節點個數不小於4，同一組內的節點在節點名的順序連續；
4）根據炮檢距個數和節點個數進行並行計算分配，每一組節點一次計算一個炮檢距組分的疊前時間偏移；
5）將步驟3）分組的第一個節點確定為組長節點，組內其它節點作為組員節點；
6）根據偏移孔徑確定當前成像區間所需要的待偏移地震數距的範圍，具體方法為：待偏移地震數距的最小沿測線方向線號=當前成像區間的最小沿測線方向線號-（垂直測線方向的最大孔徑/線間距）；待偏移地震數距的最大沿測線方向線號=當前成像區間的最大沿測線方向線號+（垂直測線方向的最大孔徑/線間距）；
7）每一組的組長節點逐道讀取本炮檢距待偏移地震數據並按需分發到該組所有組員組長和組員節點；
8）每一個節點獨立完成各自分配到的克希霍夫疊前時間偏移計算任務；
9）重複步驟7）~8）完成一個炮檢距的克希霍夫疊前時間偏移；
10）每一組的組長節點回收該組組員節點的疊前時間偏移結果並進行疊加完成該組炮檢距數據的克希霍夫疊前時間偏移。
2.根據權利要求1的方法，特點是步驟1）所述的預處理過程是：
（1）收集每一道數據的炮點位置X坐標、炮點位置Y坐標、檢波點位置X坐標、檢波點位置Y坐標、沿測線方向線號，垂直測線方向線號信息；
（2）把等待偏移地震數據按照炮檢距、測線方向線號、垂直測線方向線號按照三級關鍵字分選，將每一個炮檢距數據保存為一個獨立的地震數據檔案；
（3）將以上步驟（1）中信息和以上步驟（2）中地震數據檔案相互對應。
3.根據權利要求1的方法，特點是步驟4）所述的任務分配按以下三種情況進行：
（1）當計算節點的分組個數等於疊前時間偏移的炮檢距個數，每一組節點計算一個炮檢距疊前時間偏移，當某一組節點完成計算後，其組內節點自動加入到當前進度最慢的一組協同計算；
（2）當計算節點的分組個數小於疊前時間偏移的炮檢距個數，每一組節點計算一個炮檢距疊前時間偏移，當某一組節點完成計算後，申請下一個炮檢距的計算；
（3）當計算節點的分組個數大於疊前時間偏移輸出的炮檢距個數，每一組節計算一個炮檢距疊前時間偏移，剩餘節點組依次分配加入其它組協同計算。
實施方式
《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》從算法本身上大大減少了地震數據在計算節點之間的傳輸總量，徹底解決了困擾疊前時間偏移並行算法的網路密集型問題。
該發明通過以下具體步驟實現：
1）野外採集得到的地震數據，進行靜校正、去噪、反褶積後對該數據進行預處理；
步驟1）所述的預處理過程是：
（1）收集每一道數據的炮點位置X坐標、炮點位置Y坐標、檢波點位置X坐標、檢波點位置Y坐標、沿測線方向（Inline）線號，垂直測線方向（Xline）線號信息；
（2）把等待偏移地震數據按照炮檢距（offset）、測線方向線號、垂直測線方向線號按照三級關鍵字分選，將每一個炮檢距數據保存為一個獨立的地震數據檔案；
（3）建立（1）中的道頭字信息和（2）中地震數據檔案相互對應關係。
2）根據最小炮檢距、最大炮檢距、炮檢距增量參數，圖2所示，按下式計算炮檢距個數：炮檢距個數=（最大炮檢距-最小炮檢距）/炮檢距增量。落在某一個炮檢距區間的所有等待偏移的數據僅僅對該炮檢距的偏移結果數據有貢獻，不會貢獻到其它偏移結果炮檢距上。據此把等待偏移的數據和偏移結果數據按照炮檢距區間進行分組，數據組之間沒有任何依賴關係。
3）把所有參與計算的計算機節點名編輯到一個ascii檔案中，每行一個節點名，形成節點名檔案。對該檔案中包含的所有節點進行分組。分組原則是：每組內的節點數目均勻；每組內的節點個數不小於4；同一組內的節點在節點名檔案中的順序應該連續。
4）根據步驟2）的炮檢距個數和步驟3）的節點個數進行並行計算分配，每一組節點一次計算一個炮檢距組分的疊前時間偏移；
步驟4）所述的任務分配按以下三種情況進行：
（1）當計算節點的分組個數等於疊前時間偏移的炮檢距個數，每一組節點計算一個炮檢距疊前時間偏移，當某一組節點完成計算後，其組內節點自動加入到當前進度最慢的一組協同計算；
（2）當計算節點的分組個數小於疊前時間偏移的炮檢距個數，每一組節點計算一個炮檢距疊前時間偏移，當某一組節點完成計算後，申請下一個炮檢距的計算；
（3）當計算節點的分組個數大於疊前時間偏移輸出的炮檢距個數，每一組節計算一個炮檢距疊前時間偏移，剩餘節點組依次分配加入其它組協同計算。
5）根據步驟3）的計算節點分組情況，把每一個節點組內的第一個節點確定為組長（master）節點，組內其它節點作為組員（worker）節點；
6）根據偏移孔徑確定當前成像區間所需要的待偏移地震數距的範圍，具體方法為：待偏移地震數距的最小沿測線方向線號=當前成像區間的最小沿測線方向線號-（垂直測線方向的最大孔徑/線間距）；待偏移地震數距的最大沿測線方向線號=當前成像區間的最大沿測線方向線號+（垂直測線方向的最大孔徑/線間距）；
7）每一組的組長節點逐道讀取本炮檢距待偏移地震數據並按需分發到該組所有組員組長和組員節點；
8）每一個節點獨立完成各自分配到的克希霍夫疊前時間偏移計算任務；
9）重複步驟7）~8）完成一個炮檢距的克希霍夫疊前時間偏移；
10）每一組的組長節點回收該組組員節點的疊前時間偏移結果並進行疊加完成該組炮檢距數據的克希霍夫疊前時間偏移。
該發明原理如下：設：待偏移數據空間
（3）其中：N----待偏移數據總大小，I----待偏移數據Inline線數，Ji----第i條Inline線的cmp個數，Nij----第i條線第j個cmp道集內地震數據大小。設：偏移結果數據空間
（4）其中：M----偏移結果數據總大小，K----偏移結果Inline線數，L----每條Inline線的crp個數，m----每個crp面元內地震大小。
設：節點個數為I，總計算量為P，則，一個節點上要完成的計算量Pi＝P/I⑸。設：傳統的輸入道並行方法的網路流量為T，則T=M*I+N⑹。從⑸式可以看出，單個節點上的計算量和節點個數成反比，隨著節點個數的增加，單個節點上的計算量將減少，整體計算速度將提高。從⑹式可以看出，網路流量和節點個數成正比，隨著節點個數的增加，網路流量將正比例增加，數據傳送的開銷將要增加。當結點個數多於某個數值時，集群的網路資源將不能滿足並行程式數據傳輸量的需求，使得節點的計算單元不能及時得到數據處於等待狀態，從而降低整體計算速度。
綜合分析⑸式和⑹式，輸入道並行方法雖然在工業界發揮著重要的作用，當計算節點增加到一定個數時，增加的網路網路流量嚴重超越了集群網路資源傳送能力，這就限制了輸入道並行方法只能在中小規模的並行環境中運行。同樣輸出道方法也存在相同的問題，這裡不再論述。
該發明的一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法把輸出空間細分為四維空間，四個坐標軸分別指的是：Inline線號、Xline線號、成像時間、炮檢距。從⑷式可以看出，Inline線數和Xline線數是地震工區的成像範圍，由用戶編碼提供，在地面上的投影是規則的矩形格線，同時每個CRP道集中包含的地震道數也是由用戶填寫成像炮檢距區間和炮檢距增量參數組確定。
設：MinOffset---最小炮檢距，MaxOffset---最大炮檢距，IncOffset---炮檢距增量，則每個CRP道集中的地震道數，m=（MaxOffset-MinOffset）/IncOffset+1⑺；其中第i道的炮檢距為Offseti=（i-0.5）*IncOffset+MinOffset⑻。把四維空間中相同道號或相同炮檢距的所有數據抽取為一組，整個輸出空間將變成一系列共道號或共炮檢距的三維數據集，如圖2下部所示。
該發明的一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法以圖2中的共道號或共炮檢距數據集為單位進行並行任務劃分，由一個或幾個節點共同完成一個共炮檢距數據集的三維疊前時間偏移的計算工作。由於其它炮檢距的待偏移數據不會給該炮檢距的輸出結果產生貢獻，所以只需要在該組節點上傳送該組炮檢距的待偏移數據。
設：每個節點組內的節點個數為n，n由實現步驟3）確定則該發明方法下地震數據的網路流量為：T＝N+M*n⑼。比較⑹式和⑼式，一般來說待偏移數據N和偏移結果數據M的大小基本相當，⑹式中節點個數I遠大於⑼式中n，所以⑼式表示的網路流量要遠遠小於⑹式的網路流量，隨著節點個數增加，⑹式的網路流量成線性關係遞增，⑼式網路流量保持不變。
該發明為了驗證效果，選用一個理論數據進行了單道脈衝偏移對比試驗，圖3是該發明的脈衝回響，圖4是輸入道並行方法的脈衝回響，兩附圖中的脈衝回響完全相同，可以肯定該發明方法是完全正確的。該發明為了驗證效果，選用某一實際三維工區，工區待偏移數據大小174GB，在dn8集群上進行不同並行算法地震數據網路流量測試。dn8集群包含128個節點，該次測試使用了60個節點，前30個節點運行該發明的無加速比瓶頸的疊前時間偏移並行算法，後30個節點運行輸入道疊前時間偏移並行算法。兩個測試運行相同規模的體偏移作業，且同時傳送。
圖5展示的是該發明方法和輸入道並行方法網路流量測試對比效果，其中每一個小圖代表一個單獨節點的資源使用情況，縱坐標為使用率，變化範圍為0%~100%，橫坐標為運行時間。黃色線條代表網路流量、紅色線條代表CPU使用效率、綠色線條代表記憶體的使用情況。
從圖中可以看出前面節點代表的該發明方法的地震數據網路流量遠小於下部節點代表的輸入道並行方法。所以該發明成功地解決了克希霍夫疊前時間偏移的網路密集型問題，僅剩下計算密集型，計算密集型通過增加計算節點就能解決。
該發明為了驗證效果的硬體環境：測試集群有128個計算節點，每個節點有4個核。測試數據：測試的地震數據是某三維工區，工區範圍：Inline6~Inline1066，Xline139~Xline1479，目標線測試範圍：Inline45~Inline265~Step55，即從45線起每隔55條線進行偏移總共偏移5條線。體偏移範圍：Inline100~Inline200~Step1，總共偏移101條線。
圖6是分別用該發明方法和輸入道平行算法測試的目標線偏移、體偏移的運行時間和加速比。圖6上部是目標線偏移的運行時間和加速比，運行時間計時單位為秒，藍色代表輸入道並行算法，紅色代表該發明方法。圖6下部是體偏移的運行時間和加速比，運行時間計時單位為小時，同樣藍色代表輸入道並行算法，紅色代表該發明方法。以16個節點為最小測試作業，按倍數關係依次測試16、32、64、128個節點的運行時間，並計算相應的加速比。
從圖6上部的目標線偏移測試結果可以看出該發明方法隨著節點個數的增加，運行時間基本按倍數關係減少，加速比曲線非常接近於理論值。輸入道並行方法隨著節點個數的增加，程式的運行時間在32節點處達到最小，再增加節點個數時，程式運行時間將不再減少，加速比曲線在32節點處達到最高值，繼續增加節點時，該曲線嚴重偏離理論值。
從圖6下部的體偏移測試結果可以看出，該發明方法和輸入道並行方法當節點個數的增加，運行時間都在減少，很明顯每一組相同節點個數作業的對比測試，該發明方法運行時間都小於輸入道並行方法，但是不同組間的減少關係不是很明確。但從右邊的加速比曲線可以看出，該發明的方法更接近於理論加速比。
榮譽表彰
2017年12月11日，《一種無加速比瓶頸的克希霍夫疊前時間偏移並行方法》獲得第十九屆中國專利優秀獎。
