基于Fork/Join框架的等值面快速生成并行算法

鮑婷婷，焦圣明，殷笑茹，陳景麗，牛靄琛

(江蘇省氣象信息中心，江蘇 南京 210008)

0 引 言

等值線圖是一種重要圖形，在地質(zhì)、氣象、水文、設(shè)計(jì)等領(lǐng)域中得到了廣泛應(yīng)用。在數(shù)值分析中，繪制等值線圖是應(yīng)用最多的基礎(chǔ)技術(shù)手段之一。隨著網(wǎng)絡(luò)帶寬的日益完善，傳統(tǒng)的等值線圖繪制應(yīng)用已明顯不能滿足用戶需求，探索基于Web或云計(jì)算下的繪制算法成為目前的研究主流。在軟硬件環(huán)境及算法相同的情況下，傳統(tǒng)應(yīng)用程序在執(zhí)行效率上要比基于Web的應(yīng)用高，然而在離散點(diǎn)數(shù)量多、網(wǎng)格點(diǎn)密度大的情況下，按傳統(tǒng)的串行方法實(shí)現(xiàn)等值面生成的這兩類應(yīng)用均存在響應(yīng)速度慢、效率低的問題，這一問題同時(shí)也廣泛存在于專業(yè)商業(yè)軟件中，使得業(yè)務(wù)系統(tǒng)在實(shí)時(shí)性方面無法得到保證。隨著多核處理器設(shè)計(jì)技術(shù)的快速發(fā)展，針對Web應(yīng)用研究基于多核平臺下的等值面快速生成并行算法顯得尤為迫切。

等值面的繪制過程一般分為離散數(shù)據(jù)網(wǎng)格化、等值點(diǎn)計(jì)算、等值線追蹤及光滑、等值面提取、地圖裁剪等幾個步驟。當(dāng)前，國內(nèi)外就如何提高等值線圖生成效率展開了大量的研究，其可以從兩方面著手：一方面把GPU等硬件資源應(yīng)用到普通的數(shù)值并行計(jì)算中；另一方面通過軟件方法提高計(jì)算速度，主要是通過并行算法改進(jìn)程序提升效率[1-2]。有學(xué)者利用GPU提供大量的并行數(shù)據(jù)，應(yīng)用其并行性來進(jìn)行通用計(jì)算，如使用GPU進(jìn)行等值面的提取與繪制，但其繪制過程無法完全在圖形硬件上實(shí)現(xiàn)[3-4]；文獻(xiàn)[5]在GPU并行架構(gòu)和CUDA可編程性基礎(chǔ)上提出了一種基于區(qū)間塊搜索的等值線并行提取算法，但提取方法并未給出；文獻(xiàn)[6]將基于非規(guī)則四面體的等值面提取和繪制過程完全轉(zhuǎn)移至GPU上執(zhí)行，從而降低了CPU計(jì)算負(fù)荷，提高了等值面提取和繪制速度；文獻(xiàn)[7]提出了一種等值線二值邊界追蹤的算法，以柵格邊界為基礎(chǔ)追蹤等值線；文獻(xiàn)[8]針對等高線繪制中排序耗時(shí)問題提出了一種改進(jìn)的算法，可應(yīng)用于2D與3D對象；文獻(xiàn)[9]采用分區(qū)法和OPENMP的并行算法處理形成等值填色場，但文獻(xiàn)中實(shí)現(xiàn)的等值面只是根據(jù)并行計(jì)算插值給圖片像素賦予顏色值，生成的等值面是圖像產(chǎn)品而不是矢量數(shù)據(jù)，在業(yè)務(wù)使用上存在一定的局限性；文獻(xiàn)[10]是基于ArcGIS Server的模型來實(shí)現(xiàn)等值面生成，其成本高、算法可擴(kuò)展性小，在等值面圖形復(fù)雜度較高的情況下響應(yīng)性能會受到一定的影響，致使效率不高。

