A hybrid parallel cellular automata model for urban growth simulation over GPU/CPU heterogeneous architectures

As an important spatiotemporal simulation approach and an effective tool for developing and examining spatial optimization strategies (e.g., land allocation and planning), geospatial cellular automata (CA) models often require multiple data layers and consist of complicated algorithms in order to deal with the complex dynamic processes of interest and the intricate relationships and interactions between the processes and their driving factors. Also, massive amount of data may be used in CA simulations as high-resolution geospatial and non-spatial data are widely available. Thus, geospatial CA models can be both computationally intensive and data intensive, demanding extensive length of computing time and vast memory space. Based on a hybrid parallelism that combines processes with discrete memory and threads with global memory, we developed a parallel geospatial CA model for urban growth simulation over the heterogeneous computer architecture composed of multiple central processing units (CPUs) and graphics processing units (GPUs). Experiments with the datasets of California showed that the overall computing time for a 50-year simulation dropped from 13,647 seconds on a single CPU to 32 seconds using 64 GPU/CPU nodes. We conclude that the hybrid parallelism of geospatial CA over the emerging heterogeneous computer architectures provides scalable solutions to enabling complex simulations and optimizations with massive amount of data that were previously infeasible, sometimes impossible, using individual computing approaches.     

Developing a parallel computational implementation of AMOEBA

As geospatial researchers' access to high-performance computing clusters continues to increase alongside the availability of high-resolution spatial data, it is imperative that techniques are devised to exploit these clusters' ability to quickly process and analyze large amounts of information. This research concentrates on the parallel computation of A Multidirectional Optimal Ecotope-Based Algorithm (AMOEBA). AMOEBA is used to derive spatial weight matrices for spatial autoregressive models and as a method for identifying irregularly shaped spatial clusters. While improvements have been made to the original ‘exhaustive’ algorithm, the resulting ‘constructive’ algorithm can still take a significant amount of time to complete with large datasets. This article outlines a parallel implementation of AMOEBA (the P-AMOEBA) written in Java utilizing the message passing library MPJ Express. In order to account for differing types of spatial grid data, two decomposition methods are developed and tested. The benefits of using the new parallel algorithm are demonstrated on an example dataset. Results show that different decompositions of spatial data affect the computational load balance across multiple processors and that the parallel version of AMOEBA achieves substantially faster runtimes than those reported in related publications.     

Parallel cellular automata for large-scale urban simulation using load-balancing techniques

Cellular automata (CA), which are a kind of bottom-up approaches, can be used to simulate urban dynamics and land use changes effectively. Urban simulation usually involves a large set of GIS data in terms of the extent of the study area and the number of spatial factors. The computation capability becomes a bottleneck of implementing CA for simulating large regions. Parallel computing techniques can be applied to CA for solving this kind of hard computation problem. This paper demonstrates that the performance of large-scale urban simulation can be significantly improved by using parallel computation techniques. The proposed urban CA is implemented in a parallel framework that runs on a cluster of PCs. A large region usually consists of heterogeneous or polarized development patterns. This study proposes a line-scanning method of load balance to reduce waiting time between parallel processors. This proposed method has been tested in a fast-growing region, the Pearl River Delta. The experiments indicate that parallel computation techniques with load balance can significantly improve the applicability of CA for simulating the urban development in this large complex region.     

Predicting the visualization intensity for interactive spatio-temporal visual analytics: a data-driven view-dependent approach

The continually increasing size of geospatial data sets poses a computational challenge when conducting interactive visual analytics using conventional desktop-based visualization tools. In recent decades, improvements in parallel visualization using state-of-the-art computing techniques have significantly enhanced our capacity to analyse massive geospatial data sets. However, only a few strategies have been developed to maximize the utilization of parallel computing resources to support interactive visualization. In particular, an efficient visualization intensity prediction component is lacking from most existing parallel visualization frameworks. In this study, we propose a data-driven view-dependent visualization intensity prediction method, which can dynamically predict the visualization intensity based on the distribution patterns of spatio-temporal data. The predicted results are used to schedule the allocation of visualization tasks. We integrated this strategy with a parallel visualization system deployed in a compute unified device architecture (CUDA)-enabled graphical processing units (GPUs) cloud. To evaluate the flexibility of this strategy, we performed experiments using dust storm data sets produced from a regional climate model. The results of the experiments showed that the proposed method yields stable and accurate prediction results with acceptable computational overheads under different types of interactive visualization operations. The results also showed that our strategy improves the overall visualization efficiency by incorporating intensity-based scheduling.     

