基于OpenMP的柵格數(shù)據(jù)矢量化并行算法研究2p

秦柳 畢金強(qiáng) 范俊甫

【摘要】柵格數(shù)據(jù)矢量化算法在GIS領(lǐng)域具有重要的作用，為了提高柵格數(shù)據(jù)矢量化算法的轉(zhuǎn)換效率，本文基于OpenMP并行計(jì)算平臺(tái)設(shè)計(jì)了一種針對(duì)大型柵格數(shù)據(jù)的快速轉(zhuǎn)換多個(gè)圖像的并行算法，使用開(kāi)源地理空間數(shù)據(jù)抽象庫(kù)GDAL作為數(shù)據(jù)讀寫(xiě)和轉(zhuǎn)換的工具，針對(duì)影響并行算法性能的因素：線程數(shù)、任務(wù)調(diào)度策略，對(duì)傳統(tǒng)按行劃分的矢量化算法進(jìn)行并行優(yōu)化。

【關(guān)鍵詞】柵格數(shù)據(jù)矢量化;并行算法;調(diào)度策略;OpenMP

1. 引言

矢量結(jié)構(gòu)和柵格結(jié)構(gòu)是地理信息系統(tǒng)（GIS）中兩種主要的空間數(shù)據(jù)結(jié)構(gòu)，矢柵數(shù)據(jù)間的轉(zhuǎn)換是GIS應(yīng)用中必不可少的，其中尤以柵格數(shù)據(jù)的矢量化過(guò)程應(yīng)用更為頻繁。隨著人類(lèi)獲取遙感數(shù)據(jù)的技術(shù)不斷提高，獲取柵格數(shù)據(jù)的數(shù)目和也急劇增加，數(shù)據(jù)轉(zhuǎn)換需要的規(guī)模也成倍增長(zhǎng)，傳統(tǒng)的柵格數(shù)據(jù)矢量化算法在效率上無(wú)法滿足現(xiàn)實(shí)的需求。因此，大型柵格數(shù)據(jù)的快速矢量化算法研究便有了重要的現(xiàn)實(shí)意義。近年來(lái)，并行計(jì)算技術(shù)迅速發(fā)展，出現(xiàn)了大量利用并行方法解決和遙感領(lǐng)域圖像處理等題的新方法，其強(qiáng)大的計(jì)算資源為解決中大型柵格數(shù)據(jù)的矢量化問(wèn)題提供了動(dòng)力。

2. 研究方法

2.1 矢量化串行算法

所謂柵格數(shù)據(jù)的矢量化是對(duì)柵格數(shù)據(jù)的象元或象元集合所構(gòu)成的圖斑的邊緣進(jìn)行勾繪，并以矢量坐標(biāo)點(diǎn)構(gòu)成折線段（GIS中稱(chēng)為弧段）的方式給予記錄，再經(jīng)拓?fù)鋽?shù)據(jù)結(jié)構(gòu)處理，生成面狀矢量數(shù)據(jù)結(jié)構(gòu)。典型的柵格矢量化算法主要包括有向邊界法、散列線段聚合法等。經(jīng)過(guò)近十幾年的研究，逐漸形成三種較為典型的矢量化算法：基于邊緣跟蹤的矢量化方法、基于窗口匹配的矢量化方法和基于拓?fù)潢P(guān)系的矢量化方法。

本文以基于邊緣跟蹤的矢量化方法作為研究對(duì)象，使用GDAL庫(kù)中封裝的柵格數(shù)據(jù)矢量化算法進(jìn)行設(shè)計(jì)，實(shí)現(xiàn)算法并行化?；谶吘壐櫟氖噶炕椒ㄍㄟ^(guò)讀取柵格圖像，以一個(gè)像元為起始像元，在該像元的八鄰域中，按逆時(shí)針?lè)较蛘页雠c該像元的屬性值相同的第一個(gè)像元。按此方法繼續(xù)，直到返回起始點(diǎn)為止。

2.2 矢量化并行算法設(shè)計(jì)

