EN中文

地球信息科学学报 >

2015 , Vol. 17 >Issue 12: 1465 - 1473

DOI: https://doi.org/10.3724/SP.J.1047.2015.01465

地球信息科学理论与方法

基于异构集群计算的地统计面插值并行算法

  • 云硕 ,
  • 关庆锋 , *
展开
  • 1. 中国地质大学（武汉）国家地理信息系统工程技术研究中心,武汉 430074
  • 2. 中国地质大学（武汉）信息工程学院,武汉 430074
*通讯作者：关庆锋（1977-）,男,四川绵阳人,教授,主要从事高性能地理计算和地理计算智能研究。E-mail:

作者简介：云硕（1992-）,男,湖北汉川人,硕士生,研究方向为高性能地理计算。E-mail:

收稿日期: 2015-10-09

  要求修回日期: 2015-11-11

  网络出版日期: 2015-12-20

基金资助

教育部高等学校博士学科点专项科研基金（20130145120013）

中央高校基本科研业务费用专项资金资助项目（1410491B09）

收起

A Parallel Geostatistical Areal Interpolation Algorithm Suited for Heterogeneous Cluster Computing

  • YUN Shuo ,
  • GUAN Qingfeng , *
Expand
  • 1. National Engineering Research Center of GeographicInformation System, China University of Geosciences, Wuhan 430074, China
  • 2. School of Information Engineering, China University of Geosciences, Wuhan 430074, China
*Corresponding author: GUAN Qingfeng, E-mail:

Received date: 2015-10-09

  Request revised date: 2015-11-11

  Online published: 2015-12-20

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

地统计面插值算法在空间统计分析中有广泛应用,其目的是通过一组面要素的某已知属性值估算另一组面要素的属性值。地统计面插值算法多是基于克里金（Kriging）插值及其衍生算法。克里金插值算法考虑属性在空间位置上的变异性,需计算要素之间的协方差,是典型的计算密集型算法。本文分析了基于克里金插值的地统计算法计算过程,该算法中面要素间协方差计算相互独立,可作为并行计算单元划分。另外,面要素间协方差计算可使用快速傅里叶变换（FFT）快速计算,而FFT是一种非常适合并行处理的计算密集型算法。本文根据算法特征设计了基于异构集群计算的并行算法,并使用MPI+CUDA实现了该算法。实验结果表明,本文实现的算法比使用MPI实现的CPU集群的算法有更好的性能,具备良好的可扩展性,并且随着插值精度提高表现出更好的性能。

关键词： 并行计算; 异构集群; 面插值; GPU; MPI; CUDA

本文引用格式

云硕 , 关庆锋 . 基于异构集群计算的地统计面插值并行算法[J]. 地球信息科学学报, 2015 , 17(12) : 1465 -1473 . DOI: 10.3724/SP.J.1047.2015.01465

Abstract

The goal of geostatistical areal interpolation is to estimate the unknown attribute values of a group of areal units using another group of areal units with known attribute values. Most geostatistical areal interpolation algorithms are based on the Kriging interpolation and its derivatives. Kriging interpolation considers the spatial variability of attributes and the covariance between the spatial units. It is a typical computationally intensive algorithm. The computation of covariance between a pair of areal unitsis independent from the computation between the other pairs, thus it is parallelizable. In addition, the covariance can be calculated using fast Fourier transform (FFT), which is a computationally intensive algorithm and is very suitable for the parallel processing.This paper presents a parallel algorithm for geostatistical areal interpolation that is suited for CPU+GPU heterogeneous computing clusters. The algorithm was implemented using MPI and CUDA. The experiment results showed that the hybridparallel algorithm outperformed the MPI-basedparallel algorithm that uses only the CPUs, and it exhibited a good scalability.

Key words： parallel computing; heterogeneous cluster; areal Interpolation; GPU; MPI; CUDA

1 引言

