论文推送 | 面向地理栅格元胞自动机模型的混合架构并行计算框架

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

作者简介：

高欢（共同一作），博士研究生，中国地质大学（武汉）地理与信息工程学院。研究方向为高性能空间计算。

梁哲玮（共同一作），博士研究生，中国地质大学（武汉）地理与信息工程学院。研究方向为高性能空间计算和地理时空动态模拟。

关庆锋（通讯作者），博士，教授，博导，中国地质大学（武汉）地理与信息工程学院。研究方向包括时空大数据、空间计算智能和高性能空间计算。

梁迅，博士，教授，中国地质大学（武汉）地理与信息工程学院。研究方向为地理时空动态模拟和城市规划技术。

曾文，博士，教授，博导，中国地质大学（武汉）地理与信息工程学院。研究方向为空间计算智能，地理网络模型及优化算法。

01、摘要

在进行大规模土地利用变化模拟应用时，地理空间元胞自动机（Geo-CA）模型在计算效率和可扩展性方面遇到了挑战。并行计算被证明可以有效应对这些挑战。然而，现有并行Geo-CA模型的并行化策略总是针对特定模型进行优化，对其他模型缺乏适用性。除此之外，大多数并行Geo-CA模型侧重于土地利用变化模拟的并行化，而忽视了土地利用转换规则挖掘部分。而且，在分布式异构架构上进行受需求约束的土地利用变化模拟时缺乏有效的并行策略。本研究提出了一种适用于面向地理栅格元胞自动机模型的混合架构并行计算框架，以提高其计算效率和可扩展性的同时保持模拟精度。该框架为多种土地利用类型的土地利用转换规则挖掘和分布式异构架构上的需求限制的土地利用变化模拟提供了并行化策略。该框架被用于并行化两个现代的Geo-CA模型，即PLUS和MCCA。实验表明，并行化后的模型在计算效率和可扩展性方面都有显著提高，证实了所提出的框架在大规模土地利用变化模拟研究中的有效性。

02、引言

土地利用反映了人类活动与自然环境之间的关系。土地利用建模可增强对土地利用动态的理解，并能预测未来土地利用的变化，为规划实践中的可持续发展提供支持。土地利用模拟模型被开发出来用于模拟时空土地利用变化，如地理空间元胞自动机（Geo-CA）模型。由于它们能捕捉当地的空间相互作用和时间动态，这些模型在制定环境保护和土地利用规划政策方面至关重要。

Geo-CA模型将土地利用空间抽象为元胞，每个元胞都有特定的状态，并通过模拟这些元胞的状态变化来描述土地利用动态。近些年来，Geo-CA模型的所有基本要素都得到了增强，包括元胞、元胞状态、邻域和转换规则。然而，Geo-CA模型在计算强度方面遇到了挑战，主要原因是数据密度和计算复杂性。一方面，扩大模拟任务的规模和/或使用高分辨率地理空间数据可提高土地利用变化模拟结果的全面性和质量。不过，这也会导致数据密度增加。另一方面，更复杂的理论和技术被用于提高模拟性能，从而导致计算复杂度增加。数据密度和计算复杂性的增加导致计算效率下降，对计算资源的需求增加。这些限制因素对在大规模土地利用动态应用中有效使用Geo-CA模型提出了挑战。

现有并行Geo-CA模型的开发有效地解决了上述问题，成功地提高了土地利用变化模拟的计算效率。与普通Geo-CA模型相比，这些并行模型能更好地完成计算密集型模拟任务，但仍有进一步提升的空间。首先，现有并行Geo-CA模型中使用的并行策略往往是针对特定模型进行优化的，因此限制了其对其他模型的适用性。因此需要设计出一种通用的并行策略，适用于具有类似土地利用变化模拟模块的各种Geo-CA模型。其次，大多数并行Geo-CA模型侧重于模拟模块的并行化，而忽略了规则挖掘模块。在规则挖掘中，简单的算法可能不足以从各种驱动因素中挖掘出多种类型的复杂转换规则。机器学习算法已被广泛采用来应对这一挑战。然而，这些算法通常具有较高的计算复杂度，从而降低了计算效率并使并行化工作变得复杂。鉴于计算强度不断增加，提高规则挖掘模块效率的需求日益增长。第三，现有的并行计算工具往往难以满足现代Geo-CA模型的某些需求。例如，Geo-CA模型中广泛采用需求限制型土地利用变化模拟模型来模拟各种情景下的土地利用变化，其中每种土地利用类型的比例都受到土地利用需求的约束。然而，这增加了并行化的难度。虽然不同土地利用单元的模拟在计算上是独立的，但实时动态地统计每种土地利用类型的比例以确定是否满足土地利用需求，对并行Geo-CA模型来说是一个挑战。