A machine learning approach for predicting computational intensity and domain decomposition in parallel geoprocessing

ABSTRACT

High performance computing is required for fast geoprocessing of geospatial big data. Using spatial domains to represent computational intensity (CIT) and domain decomposition for parallelism are prominent strategies when designing parallel geoprocessing applications. Traditional domain decomposition is limited in evaluating the computational intensity, which often results in load imbalance and poor parallel performance. From the data science perspective, machine learning from Artificial Intelligence (AI) shows promise for better CIT evaluation. This paper proposes a machine learning approach for predicting computational intensity, followed by an optimized domain decomposition, which divides the spatial domain into balanced subdivisions based on the predicted CIT to achieve better parallel performance. The approach provides a reference framework on how various machine learning methods including feature selection and model training can be used in predicting computational intensity and optimizing parallel geoprocessing against different cases. Some comparative experiments between the approach and traditional methods were performed using the two cases, DEM generation from point clouds and spatial intersection on vector data. The results not only demonstrate the advantage of the approach, but also provide hints on how traditional GIS computation can be improved by the AI machine learning.     

Characterization of neighborhood sensitivity of an irregular cellular automata model of urban growth

The neighborhood definition, which determines the influence on a cell from its nearby cells within a localized region, plays a critical role in the performance of a cellular automaton (CA) model. Raster CA models use a cellular grid to represent geographic space, and are sensitive to the cell size and neighborhood configuration. However, the sensitivity of vector-based CAs, an alternative to the raster-based counterpart, to neighborhood type and size remains uninvestigated. The present article reports the results of a detailed sensitivity analysis of an irregular CA model of urban land use dynamics. The model uses parcel data at the cadastral scale to represent geographic space, and was implemented to simulate urban growth in Central Texas, USA. Thirty neighborhood configurations defined by types and sizes were considered in order to examine the variability in the model outcome. Results from accuracy assessments and landscape metrics confirmed the model’s sensitivity to neighborhood configurations. Furthermore, the centroid intercepted neighborhood with a buffer of 120 m produced the most accurate simulation result. This neighborhood produced scattered development while the centroid extent-wide neighborhood resulted in a clustered development predominantly near the city center.     

A GPU-accelerated adaptive kernel density estimation approach for efficient point pattern analysis on spatial big data

Kernel density estimation (KDE) is a classic approach for spatial point pattern analysis. In many applications, KDE with spatially adaptive bandwidths (adaptive KDE) is preferred over KDE with an invariant bandwidth (fixed KDE). However, bandwidths determination for adaptive KDE is extremely computationally intensive, particularly for point pattern analysis tasks of large problem sizes. This computational challenge impedes the application of adaptive KDE to analyze large point data sets, which are common in this big data era. This article presents a graphics processing units (GPUs)-accelerated adaptive KDE algorithm for efficient spatial point pattern analysis on spatial big data. First, optimizations were designed to reduce the algorithmic complexity of the bandwidth determination algorithm for adaptive KDE. The massively parallel computing resources on GPU were then exploited to further speed up the optimized algorithm. Experimental results demonstrated that the proposed optimizations effectively improved the performance by a factor of tens. Compared to the sequential algorithm and an Open Multiprocessing (OpenMP)-based algorithm leveraging multiple central processing unit cores for adaptive KDE, the GPU-enabled algorithm accelerated point pattern analysis tasks by a factor of hundreds and tens, respectively. Additionally, the GPU-accelerated adaptive KDE algorithm scales reasonably well while increasing the size of data sets. Given the significant acceleration brought by the GPU-enabled adaptive KDE algorithm, point pattern analysis with the adaptive KDE approach on large point data sets can be performed efficiently. Point pattern analysis on spatial big data, computationally prohibitive with the sequential algorithm, can be conducted routinely with the GPU-accelerated algorithm. The GPU-accelerated adaptive KDE approach contributes to the geospatial computational toolbox that facilitates geographic knowledge discovery from spatial big data.     

地理元胞自动机模型研究进展