針對以上問題，文中提出了一種基于Fork/Join框架的等值面快速生成并行算法。首先描述算法的基本原理、并行任務(wù)及劃分策略，其次以自動氣象站的累積降水量和不同網(wǎng)格下數(shù)值預(yù)報(bào)溫度場的等值面提取為例實(shí)現(xiàn)該并行算法，并通過與傳統(tǒng)串行算法比較，從計(jì)算性能、等值面繪制效果驗(yàn)證該算法的效率及優(yōu)勢。

1 Fork/Join框架

Fork/Join框架是一個分治(divide and conquer)策略的并行編程框架，實(shí)現(xiàn)了任務(wù)定義與任務(wù)處理的分離，大大簡化了并行程序設(shè)計(jì)的復(fù)雜度，開發(fā)人員能夠方便地利用多核平臺的計(jì)算能力。盡管還沒有做到對開發(fā)人員完全透明，但已經(jīng)極大地簡化了編寫并行程序的瑣碎工作。

工作竊取算法(work-stealing algorithm)是該框架用來提高性能、保證負(fù)載均衡的一種有效方法，其本質(zhì)上是一種工作任務(wù)的調(diào)度方法。基本思想是利用已完成任務(wù)的線程去查看其他線程是否有未處理完的工作，如果有則竊取一部分工作來執(zhí)行，從而提高資源的利用率，減少程序的處理時(shí)間。

該框架主要由Fork和Join兩個操作構(gòu)成，F(xiàn)ork操作是對任務(wù)的劃分，把大任務(wù)劃分成若干小問題，能方便對簡化后的問題進(jìn)行處理；Join操作主要是完成對各個部分的運(yùn)行結(jié)果進(jìn)行合并的任務(wù)。其工作原理如圖1所示。

圖1 Fork/Join框架工作原理

2 等值面并行算法

2.1 串行處理算法

目前，規(guī)則矩形網(wǎng)格法和不規(guī)則三角網(wǎng)格法是進(jìn)行等值線圖繪制比較常見并且較成熟的算法[11]，由于氣象業(yè)務(wù)中大部分?jǐn)?shù)據(jù)是已經(jīng)插值好的網(wǎng)格數(shù)據(jù)，故多采用規(guī)則矩形網(wǎng)格法進(jìn)行等值線圖繪制。基于規(guī)則矩形網(wǎng)格法的等值面提取算法描述如下：

算法：規(guī)則矩形網(wǎng)格法等值面提取算法。

輸入：某種氣象要素的離散數(shù)據(jù)集U，等值線間隔數(shù)組K；

輸出：等值面矢量數(shù)據(jù)集。

Step1:將離散點(diǎn)氣象數(shù)據(jù)集利用一定的插值方法進(jìn)行網(wǎng)格化處理；

Step2:計(jì)算網(wǎng)格上的等值點(diǎn)，并將等值點(diǎn)連接成線段存貯到線段組隊(duì)列；

Step3:利用隊(duì)列中的線段組根據(jù)等值間隔追蹤出所有等值線，并進(jìn)行光滑處理；

Step4:通過邊界線把非閉合等值線處理成閉合等值線，對等值面進(jìn)行標(biāo)記識別；

Step5:按目標(biāo)區(qū)域范圍進(jìn)行等值面裁剪；

Step6:算法結(jié)束。

2.2 可并行過程

并行算法是一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動作從而達(dá)到給定問題的求解[12]。并行基本思想就是在一段時(shí)間內(nèi)同時(shí)處理兩件或兩件以上的作業(yè)，這兩件或兩件以上的作業(yè)可以是同一性質(zhì)也可以是不同性質(zhì)的，如果要并行計(jì)算就必須保證過程之間的獨(dú)立性，即不包括數(shù)據(jù)依賴、控制依賴、數(shù)據(jù)交換等關(guān)系。從整體上分析程序的并行化工作，綜合考慮整個計(jì)算任務(wù)在所有計(jì)算資源上的分配，盡量做到負(fù)載平衡，可以取得較大的性能提升[13]。就等值面提取算法而言，其處理流程的各個步驟是有一定依賴關(guān)系的，它們不能同時(shí)并行處理串行算法中的各個步驟，而是要按一定的先后順序執(zhí)行。因此，并行算法只能作用在可以實(shí)施并行計(jì)算的單獨(dú)步驟上，從而減少這些步驟的作業(yè)時(shí)間，達(dá)到提高程序執(zhí)行效率的目的。串行算法里有四個步驟可以實(shí)施并行計(jì)算，分別為：

