下载文档原格式
并行计算的研究与探析摘要：计算科学的发展使得“计算科学”已经与传统的“理论科学”和“实验科学”并列成为推动科技发展和社会文明进步的三大科学。
同时，并行计算作为一种研究的工具，也逐渐融入到传统的“理论科学”和“实验科学”中，本文首先介绍了并行计算，其次对并行计算的新的研究方向now的技术做了重点阐述，最后探讨了并行计算的未来发展趋势。
关键词：并行计算高性能now并行编程中图分类号：tp33 文献标识码：a 文章编号：1674-098x(2011)09(c)-0056-02创建和应用并行计算的主要原因是因为并行计算是解决单处理器速度瓶颈的最好方法之一，而并行计算的硬件平台是并行计算机，它由一组处理单元组成，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。
近几年来，世界上和我国高性能并行计算机的发展取得长足进展。
每秒数百亿次、数千亿次乃至数万亿次计算能力的高端并行机已相继研制成功，使得以前许多无法求解和研究的问题现在已经成为可能，尤其是高性能并行计算有待于进一步研究和讨论。
1并行计算一高性能并行计算的研究1.1高性能计算一机群计算和网格计算高性能计算的主要手段和发展趋势是机群计算和网格计算。
机群系统的体系结构如图1所示：它由一组称为结点的pc或工作站互联构成。
每一个结点有自己的存储器、i/0设备和操作系统，不同结点可以是同构或异构的（硬件和操作系统），机群中间件向用户提供统一、灵活、透明、协调、安全的并行编程环境和并行运行环境，机群系统的全部软硬件资源属于该系统所有者，一般分布在一间实验室或一栋大楼内，机群系统虽然投资大，但可以充分获得可用性并保证安全性，网络系统投资小，但可用性差，安全性难以保障，利用in ter net构成服务网格和数据网格系统。
较之计算网格，具有更好的前景，网格计算只适用于非常关键性计算任务，机群计算和网格计算，必须解决的问题有：①向用户提供单一的系统映象，使机群计算和网格计算系统像单一主机一样使用。
计算机科学中的并行计算算法分析一、引言随着科技的发展和计算机性能的提高，现代计算机应用对计算速度的需求越来越高，为了提高计算机的性能，计算机科学中的并行计算显得尤为重要。
并行计算是指多个计算单元同时工作，通过合理的任务分配和协作，提高整个计算系统的计算速度。
本文将从并行计算的基本概念入手，对计算机科学中的并行计算算法进行分析和探讨。
二、并行计算的基本概念并行计算是指多个计算单元同时工作的一种计算方法。
在并行计算系统中，这些计算单元可以是同一台计算机中的多个CPU，也可以是连接在网络中的多个计算机。
并行计算通过将大型的计算任务分成多个小任务，分配给不同的计算单元来完成计算任务，从而提升整个计算系统的计算速度。
并行计算的优点在于它具有高效能、高可靠性和高可扩展性的优点。
通过利用多个计算单元的计算能力，可以显著缩短计算任务的处理时间，提高计算精度和质量。
此外，因为并行计算使得任务可以同时进行，因此它具有更高的可靠性和更好的容错性。
最后，由于并行计算可以扩展到更多的计算单元，因此它具有更高的可扩展性和灵活性，可以根据需要随时扩展计算资源。
三、并行计算的算法并行计算的核心在于如何设计高效的并行计算算法。
在实际应用中，有很多种并行计算算法，我们将根据不同的计算类型进行分析和讨论。
1、并行排序算法并行排序算法是一种基本的并行计算算法，用于对大量数据进行排序操作。
在并行排序算法中，数据被划分成多个小块，然后每个块都由一个计算单元进行排序。
最后，使用归并排序将这些小块有序地合并成一个有序数据集。
并行排序算法可以显著降低排序操作的时间复杂度，提高排序算法的效率。
2、并行图像处理算法并行图像处理算法是一种针对大规模图像数据的并行计算算法。
在并行图像处理中，数据被划分成多个小块，然后每个块都由一个计算单元进行图像处理。
最后，将处理后的小块再进行拼接成一张完整的图片。
并行图像处理算法可以显著提高大规模图像处理的速度，提高图像分析和识别的效率。
在国内，并行工程作为CIMS发展的一个新阶段，得到了一些企业的广为关注，其研究已于1992年底被列为国家863计划自动化领域的重点研究内容。
在国家科技部和863/CIMS主题专家组的领导下，1995年7月由清华大学、华中理工大学、北京航空航天大学、上海交通大学和航天工业总公司二院5个单位人员组成了“863/CIMS关键技术攻关棗并行工程”的技术攻关队伍，以航天总公司二院的复杂结构件为应用背景，开展并行工程关键技术的研究与应用。
经过近两年的攻关，终于取得了重大进展。
该项目在应用上有特色，在某些关键技术上已经达到国际先进水平，目前，该项目已经通过鉴定【17】。
虽然并行工程在实际应用中产生了如此巨大的效果，但是也还存在一些不易解决的问题，如：在设计中考虑后续工作增加了当前工作的难度，支持并行工程的主模型还未统一，工程数据库还没有完全成熟等。
为此人们进行了大量的研究工作，本文的介绍只能是挂一漏万的。
四、并行工程的研究热点通过查阅国内外文献，了解到目前并行工程的研究热点主要包括：1、并行工程基础理论的研究：主要包括概念设计模型、并行设计理论、鲁棒设计及支持产品开发全过程的模型研究。
尤其是并行设计的建模技术，所谓建模就是指建立产品模型，而产品模型包括产品生命周期各阶段的信息及访问、操作这些信息的算法。
在计算机环境下，进行并行设计要求信息模型能够获取和表达产品信息、制造信息和资源信息；能够方便地获得有关产品可制造性、可装配性、可维护性、安全性等方面的信息；能够使小组成员共享信息。
要满足这些要求，必须建立一个能够表达和处理有关产品生命周期各阶段所有信息的统一产品模型。
统一模型的建立可以在特征建模基础上进行，但是特征建模只是强调设计和制造信息的集成，在多学科人员协同工作环境下，当产品开发某环节数据被改动后，它不具备自动更新相关数据的能力，即不支持所谓全相关性。
国际标准化组织(ISO)提出的产品数据模型STEP标准是建立模型的工具，但由于产品数据复杂、多变此标准仍在试用阶段。
大规模并行计算技术的研究进展随着信息技术的飞速发展，大规模并行计算技术作为计算科学中的一个重要领域，受到越来越多的关注和重视。
在当今数字化社会中，数据量呈指数级增长，传统的计算方法已经无法满足海量数据的处理需求，因此大规模并行计算技术的研究和应用显得尤为重要。
大规模并行计算技术主要是指通过将多台计算机或处理器连接起来同时工作来完成复杂计算任务的一种计算模式。
在这种模式下，计算任务被分解成多个子任务并行计算，最后再将结果合并得到最终的计算结果。
大规模并行计算技术的优势在于能够充分利用多台计算机的计算资源，提高计算效率，加快计算速度，同时提高系统的可靠性和容错能力。
在大规模并行计算技术的研究领域，分布式计算和云计算是两个重要的方向。
分布式计算是指将大规模计算任务分发给多台计算机进行计算，各台计算机之间通过网络进行通信和协作，最终将计算结果汇总。
分布式计算技术的关键是任务的分解和合并算法，以及通信和协作机制的设计。
通过合理设计分布式计算系统的结构和算法，可以充分利用计算资源，实现任务的高效并行计算。
云计算则是基于分布式计算技术，通过互联网提供计算资源和服务的一种计算模式。
在云计算环境下，用户可以根据需求灵活选择和配置计算资源，按照使用量付费，实现资源的共享和动态调整。
云计算技术的快速发展和广泛应用，为各行各业提供了更加灵活、高效和经济的计算服务。
除了分布式计算和云计算，大规模并行计算技术的研究还涉及到并行算法和并行编程模型等方面。
并行算法是指在多台计算机或处理器上同时执行的算法，其设计考虑了计算资源的充分利用和任务之间的协作关系。
并行算法的设计需要考虑任务的划分和调度、通信和同步机制等方面，以实现任务的高效并行计算。
并行编程模型则是针对不同类型的并行计算任务提供的一种程序设计范式，通过合理选择编程模型可以减少并行编程的复杂性，提高编程效率。
随着硬件技术的不断发展和计算资源的日益增加，大规模并行计算技术在科学计算、人工智能、大数据分析等领域得到了广泛的应用。
问并行计算的现状与发展并行计算是一种以并行方式执行任务的计算方法，它能够通过同时执行多个计算任务来提高计算速度和效率。
在过去的几十年里，随着硬件和软件技术的不断发展，并行计算在科学、工程和商业领域得到了广泛应用。
本文将从并行计算的现状、发展和挑战等方面进行探讨。
首先，从技术角度来看，目前并行计算主要有两种方法：共享内存和分布式内存。
共享内存并行计算是指多个处理器共享同一块内存，可以共同读写数据，充分发挥处理器之间的协同作用。
而分布式内存并行计算则是将计算任务分发给多个处理器，每个处理器处理自己独立的子任务，最后将结果进行整合。
这两种方法各有优势和应用场景，可以根据任务的特点和要求进行选择。
在硬件方面，随着并行计算的普及和需求的不断增长，计算机硬件也在不断发展。
多核处理器的出现使得并行计算更加高效，多个处理器核心可以同时执行不同的任务，提高了整体的计算速度。
而高性能的图形处理器（GPU）也成为并行计算的热门选择，其并行计算能力在处理复杂的图形和科学计算方面具有明显优势。
从应用的角度来看，并行计算已经广泛应用于许多领域。
在科学研究方面，并行计算可以加快模拟、仿真和数据分析等计算过程，辅助科学家进行研究。
在工程领域，通过并行计算可以大大减少设计时间，优化产品性能。
在商业领域，大规模数据分析和机器学习等任务也离不开并行计算的支持。
在发展方面，虽然并行计算已经取得了显著的进展和应用，但仍然面临一些挑战。
首先，在软件开发方面，编写高效的并行计算程序仍然是一个复杂的任务。
并行程序需要充分利用多个处理器和内存，并处理好并发问题，这对开发人员的技术要求较高。
其次，任务的分解和调度也是一个挑战，如何将任务合理地分发给各个处理器，以及如何高效地执行和同步任务，都需要深入研究和优化。
此外，异构计算（如CPU和GPU）的结合也是一个发展方向。
由于GPU具有优秀的并行计算性能，因此将CPU和GPU结合起来，可以发挥各自的优势，提高计算效率。
空间数据计算的并行化研究一、引言随着社会经济的发展，大数据时代已经到来。
不论是互联网上的数据还是传统行业中的数据，其数量和规模都在不断增加。
其中，空间数据具有重要的地位，因为它们不仅包含了空间信息，还有着时间和属性信息。
如何高效地利用这些空间数据，成为了当前研究的主要方向之一。
二、空间数据计算方法及其并行化研究1.空间数据计算方法空间数据计算方法包括但不限于：空间插值、空间分析、空间模型等。
其中，空间插值是空间数据处理的基础工作，它可以通过栅格、点、面三种形式进行。
栅格插值常用的算法有Kriging插值、反距离加权插值、样条插值等，点插值常用的算法有IDW插值、自然邻域法等，面插值常用的算法有三角剖分、TIN插值等。
空间分析主要利用地理信息系统（GIS）中的工具来处理数据，该方法包括缓冲区分析、裁剪分析、合并分析、统计分析等。
空间模型建立在空间数据的基础上，通过建立实体空间模型、场空间模型等，对数据进行进一步处理。
2.并行化研究并行计算技术是利用多个计算机处理器或多个处理器核心进行计算的方法，用于提高计算效率。
基于并行计算技术，可以实现空间数据的高效处理。
具体来说，可以通过以下方法实现并行化研究：（1）并行算法的设计在并行计算中，算法的设计是至关重要的。
因此，在进行并行化研究时，应该优先考虑合适的算法，以提高计算效率。
（2）并行计算的架构设计在并行计算时，要充分利用计算机器的硬件条件，如多核处理器、分布式系统等。
此外，可以通过GPU加速、多线程编程等方式优化计算速度。
（3）数据分布的设计在进行并行计算时，需要将数据分发到不同的处理器中，以提高计算效率。
因此，应该合理设计数据分配的策略，以充分利用计算资源。
三、空间数据计算并行化研究的实现1.并行算法的设计在并行算法的设计过程中，我们应该优先考虑合适的算法，以提高计算效率。
例如，在空间插值中，可以使用Kriging插值算法。
此算法的并行化效果较好，可以提高计算效率。
并行计算技术的研究进展及应用并行计算技术是指将任务分配给多个计算机或处理器同时运行，以提高计算效率和速度的技术。
它已经在许多领域得到了广泛的应用，例如科学计算、图像处理、人工智能、大数据分析等等。
本文将从技术的发展历程、应用领域和未来前景三个方面来论述并行计算技术的研究进展及应用。
一、技术的发展历程并行计算技术的发展可以追溯到20世纪60年代，当时计算机性能很低，需要几个小时甚至几天才能完成一个计算任务。
为了提高效率，早期的并行计算系统采用了不同的方式，比如多台计算机通过网络连接起来，交替地执行任务、将任务分割成不同的子任务等等。
当时使用的并行计算系统被称为“分布式计算系统”，它们可以应用于低级层次的任务，如分布在不同节点的数据的存取等。
随着计算机硬件技术的不断进步，单个机器的计算能力越来越强大。
同时，多核处理器技术的发展解决了单个CPU频率无法提升的局限性。
在当今互联网和云计算时代，高度集成的、可扩展的计算硬件架构已现成熟，并得到了广泛应用。
同时，大规模的并行计算系统也通过高速网路互连，形成了一个庞大的网络云结构，实现了高效的分布式计算。
二、应用领域并行计算技术被广泛应用于如气象学、生物学、医学、物理学、航天等各个科学领域。
例如，在气象学中，高性能并行计算器可以模拟风、温度、湿度、压力和云等气象动力学变量，以预测天气。
在生物学和药理学领域，大量探索性研究依赖于大型计算机模拟分子和蛋白质结构。
此外，人工智能系统的广泛使用也让并行计算技术成为了必要的技术之一。
在深度学习领域中，高性能并行计算平台可以加速神经网络模型的训练，提高人工智能系统的准确性和效率。
在大数据分析领域，高性能并行计算也是数据分析、数据挖掘和机器学习的基础。
三、未来前景由于并行计算技术的应用领域越来越广泛，并且硬件设施的性能也越来越强大，这种计算方法在未来将继续得到推广和广泛应用。
未来的并行计算系统将越来越多地使用可重构硬件、GPU和TPU等专用加速器来加速计算，从而实现更高效和更快速的计算。
并行计算算法优化与性能分析随着计算机科学和技术的快速发展，计算任务的规模和复杂度不断增加，传统的串行计算已经难以满足处理大规模数据和高性能计算的需求。
并行计算技术应运而生，通过同时使用多个处理单元来执行计算任务，大幅提高计算性能和效率。
然而，并行计算并不是一种简单的将计算任务分配给各个处理单元并同时执行的方式。
为了发挥并行计算的最大潜力，我们需要优化并行算法，并对其性能进行全面的分析。
首先，优化并行计算算法是实现高性能并行计算的关键。
在设计并行算法时，我们需要考虑以下几个因素：1. 数据分布：对于需要进行并行计算的问题，我们需要合理划分输入数据，使之能够同时被多个处理单元处理。
数据划分的负载均衡是优化并行算法的一个关键要素，确保每个处理单元的计算工作量均衡，并最小化通信开销。
2. 通信开销：在并行计算中，不同处理单元之间需要进行数据交换和协同工作。
减少通信开销是提高并行计算性能的重要手段。
我们可以通过减少数据交换的次数和数据量，采用更高效的通信模式（如异步通信）等方式来降低通信开销。
3. 同步机制：并行计算的多个处理单元需要进行协同工作，确保各个单元按照正确的顺序执行。
同步机制是实现协同工作的关键，在设计并行算法时需要明确各个处理单元之间的依赖关系，并合理选择同步机制，以避免冲突和死锁。
其次，对并行计算算法的性能进行分析是进一步优化算法的关键一步。
性能分析可以帮助我们找到并行算法中的瓶颈和热点，从而有针对性地进行优化。
1. 时间复杂度分析：计算并行算法的时间复杂度是评估算法性能的重要指标之一。
通过分析算法的时间复杂度，我们可以了解算法的计算需求和时间开销，从而评估其是否满足实际需求。
2. 并行效率分析：并行效率衡量了并行计算的性能提升程度。
通过比较并行计算与串行计算的时间开销，我们可以评估并行计算的效率。
高并行效率意味着算法能够有效利用并行计算资源，提高计算性能。
3. 加速比分析：加速比是评估并行计算效果的重要指标，它衡量了并行计算相对于串行计算的加速程度。
并行算法研究进展陈国良并行算法为并行计算的发展奠定理论基础，是我国高性能计算技术发展的关键之一。
要使其研究健康发展必须从学科建设入手，重视人才培养。
引言什么是并行算法简单地讲，算法就是求解问题的方法和步骤，而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。
人们之所以对并行性感兴趣，是因为在现实世界中存在着固有的并行性。
其实在日常生活中，你可能自觉或不自觉地都在运用着并行，比如一边听演讲，一边记笔记就是听觉、视觉和手写的并行。
这类例子不胜枚举。
然而，在处理很多事务时，比如进行推理和计算，人们又习惯用串行方式，在这种情况下，要改用而且要用好并行性也并非易事。
同时，就计算科学而言，并行计算理论仍处于发展阶段，特别是早期的并行机均很昂贵，编写并行软件又很难，所以并行性的优点尚未被普遍的认同。
为什么需要并行首先，对于那些要求快速计算的应用问题，单处理机由于器件受物理速度的限制而无法满足要求，所以使用多台处理机联合求解就势在必行了；其次，对于那些大型复杂的科学工程计算问题，为了提高计算精度，往往需要加密计算网格，而细网格的计算也意味着大计算量，它通常需要在并行机上实现；最后，对于那些实时性要求很高的应用问题，传统的串行处理往往难以满足实时性的需要而必须在并行机上用并行算法求解。
并行算法的分类并行算法可以分为数值并行算法和非数值并行算法：前者研究基于代数关系运算的数值计算问题的并行算法，主要包括矩阵运算、方程组的求解和数字信号处理等；后者研究基于比较关系运算的符号处理问题的并行算法，主要包括图论问题、数据库操作和组合优化等。
本文重点讨论非数值并行算法。
并行算法研究的层次并行算法的研究可分为并行计算理论、并行算法的设计与分析以及并行算法的实现三个层次。
其中并行计算理论主要研究并行计算模型、计算问题的下界、问题的可并行化、NC类问题1和P-完全问题2等。
浅谈计算机并行计算的发展与展望计算机并行计算是指通过多个计算节点同时处理不同的运算任务来提升计算性能的计算方式。
随着计算机硬件技术的不断发展和应用需求的不断增加，计算机并行计算也不断演化和发展，成为重要的计算方式之一。
本文将从发展历程、现状应用和展望三个方面来探讨计算机并行计算的发展和未来。
一、并行计算发展历程计算机并行计算技术的发展历程可以追溯到20世纪70年代的超级计算机技术。
当时，随着计算机运算速度的增加和复杂度的提高，单一计算节点已经无法满足计算需求。
因此，大规模系统已成为一种有效的解决方案。
在80年代末，随着并行处理系统的出现，计算机并行计算技术才真正开始进入大规模应用领域。
在90年代，随着并行处理系统硬件技术和软件技术的不断提高，大规模并行计算机系统逐渐成为高性能计算中的主流技术之一。
此时，计算机并行计算已经广泛应用于天气预报、金融、汽车、医学等多个领域。
二、并行计算现状应用目前，计算机并行计算技术已经在科学、工程、商业和医学等多个领域得到广泛应用。
以下是计算机并行计算技术在不同领域的应用介绍：1.科学：计算机并行计算技术在天气预报、气候模拟、宇宙学、地震学、计算流体力学等科学领域得到广泛应用。
通过大规模并行计算系统，科学家们能够进行更加精确的预测和模拟。
2.工程：计算机并行计算技术在建筑、航空、汽车制造、机器人等工程领域得到广泛应用。
通过并行计算系统，工程师们可以进行复杂结构的仿真和优化设计。
3.商业：计算机并行计算技术在商业领域中也得到广泛应用，例如金融分析、数据挖掘和在线广告等方面。
通过并行计算技术，商业领域可以快速处理庞大的数据量，从而提高决策效率和准确性。
4.医学：并行计算技术在医学领域中的应用主要集中于医学影像处理、基因组学和药物研发等方面。
通过并行计算技术，医学领域可以更加准确地诊断和治疗疾病。
在未来，计算机并行计算技术将继续向更高维度、更快速、更低功耗和更灵活的方向发展。
第27卷第6期2011年11月地理与地理信息科学G e o g r a p h y a n d G e o -I n f o r m a t i o n S c i e n c e V o l .27N o .6N o v e m b e r2011收稿日期:2011-05-18;修订日期:2011-08-22基金项目:江苏高校优势学科建设工程资助项目;国家基础科学人才培养基金能力提高项目(J 0830518作者简介:王结臣(1973-,男,博士,教授,主要从事地理信息系统理论与应用研究。
E -m a i l :h o t m a i l w a n g@y a h o o .c o m.c n 并行空间分析算法研究进展及评述王结臣,王豹,胡玮,张辉(南京大学地理信息科学系,江苏南京210093摘要:作为G I S 的核心功能之一,空间分析逐步向处理数据海量化及分析过程复杂化方向发展,以往的串行算法渐渐不能满足人们对空间分析在计算效率、性能等方面的需求,并行空间分析算法作为解决目前问题的有效途径受到越来越多的关注。
该文在简要介绍空间分析方法和并行计算技术的基础上,着重从矢量算法与栅格算法两方面阐述了目前并行空间分析算法的研究进展,评述了在空间数据自身特殊性的影响下并行空间分析算法的发展方向及存在的问题,探讨了在计算机软硬件技术高速发展的新背景下并行空间分析算法设计面临的机遇与挑战。
关键词:并行计算;空间分析;并行G I S中图分类号:P 208文献标识码:A 文章编号:1672-0504(201106-0001-05空间分析是GI S 的核心功能之一,也是G I S 区别于一般信息管理系统的显著特征之一。
作为衔接空间数据处理与应用模型的重要部分,空间分析通过对原始数据的特征观察、分析和处理,获得更多的经验和知识,并以此作为空间行为的决策依据[1]。
在G I S 应用迅猛发展的今天,G I S 空间分析已成为处理地理科学领域中各种地理对象分析的重要方法。
然而,随着应用的深入,数据海量化、构架网络化、处理实时化等要求日益提高,对空间分析功能在计算效率、性能、处理能力等方面的要求也越来越高。
并行计算是将一项大的数据处理与数值计算任务(或任务的局部分解为多个可相互独立、同时进行的子任务,并通过这些子任务相互协调的运行,实现快速、高效的问题求解[2]。
近年来网络、高性能计算机、多核计算机等的推广应用为其提供了硬件支撑,并行算法等理论技术的发展为其提供了软件、理论支撑,这些技术已开始应用于包括G I S 应用在内的诸多领域。
然而,由于并行技术发展时间不长,因此G I S 核心空间分析功能的并行化也处在发展初期。
为了较好地认识并行计算技术对改进空间分析算法的作用,本文在简单介绍并行计算方法的基础上对并行空间分析算法作了综合性的回顾与探讨。
1并行计算方法并行计算是计算数学与新一代计算机相结合的产物,其主要研究内容包括并行计算机、并行算法、并行程序设计和并行应用等。
相比于串行计算,并行计算有其明显的特点:多个处理器执行部件(执行核协作,共同完成某一项任务,各个执行部件的处理工作可分布在相同的计算机上(M P P /S M P /多核处理器,也可分布在不同的计算机上。
理论上,并行计算具有将计算能力从单个处理器无缝扩展到无限多个处理器的潜力[3]。
大量计算任务被分配到多个分处理器上将获得更快的处理速度,其巨大的数据计算和处理能力优势使并行计算成为计算机领域的研究热点之一。
在并行计算方面,并行体系结构、并行软件和并行算法三者缺一不可,其中并行算法是并行计算的核心和瓶颈技术。
并行算法是指在各种并行机上求解问题和处理数据,其本质是把多任务映射到分处理机中执行,或将现实的多维问题映射到具有拓扑结构的多处理机上求解。
为了尽可能实现计算的高效率,并行算法需通过增加单位时间的算法复杂性来减少整体的时间复杂性,达到将时间复杂性转化为空间复杂性的目的。
并行算法经过多年的发展,目前已形成一些基本设计方法,常见的并行计算策略有分治策略、平衡树方法、倍增技术、流水线技术及加速级联策略[4]。
此外,为便于并行算法的设计与理论分析以及为并行计算提供软硬件系统设计的简易界面,近30年来,针对不同类型的并行计算机提出了多种并行计算模型,如P R AM 及其改进模型、V L S I 和B S P模型等,以及与网络并行计算密切相关的C 3和L o gP 模型。
其中,P R AM 是广泛使用的抽象并行计算模型,B S P 模型提供了简单和可定量分析程序运行时间的成本函数,C 3和L o gP 模型考虑了通信和同步等因素,形成了更贴合实际的并行计算模型[5]。
2并行空间分析方法并行空间分析方法是G I S空间分析方法与并行计算的结合,致力于通过空间分析算法的并行化解决空间数据处理的速度与质量问题。
G I S数据具备空间信息容量大、地理分布广、时效性强、多源异构等特征,为了有效组织多源的相关数据进行综合分析,以建立响应速度快、计算能力强和空间数据高效组织与管理的新机制来认知、模拟、预测和调控自然地理环境和社会经济过程,客观上要求大力发展空间分析并行计算方法。
另外,大力发展并行空间分析方法也有主观上的可行性。
其一,网络并行、多核处理器、可视化并行编程及分布式G I S等技术的发展,为空间分析的并行计算提供了条件;其二,以往对空间分析算法的改进多通过建立空间索引、数据分组、高速缓冲技术、数据结构优化及其他组合优化技术来提高算法性能,这些方案中大多渗透着并行计算中常用的分组、分治等思想,利于算法的并行化。
此外,并行空间分析还要考虑G I S的特殊性,其影响主要包括:1算法因素:G I S 中并非所有的空间应用及其关键算法均可实现并行化,这受限于空间应用算法本身的特征。
2数据因素:包括空间数据的复杂程度、相关性程度和数据量大小等。
3实现因素:已有的并行化算法设计与实现大多是基于M I M D并行计算机系统,使用P VM或M P I并行计算软件,而空间数据模型的并行特征将着眼于空间数据模型本身及空间数据的组织结构和存储方式[6]。
为评估并行空间分析算法的研究进展,本文根据数据处理类型的不同,将并行G I S空间分析应用大体分为两类:基于矢量数据的并行存取与空间分析应用;基于栅格图像数据的并行空间分析应用。
2.1并行矢量算法矢量空间数据可较为精细地表达地物实体及详细属性信息,但实体间存在着多种复杂的空间关系(如相邻、相接等拓扑关系等,并行处理过程中须考虑地物实体的排序、联合、数据条带化以及拓扑关系维护等因素。
因此,面向矢量空间数据的并行化存取与处理的相关算法和机制研究有较大难度。
并不是所有的空间分析都适合并行化,这里主要从平面扫描算法、空间数据查询、空间连接操作、凸包算法、D e l a u n a y三角网构建、空间网络分析等方面阐述空间矢量数据并行算法的研究进展。
平面扫描算法是支持矢量数据空间分析的有效算法,通过该算法对空间对象进行逐一扫描可判断其间的顺序及拓扑关系,是空间拓扑分析的基础。
目前,并行平面扫描算法主要有分解归并方法和平面扫描树方法。
分解归并方法应用较普遍,即主处理机通过将事件点平均分配给分处理机,各分处理机处理完各自的任务后将结果发送给主处理机,最后主处理机将各事件点合并,得到问题的解。
平面扫描树技术是平面扫描算法并行化的一个重要手段,在具体的空间分析之前,首先进行预处理,通过并行归并等技术构建平面扫描树,然后遍历和搜索这棵扫描树,最终确定空间对象的拓扑邻近关系。
平面扫描树技术可用于梯形分解、三角剖分及平面点定位等具体的空间问题中,因为采用并行方法,平面扫描树技术可以给每个元素分配处理器,极大地减小了处理问题的时间复杂度[7]。
空间数据查询通常被归类为空间数据库中空间操作的范畴。
面对海量的空间数据,使用并行服务器实现多个并发用户同时参与数据查询,可以充分发挥并行计算的优势并大幅提高空间数据库的数据存取与处理能力。
空间数据的并行查询效率与数据划分策略及空间索引结构密切相关。
数据划分强调数据在多个磁盘系统上较均匀分布,每个磁盘上的数据保持相对平衡的状态。
面向并行空间数据库系统,贾婷等提出了一种基于H i l b e r t空间填充曲线的适于矢量空间数据的划分方法和K-平均聚类算法,较好地实现了空间数据的均衡划分[8,9]。
空间索引结构的构建要尽可能减小索引的重叠区域和空白区域,R 树索引得到了广泛应用。
刘润涛等结合改进的K-均值算法,给出了基于R树和四叉树的空间索引结构,具有更紧凑的结构和更高的查询效率[10]。
空间连接操作是G I S和空间数据库的重要操作。
已有的并行空间连接算法可归纳为基于空间数据划分策略的并行空间连接和基于并行R树索引的并行空间连接。
对于参与连接操作的两个空间关系,前者采用相同的数据划分策略将空间区域划分至并行计算机环境中的各节点上分别处理;后者充分利用了并行R树索引结构的优势,将计算负载分担到并行计算环境中的计算节点上,在并行R树构建过程中已完成海量空间数据的划分和排序[11]。
凸包是平面点集的最小外接凸多边形。
目前,串行求取凸包的经典解法有包绕法、内外法、扫描法、分治法和分层次方法等。
在凸包算法并行化方面,最初采用分治方法,即通过对散乱点集的分类,在不同处理器上分别求取分凸包,最后构造各分凸包的公共凸包[12]。
采用此方法在一定程度上提高了计算页2第地理与地理信息科学第27卷效率,但由于凸包往往只是由点集中小部分点构成,绝大多数点参与计算浪费了大量时间,而删除内点在串行计算中也是一项规模很大的工作。
郝小柱等采用并行的方法删除内点,对保留点排序形成简单有序多边形,最后对该多边形求取凸包,大大减小了时间复杂度[13]。
D e l a u n a y三角网的并行构建也可建立在凸包分组基础上,采用分治方法,首先按照一定间隔把凸包的边传给各处理机,并建立相应的边表和总边表;然后,各处理机按照D e l a u n a y三角网规则找到点集中符合要求的点,直至找不到时算法终止[14]。
因为凸包的构建是一个重要计算环节,其计算效率对D e l a u n a y三角网的生成效率影响较大。
空间网络分析是矢量数据空间分析的重要组成部分,因其涉及空间要素间复杂的拓扑关系而使得大规模网络分析计算耗时过长。
最短路径分析是网络分析中的经典问题,也是资源分配、路线设计与分析等优化问题的基础,目前实现并行化的方法主要有网络复制及网络分割[15,16]。
网络复制最短路径并行算法是主处理器将整个网络复制到各分处理器中,同时将网络中的所有源点分配到各分处理器上;然后,各处理器调用单源最短路径串行算法求解各自负责源点的最短路径,并将结果汇总到主处理器中。
