李鳴野

中國輻射防護(hù)研究院， 山西 太原 030006

0 引言

現(xiàn)行的GRIB碼版本有g(shù)rib和grib2兩種格式，目前，國內(nèi)外針對GRIB碼解碼工具有兩種，第一種為NCEP(美國國家環(huán)境預(yù)報中心)開發(fā)的wgrib命令行工具，通過命令行來操作GRIB數(shù)據(jù)，這種方法在國內(nèi)廣泛使用.第二種為ECMWF(歐洲中期天氣預(yù)報中心)開發(fā)的GRIB API，用戶使用編程語言通過GRIB API使用get和set鍵/值操作GRIB數(shù)據(jù)，這種方法在國內(nèi)很少使用，國外針對此方法也在不斷更新推出新的API，應(yīng)用也較為局限，尤其是在應(yīng)急響應(yīng)領(lǐng)域還未推廣.

傳統(tǒng)的解碼方式在國內(nèi)是調(diào)用wgrib命令行，使用命令行解碼，文獻(xiàn)[1]中提及使用多線程技術(shù)，由其方式為DOS命令行解碼，對于解碼提升的效率僅為進(jìn)程調(diào)度的優(yōu)化，且其在解碼后需生成二進(jìn)制中間文件，再對二進(jìn)制文件進(jìn)行多線程讀寫.由于文件I/O操作占用的時間相對于解碼來說占用過大，且為兩次讀寫，則其解碼耗時理論上是較大的.在文獻(xiàn)[2]中提出了并行化程度較高的方式為按段并行化解GRIB碼，其相較于文獻(xiàn)[1]中的方法在解碼過程中效率有提升，但仍需進(jìn)行二進(jìn)制解碼后內(nèi)容拼接，對系統(tǒng)資源的開銷較大.在文獻(xiàn)[3]和文獻(xiàn)[4]中提出了對于GRIB API的使用，調(diào)研文獻(xiàn)[4]發(fā)表時的GRIB API可知由于受當(dāng)時API版本的局限，其同樣需要生成二進(jìn)制中間文件再進(jìn)行提取.本文提出的HP算法是基于第二種解碼工具GRIB API的使用散列查找和多線程調(diào)度的快速解碼方法.

1 主要算法

1.1 HP算法

分析傳統(tǒng)的解碼方式可知，影響解碼效率的最大因素有兩個，一個是查找所要提取信息的位置；另一個是提取后對內(nèi)容的寫操作.在總結(jié)傳統(tǒng)解碼方式的優(yōu)缺點(diǎn)和多次實(shí)際測試的基礎(chǔ)上，分析發(fā)現(xiàn)，傳統(tǒng)解碼方法對系統(tǒng)時間空間資源的開銷都過于巨大.對比API方式相較于wgrib方式而言首先是更為靈活，二次開發(fā)性較好，其次不需要調(diào)度DOS命令，且使用API方式可以構(gòu)建更為快速的解碼數(shù)據(jù)結(jié)構(gòu)并解決grib和grib2混合壓縮的問題.固本文HP算法的設(shè)計(jì)選擇基于GRIB API.NET的解碼方式.HP算法的流程圖如圖1所示.

圖1 HP算法解碼流程圖
Fig.1 HP algorithm decoding flow chart

HP算法核心在于使用散列查找結(jié)構(gòu)和多線程調(diào)度來進(jìn)行解碼.構(gòu)造散列函數(shù)的定義域[5]包含需要提取的物理量的關(guān)鍵字，這里的關(guān)鍵字為GRIB碼物理量索引，值域的范圍依賴于散列表的大小即索引的地址范圍，根據(jù)不同的數(shù)值預(yù)報產(chǎn)品不同，其值域范圍不同.使用直接定址法，取線性物理量Level層構(gòu)建散列地址，其函數(shù)如公式1所示

H(Key)=a*Key+b

(1)

其中，a為level的增量，b為偏移量，當(dāng)物理量提取發(fā)生沖突時采用除留余數(shù)法，并構(gòu)造再散列法(雙散列法)處理，構(gòu)建第二個散列函數(shù)Hash2(Key)計(jì)算沖突地址值的增量.它的具體散列函數(shù)形式如公式2所示：