(1)離散點(diǎn)數(shù)據(jù)網(wǎng)格化處理。離散數(shù)據(jù)量的多少、網(wǎng)格設(shè)定的大小以及不同的插值方法都會影響到算法的處理速度。在傳統(tǒng)方法下，網(wǎng)格密度越大，插值精度越高，算法花費(fèi)在格點(diǎn)值的計(jì)算時(shí)間就越長，反之網(wǎng)格密度越小，計(jì)算速度越快，但輸出的等值面失真度就越高。精度和效率都是不可缺少的，為了同時(shí)保持高精度和高效率，一個有效的解決辦法就是使用并行算法來加快網(wǎng)格點(diǎn)的計(jì)算速度。

(2)等值點(diǎn)計(jì)算。根據(jù)步驟1處理好的格點(diǎn)資料計(jì)算出有效的等值線間隔的最大值和最小值，確定出等值點(diǎn)判別循壞的起始值，在并行計(jì)算等值點(diǎn)時(shí)可能會減少當(dāng)前等值線段組屬于哪條等值線的標(biāo)識時(shí)間，它在最差狀態(tài)與上面不進(jìn)行預(yù)處理時(shí)的循環(huán)次數(shù)相同。

(3)等值線追蹤與光滑。從步驟2線段組中提取出所有不同間隔的等值線值，分別建立新的隊(duì)列，將原先的線段組擺放到各自相對應(yīng)的新隊(duì)列中去，接著對這些新隊(duì)列進(jìn)行并行等值線追蹤，最后按文獻(xiàn)[14]中的方法對每條等值線進(jìn)行穿過原點(diǎn)的光滑處理。

(4)等值面標(biāo)記識別。僅根據(jù)等值線的標(biāo)記值是無法判斷由其構(gòu)成的等值面等級，需要利用格點(diǎn)上的值對等值面進(jìn)行判別，標(biāo)記識別的目的是確定使用什么顏色對該等值面進(jìn)行顏色填充。文中對標(biāo)記識別采用一種簡單實(shí)用的辦法，就是先對所有等值面進(jìn)行面積大小排序，排序完成后從等值面邊界線任取一點(diǎn)計(jì)算出相對應(yīng)的格點(diǎn)，利用該格點(diǎn)及周邊四個格點(diǎn)進(jìn)行判別，如果該格點(diǎn)在等值面內(nèi)，就以此格點(diǎn)的值換算出等值面的標(biāo)記值。通過邊界線把非閉合等值線處理成閉合等值線，把所有排好序的等值面按順序存放到數(shù)組隊(duì)列，然后把這一大數(shù)組隊(duì)列劃分成數(shù)各小數(shù)組隊(duì)列并行標(biāo)記識別。

當(dāng)用戶對實(shí)時(shí)性要求比較高時(shí)，若操作響應(yīng)時(shí)間超過3秒，則其交互體驗(yàn)效果將會變差。因此，對上述四個步驟進(jìn)行并行化處理后，計(jì)算速度明顯提升，有效地保證了客戶端用戶交互響應(yīng)的時(shí)效性。

2.3 任務(wù)劃分策略

通常算法中循環(huán)處理操作是程序執(zhí)行中蘊(yùn)含并行性最豐富的一種結(jié)構(gòu)，上述四個步驟是串行程序的并行化，就是將可以并行化的循環(huán)移植到并行環(huán)境中進(jìn)行計(jì)算的過程。一個大任務(wù)操作在劃分成許多小任務(wù)時(shí)，也不是并行小任務(wù)越多處理速度就越快，需要從硬件資源和計(jì)算任務(wù)性質(zhì)統(tǒng)籌考慮，并行任務(wù)線程池的線程數(shù)主要依據(jù)硬件資源設(shè)定，計(jì)算性質(zhì)對并行閾值(threshold value)取值也十分重要，在任務(wù)規(guī)模不大的情況下采用串行的解決方法可能會更好。上述步驟1、2計(jì)算量級相似，其劃分小任務(wù)的閾值基本一致但不能太小，可以設(shè)定在3 000～4 000；步驟3隊(duì)列數(shù)組不會太大但是一個較耗時(shí)的操作，分解的并行小任務(wù)數(shù)量和數(shù)組長度一樣；步驟4需要幾何空間，計(jì)算閾值不宜太大，可以設(shè)定在10～30。這四個并行計(jì)算都使用了工作竊取算法。

