Huan Gao#, Zhewei Liang#, Qingfeng Guan*, Xun Liang & Wen Zeng (2024): A parallel framework on hybrid architectures for raster-based geospatial cellular automata models, International Journal of Geographical Information Science, DOI: 10.1080/13658816.2024.2343776

作者簡(jiǎn)介：

高歡（共同一作），博士研究生，中國(guó)地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院。研究方向?yàn)楦咝阅芸臻g計(jì)算。

梁哲瑋（共同一作），博士研究生，中國(guó)地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院。研究方向?yàn)楦咝阅芸臻g計(jì)算和地理時(shí)空動(dòng)態(tài)模擬。

關(guān)慶鋒（通訊作者），博士，教授，博導(dǎo)，中國(guó)地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院。研究方向包括時(shí)空大數(shù)據(jù)、空間計(jì)算智能和高性能空間計(jì)算。

梁迅，博士，教授，中國(guó)地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院。研究方向?yàn)榈乩頃r(shí)空動(dòng)態(tài)模擬和城市規(guī)劃技術(shù)。

曾文，博士，教授，博導(dǎo)，中國(guó)地質(zhì)大學(xué)（武漢）地理與信息工程學(xué)院。研究方向?yàn)榭臻g計(jì)算智能，地理網(wǎng)絡(luò)模型及優(yōu)化算法。

01、摘要

在進(jìn)行大規(guī)模土地利用變化模擬應(yīng)用時(shí)，地理空間元胞自動(dòng)機(jī)（Geo-CA）模型在計(jì)算效率和可擴(kuò)展性方面遇到了挑戰(zhàn)。并行計(jì)算被證明可以有效應(yīng)對(duì)這些挑戰(zhàn)。然而，現(xiàn)有并行Geo-CA模型的并行化策略總是針對(duì)特定模型進(jìn)行優(yōu)化，對(duì)其他模型缺乏適用性。除此之外，大多數(shù)并行Geo-CA模型側(cè)重于土地利用變化模擬的并行化，而忽視了土地利用轉(zhuǎn)換規(guī)則挖掘部分。而且，在分布式異構(gòu)架構(gòu)上進(jìn)行受需求約束的土地利用變化模擬時(shí)缺乏有效的并行策略。本研究提出了一種適用于面向地理柵格元胞自動(dòng)機(jī)模型的混合架構(gòu)并行計(jì)算框架，以提高其計(jì)算效率和可擴(kuò)展性的同時(shí)保持模擬精度。該框架為多種土地利用類型的土地利用轉(zhuǎn)換規(guī)則挖掘和分布式異構(gòu)架構(gòu)上的需求限制的土地利用變化模擬提供了并行化策略。該框架被用于并行化兩個(gè)現(xiàn)代的Geo-CA模型，即PLUS和MCCA。實(shí)驗(yàn)表明，并行化后的模型在計(jì)算效率和可擴(kuò)展性方面都有顯著提高，證實(shí)了所提出的框架在大規(guī)模土地利用變化模擬研究中的有效性。

02、引言

土地利用反映了人類活動(dòng)與自然環(huán)境之間的關(guān)系。土地利用建�？稍鰪�(qiáng)對(duì)土地利用動(dòng)態(tài)的理解，并能預(yù)測(cè)未來土地利用的變化，為規(guī)劃實(shí)踐中的可持續(xù)發(fā)展提供支持。土地利用模擬模型被開發(fā)出來用于模擬時(shí)空土地利用變化，如地理空間元胞自動(dòng)機(jī)（Geo-CA）模型。由于它們能捕捉當(dāng)?shù)氐目臻g相互作用和時(shí)間動(dòng)態(tài)，這些模型在制定環(huán)境保護(hù)和土地利用規(guī)劃政策方面至關(guān)重要。