元胞自动机(Cellular Automata,简称CA)是一种基于微观个体的相互作用空间离散动态模型,其强大的计算功能、固有的平行计算能力、高度动态及空间概念等特征,使它在模拟空间复杂系统的时空动态演变研究具有较强的优势。文章回顾了元胞自动机的发展历程,阐述了CA在地理学中的主要应用领域和研究进展,在此基础上,以现实世界地理实体及现代城市扩张特征为视角,分析目前CA研究所面临的问题,并对其未来的研究趋势进行了初步探讨,认为以下3个方面将是未来CA研究的热点：① 利用不规则元胞及可控邻域的CA模型,对不同规则或不同邻域地理实体的模拟研究;② 采用三维元胞自动机对现代城市扩张进行立体化模拟,以克服二维CA模型的缺陷;③ 将矢量元胞自动机模型应用于地理实体的模拟研究,进一步提高模拟精度。     

Using adaptively coupled models and high-performance computing for enabling the computability of dust storm forecasting

Forecasting dust storms for large geographical areas with high resolution poses great challenges for scientific and computational research. Limitations of computing power and the scalability of parallel systems preclude an immediate solution to such challenges. This article reports our research on using adaptively coupled models to resolve the computational challenges and enable the computability of dust storm forecasting by dividing the large geographical domain into multiple subdomains based on spatiotemporal distributions of the dust storm. A dust storm model (Eta-8bin) performs a quick forecasting with low resolution (22 km) to identify potential hotspots with high dust concentration. A finer model, non-hydrostatic mesoscale model (NMM-dust) performs high-resolution (3 km) forecasting over the much smaller hotspots in parallel to reduce computational requirements and computing time. We also adopted spatiotemporal principles among computing resources and subdomains to optimize parallel systems and improve the performance of high-resolution NMM-dust model. This research enabled the computability of high-resolution, large-area dust storm forecasting using the adaptively coupled execution of the two models Eta-8bin and NMM-dust.     

How much past to see the future: a computational study in calibrating urban cellular automata

The objective of this computational study was to investigate to which extent the availability and the way of use of historical maps may affect the quality of the calibration process of cellular automata (CA) urban models. The numerical experiments are based on a constrained CA applied to a case study. Since the model depends on a large number of parameters, we optimize the CA using cooperative coevolutionary particle swarms, which is an approach known for its ability to operate effectively in search spaces with a high number of dimensions. To cope with the relevant computational cost related to the high number of CA simulations required by our study, we use a parallelized CA model that takes advantage of the computing power of graphics processing units. The study has shown that the accuracy of simulations can be significantly influenced by both the number and position in time of the historical maps involved in the calibration.     

Calibrating a Land Parcel Cellular Automaton (LP-CA) for urban growth simulation based on ensemble learning

The reliability of raster cellular automaton (CA) models for fine-scale land change simulations has been increasingly questioned, because regular pixels/grids cannot precisely represent irregular geographical entities and their interactions. Vector CA models can address these deficiencies due to the ability of the vector data structure to represent realistic urban entities. This study presents a new land parcel cellular automaton (LP-CA) model for simulating urban land changes. The innovation of this model is the use of ensemble learning method for automatic calibration. The proposed model is applied in Shenzhen, China. The experimental results indicate that bagging-Naïve Bayes yields the highest calibration accuracy among a set of selected classifiers. The assessment of neighborhood sensitivity suggests that the LP-CA model achieves the highest simulation accuracy with neighbor radius r = 2. The calibrated LP-CA is used to project future urban land use changes in Shenzhen, and the results are found to be consistent with those specified in the official city plan.     

Mapping fine-scale population distributions at the building level by integrating multisource geospatial big data

Fine-scale population distribution data at the building level play an essential role in numerous fields, for example urban planning and disaster prevention. The rapid technological development of remote sensing (RS) and geographical information system (GIS) in recent decades has benefited numerous population distribution mapping studies. However, most of these studies focused on global population and environmental changes; few considered fine-scale population mapping at the local scale, largely because of a lack of reliable data and models. As geospatial big data booms, Internet-collected volunteered geographic information (VGI) can now be used to solve this problem. This article establishes a novel framework to map urban population distributions at the building scale by integrating multisource geospatial big data, which is essential for the fine-scale mapping of population distributions. First, Baidu points-of-interest (POIs) and real-time Tencent user densities (RTUD) are analyzed by using a random forest algorithm to down-scale the street-level population distribution to the grid level. Then, we design an effective iterative building-population gravity model to map population distributions at the building level. Meanwhile, we introduce a densely inhabited index (DII), generated by the proposed gravity model, which can be used to estimate the degree of residential crowding. According to a comparison with official community-level census data and the results of previous population mapping methods, our method exhibits the best accuracy (Pearson R = .8615, RMSE = 663.3250, p < .0001). The produced fine-scale population map can offer a more thorough understanding of inner city population distributions, which can thus help policy makers optimize the allocation of resources.     