并行計(jì)算（Parallel Computing）通過(guò)計(jì)算機(jī)同時(shí)處理多個(gè)計(jì)算過(guò)程來(lái)提高計(jì)算速度和處理能力。并行計(jì)算根據(jù)不同的條件有不同的分類(lèi)，根據(jù)程序和算法設(shè)計(jì)人員角度來(lái)看，并行計(jì)算可分為任務(wù)并行和數(shù)據(jù)并行兩種。任務(wù)并行是將一個(gè)流水線上的任務(wù)分配給各個(gè)線程，每個(gè)線程只負(fù)責(zé)一個(gè)或固定的某些任務(wù)，而數(shù)據(jù)并行是對(duì)不同的數(shù)據(jù)采用相同的處理方法處理的過(guò)程。因此，在并行計(jì)算的過(guò)程中，主要工作就是數(shù)據(jù)劃分和任務(wù)劃分。

OpenMP（Open Multi-Processing）是一種共享式存儲(chǔ)或共享分布式存儲(chǔ)的并行編程模型，主要用于多核的計(jì)算機(jī)系統(tǒng)，即多個(gè)核共享一個(gè)內(nèi)存，將任務(wù)劃分給多個(gè)核進(jìn)行并行處理，從而提高算法的計(jì)算效率和CPU利用率。為了提高大型遙感數(shù)據(jù)在柵格數(shù)據(jù)矢量化的過(guò)程中的效率，本文以O(shè)penMP并行編程模型為基礎(chǔ)，從任務(wù)并行和數(shù)據(jù)并行兩個(gè)方面對(duì)算法進(jìn)行設(shè)計(jì)。算法對(duì)柵格數(shù)據(jù)進(jìn)行任務(wù)劃分和數(shù)據(jù)劃分，根據(jù)本地柵格數(shù)據(jù)的數(shù)量，按照線程數(shù)進(jìn)行任務(wù)劃分，實(shí)現(xiàn)多個(gè)圖像的并行矢量化;在單個(gè)圖像的矢量化過(guò)程中，對(duì)柵格圖像的柵格單元進(jìn)行數(shù)據(jù)劃分，實(shí)現(xiàn)單個(gè)圖像的并行矢量化。

2.3 OpenMP并行實(shí)現(xiàn)

在程序中，for循環(huán)是比較耗時(shí)的，因此利用OpenMP并行的關(guān)鍵是for循環(huán)的并行。OpenMP提供了parallel for指令來(lái)對(duì)循環(huán)結(jié)構(gòu)進(jìn)行并行處理，parallel for指令有兩種使用形式：

其中type有static，dynamic，guided和auto四種，chunk是表示一個(gè)并行塊的大小。static表示靜態(tài)調(diào)度，在整個(gè)并行計(jì)算過(guò)程中并行塊的大小都一樣。dynamic則表示動(dòng)態(tài)調(diào)度，默認(rèn)其并行塊尺寸為1。guided表示啟發(fā)式調(diào)度，指定第一個(gè)并行塊的大小，后面每個(gè)并行塊的尺寸都會(huì)遞減，直到最小的并行塊尺寸。采用auto或runtime時(shí)，不需要設(shè)置chunk參數(shù)，此時(shí)隊(duì)列類(lèi)型將由環(huán)境變量omp_schedule來(lái)控制。

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

3.1 數(shù)據(jù)準(zhǔn)備及實(shí)驗(yàn)環(huán)境

本次實(shí)驗(yàn)數(shù)據(jù)采用Landsat-8衛(wèi)星下載遙感影像，選取江蘇豐縣和山東曲阜的兩個(gè)區(qū)域前八個(gè)波段共16個(gè)TIFF柵格影像為源柵格影像，臨時(shí)矢量數(shù)據(jù)文件為ESRI Shapefile格式，采用8核16線程的計(jì)算機(jī)作為實(shí)驗(yàn)平臺(tái)。

3.2 并行實(shí)驗(yàn)結(jié)果分析

