并行空间分析算法研究进展及评述_王结臣(1)

格式：pdf
大小：215.96 KB
文档页数：5

下载文档原格式

临近空间大气模型的分析研究

临近空间⼤⽓模型的分析研究临近空间⼤⽓模型的分析研究摘要：建⽴临近空间中性⼤⽓模型，并对其进⾏适⽤性分析。

通过对模型精度、残差、标准差的计算，发现密度模型与温度模型的输出结果与实时观测结果具有较好的⼀致性，⽽风场模型的输出结果能较好地体现平均观测结果.最后，利⽤NSPM模型分析了中国地区临近空间区域的各⼤⽓参数(密度、温度、压强、经向风、纬向风)的变化特性.研究表明临近空间⼤⽓环境变化具有明显的季节性及区域性.关键词：临近空间;⼤⽓模型;精度分析临近空间(Near Space)是对海拔20 km到100km空间范围内的⼀个通⽤性称谓，包括地球平流层、中间层、低热层等，是地球中⾼层⼤⽓的重要组成部分.临近空间环境与⼈类⽣存和发展息息相关，同时，临近空间的开发和利⽤对临近空间环境特性研究及预报提出了迫切需求。

在地球⼤⽓层中飞⾏的飞⾏器，都要借助空⽓动⼒飞⾏，因此，作为提供空⽓动⼒的介质，空⽓的静态物理特性(密度、压强、温度等)和动态物理特性(如风场)对在⼤⽓层中飞⾏的飞⾏器的安全与准确⼊轨具有重要的影响.本⽂利⽤现有模型的部分模块，形成了适⽤于临近空间的中性⼤⽓模型.由于模型本⾝要反映物理实际，即模拟值与实际观测值要⼀致，故本⽂对临近空间的中性⼤⽓模型进⾏适⽤性分析.最后，作为临近空间⼤⽓参量模式的⼀个应⽤，分析了⼦午⼯程台站的临近空间⼤⽓环境特性.⼀、模型简介本⽂选⽤了⼤⽓模式NRLMSISE-00及风场模式HWM07以获取临近空间区域的各种⼤⽓参量，由于⼤⽓模式和风场模式模拟的各种⼤⽓参量的⾼度范围是从地⽽⾄外逸层，超出了临近空间的⾼度区域(20km⾄100 km ).另外，NRI,MSISE-00众多输出参量中仅⼤⽓密度和温度是临近空间的开发利⽤所需要的.针对临近空间应⽤需求，从这两种模式中抽取需要的模块进⾏集成，最后得到临近空间参量模式.如图1所⽰，对于⼤⽓模型NRI,MSISE-00，选取⾼度范围⼩于100 km的模块，得到临近空间⼤⽓模式M-A，再选取临近空间⼤⽓温度、密度模块，得到临近空间⼤⽓温度密度模式N-A，最后利⽤温度密度模块得到⼤⽓压强模块.对于⽔平风场模型HWM07，选取⾼度范围⼩于100 km的模块进⾏改进，得到临近空间⽔平风模式，然后将得到的温度、密度、压强、风场模块进⾏集成，得到临近空间环境参量模式NSPM.该模型经改编可在UNIX系统下运⾏，以满⾜实际应⽤需求.⼆、⼤⽓模型的适⽤性分析1.密度模型的适⽤性分析将合肥站瑞利激光雷达的⼤⽓密度观测结果与NSPM模式的输出结果进⾏⽐对，计算模型精度。

《并行计算导论》课程报告

北京科技大学《并行计算导论》实验报告题目：矩阵向量乘法的并行化学院计算机与通信工程学院班级计1301 1303 1304班指导教师李建江时间 2016年3月22日至3月31日一、任务描述基于MPI和OpenMP，分别实现矩阵向量乘法的并行化。

对实现的并行程序进行正确性测试和性能测试，并对测试结果进行分析。