Hi=(H(Key)+i*Hash2(Key))%m

(2)

初始探測位置H0=H(Key)%m.其中，m為GRIB中物理量個數(shù)長度，i是沖突的次數(shù)，初始為0.

HP算法時間復(fù)雜度：對散列表查找的時間復(fù)雜度為O(1)，在查找到地址后對物理量的提取時所需比較的平均次數(shù)計(jì)算公式如公式3所示：

(3)

其中，Pi為平均查找到目標(biāo)物理量的概率，n是查找表的長度.使用此按值查找算法的平均時間復(fù)雜度為O(n)，則整體解碼的時間復(fù)雜度為O(n)+O(1)=O(n)，如果順序固定，則其最快的時間復(fù)雜度為O(1)，則整體最快為O(1)+O(1)=O(1).

HP算法空間復(fù)雜度：其取決于需要查找的物理量的多少，設(shè)一個文件內(nèi)的所有物理量大小為m1，所需物理量為m2，則對于使用散列表的查找數(shù)據(jù)的所占用的空間復(fù)雜度為O(m2).

使用上述散列結(jié)構(gòu)算法進(jìn)行數(shù)據(jù)的查找和提取可大大提高數(shù)據(jù)在主存中的提取速度，加入多線程并行化資源調(diào)度模式[6]，可使I/O輸出倍數(shù)級縮短耗時，理論上當(dāng)線程數(shù)不大于物理核數(shù)時，使用線程k個可將整體算法的時間復(fù)雜度化為O(n/k)，但空間復(fù)雜度會增加為O(n*k).

1.2 與傳統(tǒng)算法對比

傳統(tǒng)算法核心是通過使用系統(tǒng)命令批處理調(diào)用wgrib程序進(jìn)行整個文件的解碼，解碼的方式為先輸出GRIB目錄和輸出解碼為二進(jìn)制格式的中間數(shù)據(jù)文件，再對照目錄中關(guān)鍵字內(nèi)容對二進(jìn)制中間文件進(jìn)行循環(huán)提取.提取后的數(shù)據(jù)為解碼結(jié)果.分析其解碼原理和算法可知，傳統(tǒng)方法在解碼時首先在內(nèi)存中輸出一次二進(jìn)制中間文件和一次GRIB目錄內(nèi)容.之后將二進(jìn)制中間文件輸出到外存.并在外存中打開文件，循環(huán)提取所需內(nèi)容并轉(zhuǎn)換為后續(xù)模塊需要的格式，再進(jìn)行一次外存輸出.且解碼的區(qū)域只能為全球范圍所有數(shù)據(jù).這種傳統(tǒng)的解碼模式首先由于使用系統(tǒng)控制臺命令批處理操作wgrib外部程序進(jìn)行解碼.此方式會導(dǎo)致無法通過多線程調(diào)度來實(shí)現(xiàn)解碼部分的并行化效率提升.且生成中間文件會導(dǎo)致解碼過程產(chǎn)生兩次外存輸出.內(nèi)存讀取數(shù)據(jù)的次數(shù)也為兩次，并有一次目錄文件的外存輸出和讀取.其造成大量的空間占用和較大的系統(tǒng)資源浪費(fèi).時效性較差.使用外部wgrib程序還會導(dǎo)致該方法的二次開發(fā)受到很大的限制.根據(jù)文獻(xiàn)[1]中的內(nèi)容可以對傳統(tǒng)方法進(jìn)行改良，即在對中間文件的提取部分加入多線程并行化提取.這種方式可以部分提升解碼的速度，傳統(tǒng)算法與改良算法的流程對比圖如圖2所示.

圖2 傳統(tǒng)算法與改良算法流程對比簡圖
Fig.2 Comparison of traditional algorithm and improved algorithm flow

采用改良算法僅小部分提升了解碼的效率，其他存在問題并未得到根本性的解決，傳統(tǒng)改良算法與HP算法的流程對比簡圖如圖3所示.

圖3 改良傳統(tǒng)算法與HP算法的流程對比簡圖
Fig.3 Shows a simplified comparison of the flow between the improved traditional algorithm and the HP algorithm