Geo-CA模型將土地利用空間抽象為元胞，每個(gè)元胞都有特定的狀態(tài)，并通過模擬這些元胞的狀態(tài)變化來描述土地利用動(dòng)態(tài)。近些年來，Geo-CA模型的所有基本要素都得到了增強(qiáng)，包括元胞、元胞狀態(tài)、鄰域和轉(zhuǎn)換規(guī)則。然而，Geo-CA模型在計(jì)算強(qiáng)度方面遇到了挑戰(zhàn)，主要原因是數(shù)據(jù)密度和計(jì)算復(fù)雜性。一方面，擴(kuò)大模擬任務(wù)的規(guī)模和/或使用高分辨率地理空間數(shù)據(jù)可提高土地利用變化模擬結(jié)果的全面性和質(zhì)量。不過，這也會(huì)導(dǎo)致數(shù)據(jù)密度增加。另一方面，更復(fù)雜的理論和技術(shù)被用于提高模擬性能，從而導(dǎo)致計(jì)算復(fù)雜度增加。數(shù)據(jù)密度和計(jì)算復(fù)雜性的增加導(dǎo)致計(jì)算效率下降，對(duì)計(jì)算資源的需求增加。這些限制因素對(duì)在大規(guī)模土地利用動(dòng)態(tài)應(yīng)用中有效使用Geo-CA模型提出了挑戰(zhàn)。

現(xiàn)有并行Geo-CA模型的開發(fā)有效地解決了上述問題，成功地提高了土地利用變化模擬的計(jì)算效率。與普通Geo-CA模型相比，這些并行模型能更好地完成計(jì)算密集型模擬任務(wù)，但仍有進(jìn)一步提升的空間。首先，現(xiàn)有并行Geo-CA模型中使用的并行策略往往是針對(duì)特定模型進(jìn)行優(yōu)化的，因此限制了其對(duì)其他模型的適用性。因此需要設(shè)計(jì)出一種通用的并行策略，適用于具有類似土地利用變化模擬模塊的各種Geo-CA模型。其次，大多數(shù)并行Geo-CA模型側(cè)重于模擬模塊的并行化，而忽略了規(guī)則挖掘模塊。在規(guī)則挖掘中，簡(jiǎn)單的算法可能不足以從各種驅(qū)動(dòng)因素中挖掘出多種類型的復(fù)雜轉(zhuǎn)換規(guī)則。機(jī)器學(xué)習(xí)算法已被廣泛采用來應(yīng)對(duì)這一挑戰(zhàn)。然而，這些算法通常具有較高的計(jì)算復(fù)雜度，從而降低了計(jì)算效率并使并行化工作變得復(fù)雜。鑒于計(jì)算強(qiáng)度不斷增加，提高規(guī)則挖掘模塊效率的需求日益增長(zhǎng)。第三，現(xiàn)有的并行計(jì)算工具往往難以滿足現(xiàn)代Geo-CA模型的某些需求。例如，Geo-CA模型中廣泛采用需求限制型土地利用變化模擬模型來模擬各種情景下的土地利用變化，其中每種土地利用類型的比例都受到土地利用需求的約束。然而，這增加了并行化的難度。雖然不同土地利用單元的模擬在計(jì)算上是獨(dú)立的，但實(shí)時(shí)動(dòng)態(tài)地統(tǒng)計(jì)每種土地利用類型的比例以確定是否滿足土地利用需求，對(duì)并行Geo-CA模型來說是一個(gè)挑戰(zhàn)。

本研究提出了一個(gè)面向地理柵格元胞自動(dòng)機(jī)模型的混合架構(gòu)并行計(jì)算框架。該框架的設(shè)計(jì)以當(dāng)前的土地利用模擬方法為基礎(chǔ)，可實(shí)現(xiàn)各種面向地理柵格的Geo-CA模型的并行化。研究中提出了一種利用多種并行計(jì)算工具的混合計(jì)算架構(gòu)，以并行化我們框架中多樣且計(jì)算密集的程序。首先，基于機(jī)器學(xué)習(xí)算法開發(fā)了一個(gè)并行規(guī)則挖掘模塊，以提取多種土地利用類型的轉(zhuǎn)換規(guī)則。其次，開發(fā)了受需求限制的土地利用變化模擬并行模塊，以便在分布式異構(gòu)架構(gòu)上實(shí)現(xiàn)更高效的模擬。此外，還提出了一種回溯機(jī)制，以確保土地利用需求對(duì)土地利用變化的約束。為了評(píng)估其性能，利用所提出的框架對(duì)兩個(gè)較先進(jìn)的Geo-CA模型（即PLUS和MCCA）進(jìn)行了并行化。

03、研究方法

1. 面向地理柵格元胞自動(dòng)機(jī)模型的混合架構(gòu)并行計(jì)算框架