二、矩阵向量乘法串行算法描述与分析1. 串行算法描述在线性代数中，矩阵和向量的乘法是将每行矩阵的每个元素乘以向量中的每个元素，得到一个新的向量，要求矩阵是N*N阶，向量是N阶，这样相乘后，得到一个新的N阶向量。

利用串行算法，设置循环，让矩阵中的每一行的元素乘以完向量的每个元素后得到一个数值再进行下一行的乘法，一直到最后一行的乘法结束，得到新的向量。

2. 空间复杂度分析对于N阶的矩阵向量乘法，A*b=x，定义数据类型为long，则需要的存储空间为（N^2+2*N）*4 Byte 。

（矩阵数：N^2+向量数N+结果N）3. 时间复杂度分析对于N阶的矩阵向量乘法，A*b=x，需要串行算法执行的次数为：N^2*(N-1)三、矩阵向量乘法的并行化（一）基于MPI的矩阵向量的并行化1. 并行策略（含图示）因为矩阵乘以向量，每行的乘法是相互独立的，所以可以把N阶矩阵按行平均分配给各个进程，让每个进程分别处理分配给它的数据块。

2. 并行算法描述先为程序指定阶数，然后用随机数生成N阶方阵和向量，采用静态均匀负载，为每个处理器分配相同数量的数组元素，做到负载相对比较均衡（由于可能存在0元素，使得负载相对有些偏差）。

然后把N阶方阵和向量显示出来，做MPI静态并行计算，然后将得出的结果显示出来3. 空间复杂度分析设进程数为n，数据类型为long，则N阶矩阵向量乘法的所需的空间为：N^2+n*N+N，（矩阵空间N^2+n倍的b向量空间n*N+结果N）4. 时间复杂度分析假设负载均衡，假设最小的划分块大于等于矩阵的一行，由于将行分块划分给各个进程，所以整体的时间是1/n倍的串行算法的时间复杂度，即1/n*N^2*(N-1)（二）基于OpenMP的矩阵向量的并行化1. 并行策略（含图示）与MPI并行策略类似，把矩阵按行分块，与向量相乘，但是可以采用更为灵活的池技术动态调用，更加充分利用了计算资源。

基于Matlab的遥感图像IHS小波融合算法的并行化设计

基于Matlab的遥感图像IHS小波融合算法的并行化设计作者：王淼来源：《科技视界》2016年第11期【摘要】随着遥感图像数据规模的不断扩大与融合算法计算复杂度的增大，遥感图像的快速融合成为很多遥感处理步骤的关键一环。

计算机技术快速发展，CPU多核架构逐渐普及，为了充分利用多核处理器资源，Matlab提供了并行计算模型。

本文选取了基于小波变换和IHS空间的图像融合算法进行并行化设计，利用Matlab并行计算工具箱与分布式计算服务器进行任务分割，实现了算法的并行化。

实验结果表明，并行化处理可以有效缩短图像融合的时间，获得良好的加速比，验证了并行算法的高效性，对进一步研究并行图像处理有一定的指导意义。

【关键词】Matlab；图像融合；IHS；小波变换；并行计算0 引言随着遥感技术的飞速发展，由于信息获取的途径越来越多，从而得到了各式各样的遥感数据，而且数据量也越来越大。

图像融合技术的诞生使多源遥感数据得到了充分的利用，产生了比单一信息源更精确、更可靠的估计和判断。

由于数据规模的不断增大，基于单处理器的传统的串行图像融合算法已经无法满足计算量不断增加的需求，基于多处理器或集群的并行计算使图像的快速融合成为了可能，为高效地分析遥感图像提供了有效的解决途径。

当前流行的并行化工具与多核计算平台有很多，如OpenMP、MPI等[1]，还有基于GPU 并行计算的GUDA语言[2]。

为高效利用多核处理器进行并行计算，增强计算能力，Mathwork 公司推出了Matlab 分布式计算服务器与并行计算工具箱[3]，可以实现对大规模数据进行快速、便捷地并行任务划分，而且具有良好的可扩展性。

