并行地理元胞自动机的计算强度时空变化模式及动态负载均衡方法研究

Dynamic load balancing helps improve the computational efficiency of parallel spatio-temporal dynamic models, and the spatio-temporal dynamics of computational intensity is one of the key factors for dynamic load balancing. This project aims to study the theory and methodology of parallel geospatial cellular automata (CA), including: (1) the spatio-temporal mechanism and models of of computational intensity, the “Computational Intensity Cubes” representation model, and the prediction methods of computational intensity; (2) the sub-domain assigning method based on hypergraph partitioning to achieve load balance and minimal communication cost among computing nodes; the dynamic load-balancing method and “Emigrating-Subdomain-First” scheduling method based on the consideration of the spatio-temporal dynamics of computational intensity, communication cost, data migration cost and optimization cost; (3) the pSLEUTH as an example of parallel geospatial CA with dynamic load balancing to evaluate the effectiveness of the theory and methods developed in this study. This project will enhance the computational performance, usability and scalability of spatio-temporal dynamic models, improve the theory and methodology of parallel geospatial computing, and provide supports for large-scale spatio-temporal dynamic simulation and decision making using big spatio-temporal data and complex algorithms.

动态负载均衡有利于提高并行时空演化模型的计算效率，而计算强度的时空变化模式是动态负载均衡的重要依据。本项目以地理元胞自动机（CA）为对象，拟开展以下研究：（1）通过分析地理CA转换规则和数据I/O的时空特征，研究计算强度时空变化机理及建模方法、“计算强度立方体”时空模式表征模型和计算强度预测方法；（2）研究基于超图分割的子空间域分配求解方法，以达到计算节点间负载均衡和交互代价最小；综合考虑计算强度时空变化模式、交互代价、迁移代价和优化求解代价，研究并行地理CA的动态负载均衡方法和“迁出子空间域优先计算”任务调度方法；（3）以SLEUTH模型为例，实现并行地理CA并应用动态负载均衡方法，通过实验验证和评价以上理论和方法的有效性。通过以上研究，可以提高地理CA的时效性、可用性和可扩展性，扩展高性能空间计算的理论和方法，为基于时空大数据和复杂算法的时空演化模拟研究以及决策制定提供支持。

基于元胞自动机（Cellular Automata, CA）的时空演化模型被广泛应用于模拟和预测土地利用的动态变化过程。已有的并行CA模型大都采用静态负载均衡的方式，缺乏综合考虑计算强度、交互代价和迁移代价的动态负载均衡方法。针对此问题，本项目以地理CA为对象，在离散内存并行计算环境下，开展以下研究：1）地理CA中计算强度时空变化机理与模式的建模、表征和预测方法；2）并行地理CA的动态负载均衡方法；3）以上方法在土地利用变化模拟模型的并行计算中的应用。.本项目主要研究成果：1）开发了一个栅格大数据并行I/O库pGTIOL，可支持对条带存储于块状存储数据的异步并行读写，并将其集成到并行栅格处理库pRPL中，满足动态负载均衡对海量栅格数据并行I/O的需求；2）提出了一个CPU/GPU异构集群架构下的通用并行栅格处理编程框架mcRPL，可将栅格数据分配到多个计算处理器上同时进行计算，加速效果明显；3）实现了并行地理CA的动态负载均衡方法，研究提出一个子空间域迁移优先算法，通过超图分割的方式将子域动态地重新分配给进程，解决了计算强度时空动态变化导致的计算单元间负载不均衡问题。与静态负载均衡的并行CA相比，计算性能从21.4%提高到63.3%。4）提出了包括真实地块矢量元胞自动机（CNN-VCA）、斑块生成土地利用模拟模型（PLUS）和混合元胞自动机（MCCA）等在内的多种城市发展模拟模型，并发布相关模型软件供全球研究者免费下载，支持算法并行和模拟过程的可视化。.通过本项目研究，团队共发表期刊论文30篇，其中SCI/SSCI期刊论文26篇，EI论文1篇，中文核心论文3篇；获批专利3项；研发软件5套，并全部在互联网上免费共享，部分软件源代码也共享。.本项目研究是对高性能地理空间计算理论与方法的扩展和补充，提高了时空演化模型的时效性、可用性和可扩展性，为利用高分辨率时空大数据和复杂算法的大规模时空演化模拟提供支持。同时，项目研究为快速制定空间决策（如城市规划、土地利用政策）提供方法和技术支持，具有重要的应用价值。