研究中提出的并行計(jì)算框架由兩個(gè)模塊組成：一個(gè)用于土地利用轉(zhuǎn)換規(guī)則挖掘，另一個(gè)用于土地利用變化模擬（圖1）。轉(zhuǎn)換規(guī)則挖掘是Geo-CA模型的核心，而機(jī)器學(xué)習(xí)（ML）模型則是挖掘轉(zhuǎn)換規(guī)則的主要方法。在轉(zhuǎn)換規(guī)則挖掘模塊中，使用歷史土地利用數(shù)據(jù)和各種驅(qū)動(dòng)因素訓(xùn)練ML模型。然后，訓(xùn)練好的模型會(huì)預(yù)測(cè)土地利用單元的轉(zhuǎn)換適宜性。在土地利用變化模擬模塊中，利用土地利用數(shù)據(jù)和預(yù)測(cè)的轉(zhuǎn)換適宜性地圖來模擬未來的土地利用地圖。通過整合這兩個(gè)模塊，我們的框架采用了普遍的土地利用變化模擬方法，從而確保其適用于各種Geo-CA模型。

圖1 包含混合并行計(jì)算模式的框架圖

為了提高計(jì)算效率，我們使用不同的并行編程工具對(duì)其中的模塊進(jìn)行并行化處理。我們的框架中使用了三種并行模式，包括共享內(nèi)存模式、分布式內(nèi)存模式和異構(gòu)并行模式。具體來說，在轉(zhuǎn)換規(guī)則挖掘方面，共享內(nèi)存模式和異構(gòu)模式分別用于ML模型的訓(xùn)練和預(yù)測(cè)。在土地利用變化模擬方面，利用名為mcRPL的通用并行地理空間柵格計(jì)算庫(kù)的擴(kuò)展版本，實(shí)現(xiàn)了分布式內(nèi)存模式與異構(gòu)模式相結(jié)合的混合模式。此外，還設(shè)計(jì)了一種回溯機(jī)制，以滿足受需求限制的Geo-CA模型的需求。更進(jìn)一步的是，研究中還對(duì)這些并行策略進(jìn)行了優(yōu)化，以應(yīng)對(duì)大規(guī)模土地利用變化模擬中的挑戰(zhàn)。

2. 針對(duì)多種土地利用類型的并行規(guī)則挖掘

在我們的框架中，設(shè)計(jì)了一個(gè)并行規(guī)則挖掘模塊來挖掘多種土地利用類型的轉(zhuǎn)換規(guī)則。該模塊專為機(jī)器學(xué)習(xí)（ML）算法設(shè)計(jì)，ML算法已廣泛應(yīng)用于土地利用變化模擬模型。不同的ML算法可能采用不同的計(jì)算原理，但它們?cè)谕恋乩�用轉(zhuǎn)換規(guī)則挖掘方面的輸入和輸出是相同的。出于通用性考慮，我們總結(jié)了使用ML算法進(jìn)行轉(zhuǎn)換規(guī)則挖掘的過程，并設(shè)計(jì)了由兩個(gè)計(jì)算程序組成的框架：一個(gè)用于ML模型訓(xùn)練，另一個(gè)用于預(yù)測(cè)轉(zhuǎn)換適宜性。如圖2所示，該框架需要?dú)v史土地利用數(shù)據(jù)和驅(qū)動(dòng)因素作為輸入。首先對(duì)輸入數(shù)據(jù)進(jìn)行采樣，形成訓(xùn)練數(shù)據(jù)集。然后，訓(xùn)練ML模型，以捕捉驅(qū)動(dòng)因素與土地利用變化之間的關(guān)系。最后，利用訓(xùn)練好的模型預(yù)測(cè)轉(zhuǎn)換適宜性地圖，該地圖顯示了每個(gè)元胞過渡到所有可能的土地利用類型的適宜性。為了提高計(jì)算效率，我們?cè)O(shè)計(jì)了一種混合并行策略，根據(jù)兩個(gè)程序的特征選擇不同的并行計(jì)算模式。這種混合并行策略的實(shí)施與具體的ML模型無關(guān)，因此我們的框架可用于多種ML算法。

圖2 并行規(guī)則挖掘模塊流程圖