HP算法相較于傳統(tǒng)算法在運(yùn)行流程上更為簡化，其使用散列查找模式對GRIB結(jié)構(gòu)數(shù)據(jù)進(jìn)行提取.僅需讀取一次源數(shù)據(jù)文件，不需要讀寫目錄.并且可根據(jù)目標(biāo)范圍直接在主存中縮小提取數(shù)據(jù)的內(nèi)容，根據(jù)后續(xù)物理模塊的計(jì)算需求，目標(biāo)范圍越小解碼速度越快.輸出結(jié)果也僅為一次.相較于傳統(tǒng)算法，HP解碼方法節(jié)省了生成中間文件所需的時間空間資源，并可實(shí)現(xiàn)全過程多線程并行化提速，極大程度上提升了解碼的效率.且該方法具有較高的兼容性、封裝性和可擴(kuò)展性.

2 案例測試及結(jié)果分析

調(diào)研文獻(xiàn)和分析解碼模式認(rèn)為當(dāng)運(yùn)行物理環(huán)境一定的情況下，單從方法角度分析影響解碼效率的因素有①解碼區(qū)域范圍、②數(shù)據(jù)分辨率大小、③所需物理量數(shù)量、④預(yù)處理文件個數(shù)(評價時長)和⑤線程數(shù)，分別對單一變量控制進(jìn)行效率測試.對比組使用文獻(xiàn)[7]中提及的應(yīng)用較為典型的境外核事故放射性后果評價軟件(RADCON)中的解碼方法.即wgrib解碼方法進(jìn)行對比測試.測試硬件選用的配置為win7-64位操作系統(tǒng)，16 G內(nèi)存，8核CPU計(jì)算機(jī).測試案例選用NCAR(National Center for Atmospheric Research)發(fā)布的FNL再分析數(shù)據(jù)進(jìn)行測試.首先對解碼區(qū)域范圍的影響進(jìn)行效率測試.選取2016年10月01日00時刻的以grib2[8]格式壓縮的FNL數(shù)據(jù)，區(qū)域分為全球區(qū)域360*181°和局部范圍40*40°經(jīng)緯度范圍[9].測試長度都選擇10天(240小時分析時長)，每6小時一個文件，共40個文件.源數(shù)據(jù)內(nèi)容長度都控制在328個物理量，分辨率為1°，提取物理量為從100 mb～850 mb共16層高度層的風(fēng)場U、風(fēng)場V、垂直速度、溫度、相對濕度、位勢高度變量和surface層常用的地面壓力、對流性降水、總降水、下墊面特征、雪厚度，變量總共101個變量，線程數(shù)選擇單線程進(jìn)行測試.測試結(jié)果如表1所示.

對五次測試結(jié)果中解碼耗時取平均繪制對比結(jié)果圖如圖4所示.從圖4中可以明顯看出，對于解碼范圍從全球到局部尺度，隨著解碼范圍的縮小，HP算法的耗時大幅下降，而傳統(tǒng)算法的解碼耗時也有所下降，但是幅度不明顯.據(jù)分析可知，使用HP算法是根據(jù)GRIB壓縮格式直接通過散列函數(shù)讀取內(nèi)部結(jié)構(gòu)數(shù)據(jù)的，對于縮小解碼范圍，可在解碼數(shù)據(jù)讀入的過程中縮小提取數(shù)據(jù)的量，從而在之后的數(shù)組建立和文件輸出的過程中都減少時間和空間資源的占用.而對于傳統(tǒng)算法，縮小解碼范圍對于解GRIB碼的過程無影響，因?yàn)槠涫窍葘φ麄€區(qū)域進(jìn)行解碼生成中間文件之后，當(dāng)縮小解碼范圍，那么對于中間文件的數(shù)據(jù)讀取量會縮小，生成最終所需文件的耗時會縮小.這樣看來，傳統(tǒng)算法在解GRIB碼時對于解碼范圍縮小是不影響其效率的.在二次提取數(shù)據(jù)時才會有效率的提升.而HP算法在解GRIB碼數(shù)據(jù)之前就縮小了提取數(shù)據(jù)的范圍.所以當(dāng)解碼范圍為局地小尺度時，使用HP算法可以在較大程度上提升解碼的效率.