本研究提出了一个面向地理栅格元胞自动机模型的混合架构并行计算框架。该框架的设计以当前的土地利用模拟方法为基础，可实现各种面向地理栅格的Geo-CA模型的并行化。研究中提出了一种利用多种并行计算工具的混合计算架构，以并行化我们框架中多样且计算密集的程序。首先，基于机器学习算法开发了一个并行规则挖掘模块，以提取多种土地利用类型的转换规则。其次，开发了受需求限制的土地利用变化模拟并行模块，以便在分布式异构架构上实现更高效的模拟。此外，还提出了一种回溯机制，以确保土地利用需求对土地利用变化的约束。为了评估其性能，利用所提出的框架对两个较先进的Geo-CA模型（即PLUS和MCCA）进行了并行化。

03、研究方法

1. 面向地理栅格元胞自动机模型的混合架构并行计算框架

研究中提出的并行计算框架由两个模块组成：一个用于土地利用转换规则挖掘，另一个用于土地利用变化模拟（图1）。转换规则挖掘是Geo-CA模型的核心，而机器学习（ML）模型则是挖掘转换规则的主要方法。在转换规则挖掘模块中，使用历史土地利用数据和各种驱动因素训练ML模型。然后，训练好的模型会预测土地利用单元的转换适宜性。在土地利用变化模拟模块中，利用土地利用数据和预测的转换适宜性地图来模拟未来的土地利用地图。通过整合这两个模块，我们的框架采用了普遍的土地利用变化模拟方法，从而确保其适用于各种Geo-CA模型。

图1 包含混合并行计算模式的框架图

为了提高计算效率，我们使用不同的并行编程工具对其中的模块进行并行化处理。我们的框架中使用了三种并行模式，包括共享内存模式、分布式内存模式和异构并行模式。具体来说，在转换规则挖掘方面，共享内存模式和异构模式分别用于ML模型的训练和预测。在土地利用变化模拟方面，利用名为mcRPL的通用并行地理空间栅格计算库的扩展版本，实现了分布式内存模式与异构模式相结合的混合模式。此外，还设计了一种回溯机制，以满足受需求限制的Geo-CA模型的需求。更进一步的是，研究中还对这些并行策略进行了优化，以应对大规模土地利用变化模拟中的挑战。

2. 针对多种土地利用类型的并行规则挖掘

在我们的框架中，设计了一个并行规则挖掘模块来挖掘多种土地利用类型的转换规则。该模块专为机器学习（ML）算法设计，ML算法已广泛应用于土地利用变化模拟模型。不同的ML算法可能采用不同的计算原理，但它们在土地利用转换规则挖掘方面的输入和输出是相同的。出于通用性考虑，我们总结了使用ML算法进行转换规则挖掘的过程，并设计了由两个计算程序组成的框架：一个用于ML模型训练，另一个用于预测转换适宜性。如图2所示，该框架需要历史土地利用数据和驱动因素作为输入。首先对输入数据进行采样，形成训练数据集。然后，训练ML模型，以捕捉驱动因素与土地利用变化之间的关系。最后，利用训练好的模型预测转换适宜性地图，该地图显示了每个元胞过渡到所有可能的土地利用类型的适宜性。为了提高计算效率，我们设计了一种混合并行策略，根据两个程序的特征选择不同的并行计算模式。这种混合并行策略的实施与具体的ML模型无关，因此我们的框架可用于多种ML算法。

图2 并行规则挖掘模块流程图

在该模块中，训练程序采用共享内存并行模式，使用多个CPU线程进行并行处理，而预测程序采用异构并行模式进行并行处理。与此同时，我们采用了自适应数据域分解策略来应对大规模模拟任务带来的挑战。

3. 基于分布式异构架构下的需求限制的模拟

设计并行土地利用变化模拟模块是为了提高受需求限制的土地利用变化模拟的计算效率。如图3所示，该模块需要输入转换适宜性图和初始土地利用图。通过多次迭代来模拟每个土地利用元胞的土地利用变化，直至达到所有土地利用类型的土地利用需求或不发生土地利用变化。

图3 受需求限制的并行土地利用变化模拟模块