在該模塊中，訓(xùn)練程序采用共享內(nèi)存并行模式，使用多個(gè)CPU線程進(jìn)行并行處理，而預(yù)測(cè)程序采用異構(gòu)并行模式進(jìn)行并行處理。與此同時(shí)，我們采用了自適應(yīng)數(shù)據(jù)域分解策略來應(yīng)對(duì)大規(guī)模模擬任務(wù)帶來的挑戰(zhàn)。

3. 基于分布式異構(gòu)架構(gòu)下的需求限制的模擬

設(shè)計(jì)并行土地利用變化模擬模塊是為了提高受需求限制的土地利用變化模擬的計(jì)算效率。如圖3所示，該模塊需要輸入轉(zhuǎn)換適宜性圖和初始土地利用圖。通過多次迭代來模擬每個(gè)土地利用元胞的土地利用變化，直至達(dá)到所有土地利用類型的土地利用需求或不發(fā)生土地利用變化。

圖3 受需求限制的并行土地利用變化模擬模塊

分布式異構(gòu)并行計(jì)算已在大規(guī)模土地利用模擬應(yīng)用中證明了其有效性。多臺(tái)計(jì)算機(jī)的計(jì)算資源可以滿足大規(guī)模模擬任務(wù)對(duì)計(jì)算資源和效率的需求。在我們的框架中，采用了分布式異構(gòu)架構(gòu)上的通用并行地理空間柵格計(jì)算庫(kù)mcRPL，因?yàn)樗�通過封裝編程細(xì)節(jié)簡(jiǎn)化了并行化。為滿足現(xiàn)代Geo-CA模型的要求，mcRPL進(jìn)一步擴(kuò)展并整合了有關(guān)土地利用元胞的全局柵格信息，使其適用于更多的Geo-CA模型。此外，還對(duì)mcRPL中的隨機(jī)數(shù)生成器進(jìn)行了調(diào)整，以滿足Geo-CA模型對(duì)多類型隨機(jī)值的要求。

除此之外，框架中還為該模塊提出了一種回溯機(jī)制，以確保土地利用的變化能夠受到全局需求的限制。每次迭代后，都能夠計(jì)算每種土地利用類型的比例，以確定是否超出土地利用需求。如果在迭代i中超過了k類型的需求，則將回溯該迭代中的土地利用變化。如圖4所示，一些元胞的土地利用類型被選擇回溯，而另一些元胞則在迭代i后保留土地利用類型。在回溯后，進(jìn)一步比較土地利用類型的比例和需求以保證剛剛達(dá)到土地使用需求且不會(huì)超出。

圖4 回溯機(jī)制

在大多數(shù)模擬迭代中，回溯機(jī)制避免了實(shí)時(shí)比例計(jì)算和跨處理器的數(shù)據(jù)通信。它僅在超出需求的迭代中運(yùn)行，因此其他迭代的效率不受影響。因此，該機(jī)制保持了分布式異構(gòu)架構(gòu)上受需求限制的土地利用變化模擬的有效性，并提高了其計(jì)算效率。

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

本研究使用了提出的框架對(duì)兩種現(xiàn)代Geo-CA模型（PLUS和MCCA）進(jìn)行了并行化。我們?cè)谔旌佣��?hào)超級(jí)計(jì)算機(jī)上使用mcPLUS和mcMCCA進(jìn)行了一系列實(shí)驗(yàn)，以評(píng)估提出的框架的性能。天河二號(hào)的每個(gè)節(jié)點(diǎn)的配置都為兩個(gè)英特爾至強(qiáng)E5-2660 2.6 GHz 10核CPU、256 GB主內(nèi)存和四個(gè)Nvidia Tesla K80 GPU。PLUS和MCCA也在天河二號(hào)GPU節(jié)點(diǎn)上運(yùn)行作為mcPLUS和mcMCCA的基準(zhǔn)，它們只使用天河二號(hào)GPU節(jié)點(diǎn)上的CPU。實(shí)驗(yàn)中使用的土地利用數(shù)據(jù)集包括中國(guó)湖北省2008年和2018年的土地利用數(shù)據(jù)。具體來說，mcPLUS使用的是30m分辨率的原始土地利用數(shù)據(jù)集，mcMCCA使用的是將原始數(shù)據(jù)匯總為90米分辨率的混合單元土地利用數(shù)據(jù)集。