在很多地理空间分析的应用中,需将一部分属性信息从当前空间位置转换到其他的空间位置[1]。地理空间分析中使用的地理空间数据往往由带有属性信息的空间对象构成[2]。插值是通过一组已知某属性值的要素估算另外一组相关要素的属性值。例如,在一个公共健康研究案例中,往往需集成经济条件、生活环境及健康状况等数据,而这些数据可能是基于不同空间单元,如行政划分、空气质量预测网点或者人口普查区等[3]。因此,必须基于现有空间单元及其相应的属性值,通过面插值以获取研究问题的空间单元的属性值。
地统计面插值方法主要通过克里金（Kriging）插值及其相关的衍生算法进行计算[4]。经过长时间发展已衍生出各种不同原理的克里金插值方式,广泛应用于土壤制图、地下水模拟等众多领域。地统计面插值相比于简单的制图面插值方法[5],不仅考虑了计算对象的空间自相关,还能在插值的同时给出精确度评估。地统计面插值通过源要素之间,以及源要素和目标要素之间的协方差矩阵来计算源要素对目标要素的权值。面要素之间的协方差计算首先对面要素进行网格分解。每一个格子作为一个子元素。然后对这些子元素之间的协方差进行积分求得2个面要素间的协方差。Kyriakidis等提出的快速地统计面插值计算方法将面插值的计算复杂度大幅度降低[6]。但在实际使用中,当计算范围较大,计算要素较多,划分的网格较密集时,快速地统计面插值过程仍需花费大量的计算时间。目前已有很多点插值的并行算法研究,如利用MPI+OpenMP在CPU环境下的并行Kriging点差值[7],以及利用CUDA实现的GPU环境下得双线性插值算法[8]。并行面插值算法的研究中,Guan等使用MPI实现的基于CPU集群的地统计面插值算法,在计算加速上已取得可观的加速比[9]。近年来,以GPU、众核处理器（MIC）等协处理器和CPU构成的混合集群表现出非常好的计算性能,这2种结构在不同计算下各有优势[10],前者如天河一号[11],后者如天河二号[12]。英伟达公司推出的GPU的通用编程架构CUDA和英特尔公司推出的众核处理器MIC架构都简化了程序编写的难度[13-14]。本文设计了基于CPU/GPU异构集群的算法,进一步突破地统计面插值的计算壁垒。

2 地统计面插值算法原理

2.1 简单克里金面插值和普通克里金面插值

考虑二阶平稳假设下点要素的期望稳定,且点要素期望值 μ Z 已知,通过简单克里金预测第p个目标要素的属性值如式（1）所示。
z ^ t p = μ Z a p + w p T z s - μ Z a s (1)
式中, w p = w p s k , k = 1 , ⋯ , K T 是一个K×1的向量,其中 w p s k 是第k个源要素对第p个未知目标要素的权重; a s = [ a s k , k = 1 , ⋯ , K ] T 是一个K×1的向量,表示所有的源要素的采样函数积分; z s - μ Z a s 是K×1的向量,表示源要素采样值和期望的残差。
当预测值为实际值得无偏估计时,简单克里金面插值权重方程如式（2）所示[15]。
∑ k = 1 K w p s k ' σ Z s k , s k ' = σ Z t p , s k (2)
简单克里金面插值求得源要素之间的协方差矩阵,其和目标要素与源要素之间的协方差矩阵即可求解源要素对目标要素的权重,再通过式（1）求得目标要素的属性值。
简单克里金面插值设定了已知点要素期望值 μ Z ,但实际往往不知道要素期望值,需用普通克里金的原理进行求解,使用一种更一般的约束线性组合来预测目标要素属性值（式（3））。
z ^ t p = ∑ k = 1 K w p s k z s k = w p T z s (3)
在无偏条件约束下,可得到普通克里金面插值的权值计算矩阵（式（4））。
∑ a s a s T 0 w p - ξ p = σ p a p (4)
由上述原理可知克里金面插值算法步骤：
(1) 求源要素之间的协方差矩阵,源要素和目标要素之间的协方差矩阵;
(2) 构建矩阵方程;
(3) 通过求解方程得到权值矩阵;
(4) 通过权值矩阵求得目标要素的属性值。

2.2 面要素间协方差计算