2.4 并行算法實(shí)現(xiàn)

Java從JDK1.7版本開始引入Fork/Join框架編程模式，采用這個并行框架最大的優(yōu)勢是能夠高效快捷地實(shí)現(xiàn)程序跨平臺功能。Fork/Join框架里的java.util.concurrent包提供ForkJoinTask和ForkJoinPool兩個類來實(shí)現(xiàn)算法的并行，通常情況下不需要直接繼承ForkJoinTask類，而只需要繼承它的子類RecursiveAction和RecursiveTask。RecursiveAction類用于沒有返回結(jié)果的任務(wù)，RecursiveTask用于有返回結(jié)果的任務(wù)。上述步驟1～步驟3的并行算法都是繼承有返回任務(wù)的RecursiveTask類實(shí)現(xiàn)。ForkJoinTask需要通過ForkJoinPool來執(zhí)行，任務(wù)分割出的子任務(wù)會添加到當(dāng)前工作線程所維護(hù)的雙端隊(duì)列中，進(jìn)入隊(duì)列的頭部,當(dāng)一個工作線程的隊(duì)列里暫時(shí)沒有任務(wù)時(shí)，它會隨機(jī)從其他工作線程的隊(duì)列的尾部獲取一個任務(wù)，原理實(shí)現(xiàn)如圖2所示。

通過對上述等值面提取算法及其并行性的分析，得出算法核心過程的任務(wù)可分割性，提取了各個任務(wù)中的可并行部分，得到基于Fork/Join框架編程模式下實(shí)現(xiàn)的并行算法流程示意圖(見圖3)。文中基于Fork/Join框架編程模式實(shí)現(xiàn)的并行算法最核心的偽代碼如下：

public class TaskName extends RecursiveTask {//V是返回結(jié)果的變量

//變量定義

……

public TaskName(//傳入?yún)?shù)){

//類初始化

}

@Override

protected V compute( ){

//定義返回的變量

V sum；

if(問題規(guī)模<閾值){

//使用串行模式解決或選擇其他更優(yōu)算法解決

……

}

else{

//將任務(wù)Task進(jìn)行分解,分解成Task1、Task2…

TaskName Task1=new TaskName();

圖2 Work-stealing(工作竊取)實(shí)現(xiàn)

圖3 等值面提取并行算法流程示意圖

TaskName Task2=new TaskName();

……

//將任務(wù)Task1、Task2…提交給線程池執(zhí)行

Task1.fork();

Task2.fork();

……

//如果任務(wù)有返回結(jié)果，收集結(jié)果合并

V v1=Task1.join();

V v2=Task2.join();

sum=v1+v2;

}

return sum;

}

}

等值面提取算法是通過編寫com.jandy.isolines類包來實(shí)現(xiàn)的，其中IsoLines是主類，定義了一系列屬性和方法供程序調(diào)用，最重要的方法是parallelMakeIsolines(),它包含了四個并行過程。在com.jandy.isolines.parallel子包下，這四個并行過程的類就是利用上述偽代碼思想編碼完成，只不過各自類的輸入任務(wù)、計(jì)算方法和輸出結(jié)果不一樣而已。這個包單獨(dú)編譯后形成的jar文件還可以提供其他Java開發(fā)人員當(dāng)作組件使用，提高了代碼的復(fù)用性。

3 實(shí) 驗(yàn)

3.1 算法處理時(shí)間

等值面提取算法的計(jì)算時(shí)間是可以進(jìn)行估算的。

設(shè)算法處理時(shí)間為T，串行算法處理時(shí)間為：

T=Ti+Tg+Tc+Ts+Tp+Tw+Tm