近年来，小波变换理论被广泛应用于图像融合并行处理当中，有基于MPI的复小波变换的遥感图像并行融合算法[4]，有基于GPU的小波变换图像融合快速实现算法等[5]。

本文在Matlab并行计算环境下，分析了基于小波变换与IHS空间的图像融合算法流程，将读入内存数据规模较大的遥感图像像元矩阵进行均等任务划分，分配给不同的处理单元进行融合计算，实现了算法的并行化，为提高大规模矩阵的计算速度与多核处理器的利用率提供了并行处理方法。

基于Kriging模型的自适应多阶段并行代理优化算法

第27卷第11期2021年11月计算机集成制造系统Vol.27No.11 Computer Integrated Manufacturing Systems Nov.2021DOI：10.13196/j.cims.2021.11.016基于Kriging模型的自适应多阶段并行代理优化算法乐春宇，马义中+(南京理工大学经济管理学院，江苏南京210094)摘要：为了充分利用计算资源，减少迭代次数,提出一种可以批量加点的代理优化算法。

该算法分别采用期望改进准则和WB2(Watson and Barnes)准则探索存在的最优解并开发已存在最优解的区域,利用可行性概率和多目标优化框架刻画约束边界。

在探索和开发阶段，设计了两种对应的多点填充算法，并根据新样本点和已知样本点的距离关系，设计了两个阶段的自适应切换策略。

通过3个不同类型算例和一个工程实例验证算法性能，结果表明，该算法收敛更快，其结果具有较好的精确性和稳健性。

关键词:Kriging模型;代理优化;加点准则；可行性概率;多点填充中图分类号：O212.6文献标识码：AParallel surrogate-based optimization algorithm based on Kriging model usingadaptive multi-phases strategyYUE Chunyu,MA Yizhong+(School o£Economics and Management,Nanjing University of Science and Technology,Nanjing210094,China) Abstract：To make full use of computing resources and reduce the number of iterations,a surrogate-based optimization algorithm which could add batch points was proposed.To explore the optimum solution and to exploit its area, the expected improvement and the WB2criterion were used correspondingly.The constraint boundary was characterized by using the probability of feasibility and the multi-objective optimization framework.Two corresponding multi-points infilling algorithms were designed in the exploration and exploitation phases and an adaptive switching strategy for this two phases was designed according to the distance between new sample points and known sample points.The performance of the algorithm was verified by three different types of numerical and one engineering benchmarks.The results showed that the proposed algorithm was more efficient in convergence and the solution was more precise and robust.Keywords:Kriging model；surrogate-based optimization；infill sampling criteria；probabil让y of feasibility；multipoints infill0引言现代工程优化设计中，常采用高精度仿真模型获取数据，如有限元分析和流体动力学等E,如何在优化过程中尽可能少地调用高精度仿真模型，以提高优化效率，显得尤为重要。

3-RSR并联机构工作空间的研究

机械设计与制造工程Machine Desicn and Manufacturing Engineering 2021年4月第50卷第4期Ape. 2021Vol. 50 No. 4D0I ： 10. 3969/j. issn. 2095 - 509X. 2021.04. 0053-RSR 并联机构工作空间的研究罗建国1 !2，王婷3,王宇强3（1•华北科技学院机电工程学院，河北三河065201）（2.河北山设备测重点室，河北三河065201）（3.华北科技学院安全工程学院，河北三河065201）摘要：首先介绍了一类具有1T2R 的3 - RSR 并联机构，并对该机构的自由度、奇异位形、位置求解、工作空间等进行分析；然后利用基于螺旋理论（反）的自由度分析原理结合动平台约束分布给出了机构类型，并获得了运动奇异产生的件；值法给出了该机构位置逆解公式,并通过具体求解步骤导出了正解的公式；最实例分析中的具体数值代入位置求解公式中，并利用AutoCAD 软件绘制出该机构的工作空间。

所提方法为机构运动学分析提供了理论依据。