对于2个随机面要素有变量 Z s k 和 Z s k ' 的协方差 σ Z s k , s k ' [16],如式（5）所示。
σ Z s k , s k ' = Cov Z s k , Z s k ' = ∫ u ∈ D ∫ u ' ∈ D g k u σ Z u - u ' g k u ' d u ' du (5)
式中, s k 表示一个随机面要素;D表示研究域; g k u 是面要素的采样函数; σ Z u - u ' 是2个采样点间的协方差。
面插值应用中,一般使用网格将面进行划分,用划分的格子代表原来的未知点,对于第k个源数据将会离散分解成一些未知点的属性值（式（6））。
z ( s k ) ≈ ∑ i = 1 N g k u i z u i , k = 1,2 , ⋯ , K (6)
式中,N表示面要素被网格分解成了N个格子。式(5)离散化后成为式（7）。
σ Z s k , s k ' = Cov Z s k , Z s k ' ≈ ∑ i = 1 N ∑ j = 1 N g k u i σ Z u i - u j g k u j (7)

2.3 基于快速傅里叶变换（FFT）的协方差计算

考虑网格将研究域分为N个格子,在二维情况下,N=NxNy,分别代表2个方向的格网大小。由此可得到源要素之间的协方差矩阵[17]（式（8））。
∑ ss = G s ∑ ss G s T (8)
式中, ∑ ss 表示K×K的源要素与源要素的协方差矩阵; ∑ zz 表示N×N的网格离散后的任意2个格子之间协方差,由基于点的协方差模型计算; G s 是K×N的矩阵,其中第k行是第k个源要素在网格中的采样函数矢量。
同样可给出目标要素和源要素之间的协方差矩阵（式（9））。
∑ ts = G t ∑ ss G s T (9)
对于2个要素之间的计算,从式（7）可看出 σ Z u i - u j 的计算重复,计算量增加。
在实际应用中,当要素数量较大时,网格划分得细一些会使得N非常大,这样存储中间计算结果就变得不容易实现,可能会超出计算机内存[18]。
∑ zz 扩展后在二维下是对称的块托普利茨（Toeplitz）矩阵,其矩阵由第一行的块移动得到[19]。这种循环行列式形式的矩阵可分解成式（10）。
∑ ~ zz = F E ~ F H (10)
式中, F 是2N×2N的傅里叶矩阵; F H 是 F 的共轭矩阵,并且有 F H = F - 1 。
当一个向量v与 F H 相乘时,称为对该向量进行向前离散傅里叶变换（DFT）,表示为 f v 。通过变换后得到特征值求取的公式如式（11）所示。
e ~ = f ∑ ~ zz 1 , ⋅ (11)
目标要素和源要素间的协方差计算如式（12）。
σ Z t p , s k = F H g ~ p H E ~ F H g ~ k (12)
DFT可通过FFT更高效地进行计算。面插值的元素间协方差计算步骤如下：
(1) 用格网划分研究域格网;
(2) 计算格网格子之间的协方差,并扩展为符合公式的形式;
(3) 求扩展矩阵特征值;
(4) 对要素的采样函数向量进行FFT变换;
(5) 将计算结果通过式（12）计算得到要素之间的协方差。

3 并行算法研究

3.1 算法复杂度和并行分析