(1)

其中，T為處理總的運(yùn)行時(shí)間，Ti為讀取數(shù)據(jù)處理時(shí)間，Tg為離散數(shù)據(jù)網(wǎng)格化處理時(shí)間，Tc為等值點(diǎn)計(jì)算時(shí)間，Ts為等值線追蹤和光滑時(shí)間，Tp為非閉合等值線處理成閉合等值線和面積排序時(shí)間，Tw為等值面標(biāo)記識別時(shí)間，Tm為地圖裁剪時(shí)間。

并行算法處理時(shí)間為：

(2)

其中，N是處理器核個數(shù)，算法通過把各個任務(wù)分配到N個核處理器上以相同方法同時(shí)進(jìn)行計(jì)算，從而減少程序的計(jì)算時(shí)間，提高執(zhí)行效率。實(shí)驗(yàn)數(shù)據(jù)分析主要針對可以并行的過程，不能并行的過程執(zhí)行時(shí)間相似且極小，基本可以忽略不計(jì)。

根據(jù)上述串行算法處理時(shí)間(T1)與并行算法處理時(shí)間(T2)得到的兩者所耗時(shí)間比(加速比)來評價(jià)該并行程序的性能，即，并行執(zhí)行與串行執(zhí)行時(shí)的計(jì)算性能的比值[15]:

(3)

3.2 實(shí)驗(yàn)平臺

等值面提取算法的性能測試是在軟硬件環(huán)境相同的實(shí)驗(yàn)平臺上進(jìn)行的，通過串、并行算法實(shí)例運(yùn)行，比較兩者的計(jì)算時(shí)間。采用的硬件平臺是一臺配備Intel(R) Xeon(R) E7-4820 v2 主頻2.00 GHz的8核CPU處理器和128 G內(nèi)存的X3860服務(wù)器,操作系統(tǒng)為64位Redhat Linux 6.0，Java虛擬機(jī)為64位JDK1.8。為了避免其他軟件的干擾，對操作系統(tǒng)及測試必要的軟件都進(jìn)行了全新安裝。

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

實(shí)驗(yàn)中分別使用了離散站點(diǎn)的累積降水量和不同網(wǎng)格大小的數(shù)值預(yù)報(bào)溫度場這兩類資料進(jìn)行測試和分析，之所以選擇這兩種類型的資料是因?yàn)樗鼈冊趯?shí)際的氣象業(yè)務(wù)應(yīng)用中極具代表性。為了評估并行計(jì)算對等值面處理效率的提高，使用加速比作為衡量標(biāo)準(zhǔn)，執(zhí)行時(shí)間單位為毫秒。

(1)離散數(shù)據(jù)。

離散數(shù)據(jù)使用的是江蘇省氣象局全省地面自動站2015年6月某日的累積降水量數(shù)據(jù)，對71個基本站和含加密站的1 441個所有站的兩組數(shù)據(jù)分別進(jìn)行了實(shí)驗(yàn)。網(wǎng)格大小設(shè)定為201×201，經(jīng)度116°～122°，緯度30°～36°，空間分辨率遠(yuǎn)小于加密站分布密度能夠滿足插值精度，生成了7級降水分布圖，測試不同站點(diǎn)數(shù)量對插值速度的影響，見表1。

表1 71個基本站和含加密站的1 441個所有站的等值面提取串并行性能對比