對(duì)于土地利用轉(zhuǎn)換規(guī)則挖掘部分，研究中對(duì)比了并行版本與普通版本模型的計(jì)算時(shí)間。實(shí)驗(yàn)結(jié)果表明（圖5），研究中提出的框架能夠提高土地利用轉(zhuǎn)換規(guī)則挖掘部分的計(jì)算效率。在并行過后，mcPLUS和mcMCCA分別比PLUS和MCCA快19.1倍和5.9倍。

圖5 土地利用轉(zhuǎn)換規(guī)則挖掘模塊的運(yùn)行時(shí)間以及加速比

對(duì)于土地利用變化模擬部分，進(jìn)行了兩次精度實(shí)驗(yàn)，以驗(yàn)證提出的框架對(duì) Geo-CA模型進(jìn)行并行化不會(huì)影響其精度。還進(jìn)行了一次效率實(shí)驗(yàn)，以評(píng)估該框架在提高Geo-CA模型效率方面的有效性。在第一個(gè)精度實(shí)驗(yàn)中，使用相同的輸入對(duì)Geo-CA模型進(jìn)行了比較。如圖6（a）所示，使用mcPLUS模擬的土地利用圖與使用PLUS模擬的土地利用圖完全相同。mcMCCA對(duì)各土地利用類型的模擬結(jié)果與MCCA相同，其結(jié)果以林地為例展示（圖6（b））。

圖6 2018年土地利用變化圖：（a）PLUS和mcPLUS；（b）MCCA和mcMCCA

在第二個(gè)精度實(shí)驗(yàn)中，我們?cè)u(píng)估了PLUS、MCCA、mcPLUS和mcMCCA在實(shí)際應(yīng)用中的精度。如表1所示，PLUS和mcPLUS與MCCA和mcMCCA的精度基本相同。精度上的細(xì)微差別是由于隨機(jī)因素造成的，而隨機(jī)因素對(duì)于我們實(shí)驗(yàn)中的Geo-CA模型是必要的。

表1 PLUS、mcPLUS、MCCA和mcMCCA的模擬精度

在效率實(shí)驗(yàn)中，我們記錄了PLUS、mcPLUS、MCCA和mcMCCA在實(shí)際應(yīng)用中的運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果如圖7所示，這表明研究中提出的框架能夠提高土地利用變化模擬部分的計(jì)算效率。在并行過后，mcPLUS分別比PLUS快4.9倍、7.3倍、9.6倍、11.6倍和12.4倍，而mcMCCA比MCCA快4.5、6.9、9.6、12.6和13.1倍。

圖7 土地利用變化模擬模塊的運(yùn)行時(shí)間以及加速比

05、總結(jié)

本研究提出了一種基于混合并行計(jì)算架構(gòu)的并行框架，用于開發(fā)面向地理柵格的并行Geo-CA模型。該框架的設(shè)計(jì)考慮了Geo-CA模型的發(fā)展趨勢(shì)，確保其適用于廣泛的Geo-CA模型，尤其是現(xiàn)代和廣泛使用的模型。在轉(zhuǎn)換規(guī)則挖掘和土地利用變化模擬中，混合計(jì)算架構(gòu)與各種并行工具被用于并行化理論上多樣且計(jì)算密集的程序。此外，研究中提出了一種回溯機(jī)制，通過混合計(jì)算架構(gòu)上的土地利用需求，有效約束土地利用變化。與提出框架的工作流程部分或完全相似的Geo-CA模型都可以使用該框架進(jìn)行并行化。

所提出的框架已被應(yīng)用于并行化兩個(gè)現(xiàn)代的且廣泛使用的Geo-CA模型。實(shí)驗(yàn)結(jié)果表明，在基本保證精度的前提下，土地利用轉(zhuǎn)換規(guī)則挖掘和土地利用變化模擬的計(jì)算效率都有了顯著提高。此外，增加GPU的數(shù)量還能進(jìn)一步提高土地利用變化模擬的效率，證明了該框架在利用多種計(jì)算資源方面的可擴(kuò)展性。研究中提出的框架在效率、精度和可擴(kuò)展性方面的表現(xiàn)都能證明了其在大規(guī)模土地利用變化模擬中加強(qiáng)Geo-CA模型應(yīng)用的潛力。在未來，我們的計(jì)劃是用其他支持更多處理器的并行工具取代CUDA，從而進(jìn)一步提高我們框架的通用性。