本文使用的基于FFT的快速地统计面插值算法主要步骤如下：
(1) 获取源数据和目标数据;
(2) 对源面要素和目标面要素进行格网处理,离散成格子单元;
(3) 计算格网的所有格子间的协方差矩阵,并扩展该矩阵;
(4) 对该格网的协方差矩阵进行FFT变换,得到特征值矩阵,然后该要素的取样函数矢量进行FFT变换,然后求取这2个结果的积,再对该结果进行FFT变换,得到每个要素对于其他要素的协方差矩阵中间值;
(5) 通过每个要素和其它要素的协方差矩阵中间值,和要求取协方差的那个要素的采样函数矢量,计算源要素之间的协方差矩阵,源要素和目标要素之间的协方差矩阵;
(6) 根据选用的克里金面插值方式的原理构建协方差矩阵方程;
(7) 求解协方差矩阵方程,得到每个源要素对每个目标要素的权值矩阵;
(8) 通过权值矩阵和选用克里金原理公式计算得到每个目标的值。
上述步骤中,对于任何2个块之间的协方差计算需3次FFT计算,1次向量乘法计算。块的大小影响计算可忽略。对于n个块之间的计算需2n-1次FFT计算,n（n-1）次向量乘法计算。此时块的大小对计算的影响也很小。但是如果扩大网格大小,此时计算量将会提升。
设置源要素个数为K,目标要素个数为P。步骤（2）需要计算每个格子和网格的交点,此时计算复杂度和块的边数有关,假设总计算边数为E,时间计算复杂度为O（E）。而步骤（3）中是计算格网间要素的协方差,其计算复杂度与网格划分情况有关,时间计算复杂度为O（N×N）。此时步骤（4）需要进行3K+1次FFT计算。FFT的时间计算复杂度为O（NlogN）,N表示了离散点的数量,那么要素间协方差计算的过程的计算复杂度为O（3K×NlogN）。步骤（5）求解方程组所需要的时间和要素的规模有关系,要素数量越多所需要的时间越多。其计算复杂度为O（K3）。步骤（6）计算目标值和要素多少有关,其时间计算复杂度为O（K×M）。在实际的应用中,N要远大于K、P、E。可以看出,协方差计算的时间复杂度最大。由此需进行并行计算,对计算复杂度最高的地方进行并行处理。
对要素间协方差计算的过程进行分析。本文采用计算协方差中间值即块对点的协方差的方式减少协方差计算中FFT的数量。其对于每个块进行处理所需的参数如表1所示。
Tab. 1 Independence analysis ofthe block-point covariance calculation

表1 块对点协方差计算独立性分析

所需参数 计算是否独立
格网的协方差矩阵 是
该要素的采样函数分布向量 是
由表1中所需元素计算独立性可知,每个要素的协方差计算都相互独立,所以可将块对点的协方差计算作为并行计算的计算单元。
由上述的时间复杂度分析可知,元素间协方差计算的时间计算复杂度为O（3K×NlogN）,并且在实际计算的时候N会远大于K,所以对K进行分解后应进一步加速。而FFT是一种非常适合使用并行计算的算法,可进一步使用并行的FFT进行加速。

3.2 并行算法设计与实现

异构集群在CPU集群的基础上,将计算复杂度较高的部分转移到协处理器上进行计算。这种计算模式受制于协处理器的内存空间。如GPU的显存往往只有1 G或2 G（专业高端GPU的内存可达4 G以上）,对处理的数据大小有一定的要求。所以算法在设计时需考虑在协处理器上进行计算的数据粒度大小。原算法所需空间较大,不太适合使用协处理器进行处理。本文的面要素协方差计算使用基于FFT的快速计算模式,节省了计算空间和时间,能有效利用协处理器处理。
面插值计算中,面要素间的协方差计算占据绝大部分计算时间。因此,将协方差计算中FFT计算转移到协处理器上,能有效提高算法的执行速度。本算法中每2个面要素之间的协方差计算相互独立,所以在任务划分上以要素作为任务单元。而每个进程的计算过程完全独立,因此不需考虑要素在空间划分上的空间重合问题。
计算开始时,主节点将读取的面要素矢量数据广播到各个节点,传输的数据量较小。计算结束后,各节点将插值结果的局部数据发送回主节点,由于数据量小,传输时间非常短。相比于计算的复杂度,数据传输对整体的计算时间没有太大的影响。
根据异构集群的计算特点和算法特点设计出算法流程。如图1所示。
Fig. 1 Flow chart of the parallel algorithm

图1 并行算法流程