关键词:并联机构；自由度;奇异位形；位置分析;工作空间中图分类号:TH112文献标识码:A 文章编号：2095 -509X （2021）04 -0021 -05机刚度较大、稳、误差小、精度高、现高速运动、等点,这也是机构比机用更广泛的原因'1（。

3 -RSR 并联机构是一类具有1T2R 少自由度的空间对机构,其被广用于医学、、车装配、工、测量等工程领域。

学对转机过研究'2一4（,并提出了具有1T2R 的不同类型并联机构。

文献'5 ］基于拉格程建机构的动力学，并对机构载荷以及力；［6 ］对各支链转动副平行的3-RS'机位置；文献［7］〜'9］对并联机构自由度、位形、位置;［10 ］〜'11 ］基于3 -RSR机构几何运动特性和雅可比对机构进析。

1.3.2 Dolev-Yao 1983 ,Dolev Yao [20].

1000-9825/2003/14(10)1740
©2003 Journal of Software
软件学报
Vol.14, No.10
安全协议 20 年研究进展
卿斯汉+
∗
(中国科学院信息安全技术工程研究中心,北京 100080) (中国科学院软件研究所信息安全国家重点实验室,北京 100080)
Received 2003-02-20; Accepted 2003-07-07 Qing SH. Twenty years development of security protocols research. Journal of Software, 2003,14(10): 1740~1752. /1000-9825/14/1740.htm Abstract: This paper is a survey on the twenty years development of security protocols research. The state of the
卿斯汉:安全协议 20 年研究进展
1741
式描述语言、安全协议的基本假设和针对安全协议的攻击.第 4 节进行展望,讨论安全协议研究领域今与基本概念安全协议,有时也称作密码协议, 是以密码学为基础的消息交换协议,其目的是在网络环境中提供各种安全服务 .安全目标是多种多样的 .例如, 认证协议的目标是认证参加协议的主体的身份 .此外, 许多认证协议还有一个附加的目标,即在主体之间安全地分配密钥或其他各种秘密. 非否认协议的目标有两个 :一个是确认发方非否认(non-repudiation of origin),亦即非否认协议向接收方提供不可抵赖的证据, 证明收到消息的来源的可靠性 ;另一个是确认收方非否认(non-repudiation of receipt), 亦即非否认协议向发送方提供不可抵赖的证据,证明接收方已收到了某条消息.电子商务协议的目标除认证性、非否认性之外,还有可追究性、公平性等等. Needham-Schroeder 协议 [1] 是最为著名的早期的认证协议 , 许多广泛使用的认证协议都是以 NeedhamSchroeder 协议为蓝本而设计的.Needham-Schroeder 协议可分为对称密码体制和非对称密码体制下的两种版本,分别简称为 NSSK 协议和 NSPK 协议.这些早期的经典安全协议是安全协议分析的“试验床”,亦即每当出现一个新的形式化分析方法 ,都要先分析这几个安全协议, 验证新方法的有效性. 同时 ,学者们也经常以它们为例, 说明安全协议的设计原则和各种不同分析方法的特点. 安全协议的设计极易出错,即使我们只讨论安全协议中最基本的认证协议,其中参加协议的主体只有两三个,交换的消息只有 3~5 条, 设计一个正确的、符合认证目标的、没有冗余的认证协议也十分困难 [2,3].因此,20 年来,为了应对这一挑战,人们设计了不同种类的形式化分析方法,投入了大量的精力,取得了可喜的成果. 安全协议设计与分析的困难性在于 :(1) 安全目标本身的微妙性.例如, 表面上十分简单的“认证目标”,实际上十分微妙.关于认证性的定义,至今存在各种不同的观点 ;(2) 协议运行环境的复杂性. 实际上, 当安全协议运行在一个十分复杂的公开环境时, 攻击者处处存在.我们必须形式化地刻画安全协议的运行环境,这当然是一项艰巨的任务 ;(3) 攻击者模型的复杂性. 我们必须形式化地描述攻击者的能力, 对攻击者和攻击行为进行分类和形式化的分析;(4) 安全协议本身具有“高并发性”的特点.因此,安全协议的分析变得更加复杂并具有挑战性. 1.2 重要的安全协议从 1978 年 Needham-Schroeder 协议的诞生算起,安全协议的发展已经历经 20 余年了. 除了 NSSK 协议和 NSPK 协议之外,早期著名的经典安全协议还有 Otway-Rees 协议 [4]、 Yahlom 协议 [5]、大嘴青蛙协议[5]等,以及一些重要的实用协议,如 Keberos 协议[6]、CCITT X.509 协议[7]等. 1997 年,Clark 和 Jacob[8] 对安全协议进行了概括和总结, 列举了一系列有研究意义和实用价值的安全协议. 他们将安全协议进行如下分类: (1) 无可信第三方的对称密钥协议. 属于这一类的典型协议包括以下 ISO 系列协议 [9] :ISO 对称密钥一遍单边认证协议、 ISO 对称密钥二遍单边认证协议、 ISO 对称密钥二遍相互认证协议、ISO 对称密钥三遍相互认证协议、Andrew 安全 RPC 协议[10]等. (2) 应用密码校验函数(CCF)的认证协议.属于这一类的典型协议包括以下 ISO 系列协议[11] :ISO 应用 CCF 的一遍单边认证协议、ISO 应用 CCF 的二遍单边认证协议、 ISO 应用 CCF 的二遍相互认证协议、 ISO 应用 CCF 的三遍相互认证协议. (3) 具有可信第三方的对称密钥协议. 属于这一类的典型协议包括 NSSK 协议[1] 、Otway-Rees 协议 [4]、 Yahlom 协议[5]、大嘴青蛙协议[5]、Denning-Sacco 协议[12]、Woo-Lam 协议[13]等. (4) 对称密钥重复认证协议. 属于这一类的典型协议有 Kerberos 协议版本 5、 Neuman-Stubblebine 协议 [14]、 Kao-Chow 重复认证协议[15]等. (5) 无可信第三方的公开密钥协议. 属于这一类的典型协议包括以下 ISO 系列协议[16] :ISO 公开密钥一遍单边认证协议、 ISO 公开密钥二遍单边认证协议、 ISO 公开密钥二遍相互认证协议、ISO 公开密钥三遍相互认