從表1可以看出，上述離散數(shù)據(jù)的等值面提取算法四個并行過程Tg、Tc、Ts和Tw，無論是串行還是并行最耗時(shí)間的過程是離散數(shù)據(jù)網(wǎng)格化處理過程Tg，在71個基本站這一組數(shù)據(jù)中Tg的串、并行執(zhí)行時(shí)間分別占總處理時(shí)間的96.34%和90.88%；在含加密站的這一組數(shù)據(jù)中分別為99.46%和94.98%；隨著參與插值計(jì)算站點(diǎn)個數(shù)的增加，Tg過程的計(jì)算時(shí)間呈增加趨勢但加速比獲得顯著提高，但其他三個過程的加速比就不那么明顯甚至?xí)档汀Ｒ虼藢τ谛【W(wǎng)格、等值線稀疏的場景下更適合使用串行算法，并行算法可能會適得其反，增加了處理時(shí)間。針對此類業(yè)務(wù)應(yīng)用是采取串行還是并行需要具體對待，但離散數(shù)據(jù)網(wǎng)格化處理過程Tg采用并行算法處理是毫無疑問的。圖4(a)是以71個基本站數(shù)據(jù)進(jìn)行插值計(jì)算的累積降水量分布圖，圖4(b)是以含加密站的1 441個所有站數(shù)據(jù)進(jìn)行插值計(jì)算的累積降水量分布圖。圖4(b)更能反映出較小尺度下的降水差異性，提高了空間精度，與圖4(a)相比在處理時(shí)間上要長些，但采用并行算法處理后生成時(shí)間控制在2秒以下能夠滿足業(yè)務(wù)要求。

圖4 降水分布對比

(2)網(wǎng)格數(shù)據(jù)。

網(wǎng)格數(shù)據(jù)是使用美國、歐洲、日本和中國的數(shù)值預(yù)報(bào)中心輸出的2米高溫度場格點(diǎn)預(yù)報(bào)產(chǎn)品作為實(shí)驗(yàn)數(shù)據(jù)，產(chǎn)品數(shù)據(jù)都是采用氣象信息綜合分析處理系統(tǒng)(meteorological information comprehensive analysis and process system，MICAPS)標(biāo)準(zhǔn)的第四類文件格式進(jìn)行存儲，十分方便業(yè)務(wù)人員進(jìn)行讀寫操作。提取2016年3月06日16時(shí)四家數(shù)值預(yù)報(bào)中心全球模式不同分辨率下的溫度場數(shù)據(jù)，等值線間隔設(shè)為5 ℃，溫度范圍設(shè)定在-60～40 ℃，對比串行與并行算法的耗時(shí)，生成20級等值面，測試不同網(wǎng)格大小對加速比的影響，見表2。

表2 不同網(wǎng)格大小等值面提取串并行性能對比

圖5 不同網(wǎng)格下的串、并行處理時(shí)間及加速比

根據(jù)表2結(jié)果繪制如圖5所示的折線圖。在網(wǎng)格規(guī)模較小的情況下，并行算法的性能突出不明顯，但網(wǎng)格規(guī)模加大時(shí)，并行算法效率提升的效果十分顯著。從表2中可以看出，在1 440×721網(wǎng)格下達(dá)到最大加速比5.308 1，網(wǎng)格大小從720×361到1 440×721，串行處理時(shí)間增加了5.6秒，而并行處理時(shí)間只增加了1.0秒，串行算法的處理時(shí)間增長幅度遠(yuǎn)高于并行算法。

圖6為利用文中并行算法繪制的網(wǎng)格大小為1 440×721的溫度要素等值面效果圖，從讀取數(shù)據(jù)到繪制完成用時(shí)不到2秒，而用專業(yè)氣象業(yè)務(wù)軟件MICAPS繪制耗時(shí)近15秒。

圖6 1 440×721網(wǎng)格溫度要素個例

4 結(jié)束語

通過對常用的兩類氣象資料等值面生成的特點(diǎn)分析，研究了基于Fork/Join框架下多核并行計(jì)算數(shù)據(jù)處理的方法。實(shí)驗(yàn)結(jié)果表明，該方法在實(shí)現(xiàn)復(fù)雜計(jì)算量下的等值面提取時(shí)較大地提高了數(shù)據(jù)處理速度，等值面的生成時(shí)間控制在2秒內(nèi)，能夠滿足氣象業(yè)務(wù)需求，在生成效率上具有優(yōu)越性，為其他相關(guān)業(yè)務(wù)的等值面分析提供了一種借鑒思路。特別是針對實(shí)時(shí)性要求極高、基于Web應(yīng)用的等值面分析時(shí)，在服務(wù)端使用并行計(jì)算是一種較好的解決方案。后續(xù)工作將利用此算法構(gòu)建云服務(wù)平臺，為注冊用戶開放API云接口，便于用戶在自己的Web應(yīng)用中接入使用。