（1） 数据准备。这个流程中需读取数据,包括源要素和目标要素的空间信息及源要素的属性信息,然后构建相应的要素目标;读取协方差模型参数,构建协方差参数对象;设置格网大小,生成格网格网信息。通过格网信息计算每个源要素和目标要素基于格网的坐标集合。
（2） 广播协方差参数对象,数据对象集合、网格信息对象、数据基于格网的坐标集合。
（3） 开始并行计算要素之间局部的协方差。以某一要素与其他要素的协方差矩阵计算为计算单元,分配到相应的计算结点上。每一个要素间协方差计算具体步骤如图2所示。每个进程中首先使用协方差参数模型构建协方差模型,利用格网信息计算格网中的协方差矩阵,然后对协方差矩阵进行计算。通过将数据基于格网的坐标集合上载到协处理器进行FFT处理,在进程中计算以上2个FFT的结果的乘法,将结果上载到协处理器重新进行FFT处理,然后将获取的结果和其它的坐标集合矢量进行乘法运算获取结果。重复当前源要素与其所有源要素和目标要素的计算,获取局部的源要素之间的协方差矩阵和局部源要素与目标要素之间的协方差矩阵。
Fig. 2 Covariance calculation between blocks

图2 面要素间协方差计算

（4） 将协方差矩阵通过广播或者消息发送的方式返回给主进程。
（5） 主进程开始使用相关算法进行方程分解,得到源要素对目标要素的权重矩阵。
（6） 主进程使用权重矩阵对目标要素属性 求值。
（7） 将计算结果写入目标文件。
本文使用C++实现上述算法,集群节点间通信使用MPI实现,GPU计算使用CUDA实现。程序使用shapefile库读取shapefile格式的数据。点之间协方差计算使用GsTL进行计算,要素之间协方差计算通过修改Liu的基于FFT的面要素间协方差计算代码[20],其中FFT计算通过CUDA的cuFFT完成。最后,矩阵求解部分通过TNT库实现。程序提供一系列用户选项,包括格网规模设置及协方差模型 设置。

4 并行算法实验和分析

4.1 实验环境和实验设计

本实验采用3台服务器构成的集群,根据现有的硬件环境,使用CPU+GPU异构集群算法测试。使用软件Rocks clusters 5.5搭建集群,总共3个节点,每个节点上有24 G内存,2个Intel Xeon E5系列CPU,2个NVIDIA的Tesla C2050 GPU,每个GPU有1G显存。
实验数据以人口密度为插值属性,源数据为美国东部部分地区的97个郡（County）,目标数据为该地区38个流域区划（Watershed）,数据文件格式为shapefile格式。
由于协方差模型设置、格网规模及Kriging计算方式的不同,程序会表现出不同的计算性能。根据本文并行算法的设计思想,需要测试GPU协处理器加速效果和基于CPU/GPU异构集群的加速效果。
协处理器加速主要体现在FFT计算上。单个FFT计算的时间取决于格网划分的粒度,总体的FFT计算还取决于源数据的要素数量。对于不同要素,FFT计算次数和计算规模是相同的。只需通过改变格网大小来对比分析并行算法的计算性能。在并行模式下,本文采用块分配的方式分配任务,每个进程的任务差别不大。但是使用集群多进程进行计算,还是会出现负载不均的情况。所以这里采用一个进程进行测试。根据数据的规模分别使用200、400、800、1600 m格网大小进行测试。
集群的加速效果将会体现在多个进程对问题进行分解,所以测试选用一个合适的格网对不同数量的进程进行测试。本文根据服务器集群的情况分别设置结点数为1、2、3,分别使用1、2、4、6个GPU进行计算。
以上2个不同的测试都会和同构的MPI程序进行对比,从而评价异构集群对比同构集群的优势。本文会同时考虑整体程序加速时间和并行部分的时间,使用加速比来衡量。令 t p 表示使用p个进程时程序执行的时间, t 1 表示使用1个进程时程序执行的时间,则加速比表示如式（13）所示。
S p = t 1 t p （13）

4.2 算法结果和性能分析

计算结果如图3所示。对比串行和异构集群计算得到目标数据,二者完全相同,从而验证了并行算法的正确性。
Fig. 3 The results of interpolation (the source data (a) and the target data (b))

图3 插值计算结果

4.2.1 CPU+GPU异构单节点测试结果与分析
图4是单进程测试的CPU和CPU+GPU在不同格网设置下的时间对比折线图。图中格网从左至右依次变密集（即网格变小）。随着格网密集程度越高,单CPU的计算时间大幅增长,而单CPU+GPU的计算时间增加较缓。
Fig. 4 Computationaltime of a single process

