基于 OpenMP 的并行化水文分析算法研究與實(shí)現(xiàn)

0 引 言

地理信息系統(tǒng)( Geographic Information System，以下簡稱 GIS) 中的空間分析服務(wù)具有算法邏輯復(fù)雜、數(shù)據(jù)規(guī)模龐大的特點(diǎn)，屬于一種計(jì)算密集型服務(wù)。隨著數(shù)據(jù)采集、傳輸、處理技術(shù)的不斷發(fā)展，大范圍、高分辨率的地理空間數(shù)據(jù)使得傳統(tǒng)串行算法難以滿足性能要求。與此同時 64 位系統(tǒng)和多核計(jì)算技術(shù)不斷發(fā)展，如何充分利用 64位系統(tǒng)和多核環(huán)境下的計(jì)算資源成為 GIS 研究人員必須面對的問題。而高性能地學(xué)計(jì)算概念的提出，正是希望將 IT 技術(shù)發(fā)展成果與地理信息理論相結(jié)合，解決 GIS 中大規(guī)模地理空間數(shù)據(jù)的并行存儲、查詢、分析等關(guān)鍵技術(shù)問題，提高 GIS 的空間數(shù)據(jù)處理、管理與分析能力。

1 空間分析并行化

作為銜接空間數(shù)據(jù)處理與應(yīng)用模型的重要部分，空間分析通過對原始數(shù)據(jù)的特征觀察分析和處理獲得更多的經(jīng)驗(yàn)和知識，并以此作為空間行為的決策依據(jù)[1]。GIS空間數(shù)據(jù)規(guī)模不斷膨脹，導(dǎo)致傳統(tǒng)串行空間分析方法很容易成為系統(tǒng)性能瓶頸。而并行計(jì)算技術(shù)憑借其對于多核計(jì)算能力的充分利用，以及可擴(kuò)展的計(jì)算模式為大規(guī)?？臻g數(shù)據(jù)的分析提供了一種解決方案。

并行算法經(jīng)過多年的發(fā)展，目前已形成一些基本設(shè)計(jì)方法，常見的并行計(jì)算策略有分治策略，平衡樹方法，倍增技術(shù)，流水線技術(shù)及加速級聯(lián)策略[2]。由于 GIS 數(shù)據(jù)具有空間信息量大、地理分布廣、時效性強(qiáng)、多源異構(gòu)等特征，為了有效組織多源的相關(guān)數(shù)據(jù)進(jìn)行綜合分析，以建立響應(yīng)速度快、計(jì)算能力強(qiáng)和空間數(shù)據(jù)高效組織與管理的新機(jī)制來認(rèn)知、模擬、預(yù)測和調(diào)控自然地理環(huán)境和社會經(jīng)濟(jì)過程，客觀上要求大力發(fā)展空間分析并行計(jì)算方法[3]。而在空間分析功能并行化的具體實(shí)施過程中，可以劃分為基于數(shù)據(jù)的并行化、基于算法的并行化和基于硬件技術(shù)的并行化幾種模式。

1. 1 基于數(shù)據(jù)的并行化

該模式主要是指那些不需要對空間分析算法進(jìn)行整體調(diào)整，即主要通過對待分析數(shù)據(jù)的均勻劃分，從而將原始計(jì)算任務(wù)均勻的分配到多個計(jì)算單元中。較為典型的應(yīng)用場景為空間分析中面向柵格數(shù)據(jù)的分析，如水文分析、插值計(jì)算、等值線提取、地形計(jì)算等分析功能。與矢量數(shù)據(jù)相比，柵格數(shù)據(jù)結(jié)構(gòu)簡單，沒有復(fù)雜的拓?fù)潢P(guān)系，空間分析算法邏輯也相對簡單[4]。但另一方面，柵格數(shù)據(jù)一般數(shù)據(jù)量較大，導(dǎo)致整體計(jì)算量較大，因此柵格數(shù)據(jù)空間分析的并行模式多采用數(shù)據(jù)并行模式。

1. 2 基于算法的并行化

該模式主要指那些不能完全通過數(shù)據(jù)劃分達(dá)到分析過程并行化的功能，舉例來說，空間分析中的矢量數(shù)據(jù)之間一般存在較為復(fù)雜的空間關(guān)系，如線與面的邊界覆蓋關(guān)系，面與面的鄰接關(guān)系，面與點(diǎn)的包含關(guān)系等。使得基于矢量數(shù)據(jù)的空間分析操作較難通過簡單的數(shù)據(jù)劃分來并行化。即在對分析數(shù)據(jù)進(jìn)行劃分的基礎(chǔ)上，還需要分析算法針對數(shù)據(jù)特點(diǎn)，對劃分和合并過程進(jìn)行特殊處理。如矢量數(shù)據(jù)處理較多使用平面掃描算法，在進(jìn)行該算法的并行化改進(jìn)時，主處理單元通過將事件點(diǎn)平均分配給從處理單元，各從處理單元處理完各自的任務(wù)后將結(jié)果發(fā)送給主處理單元，最后主處理單元將各事件點(diǎn)合并，才能得到最終解。

更多內(nèi)容請查看pdf