并行空间分析算法研究进展及评述

《并行空间分析算法研究进展及评述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第２７卷第６期地理与地理信息科学Ｖｏｌ．２７Ｎｏ．６２０１１年１１月ＧｅｏｇｒａｐｈｙａｎｄＧｅｏ－ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅＮｏｖｅｍｂｅｒ２０１１并行空间分析算法研究进展及评述王结臣，王豹，胡玮，张辉（南京大学地理信息科学系，江苏南京２１００９３）摘要：作为ＧＩＳ的核心功能之一，空间分析逐步向处理数据海量化及分析过程复杂化方向发展，以往的串行算法渐渐不能满足人们对空间分析在计算效率、性能等方面的需求，并行空间分析算法作为解决目前问题的有效途径受到越来越多的关注。该文在简要介绍空间分析方法和并行计算技术的基础上，着重从矢量算法与栅格算法两方面阐述了目前并行空间分析算法的研究进

2、展，评述了在空间数据自身特殊性的影响下并行空间分析算法的发展方向及存在的问题，探讨了在计算机软硬件技术高速发展的新背景下并行空间分析算法设计面临的机遇与挑战。关键词：并行计算；空间分析；并行ＧＩＳ中图分类号：Ｐ２０８文献标识码：Ａ文章编号：１６７２－０５０４（２０１１）０６－０００１－０５空间分析是ＧＩＳ的核心功能之一，也是ＧＩＳ区核）协作，共同完成某一项任务，各个执行部件的处别于一般信息管理系统的显著特征之一。作为衔接理工作可分布在相同的计算机上（ＭＰＰ／ＳＭＰ／多核空间数据处理与应用模型的重要部分，空间分析通处理器），也可分布在不同的计算机上。理论上，并过对原始数据的特征观察、分析和

3、处理，获得更多的行计算具有将计算能力从单个处理器无缝扩展到无［１］［３］经验和知识，并以此作为空间行为的决策依据。限多个处理器的潜力。大量计算任务被分配到多在ＧＩＳ应用迅猛发展的今天，ＧＩＳ空间分析已成为处个分处理器上将获得更快的处理速度，其巨大的数理地理科学领域中各种地理对象分析的重要方法。据计算和处理能力优势使并行计算成为计算机领域然而，随着应用的深入，数据海量化、构架网络化、处的研究热点之一。在并行计算方面，并行体系结构、理实时化等要求日益提高，对空间分析功能在计算效并行软件和并行算法三者缺一不可，其中并行算法率、性能、处理能力等方面的要求也越来越高。是并行计算的核心和瓶颈技术。并

4、行计算是将一项大的数据处理与数值计算任并行算法是指在各种并行机上求解问题和处理务（或任务的局部）分解为多个可相互独立、同时进数据，其本质是把多任务映射到分处理机中执行，或行的子任务，并通过这些子任务相互协调的运行，实将现实的多维问题映射到具有拓扑结构的多处理机［２］现快速、高效的问题求解。近年来网络、高性能计上求解。为了尽可能实现计算的高效率，并行算法算机、多核计算机等的推广应用为其提供了硬件支需通过增加单位时间的算法复杂性来减少整体的时撑，并行算法等理论技术的发展为其提供了软件、理间复杂性，达到将时间复杂性转化为空间复杂性的论支撑，这些技术已开始应用于包括ＧＩＳ应用在内目的。并行算法经

5、过多年的发展，目前已形成一些的诸多领域。然而，由于并行技术发展时间不长，因基本设计方法，常见的并行计算策略有分治策略、平此ＧＩＳ核心空间分析功能的并行化也处在发展初衡树方法、倍增技术、流水线技术及加速级联策［４］期。为了较好地认识并行计算技术对改进空间分析略。此外，为便于并行算法的设计与理论分析以算法的作用，本文在简单介绍并行计算方法的基础及为并行计算提供软硬件系统设计的简易界面，近上对并行空间分析算法作了综合性的回顾与探讨。３０年来，针对不同类型的并行计算机提出了多种并行计算模型，如ＰＲＡＭ及其改进模型、ＶＬＳＩ和ＢＳＰ１并行计算方法模型等，以及与网络并行计算密切相关的Ｃ３和并行计算是

6、计算数学与新一代计算机相结合的ＬｏｇＰ模型。其中，ＰＲＡＭ是广泛使用的抽象并行计产物，其主要研究内容包括并行计算机、并行算法、算模型，ＢＳＰ模型提供了简单和可定量分析程序运并行程序设计和并行应用等。相比于串行计算，并行时间的成本函数，Ｃ３和ＬｏｇＰ模型考虑了通信和［５］行计算有其明显的特点：多个处理器执行部件（执行同步等因素，形成了更贴合实际的并行计算模型。收稿日期：２０１１－０５－１８；修订日期：２０１１－０８－２２基金项目：江苏高校优势学科建设工程资助项目；国家基础科学人才培养基金能力提高项目（Ｊ０８３０５１８）作者简介：王结臣（１９７３－），男，博士，教授，主要从事地理信息系统理论

7、与应用研究。Ｅ－ｍａｉｌ：ｈｏｔｍａｉｌｗａｎｇ＠ｙａｈｏｏ．ｃｏｍ．ｃｎ第２页地理与地理信息科学第２７卷其间的顺序及拓扑关系，是空间拓扑分析的基础。２并行空间分析方法目前，并行平面扫描算法主要有分解归并方法和平并行空间分析方法是ＧＩＳ空间分析方法与并行面扫描树方法。分解归并方法应用较普遍，即主处计算的结合，致力于通过空间分析算法的并行化解理机通过将事件点平均分配给分处理机，各分处理决空间数据处理的速度与质量问题。ＧＩＳ数据具备机处