图4 单进程时间对比

如图5所示,在格网大小为1600 m时,异构结点的加速比小于1。此时异构结点的GPU并没有起到加速作用。这是因为GPU协处理器计算都需要数据传输,即CPU首先需将数据从主机内存上载到GPU显存中,计算完成后再将数据传输回内存。这个过程需要一定的时间。当计算量较小时,会出现计算加速所节省的时间无法抵消传输所消耗的时间,因而导致总体计算时间更长。从图5中可看到,随着格网密度增加,加速比开始快速提升。
Fig. 5 Speed-up of a single process

图5 单进程加速比对比

图6显示了面要素之间的协方差计算（主要是FFT计算）在整体计算中所占比例。在不同的网格划分情况下,协方差计算时间占比均超过90%。从图7可看到,不同格网设置下,其他计算时间差别不大,主要差别表现在协方差计算上。由此可看出,GPU对FFT计算产生了明显的加速效果。
Fig. 6 The time proportions of covariance calculations

图6 协方差计算占总体计算的时间比例

Fig. 7 Computationaltime of different settings

图7 不同部分计算时间

4.2.2 CPU+GPU异构并行测试结果与分析

在异构并行计算实验中,采用200 m的格网规模进行测试。由图8可看出,异构并行计算随着并行规模提升（即进程数的增加）,计算时间减小。异构并行算法（MPI+CUDA）加速效果也比CPU同构并行算法（MPI）明显。由图9可看出,异构并行算法相比于CPU并行算法,在不同进程数的情况下均表现出高于2倍的加速,而随着进程数加大,加速比逐渐减小。这说明在单进程计算量更大的情况下,异构并行的进程能表现出更好的加速效果。因为实验的硬件环境有限,没有选取更大规模数据做测试。在Guan的研究中,基于MPI的CPU同构并行算法在大规模数据的情况下起到非常好的加速效果[9]。而本文的基于GPU/CPU异构并行的算法的计算速度明显优于CPU同构并行算法,因此在大规模数据情况下,相同规模节点的异构集群会表现出很好的加速效果。
Fig. 8 Computationaltime of the heterogeneous parallelism and homogeneous parallelism

图8 异构并行和同构并行的计算时间对比

Fig. 9 Speed-up of heterogeneous parallelism over homogeneous parallelism

图9 异构并行相对同构并行的加速比

由此可看出,CPU+GPU的异构并行相比单纯的CPU并行,性能有较大的提升,并且随着要素数量增加能更好地发挥异构集群的计算能力。另外,由上述单个异构结点的情况可判断,随着格网密度增加,加速比还会有进一步的提升。
如图10所示,相比串行算法,异构并行算法使用6个进程时可达到10倍的加速比,时间由139.7 s减少到14 s,加速比随着进程增加而增加。图11比较了异构并行算法相对单个CPU+GPU节点的加速情况,加速比随进程数增加而增加的趋势,显示异构并行算法具有较好地可扩展性（Scalability）。
Fig. 10 Speed-up of heterogeneous parallelism over sequential algorithm

图10 异构并行算法相对串行算法的加速比

Fig. 11 Speed-up of heterogeneous parallelism over a single CPU+GPU process

图11 异构并行算法相对异构单进程的加速比

通过上述性能分析,得到以下结论：（1）基于异构集群计算的地统计面插值并行算法,在格网划分密度大的情况下才能发挥协处理器计算能力;（2）基于异构集群计算的地统计面插值并行算法,随着集群规模的扩大会有更好的加速效果。总体来说,基于异构集群计算的地统计面插值并行算法在格网划分密度大、计算要素多的情况下,随着集群规模扩大,有较好加速效果,并且加速效果明显优于同构并行算法。

5 结语