分布式异构并行计算已在大规模土地利用模拟应用中证明了其有效性。多台计算机的计算资源可以满足大规模模拟任务对计算资源和效率的需求。在我们的框架中，采用了分布式异构架构上的通用并行地理空间栅格计算库mcRPL，因为它通过封装编程细节简化了并行化。为满足现代Geo-CA模型的要求，mcRPL进一步扩展并整合了有关土地利用元胞的全局栅格信息，使其适用于更多的Geo-CA模型。此外，还对mcRPL中的随机数生成器进行了调整，以满足Geo-CA模型对多类型随机值的要求。

除此之外，框架中还为该模块提出了一种回溯机制，以确保土地利用的变化能够受到全局需求的限制。每次迭代后，都能够计算每种土地利用类型的比例，以确定是否超出土地利用需求。如果在迭代i中超过了k类型的需求，则将回溯该迭代中的土地利用变化。如图4所示，一些元胞的土地利用类型被选择回溯，而另一些元胞则在迭代i后保留土地利用类型。在回溯后，进一步比较土地利用类型的比例和需求以保证刚刚达到土地使用需求且不会超出。

图4 回溯机制

在大多数模拟迭代中，回溯机制避免了实时比例计算和跨处理器的数据通信。它仅在超出需求的迭代中运行，因此其他迭代的效率不受影响。因此，该机制保持了分布式异构架构上受需求限制的土地利用变化模拟的有效性，并提高了其计算效率。

04实验

本研究使用了提出的框架对两种现代Geo-CA模型（PLUS和MCCA）进行了并行化。我们在天河二号超级计算机上使用mcPLUS和mcMCCA进行了一系列实验，以评估提出的框架的性能。天河二号的每个节点的配置都为两个英特尔至强E5-2660 2.6 GHz 10核CPU、256 GB主内存和四个Nvidia Tesla K80 GPU。PLUS和MCCA也在天河二号GPU节点上运行作为mcPLUS和mcMCCA的基准，它们只使用天河二号GPU节点上的CPU。实验中使用的土地利用数据集包括中国湖北省2008年和2018年的土地利用数据。具体来说，mcPLUS使用的是30m分辨率的原始土地利用数据集，mcMCCA使用的是将原始数据汇总为90米分辨率的混合单元土地利用数据集。

对于土地利用转换规则挖掘部分，研究中对比了并行版本与普通版本模型的计算时间。实验结果表明（图5），研究中提出的框架能够提高土地利用转换规则挖掘部分的计算效率。在并行过后，mcPLUS和mcMCCA分别比PLUS和MCCA快19.1倍和5.9倍。

图5 土地利用转换规则挖掘模块的运行时间以及加速比

对于土地利用变化模拟部分，进行了两次精度实验，以验证提出的框架对 Geo-CA模型进行并行化不会影响其精度。还进行了一次效率实验，以评估该框架在提高Geo-CA模型效率方面的有效性。在第一个精度实验中，使用相同的输入对Geo-CA模型进行了比较。如图6（a）所示，使用mcPLUS模拟的土地利用图与使用PLUS模拟的土地利用图完全相同。mcMCCA对各土地利用类型的模拟结果与MCCA相同，其结果以林地为例展示（图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在实际应用中的运行时间。实验结果如图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、总结

本研究提出了一种基于混合并行计算架构的并行框架，用于开发面向地理栅格的并行Geo-CA模型。该框架的设计考虑了Geo-CA模型的发展趋势，确保其适用于广泛的Geo-CA模型，尤其是现代和广泛使用的模型。在转换规则挖掘和土地利用变化模拟中，混合计算架构与各种并行工具被用于并行化理论上多样且计算密集的程序。此外，研究中提出了一种回溯机制，通过混合计算架构上的土地利用需求，有效约束土地利用变化。与提出框架的工作流程部分或完全相似的Geo-CA模型都可以使用该框架进行并行化。

所提出的框架已被应用于并行化两个现代的且广泛使用的Geo-CA模型。实验结果表明，在基本保证精度的前提下，土地利用转换规则挖掘和土地利用变化模拟的计算效率都有了显著提高。此外，增加GPU的数量还能进一步提高土地利用变化模拟的效率，证明了该框架在利用多种计算资源方面的可扩展性。研究中提出的框架在效率、精度和可扩展性方面的表现都能证明了其在大规模土地利用变化模拟中加强Geo-CA模型应用的潜力。在未来，我们的计划是用其他支持更多处理器的并行工具取代CUDA，从而进一步提高我们框架的通用性。