表1 不同解碼范圍對解碼耗時的影響表Tab.1 Table of effects of different decoding ranges on decoding time consumption

之后研究不同分辨率對數(shù)據(jù)解碼耗時的影響，數(shù)據(jù)選取全球范圍360*181，分辨率選擇1°和0.5°的源數(shù)據(jù)，上述其他變量都保持不變的情況下再進(jìn)行測試.測試結(jié)果如表2所示.

表2 不同分辨率對解碼耗時的影響表Tab.2 Table of effects of different resolutions on decoding time consumption

對五次測試結(jié)果中解碼耗時取平均繪制對比結(jié)果如圖5所示.

圖4 解碼范圍對解碼耗時影響對比圖Fig.4 Comparison of decoding range on decoding time consumption圖5 解碼分辨率對解碼耗時影響對比圖Fig.5 Comparison of decoding resolution on decoding time consumption

觀察圖中兩種分辨率對解碼耗時的影響可知，當(dāng)解碼分辨率擴(kuò)大一倍時，兩種算法的耗時都會增加，對于HP算法來說，當(dāng)數(shù)據(jù)量增加一倍，那么其耗時會相應(yīng)增加一倍，但是由于GRIB數(shù)據(jù)的基數(shù)增加，導(dǎo)致循環(huán)索引的數(shù)組增加一倍，隨著數(shù)組量的增加，處理數(shù)組所占用的時間資源量要多于一倍，固對于HP算法來說，耗時會增加一倍多一點(diǎn).根據(jù)圖中數(shù)據(jù)可知，分辨率增加一倍耗時為原耗時的229 %.分析傳統(tǒng)算法可知，由分辨率的增加，生成的中間文件的數(shù)據(jù)量會增加，由于文件IO所占的時間空間資源都是很大的，固當(dāng)分辨率增加一倍時，解碼的耗時會大于一倍.據(jù)圖中數(shù)據(jù)分析可知0.5°分辨率的解碼耗時為原解碼耗時的319 %.因此，HP算法在對于高分辨率GRIB數(shù)據(jù)解碼的效率要優(yōu)于傳統(tǒng)解碼，且分辨率越高，效果越明顯.

再研究變量提取量的多少對解碼耗時的影響，選取分辨率1°的grib2壓縮格式FNL源數(shù)據(jù)，物理量提取設(shè)置原變量組為101組，新設(shè)變量新增土溫4層土濕4層，2米高度層露點(diǎn)溫度、溫度、相對濕度、比濕，10米高度層風(fēng)場U、風(fēng)場V、地表溫度、海平面壓力、地面感應(yīng)熱通量，地表溫度t，海平面壓力msl，雪厚度，高度層增設(shè)為900 mb～1 000 mb共5層高度層的風(fēng)場U、風(fēng)場V、垂直速度、溫度、相對濕度、位勢高度變量，總共148個變量為148組.上述其他變量都保持不變的情況下再進(jìn)行測試.測試結(jié)果如表3所示.

表3 不同變量提取組對解碼耗時的影響表Tab.3 Table of effects of different variable extraction groups on decoding time consumption

對五次測試結(jié)果中解碼耗時取平均繪制對比結(jié)果如圖6所示.從測試結(jié)果可以大致分析得出，當(dāng)所提取的物理量內(nèi)容增加時，解碼的耗時也會相應(yīng)增加，且大致推算可以得出兩種解碼的耗時與所提取物理量的內(nèi)容成正比，HP算法由于物理量提取組增多，耗時為原來的1.39倍，而傳統(tǒng)算法的耗時約為1.44倍，對比可知HP算法略優(yōu)于傳統(tǒng)算法，但差別不大.在實(shí)際解碼的過程中由于HP算法的耗時基數(shù)較小，所以當(dāng)對于大量的物理量或者是全部物理量的提取來說，HP算法相對于傳統(tǒng)算法更節(jié)省時間.

分析解碼時長對解碼耗時的影響，選取物理量提取組為101組，測試預(yù)處理數(shù)據(jù)長度選擇10天(240小時分析時長)數(shù)據(jù)、2天(48小時分析時長)和1天(24小時分析時長)，上述其他變量都保持不變的情況下再進(jìn)行測試.測試結(jié)果如表4所示.