2-SPR(U+UPR)P(vA)可重构并联机构的运动学与工作空间研究

2-SPR/（U+UPR）P（vA）可重构并联机构的运动学与工作空间研究马春生米文博尹晓秦马振东（中北大学机械工程学院，山西太原030051）摘要提出了一种含可重构运动副的2-SPR/（U+UPR）P（vA）冗余并联机构，可应用于并联操作平台。

首先，建立了2-SPR/（U+UPR）P（vA）并联机构的螺旋矩阵，求解机构在R相和U相下的自由度，并应用修正的Kutzbach-Grübler公式对机构的自由度进行了验证；其次，应用闭环矢量法求解机构的两组运动学逆解并验证、应用粒子群优化算法研究建立机构在R相下的正解模型并验证；最后，联合使用SolidWorks和Matlab软件求解了机构在R相下的可达工作空间和U相下的平动工作空间。

研究结果为该机构的进一步优化和实际应用提供了理论支持。

关键词可重构并联机构运动学分析粒子群优化工作空间Research of Kinematics and Workspace of2-SPR/(U+UPR)P(vA)Reconfigurable Parallel MechanismMa Chunsheng Mi Wenbo Yin Xiaoqin Ma Zhendong（School of Mechanical Engineering，North University of China，Taiyuan030051，China）Abstract A2-SPR/(U+UPR)P(vA)redundant parallel mechanism with reconfigurable kinematic pairs is proposed，which can be applied to parallel operation platform.Firstly，the spiral matrix of the2-SPR/(U+UPR)P (vA)parallel mechanism is established，the DOF of the mechanism under the R and U phases are solved，and the DOF of the mechanism are verified by using modified Kutzbach-Grübler formula.Secondly，the closed-loop vector method is used to solve the two sets of inverse kinematic solutions of the mechanism and verifica⁃tion，and the particle swarm optimization algorithm is used to study and establish the positive solution model of the mechanism under the R phase and verify.Finally，software to solve the mechanism´s reachable workspace under the R phase and the translational workspace under the U phase are solved using SolidWorks combing with Matlab.The research results provide theoretical support for the further optimization and practical applica⁃tion of the mechanism.Key words Reconfigurable parallel mechanism Kinematics analysis Particle swarm optimization Workspace0引言近几年，国内外十分重视并联机构的研究。

