并行算法是什么

小白 QA 2020-04-25 10:03:17 阅读(...)

并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解。

并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解。

并行算法是什么

定义

并行算法是并行计算中非常重要的问题。并法研究应该确立一个“理论-设计-实现-应用”的系统方法,形成一个完善的 “架构—算法—编程” 方法论,这样才能保证并行算法不断发展并变得更加实用。

简介

简单的说,算法就是求解问题的方法和步骤。并行算法,就是在并行机上用很多个处理器联合求解问题的方法和步骤。实际上,在自然界中并行是客观存在的普遍现象,关键问题在于能不能很好的利用。由于人们的思维能力以及思考问题的方法对并行不太习惯,且并行算法理论不成熟,所以总是出现了需求再来研究算法,不具有导向性,同时实现并行算法的并行程序性能较差,往往满足不了人们的需求。并行算法的研究历史可简单归纳为:上世纪 70 到 80 年代,并行算法研究处于高潮;到上世纪 90 年代跌入低谷;目前,又处于研究的热点阶段。现在,人们已经可以自己搭建 PC cluster,利用学习到的理论知识来解决实际问题,不再是纸上谈兵,这也为我们提供了新的机遇和挑战。

体系结构

相对于串行计算,并行计算可以划分成时间并行和空间并行。时间并行即流水线技术,空间并行使用多个处理器执行并发计算,当前研究的主要是空间的并行问题。以程序和算法设计人员的角度看,并行计算又可分为数据并行和任务并行。数据并行把大的任务化解成若干个相同的子任务,处理起来比任务并行简单。

空间上的并行导致两类并行机的产生,按照麦克·弗莱因(Michael Flynn)的说法分为单指令流多数据流(SIMD)和多指令流多数据流(MIMD),而常用的串行机也称为单指令流单数据流(SISD)。MIMD 类的机器又可分为常见的五类:并行向量处理机(PVP)、对称多处理机(SMP)、大规模并行处理机(MPP)、工作站机群(COW)、分布式共享存储处理机(DSM)。

访存模型

并行计算机有以下五种访存模型:均匀访存模型(UMA)、非均匀访存模型(NUMA)、全高速缓存访存模型(COMA)、一致性高速缓存非均匀存储访问模型(CC-NUMA)和非远程存储访问模型(NORMA)。

计算模型

不像串行计算机那样,全世界基本上都在使用冯·诺伊曼的计算模型;并行计算机没有一个统一的计算模型。不过,人们已经提出了几种有价值的参考模型:PRAM 模型,BSP 模型,LogP 模型,C^3 模型等。

研究内容

(1)并行计算模型 并行算法作为一门学科,首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁,是并行算法设计和分析的基础。它屏蔽了并行机之间的差异,从并行机中抽取若干个能反映计算特性的可计算或可测量的参数,并按照模型所定义的计算行为构造成本函数,以此进行算法的复杂度分析。

并行计算模型的第一代是共享存储模型,如 SIMD-SM 和 MIMD-SM 的一些计算模型,模型参数主要是 CPU 的单位计算时间,这样科学家可以忽略一些细节,集中精力设计算法。第二代是分布存储模型。在这个阶段,人们逐渐意识到对并行计算机性能带来影响的不仅仅是 CPU,还有通信。因此如何把不同的通信性能抽象成模型参数,是这个阶段的研究重点。第三代是分布共享存储模型,也是我们目前研究所处的阶段。随着网络技术的发展,通信延迟固然还有影响,但对并行带来的影响不再像当年那样重要,注重计算系统的多层次存储特性的影响。

(2)设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟,但并行算法的设计依然是有章可循的,例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。

(3)并行算法分为多机并行和多线程并行。多机并行,如 MPI 技术;多线程并行,如 OpenMP 技术。

以上是并行算法的常规研究内容。

收藏 0个人收藏
走进科技生活方式

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • Windows Linux

    计算机系统是什么

    计算机系统由计算机硬件和软件两部分组成。硬件包括中央处理机、存储器和外部设备等;软件是计算机的运行程序和相应的文档。计算机系统具有接收和存储信息、按程序快速计算和判断并输出处理结果等功能。常见的系统有Windows,Linux等。
  • Face recognition 人脸识别

    人脸识别三大经典算法是什么

    人脸识别三大经典算法是特征脸法,近期发展起来的用于人脸或者一般性刚体识别以及其它涉及到人脸处理的一种方法;以及局部二值模式,是计算机视觉领域里用于分类的视觉算子;还有Fisherface算法,线性鉴别分析在降维的同时考虑类别信息。
  • 搜索算法 search algorithm

    搜索算法是什么

    搜索算法是解决搜索问题的任何算法,即检索存储在某个数据结构中的信息,或者在问题域的搜索空间中计算的信息。这种结构的例子包括但不限于链表,数组数据结构或搜索树。合适的搜索算法通常取决于正在搜索的数据结构,并且还可能包括有关数据的先前知识。
  • sort 排序

    排序算法稳定性是指什么

    排序算法稳定性指假定在待排序的记录序列中,存在多个具有相同的关键字的记录,经过排序这些记录的相对次序保持不变,则是稳定的;否则为不稳定。不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。
  • 确定性算法是什么

    确定性算法是什么

    确定性算法是利用问题的解析性质,产生一确定的有限或无限点序列使其收敛于全局最优解。这类方法依据某一确定性策略搜索局部极小,并试图跳跃已获得的局部极小而达到某个全局最优点,能充分利用问题的解析性质,从而计算效率高。
  • 最陡下降算法是什么

    最陡下降算法是什么

    最陡下降法又称梯度下降法是一个一阶最优化算法。要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。