A parallel computing approach to viewshed analysis of large terrain data using graphics processing units

Viewshed analysis, often supported by geographic information system, is widely used in many application domains. However, as terrain data continue to become increasingly large and available at high resolutions, data-intensive viewshed analysis poses significant computational challenges. General-purpose computation on graphics processing units (GPUs) provides a promising means to address such challenges. This article describes a parallel computing approach to data-intensive viewshed analysis of large terrain data using GPUs. Our approach exploits the high-bandwidth memory of GPUs and the parallelism of massive spatial data to enable memory-intensive and computation-intensive tasks while central processing units are used to achieve efficient input/output (I/O) management. Furthermore, a two-level spatial domain decomposition strategy has been developed to mitigate a performance bottleneck caused by data transfer in the memory hierarchy of GPU-based architecture. Computational experiments were designed to evaluate computational performance of the approach. The experiments demonstrate significant performance improvement over a well-known sequential computing method, and an enhanced ability of analyzing sizable datasets that the sequential computing method cannot handle.     

Near real-time geoprocessing on the grid: A scalable approach to road traffic monitoring

The geospatial sensor web is set to revolutionise real-time geospatial applications by making up-to-date spatially and temporally referenced data relating to real-world phenomena ubiquitously available. The uptake of sensor web technologies is largely being driven by the recent introduction of the OpenGIS Sensor Web Enablement framework, a standardisation initiative that defines a set of web service interfaces and encodings to task and query geospatial sensors in near real time. However, live geospatial sensors are capable of producing vast quantities of data over a short time period, which presents a large, fluctuating and ongoing processing requirement that is difficult to adequately provide with the necessary computational resources. Grid computing appears to offer a promising solution to this problem but its usage thus far has primarily been restricted to processing static as opposed to real-time data sets. A new approach is presented in this work whereby geospatial data streams are processed on grid computing resources. This is achieved by submitting ongoing processing jobs to the grid that continually poll sensor data repositories using relevant OpenGIS standards. To evaluate this approach a road-traffic monitoring application was developed to process streams of GPS observations from a fleet of vehicles. Specifically, a Bayesian map-matching algorithm is performed that matches each GPS observation to a link on the road network. The results show that over 90% of observations were matched correctly and that the adopted approach is capable of achieving timely results for a linear time geoprocessing operation performed every 60 seconds. However, testing in a production grid environment highlighted some scalability and efficiency problems. Open Geospatial Consortium (OGC) data services were found to present an IO bottleneck and the adopted job submission method was found to be inefficient. Consequently, a number of recommendations are made regarding the grid job-scheduling mechanism, shortcomings in the OGC Web Processing Service specification and IO bottlenecks in OGC data services.     

Local interpolation using a distributed parallel supercomputer

Abstract

Large spatial interpolation problems present significant computational challenges even for the fastest workstations. In this paper we demonstrate how parallel processing can be used to reduce computation times to levels that are suitable for interactive interpolation analyses of large spatial databases. Though the approach developed in this paper can be used with a wide variety of interpolation algorithms, we specifically contrast the results obtained from a global ‘brute force’ inverse–distance weighted interpolation algorithm with those obtained using a much more efficient local approach. The parallel versions of both implementations are superior to their sequential counterparts. However, the local version of the parallel algorithm provides the best overall performance.     

An IO-efficient parallel implementation of an R2 viewshed algorithm for large terrain maps on a CUDA GPU

A rapid and flexible parallel approach for viewshed computation on large digital elevation models is presented. Our work is focused on the implementation of a derivate of the R2 viewshed algorithm. Emphasis has been placed on input/output (IO) efficiency that can be achieved by memory segmentation and coalesced memory access. An implementation of the parallel viewshed algorithm on the Compute Unified Device Architecture (CUDA), which exploits the high parallelism of the graphics processing unit, is presented. This version is referred to as r.cuda.visibility. The accuracy of our algorithm is compared to the r.los R3 algorithm (integrated into the open-source Geographic Resources Analysis Support System geographic information system environment) and other IO-efficient algorithms. Our results demonstrate that the proposed implementation of the R2 algorithm is faster and more IO efficient than previously presented IO-efficient algorithms, and that it achieves moderate calculation precision compared to the R3 algorithm. Thus, to the best of our knowledge, the algorithm presented here is the most efficient viewshed approach, in terms of computational speed, for large data sets.     