基于并行算法的大型屏障隔振三维数值模拟分析

式中，为时间步长；、Ｕ＋ｔ示不同时刻的位移．ｕ、ｔ￣表
（）３
有限元模型的并行化，就是针对式（）３的并行计算，目前常采用的方法是区域分解
法．Ｊ区域分解方法采用“ 分而治之” 的思想，首先将整个计算区域分解成若干个子区域，将各个子区域分配到不同的节点机上同时进行计算，并在各个节点机之间进行信息传递．区域分解有两种方法，贪婪算法（ｒｄ）坐标递归对分方法（ｅｕｉｏｒｎｔＧｅｙ与ｅｒｒｖｃｏｉｅｃｓｅｄａｂｅｔｎＲＢ．ｉｃｏ，Ｃ）一个好的分区方案应该有高的加速比及并行效率，响并行计算效率的ｓｉ影主要因素有：１载荷的分配是否均匀；２各处理器之间的相互通信量是否最小；３各（）（）（）处理器单元数量是否相同；４各区域时间步长的影响．（）贪婪算法及坐标递归对分方法均能满足各处理器单元数量相等的原则，一个好的但区域划分方案还要求各处理器之间相互通信量最小．因此，本文在坐标递归对分方法的基础上，结合上海曙光４０Ａ巨型机的体系结构平台，００设计了基于消息传递的，各子区域之间共享节点最少即各处理器之间相互通信量最小的分区方法（ｈｒｎｄｉｉｕｓａｅｏｅｍｎｍｍｂｅｔｎＳＭ）根据此方法，ｉｃｏ，ＮＢ．ｓｉ依据共享节点最少的原则，划定区域边界，在相邻的区域之间，单元节点被复制，分配到相应的子区域中，当满足分区收敛条件时输出模型的分区结果．采用ｃ语言和ＭＩＰ消息传递函数库，开发了处理器之间通信量最小分区程序，实现上述方法，该程序可读人有限元网格，并进行网格初始化分区，区结果可被有限元软件分读人，并各分区指定处理器负责，实现并行计算．

一种三维结构网格并行算法

第４０卷
第６期
Байду номын сангаас
航空计算技术
ＡｅｏｕｉａｍｐｉｃｎｑｅｒｎａｔｃｌＣｏｕｔＴｅｈｉｕｎｇ
Ｖｏ．０Ｎｏ．１４６ＮＯ．０１Ｖ２０
２１００年１月１
一
种三维结构网格并行算法
韩志熔陆志良郭同庆陈迎春，，，，
算法，能并行实现。三维结构网格下，Ｓ程的并才Ｎ．方行算法的主要思想就是将计算区域划分成若干子区
需要进行数据通信的网格单元取决于控制方程的数值离散方法。例如有限体积法下，用Ｊｍｏ使ａｓｎ中心格式，在计算过程中需要用到相邻子区域的二层网格单元的变量值，因此相邻子区域的第一、二层网格单第元需要进行数据通信；使用Ｒｅ格式在计算过程中只ｏ需要使用到相邻子区域的第一层网格单元的变量值。
（．１南京航空航天大学航空宇航学院，南京２０１；．海飞机设计研究院，１０６２上上海２０３）０２２
摘要：于三维结构网格，ＭＩＨ基以ＰＣ２作为并行开发环境，究了对等模式下流场的并行计算问研种并行算法。算法的核心思想是将需要通讯的其他区域的单元按区号从ｌ到ｎ排列，获得本区并
率，还可进一步将网格数目较大的子分区再次剖分，使

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

