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
作者簡介：
高歡（共同一作），博士研究生，中國地質(zhì)大學（武漢）地理與信息工程學院。研究方向為高性能空間計算。
梁哲瑋（共同一作），博士研究生，中國地質(zhì)大學（武漢）地理與信息工程學院。研究方向為高性能空間計算和地理時空動態(tài)模擬。
關慶鋒（通訊作者），博士，教授，博導，中國地質(zhì)大學（武漢）地理與信息工程學院。研究方向包括時空大數(shù)據(jù)、空間計算智能和高性能空間計算。
梁迅，博士，教授，中國地質(zhì)大學（武漢）地理與信息工程學院。研究方向為地理時空動態(tài)模擬和城市規(guī)劃技術。
曾文，博士，教授，博導，中國地質(zhì)大學（武漢）地理與信息工程學院。研究方向為空間計算智能，地理網(wǎng)絡模型及優(yōu)化算法。
01、摘要
在進行大規(guī)模土地利用變化模擬應用時，地理空間元胞自動機（Geo-CA）模型在計算效率和可擴展性方面遇到了挑戰(zhàn)。并行計算被證明可以有效應對這些挑戰(zhàn)。然而，現(xiàn)有并行Geo-CA模型的并行化策略總是針對特定模型進行優(yōu)化，對其他模型缺乏適用性。除此之外，大多數(shù)并行Geo-CA模型側(cè)重于土地利用變化模擬的并行化，而忽視了土地利用轉(zhuǎn)換規(guī)則挖掘部分。而且，在分布式異構架構上進行受需求約束的土地利用變化模擬時缺乏有效的并行策略。本研究提出了一種適用于面向地理柵格元胞自動機模型的混合架構并行計算框架，以提高其計算效率和可擴展性的同時保持模擬精度。該框架為多種土地利用類型的土地利用轉(zhuǎn)換規(guī)則挖掘和分布式異構架構上的需求限制的土地利用變化模擬提供了并行化策略。該框架被用于并行化兩個現(xiàn)代的Geo-CA模型，即PLUS和MCCA。實驗表明，并行化后的模型在計算效率和可擴展性方面都有顯著提高，證實了所提出的框架在大規(guī)模土地利用變化模擬研究中的有效性。
02、引言
土地利用反映了人類活動與自然環(huán)境之間的關系。土地利用建模可增強對土地利用動態(tài)的理解，并能預測未來土地利用的變化，為規(guī)劃實踐中的可持續(xù)發(fā)展提供支持。土地利用模擬模型被開發(fā)出來用于模擬時空土地利用變化，如地理空間元胞自動機（Geo-CA）模型。由于它們能捕捉當?shù)氐目臻g相互作用和時間動態(tài)，這些模型在制定環(huán)境保護和土地利用規(guī)劃政策方面至關重要。
Geo-CA模型將土地利用空間抽象為元胞，每個元胞都有特定的狀態(tài)，并通過模擬這些元胞的狀態(tài)變化來描述土地利用動態(tài)。近些年來，Geo-CA模型的所有基本要素都得到了增強，包括元胞、元胞狀態(tài)、鄰域和轉(zhuǎn)換規(guī)則。然而，Geo-CA模型在計算強度方面遇到了挑戰(zhàn)，主要原因是數(shù)據(jù)密度和計算復雜性。一方面，擴大模擬任務的規(guī)模和/或使用高分辨率地理空間數(shù)據(jù)可提高土地利用變化模擬結(jié)果的全面性和質(zhì)量。不過，這也會導致數(shù)據(jù)密度增加。另一方面，更復雜的理論和技術被用于提高模擬性能，從而導致計算復雜度增加。數(shù)據(jù)密度和計算復雜性的增加導致計算效率下降，對計算資源的需求增加。這些限制因素對在大規(guī)模土地利用動態(tài)應用中有效使用Geo-CA模型提出了挑戰(zhàn)。
現(xiàn)有并行Geo-CA模型的開發(fā)有效地解決了上述問題，成功地提高了土地利用變化模擬的計算效率。與普通Geo-CA模型相比，這些并行模型能更好地完成計算密集型模擬任務，但仍有進一步提升的空間。首先，現(xiàn)有并行Geo-CA模型中使用的并行策略往往是針對特定模型進行優(yōu)化的，因此限制了其對其他模型的適用性。因此需要設計出一種通用的并行策略，適用于具有類似土地利用變化模擬模塊的各種Geo-CA模型。其次，大多數(shù)并行Geo-CA模型側(cè)重于模擬模塊的并行化，而忽略了規(guī)則挖掘模塊。在規(guī)則挖掘中，簡單的算法可能不足以從各種驅(qū)動因素中挖掘出多種類型的復雜轉(zhuǎn)換規(guī)則。機器學習算法已被廣泛采用來應對這一挑戰(zhàn)。然而，這些算法通常具有較高的計算復雜度，從而降低了計算效率并使并行化工作變得復雜。鑒于計算強度不斷增加，提高規(guī)則挖掘模塊效率的需求日益增長。第三，現(xiàn)有的并行計算工具往往難以滿足現(xiàn)代Geo-CA模型的某些需求。例如，Geo-CA模型中廣泛采用需求限制型土地利用變化模擬模型來模擬各種情景下的土地利用變化，其中每種土地利用類型的比例都受到土地利用需求的約束。然而，這增加了并行化的難度。雖然不同土地利用單元的模擬在計算上是獨立的，但實時動態(tài)地統(tǒng)計每種土地利用類型的比例以確定是否滿足土地利用需求，對并行Geo-CA模型來說是一個挑戰(zhàn)。
本研究提出了一個面向地理柵格元胞自動機模型的混合架構并行計算框架。該框架的設計以當前的土地利用模擬方法為基礎，可實現(xiàn)各種面向地理柵格的Geo-CA模型的并行化。研究中提出了一種利用多種并行計算工具的混合計算架構，以并行化我們框架中多樣且計算密集的程序。首先，基于機器學習算法開發(fā)了一個并行規(guī)則挖掘模塊，以提取多種土地利用類型的轉(zhuǎn)換規(guī)則。其次，開發(fā)了受需求限制的土地利用變化模擬并行模塊，以便在分布式異構架構上實現(xiàn)更高效的模擬。此外，還提出了一種回溯機制，以確保土地利用需求對土地利用變化的約束。為了評估其性能，利用所提出的框架對兩個較先進的Geo-CA模型（即PLUS和MCCA）進行了并行化。
03、研究方法
1. 面向地理柵格元胞自動機模型的混合架構并行計算框架
研究中提出的并行計算框架由兩個模塊組成：一個用于土地利用轉(zhuǎn)換規(guī)則挖掘，另一個用于土地利用變化模擬（圖1）。轉(zhuǎn)換規(guī)則挖掘是Geo-CA模型的核心，而機器學習（ML）模型則是挖掘轉(zhuǎn)換規(guī)則的主要方法。在轉(zhuǎn)換規(guī)則挖掘模塊中，使用歷史土地利用數(shù)據(jù)和各種驅(qū)動因素訓練ML模型。然后，訓練好的模型會預測土地利用單元的轉(zhuǎn)換適宜性。在土地利用變化模擬模塊中，利用土地利用數(shù)據(jù)和預測的轉(zhuǎn)換適宜性地圖來模擬未來的土地利用地圖。通過整合這兩個模塊，我們的框架采用了普遍的土地利用變化模擬方法，從而確保其適用于各種Geo-CA模型。
圖1 包含混合并行計算模式的框架圖
為了提高計算效率，我們使用不同的并行編程工具對其中的模塊進行并行化處理。我們的框架中使用了三種并行模式，包括共享內(nèi)存模式、分布式內(nèi)存模式和異構并行模式。具體來說，在轉(zhuǎn)換規(guī)則挖掘方面，共享內(nèi)存模式和異構模式分別用于ML模型的訓練和預測。在土地利用變化模擬方面，利用名為mcRPL的通用并行地理空間柵格計算庫的擴展版本，實現(xiàn)了分布式內(nèi)存模式與異構模式相結(jié)合的混合模式。此外，還設計了一種回溯機制，以滿足受需求限制的Geo-CA模型的需求。更進一步的是，研究中還對這些并行策略進行了優(yōu)化，以應對大規(guī)模土地利用變化模擬中的挑戰(zhàn)。
2. 針對多種土地利用類型的并行規(guī)則挖掘
在我們的框架中，設計了一個并行規(guī)則挖掘模塊來挖掘多種土地利用類型的轉(zhuǎn)換規(guī)則。該模塊專為機器學習（ML）算法設計，ML算法已廣泛應用于土地利用變化模擬模型。不同的ML算法可能采用不同的計算原理，但它們在土地利用轉(zhuǎn)換規(guī)則挖掘方面的輸入和輸出是相同的。出于通用性考慮，我們總結(jié)了使用ML算法進行轉(zhuǎn)換規(guī)則挖掘的過程，并設計了由兩個計算程序組成的框架：一個用于ML模型訓練，另一個用于預測轉(zhuǎn)換適宜性。如圖2所示，該框架需要歷史土地利用數(shù)據(jù)和驅(qū)動因素作為輸入。首先對輸入數(shù)據(jù)進行采樣，形成訓練數(shù)據(jù)集。然后，訓練ML模型，以捕捉驅(qū)動因素與土地利用變化之間的關系。最后，利用訓練好的模型預測轉(zhuǎn)換適宜性地圖，該地圖顯示了每個元胞過渡到所有可能的土地利用類型的適宜性。為了提高計算效率，我們設計了一種混合并行策略，根據(jù)兩個程序的特征選擇不同的并行計算模式。這種混合并行策略的實施與具體的ML模型無關，因此我們的框架可用于多種ML算法。
圖2 并行規(guī)則挖掘模塊流程圖
在該模塊中，訓練程序采用共享內(nèi)存并行模式，使用多個CPU線程進行并行處理，而預測程序采用異構并行模式進行并行處理。與此同時，我們采用了自適應數(shù)據(jù)域分解策略來應對大規(guī)模模擬任務帶來的挑戰(zhàn)。
3. 基于分布式異構架構下的需求限制的模擬
設計并行土地利用變化模擬模塊是為了提高受需求限制的土地利用變化模擬的計算效率。如圖3所示，該模塊需要輸入轉(zhuǎn)換適宜性圖和初始土地利用圖。通過多次迭代來模擬每個土地利用元胞的土地利用變化，直至達到所有土地利用類型的土地利用需求或不發(fā)生土地利用變化。
圖3 受需求限制的并行土地利用變化模擬模塊
分布式異構并行計算已在大規(guī)模土地利用模擬應用中證明了其有效性。多臺計算機的計算資源可以滿足大規(guī)模模擬任務對計算資源和效率的需求。在我們的框架中，采用了分布式異構架構上的通用并行地理空間柵格計算庫mcRPL，因為它通過封裝編程細節(jié)簡化了并行化。為滿足現(xiàn)代Geo-CA模型的要求，mcRPL進一步擴展并整合了有關土地利用元胞的全局柵格信息，使其適用于更多的Geo-CA模型。此外，還對mcRPL中的隨機數(shù)生成器進行了調(diào)整，以滿足Geo-CA模型對多類型隨機值的要求。
除此之外，框架中還為該模塊提出了一種回溯機制，以確保土地利用的變化能夠受到全局需求的限制。每次迭代后，都能夠計算每種土地利用類型的比例，以確定是否超出土地利用需求。如果在迭代i中超過了k類型的需求，則將回溯該迭代中的土地利用變化。如圖4所示，一些元胞的土地利用類型被選擇回溯，而另一些元胞則在迭代i后保留土地利用類型。在回溯后，進一步比較土地利用類型的比例和需求以保證剛剛達到土地使用需求且不會超出。
圖4 回溯機制
在大多數(shù)模擬迭代中，回溯機制避免了實時比例計算和跨處理器的數(shù)據(jù)通信。它僅在超出需求的迭代中運行，因此其他迭代的效率不受影響。因此，該機制保持了分布式異構架構上受需求限制的土地利用變化模擬的有效性，并提高了其計算效率。
04實驗
本研究使用了提出的框架對兩種現(xiàn)代Geo-CA模型（PLUS和MCCA）進行了并行化。我們在天河二號超級計算機上使用mcPLUS和mcMCCA進行了一系列實驗，以評估提出的框架的性能。天河二號的每個節(jié)點的配置都為兩個英特爾至強E5-2660 2.6 GHz 10核CPU、256 GB主內(nèi)存和四個Nvidia Tesla K80 GPU。PLUS和MCCA也在天河二號GPU節(jié)點上運行作為mcPLUS和mcMCCA的基準，它們只使用天河二號GPU節(jié)點上的CPU。實驗中使用的土地利用數(shù)據(jù)集包括中國湖北省2008年和2018年的土地利用數(shù)據(jù)。具體來說，mcPLUS使用的是30m分辨率的原始土地利用數(shù)據(jù)集，mcMCCA使用的是將原始數(shù)據(jù)匯總為90米分辨率的混合單元土地利用數(shù)據(jù)集。
對于土地利用轉(zhuǎn)換規(guī)則挖掘部分，研究中對比了并行版本與普通版本模型的計算時間。實驗結(jié)果表明（圖5），研究中提出的框架能夠提高土地利用轉(zhuǎn)換規(guī)則挖掘部分的計算效率。在并行過后，mcPLUS和mcMCCA分別比PLUS和MCCA快19.1倍和5.9倍。
圖5 土地利用轉(zhuǎn)換規(guī)則挖掘模塊的運行時間以及加速比
對于土地利用變化模擬部分，進行了兩次精度實驗，以驗證提出的框架對 Geo-CA模型進行并行化不會影響其精度。還進行了一次效率實驗，以評估該框架在提高Geo-CA模型效率方面的有效性。在第一個精度實驗中，使用相同的輸入對Geo-CA模型進行了比較。如圖6（a）所示，使用mcPLUS模擬的土地利用圖與使用PLUS模擬的土地利用圖完全相同。mcMCCA對各土地利用類型的模擬結(jié)果與MCCA相同，其結(jié)果以林地為例展示（圖6（b））。
圖6 2018年土地利用變化圖：（a）PLUS和mcPLUS；（b）MCCA和mcMCCA
在第二個精度實驗中，我們評估了PLUS、MCCA、mcPLUS和mcMCCA在實際應用中的精度。如表1所示，PLUS和mcPLUS與MCCA和mcMCCA的精度基本相同。精度上的細微差別是由于隨機因素造成的，而隨機因素對于我們實驗中的Geo-CA模型是必要的。
表1 PLUS、mcPLUS、MCCA和mcMCCA的模擬精度
在效率實驗中，我們記錄了PLUS、mcPLUS、MCCA和mcMCCA在實際應用中的運行時間。實驗結(jié)果如圖7所示，這表明研究中提出的框架能夠提高土地利用變化模擬部分的計算效率。在并行過后，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 土地利用變化模擬模塊的運行時間以及加速比
05、總結(jié)
本研究提出了一種基于混合并行計算架構的并行框架，用于開發(fā)面向地理柵格的并行Geo-CA模型。該框架的設計考慮了Geo-CA模型的發(fā)展趨勢，確保其適用于廣泛的Geo-CA模型，尤其是現(xiàn)代和廣泛使用的模型。在轉(zhuǎn)換規(guī)則挖掘和土地利用變化模擬中，混合計算架構與各種并行工具被用于并行化理論上多樣且計算密集的程序。此外，研究中提出了一種回溯機制，通過混合計算架構上的土地利用需求，有效約束土地利用變化。與提出框架的工作流程部分或完全相似的Geo-CA模型都可以使用該框架進行并行化。
所提出的框架已被應用于并行化兩個現(xiàn)代的且廣泛使用的Geo-CA模型。實驗結(jié)果表明，在基本保證精度的前提下，土地利用轉(zhuǎn)換規(guī)則挖掘和土地利用變化模擬的計算效率都有了顯著提高。此外，增加GPU的數(shù)量還能進一步提高土地利用變化模擬的效率，證明了該框架在利用多種計算資源方面的可擴展性。研究中提出的框架在效率、精度和可擴展性方面的表現(xiàn)都能證明了其在大規(guī)模土地利用變化模擬中加強Geo-CA模型應用的潛力。在未來，我們的計劃是用其他支持更多處理器的并行工具取代CUDA，從而進一步提高我們框架的通用性。