本文分析了地统计面插值算法及基于FFT的改进算法的特性,针对对异构集群的特点,将算法的主要计算部分转移到计算内核更多、处理速度更快的协处理器上进行,提出了地统计面插值的异构并行算法,以该设计思想为基础,利用MPI和CUDA结合,实现了适用于CPU+GPU异构集群的并行程序。
实验测试显示,该算法设计思想对于大计算规模地统计面插值计算,在密集格网划分下才能在单进程（即单CPU+GPU节点）上起到明显加速效果。而使用多个进程,能为复杂计算起到较好的加速效果。更重要的是,相比于单纯使用同构CPU集群的MPI并行加速算法,异构并行算法体现出了更高的计算能力,进一步提高计算效率并缩短计算时间,为突破由计算复杂度造成的计算壁垒提供了更强大的工具,有利于提高复杂空间算法的实用性。
目前主流的众核协处理器除了GPU以外,还有Intel的基于MIC架构的Xeon Phi众核协处理器,也拥有非常强大的辅助计算能力。下一步将完成基于CPU+MIC的异构并行算法。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Seymour L.Spatial data analysis: Theory and Practice. Robert Haining[J]. Journal of the American Statistical Association, 2005,100(469):353-354.

[2]
Goodchild M F, Anselin L, Deichmann U.A framework for the areal interpolation of socioeconomic data[J]. Environment & Planning A, 1993,25(3):383-397.Spatial data are collected and represented as attributes of spatial objects embedded in a plane. Basis change is defined as the transfer of attributes from one set of objects to another. Methods of basis change for socioeconomic data are reviewed and are seen to differ in the assumptions made in each about underlying density surfaces. These methods are extended to more general cases, and an illustration is provided by using Californian data. The implementation of this framework within a geographical information system is discussed.

DOI

[3]
Gotway C, Waller L.Applied Spatial Statistics for Public Health Data[M]. Hoboken, NJ:Wiley-Interscience, 2004.

[4]
Flowerdew R, Green M.Areal interpolation and types of data[A]. In Fotheringham S, Rogerson P(eds.). Spatial Analysis and GIS[M]. London: Taylor and Francis, 1994.

[5]
Goodchild M F, Lam N S N. Areal interpolation: A variant of the traditional spatial problem[J]. Geo Processing, 1980,1(3):297-312.Geo-Processing, 1(1980) 297—312 Elsevier Scientific Publishing Company, Amsterdam 297 - Printed in The Netherlands AREAL INTERPOLATION: A VARIANT OF THE. TRADITIONAL SPATIAL PROBLEM MICHAEL F. GOODCHILD and NINA SIU-NG02N LAM Department of

DOI

[6]
Kyriakidis P C, Schneider P, Goodchild M F.Fast geostatistical areal interpolation[C]. 7th International Conference on Geocomputation, Ann Arbor Michigan, 2005.

[7]
吴博,高超,谢健.基于混合并行的Kriging插值算法研究[J].计算技术与自动化,2014,33(1):65-68.普通Kriging方法是进行 空间降水插值的一种有效方法。然而一方面由于海量数据插值计算量大,另一方面该算法的时间复杂度大,为减少空间降水插值的计算时间,采用OpenMP和 MPI混合并行技术,实现Kriging并行算法。在Windows操作系统上搭建并行计算环境,实验数据表明,该并行算法能有效地节省计算时间。

DOI

[8]
肖汉. 利用GPU计算的双线性插值并行算法[J].小型微型计算机系统,2010,32(11):2241-2245.双线性插值算法在数字图像处理 中有广泛的应用,但计算速度慢.为提高其计算速度,提出一种基于图形处理器加速的双线性插值并行算法.主要利用Wallis变换双线性插值中各分块之间的 独立性适合GPU并行处理架构的特点,把传统串行双线性插值算法映射到CUDA并行编程模型,并从线程分配,内存使用,硬件资源划分等方面进行优化,来充 分利用GPU的巨大运算能力.实验结果表明,随着图像分辨率的增大,双线性内插并行算法可以把计算速度提高28倍.