率、性能、处理能力等方面的要求也越来越高。
是并行计算的核心和瓶颈技术。
并行计算是将一项大的数据处理与数值计算任
并行算法是指在各种并行机上求解问题和处理
务（或任务的局部）分解为多个可相互独立、同时进数据，其本质是把多任务映射到分处理机中执行，或
行的子任务，并通过这些子任务相互协调的运行，实将现实的多维问题映射到具有拓扑结构的多处理机
衡树方法、倍增技术、流水线技术及加速级联策略。［４］此外，为便于并行算法的设计与理论分析以
算法的作用，本文在简单介绍并行计算方法的基础及为并行计算提供软硬件系统设计的简易界面，近
平面扫描算法是支持矢量数据空间分析的有效算法，通过该算法对空间对象进行逐一扫描可判断
其间的顺序及拓扑关系，是空间拓扑分析的基础。目前，并行平面扫描算法主要有分解归并方法和平面扫描树方法。分解归并方法应用较普遍，即主处理机通过将事件点平均分配给分处理机，各分处理机处理完各自的任务后将结果发送给主处理机，最后主处理机将各事件点合并，得到问题的解。平面扫描树技术是平面扫描算法并行化的一个重要手段，在具体的空间分析之前，首先进行预处理，通过并行归并等技术构建平面扫描树，然后遍历和搜索这棵扫描树，最终确定空间对象的拓扑邻近关系。平面扫描树技术可用于梯形分解、三角剖分及平面点定位等具体的空间问题中，因为采用并行方法，平面扫描树技术可以给每个元素分配处理器，极大地减小了处理问题的时间复杂度。［７］
摘要：作为ＧＩＳ的核心功能之一，空间分析逐步向处理数据海量化及分析过程复杂化方向发展，以往的串行算法渐渐不能满足人们对空间分析在计算效率、性能等方面的需求，并行空间分析算法作为解决目前问题的有效途径受到越来越多的关注。该文在简要介绍空间分析方法和并行计算技术的基础上，着重从矢量算法与栅格算法两方面阐述了目前并行空间分析算法的研究进展，评述了在空间数据自身特殊性的影响下并行空间分析算法的发展方向及存在的问题，探讨了在计算机软硬件技术高速发展的新背景下并行空间分析算法设计面临的机遇与挑战。关键词：并行计算；空间分析；并行ＧＩＳ中图分类号：Ｐ２０８文献标识码：Ａ文章编号：１６７２－０５０４（２０１１）０６－０００１－０５
矢量空间数据可较为精细地表达地物实体及详细属性信息，但实体间存在着多种复杂的空间关系（如相邻、相接等拓扑关系等），并行处理过程中须考虑地物实体的排序、联合、数据条带化以及拓扑关系维护等因素。因此，面向矢量空间数据的并行化存取与处理的相关算法和机制研究有较大难度。并不是所有的空间分析都适合并行化，这里主要从平面扫描算法、空间数据查询、空间连接操作、凸包算法、Ｄｅｌａｕｎａｙ三角网构建、空间网络分析等方面阐述空间矢量数据并行算法的研究进展。
论支撑，这些技术已开始应用于包括ＧＩＳ应用在内目的。并行算法经过多年的发展，目前已形成一些
的诸多领域。然而，由于并行技术发展时间不长，因基本设计方法，常见的并行计算策略有分治策略、平
此ＧＩＳ核心空间分析功能的并行化也处在发展初期。为了较好地认识并行计算技术对改进空间分析
此外，并行空间分析还要考虑ＧＩＳ的特殊性，其影响主要包括：１）算法因素：ＧＩＳ中并非所有的空间应用及其关键算法均可实现并行化，这受限于空间应用算法本身的特征。２）数据因素：包括空间数据的复杂程度、相关性程度和数据量大小等。３）实现因素：已有的并行化算法设计与实现大多是基于ＭＩＭＤ并行计算机系统，使用ＰＶＭ或ＭＰＩ并行计算软件，而空间数据模型的并行特征将着眼于空间数据模型本身及空间数据的组织结构和存储方式。［６］为评估并行空间分析算法的研究进展，本文根据数据处理类型的不同，将并行ＧＩＳ空间分析应用大体分为两类：基于矢量数据的并行存取与空间分析应用；基于栅格图像数据的并行空间分析应用。２．１并行矢量算法
上对并行空间分析算法作了综合性的回顾与探讨。３０年来，针对不同类型的并行计算机提出了多种并
１并行计算方法
行计算模型，如ＰＲＡＭ及其改进模型、ＶＬＳＩ和ＢＳＰ模型等，以及与网络并行计算密切相关的Ｃ３和
并行计算是计算数学与新一代计算机相结合的ＬｏｇＰ模型。其中，ＰＲＡＭ是广泛使用的抽象并行计
第２页
地理与地理信息科学第２７卷
２并行空间分析方法
并行空间分析方法是ＧＩＳ空间分析方法与并行计算的结合，致力于通过空间分析算法的并行化解决空间数据处理的速度与质量问题。ＧＩＳ数据具备空间信息容量大、地理分布广、时效性强、多源异构等特征，为了有效组织多源的相关数据进行综合分析，以建立响应速度快、计算能力强和空间数据高效组织与管理的新机制来认知、模拟、预测和调控自然地理环境和社会经济过程，客观上要求大力发展空间分析并行计算方法。另外，大力发展并行空间分析方法也有主观上的可行性。其一，网络并行、多核处理器、可视化并行编程及分布式ＧＩＳ等技术的发展，为空间分析的并行计算提供了条件；其二，以往对空间分析算法的改进多通过建立空间索引、数据分组、高速缓冲技术、数据结构优化及其他组合优化技术来提高算法性能，这些方案中大多渗透着并行计算中常用的分组、分治等思想，利于算法的并行化。
产物，其主要研究内容包括并行计算机、并行算法、算模型，ＢＳＰ模型提供了简单和可定量分析程序运
并行程序设计和并行应用等。相比于串行计算，并行计算有其明显的特点：多个处理器执行部件（执行
行时间的成本函数，Ｃ３和ＬｏｇＰ模型考虑了通信和同步等因素，形成了更贴合实际的并行计算模型。［５］
空间分析是ＧＩＳ的核心功能之一，也是ＧＩＳ区核）协作，共同完成某一项任务，各个执行部件的处
别于一般信息管理系统的显著特征之一。作为衔接理工作可分布在相同的计算机上（ＭＰＰ／ＳＭＰ／多核
空间数据处理与应用模型的重要部分，空间分析通处理器），也可分布在不同的计算机上。理论上，并
理地理科学领域中各种地理对象分析的重要方法。据计算和处理能力优势使并行计算成为计算机领域
然而，随着应用的深入，数据海量化、构架网络化、处的研究热点之一。在并行计算方面，并行体系结构、
理实时化等要求日益提高，对空间分析功能在计算效并行软件和并行算法三者缺一不可，其中并行算法
收稿日期：２０１１－０５－１８；修订日期：２０１１－０８－２２基金项目：江苏高校优势学科建设工程资助项目；国家基础科学人才培养基金能力提高项目（Ｊ０８３０５１８）作者简介：王结臣（１９７３－），男，博士，教授，主要从事地理信息系统理论与应用研究。Ｅ－ｍａｉｌ：ｈｏｔｍａｉｌｗａｎｇ＠ｙａｈｏｏ．ｃｏｍ．ｃｎ
现快速、高效的问题求解。［２］近年来网络、高性能计上求解。为了尽可能实现计算的高效率，并行算法
算机、多核计算机等的推广应用为其提供了硬件支需通过增加单位时间的算法复杂性来减少整体的时
撑，并行算法等理论技术的发展为其提供了软件、理间复杂性，达到将时间复杂性转化为空间复杂性的