Building the distributed geographic SQL workflow in the Grid environment

Over recent years, massive geospatial information has been produced at a prodigious rate, and is usually geographically distributed across the Internet. Grid computing, as a recent development in the landscape of distributed computing, is deemed as a good solution for distributed geospatial data management and manipulation. Thus, the Grid computing technology can be applied to integrate various distributed resources into a ‘super-computer’ that enables efficient distributed geospatial query processing. In order to realize this vision, an effective mechanism for building the distributed geospatial query workflow in the Grid environment needs to be elaborately designed. The workflow-building technology aims to automatically transform the global geospatial query into an equivalent distributed query process in the Grid. In response to this goal, detailed steps and algorithms for building the distributed geospatial query workflow in the Grid environment are discussed in this article. Moreover, we develop corresponding software tools that enable Grid-based geospatial queries to be run against multiple data resources. Experimental results demonstrate that the proposed methodology is feasible and correct.     

Sensing spatial distribution of urban land use by integrating points-of-interest and Google Word2Vec model

Urban land use information plays an essential role in a wide variety of urban planning and environmental monitoring processes. During the past few decades, with the rapid technological development of remote sensing (RS), geographic information systems (GIS) and geospatial big data, numerous methods have been developed to identify urban land use at a fine scale. Points-of-interest (POIs) have been widely used to extract information pertaining to urban land use types and functional zones. However, it is difficult to quantify the relationship between spatial distributions of POIs and regional land use types due to a lack of reliable models. Previous methods may ignore abundant spatial features that can be extracted from POIs. In this study, we establish an innovative framework that detects urban land use distributions at the scale of traffic analysis zones (TAZs) by integrating Baidu POIs and a Word2Vec model. This framework was implemented using a Google open-source model of a deep-learning language in 2013. First, data for the Pearl River Delta (PRD) are transformed into a TAZ-POI corpus using a greedy algorithm by considering the spatial distributions of TAZs and inner POIs. Then, high-dimensional characteristic vectors of POIs and TAZs are extracted using the Word2Vec model. Finally, to validate the reliability of the POI/TAZ vectors, we implement a K-Means-based clustering model to analyze correlations between the POI/TAZ vectors and deploy TAZ vectors to identify urban land use types using a random forest algorithm (RFA) model. Compared with some state-of-the-art probabilistic topic models (PTMs), the proposed method can efficiently obtain the highest accuracy (OA = 0.8728, kappa = 0.8399). Moreover, the results can be used to help urban planners to monitor dynamic urban land use and evaluate the impact of urban planning schemes.     

分布式水文模型的并行计算研究进展

大流域、高分辨率、多过程耦合的分布式水文模拟计算量巨大,传统串行计算技术不能满足其对计算能力的需求,因此需要借助于并行计算的支持。本文首先从空间、时间和子过程三个角度对分布式水文模型的可并行性进行了分析,指出空间分解的方式是分布式水文模型并行计算的首选方式,并从空间分解的角度对水文子过程计算方法和分布式水文模型进行了分类。然后对分布式水文模型的并行计算研究现状进行了总结。其中,在空间分解方式的并行计算方面,现有研究大多以子流域作为并行计算的基本调度单元;在时间角度的并行计算方面,有学者对时空域双重离散的并行计算方法进行了初步研究。最后,从并行算法设计、流域系统综合模拟的并行计算框架和支持并行计算的高性能数据读写方法3个方面讨论了当前存在的关键问题和未来的发展方向。     

高性能并行分布式水文模型研究进展

传统分布式水文模型采用串行计算模式,其计算能力无法满足大规模水文精细化、多要素、多过程耦合模拟的需求,亟需并行计算的支持。进入21世纪后,计算机技术的飞速发展和并行环境的逐步完善,为分布式水文模型并行计算提供了软硬件支撑。论文从并行环境、并行算法2个方面对已有研究进行总结概括,分析了不同并行环境和并行算法的优势与不足,并提出提高模型并行效率的手段,即合理分配进程/线程数缩减通信开销,采用混合并行环境增强模型可扩展性,空间或时空离散化提高模型的可并行性及动态分配计算任务、平衡工作负载等。最后,论文对高性能并行分布式模型的未来研究方向进行展望。