為了更好的了解算法在多核共享存儲(chǔ)的計(jì)算機(jī)上的可擴(kuò)展性，本次實(shí)驗(yàn)分別對(duì)靜態(tài)調(diào)度（static）、動(dòng)態(tài)調(diào)度（dynamic）、啟發(fā)式調(diào)度（guided）三種調(diào)度策略進(jìn)行測(cè)試。按照不同的線程數(shù)分為8組測(cè)試，記錄在三種動(dòng)態(tài)策略下共計(jì)3×8組實(shí)驗(yàn)耗費(fèi)的具體時(shí)間，并計(jì)算對(duì)應(yīng)的加速比（如圖）。其中當(dāng)線程數(shù)為1時(shí)，采用的是串行算法，由主線程單獨(dú)完成。

不同線程下不同調(diào)度策略對(duì)計(jì)算效率影響對(duì)比

加速比是衡量并行算法時(shí)間性能的重要指標(biāo)，它是指任務(wù)由單核執(zhí)行完成所耗費(fèi)的時(shí)間與并行化所耗費(fèi)時(shí)間的比值。加速比可以反映并行計(jì)算帶來(lái)的效益。由圖2可以看出，三種調(diào)度策略加速比的整體趨勢(shì)是相同的，都是先升高后降低，這是因?yàn)殡S著線程數(shù)的增加，計(jì)算機(jī)CPU的利用率也不斷增大，并行計(jì)算產(chǎn)生的開(kāi)銷(xiāo)包括通信開(kāi)銷(xiāo)和負(fù)載開(kāi)銷(xiāo)等也會(huì)不斷增大，因此會(huì)導(dǎo)致運(yùn)行時(shí)間不減反增的情況。雖然三種調(diào)度策略的整體趨勢(shì)不同，但通過(guò)比較可以看出，采用靜態(tài)調(diào)度的加速比波折較大，不夠穩(wěn)定，說(shuō)明采用這種任務(wù)調(diào)度方式的負(fù)載均衡性能較差，而采用動(dòng)態(tài)調(diào)度的并行算法相對(duì)穩(wěn)定且加速比大，說(shuō)明動(dòng)態(tài)調(diào)度策略最適合于柵格數(shù)據(jù)矢量化的并行計(jì)算。

4. 結(jié)語(yǔ)

本文以O(shè)penMP為并行編程模型，發(fā)掘柵格矢量化函數(shù)的并行潛力，完成了矢量化函數(shù)的并行化以及多個(gè)柵格圖像的并行算法，對(duì)提高大型遙感數(shù)據(jù)在柵格數(shù)據(jù)矢量化的過(guò)程中的效率有一定的幫助。通過(guò)對(duì)三種調(diào)度策略的測(cè)試，選取了加速比最高，且隨著線程數(shù)增加，運(yùn)行時(shí)間相對(duì)穩(wěn)定的動(dòng)態(tài)調(diào)度策略?？紤]到通信開(kāi)銷(xiāo)、負(fù)載開(kāi)銷(xiāo)、進(jìn)程啟動(dòng)和結(jié)束時(shí)間對(duì)并行算法性能的影響，為了獲取最大的效益，計(jì)算機(jī)線程數(shù)要控制在一定范圍內(nèi)，不宜過(guò)少或過(guò)多。

參考文獻(xiàn)：

[1]魏金標(biāo).自適應(yīng)柵格數(shù)據(jù)矢量化并行方法研究[D].南京大學(xué)，2014.

[2]章孝燦，潘云鶴.GIS中基于“柵格技術(shù)”的柵格數(shù)據(jù)矢量化技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13（10）：895-900.

[3]Tzen T H， Ni L M. Trapezoid self-scheduling： A practical scheduling scheme for parallel compilers[J]. IEEE Transactions on Parallel and Distributed Systems，1993， 4（1）： 87-98.

[4]Hummel S F， Schonberg E， Flynn L E. Factoring： A method for scheme scheduling parallel loops[J]. Communications of the ACM， 1992， 35（8）： 90-101.

[5]王亭亭.基于OpenMP和MPI的并行算法研究[D].吉林大學(xué)，2011.

[6]范會(huì)敏，李滋田.基于OpenMP的多線程負(fù)載均衡調(diào)度策略[J].計(jì)算機(jī)與現(xiàn)代化，2013，（12）：192-195+200.

作者簡(jiǎn)介：秦柳，山東臨沂人，碩士研究生，主要研究方向?yàn)?D時(shí)空分析與可視化技術(shù)。