[9]
Guan Q, Kyriakidis P C, Goodchild M F.A parallel computing approach to fast geostatistical areal interpolation[J]. International Journal of Geographical Information Science, 2011,25(8):1241-1267Areal interpolation is the procedure of using known attribute values at a set of (source) areal units to predict unknown attribute values at another set of (target) units. Geostatistical areal interpolation employs spatial prediction algorithms, that is, variants of Kriging, which explicitly incorporate spatial autocorrelation and scale differences between source and target units in the interpolation endeavor. When all the available source measurements are used for interpolation, that is, when a global search neighborhood is adopted, geostatistical areal interpolation is extremely computationally intensive. Interpolation in this case requires huge memory space and massive computing power, even with the dramatic improvement introduced by the spectral algorithms developed by Kyriakidis et al. (2005. Improving spatial data interoperability using geostatistical support-to-support interpolation. In: Proceedings of geoComputation. Ann Arbor, MI: University of Michigan) and Liu et al. (2006. Calculation of average covariance using fast Fourier transform (FFT). Menlo Park, CA: Stanford Center for Reservoir Forecasting, Petroleum Engineering Department, Stanford University) based on the fast Fourier transform (FFT). In this study, a parallel FFT-based geostatistical areal interpolation algorithm was developed to tackle the computational challenge of such problems. The algorithm includes three parallel processes: (1) the computation of source-to-source and source-to-target covariance matrices by means of FFT; (2) the QR factorization of the source-to-source covariance matrix; and (3) the computation of source-to-target weights via Kriging, and the subsequent computation of predicted attribute values for the target supports. Experiments with real-world datasets (i.e., predicting population densities of watersheds from population densities of counties in the Eastern Time Zone and in the continental United States) showed that the parallel algorithm drastically reduced the computing time to a practical length that is feasible for actual spatial analysis applications, and achieved fairly high speed-ups and efficiencies. Experiments also showed the algorithm scaled reasonably well as the number of processors increased and as the problem size increased.

DOI

[10]
Bernaschi M, Salvadore F.Multi-Kepler GPU vs. multi-intel MIC: A two test case performance study[C]. IEEE 2014 International Conference on High Performance Computing & Simulation (HPCS), 2014:1-8.

[11]
王握文,陈明."天河一号"超级计算机系统研制[J].国防科技,2009(6):1-4.2009年10月,国家首台千万亿次超级计算机系统--"天河一号"在国防科学技术大学诞生."天河一号"的诞生,是我国高性能计算机技术发展的又一重大突破,标志着我国超级计算机研制能力实现了从百万亿次到千万亿次的重大跨越,我国成为继美国之后第二个能研制千万亿次超级计算机系统的国家.

[12]
王涛. “天河二号”超级计算机[J].科学,2013(4):52-52.2013年6月17日，国际超级计算机大会（International Supercomputer Conference）发布了全球最快的500台超级计算机排行榜，中国国防科技大学与浪潮公司共同研发的“天河二号”超级计算机位列第一。这是中国研制的超级计算机第二次荣获冠军，第一次获得冠军的是2010年中国国防科技大学研制的“天河一号”超级计算机。

[13]
Kirk D.NVIDIA CUDA software and GPU parallel computing architecture[C]. International Symposium on Memory Management Proceedings of International Symposium on Memory Management, 2007,27(5-6):578.

[14]
Felicie A L.Intel MIC[M]. Newport, RI: Salve Regina University, 2012.

[15]
Journel A G, Huijbregts C.Mining Geostatistics[M].London: Academic Press, 1978.

[16]
Coburn T C.Geostatistics for Natural Resources Evaluation[J]. Technometrics, 2000,42(4):437-438.

DOI

[17]
Anderson T W.An introduction to multivariate statistical analysis[J]. Wiley, 1958,148:164-165.

[18]
Strang G.Introduction to applied mathematics[J]. Journal of Vibration & Acoustics, 1986,110(2):428-429.

[19]
Davis P. Circulant Matrices.Second Edition[M]. New York, NY: Chelsea Publishing, 1994.

[20]
Liu Y, Jiang Y, Kyriakidis P .Calculation of average covariance using fast Fouriertransform (FFT)[R]. Menlo Park, CA: Stanford Center for Reservoir Forecasting, PetroleumEngineering Department, Stanford University, 2006.

Options
文章导航

/

〈 〉