表4 不同分析時長對解碼耗時的影響表Tab.4 Table of effects of different analysis durations on decoding time consumption

對五次測試結(jié)果中解碼耗時取平均繪制對比結(jié)果如圖7所示.根據(jù)測試結(jié)果可知當(dāng)分析時長減少時，解碼的耗時也相應(yīng)減少，且對應(yīng)成正比.分析原因可知，由于兩種算法對于解碼的過程都是按照一個分析時刻解完后進(jìn)行下一個分析時刻的解碼.其內(nèi)在的邏輯過程是串行，且如果當(dāng)每個時刻的文件大小一致的情況下，解碼單時刻的耗時是一致的.所以，兩種解碼方法對于分析時長變化，其解碼耗的變化時對應(yīng)成正比關(guān)系.

最后探討線程數(shù)對解碼耗時的影響[10]，選取預(yù)處理數(shù)據(jù)長度10天(240小時分析時長)數(shù)據(jù)，線程調(diào)度分為使用單線程、雙線程和四線程進(jìn)行解碼，上述其他變量都保持不變的情況下再進(jìn)行測試.由于傳統(tǒng)算法未加入多線程并行化方法.固在傳統(tǒng)方法的基礎(chǔ)上使用改良型傳統(tǒng)方法，加入線程調(diào)度方法，其核心也是使用wgrib命令進(jìn)行解碼預(yù)處理，測試結(jié)果如表5所示.

圖6 變量提取對解碼耗時影響對比圖Fig. is a comparison of the effects of variable extraction on decoding time圖7 分析時長對解碼耗時影響對比圖Fig.7 Comparison of the influence of analysis time on decoding time consumption

表5 不同線程數(shù)對解碼耗時的影響表Tab.5 Effect of different thread counts on decoding time consumption

對五次測試結(jié)果中解碼耗時取平均繪制對比結(jié)果圖如圖8所示.

根據(jù)圖中測試結(jié)果不難看出，HP線程數(shù)的調(diào)用對于解碼效率的影響成倍數(shù)關(guān)系，在物理核數(shù)對比線程數(shù)未達(dá)到飽和狀態(tài)(即N核，M線程，其中N≤M).所調(diào)用線程數(shù)即為解碼耗時縮短的倍數(shù)，如圖中所示，當(dāng)線程數(shù)為雙線程時，解碼的耗時大致為原解碼耗時的1/2.當(dāng)線程數(shù)為四線程時，解碼的耗時為原解碼耗時的1/4.而傳統(tǒng)算法在調(diào)度多線程的情況下無法達(dá)到按比例縮短解碼耗時.從圖中可見其解碼調(diào)度四線程時耗時為原解碼耗時的0.75倍.由上述算法分析可知，傳統(tǒng)算法調(diào)度線程僅可提升文件I/O速度，并無法提升解碼速度.固當(dāng)解碼線程提升時，耗時減少的部分僅為文件I/O部分，而解碼過程并無效率提升.由此可得使用HP算法可以在硬件允許的情況下調(diào)度多線程來大幅提升解碼效率.

圖8 不同線程數(shù)對解碼耗時影響對比圖
Fig.8 Comparison of the impact of different thread counts on decoding time

3 結(jié)論

本文在分析傳統(tǒng)解碼方法的基礎(chǔ)之上，設(shè)計(jì)了全新的利用多線程調(diào)度模式和高效GRIB碼散列查找結(jié)構(gòu)的新算法HP算法.通過與傳統(tǒng)解碼方法的對比測試，分別討論了HP算法與傳統(tǒng)算法在解碼區(qū)域范圍、數(shù)據(jù)分辨率大小、物理量提取數(shù)量、評價時長和線程數(shù)方面對解碼耗時的影響.結(jié)果證明利用HP算法解碼在各方面都優(yōu)于傳統(tǒng)算法且解碼效率提升明顯.分析認(rèn)為在實(shí)際的解碼過程中使用HP算法能大幅提升解碼效率，可應(yīng)用于對解碼效率有較高需求的應(yīng)急響應(yīng)系統(tǒng)[11]中，為其GRIB數(shù)據(jù)預(yù)處理模塊的快速解碼提供參考方法.