平行算法

平行算法（Parallel algorithm），又称并行算法，是一种算法。平行算法又称为盒式决策规则，是在并行计算机上的一种算法，是根据训练样本的亮度值范围形成一个多维数据空间。其他像元的光谱值如果落在训练样本的亮度值所对应的区域，就被划分到其对应的类别中。例如用来解流体流动可以分区、分块，随机地选取某流动区域在多台计算机上同时进行。计算中间的误差控制，信息交换，可以通过一定的算法控制进行。

简介

平行算法一般是指许多指令得以同时进行的计算模式。在同时进行的前提下，可以将计算的过程分解成小部分，之后以并发方式来加以解决，或指用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。由于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性，同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。并行算法的研究历史可简单归纳为：上世纪70到80年代，并行算法研究处于高潮；到上世纪90年代跌入低谷；又处于研究的热点阶段。人们已经可以自己搭建PC cluster，利用学习到的理论知识来解决实际问题，不再是纸上谈兵，这也为我们提供了新的机遇和挑战。20世纪60年代开始发展含大量处理机的并行计算机，它分单指令流多数据流与多指令流多数据流两类，每一时刻分别按一条或多条指令处理多个数据。并行计算机的出现促使了适应其并行这个特点的并行算法的发展。随着时代的进步，我们需要不断调整研究方向。并行算法研究的新走向是：并行算法研究内容不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模式，如神经计算、量子计算等，这些模式能够解决某类特定问题，有其自身的优越性。

研究内容

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

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

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

（3）并行算法分为多机并行和多线程并行。多机并行，如MPI技术；多线程并行，如OpenMP技术。

并行机与多处理机

并行机

并行机就其控制方式分为单指令多数据(Single-Instruction-Multiple-Data缩写为SIMD)和多指令多数据(MIMD)两大类，每一时刻分别按一条和多条指令处理多个数据;就主存储器设置方式又可分为共享存储器型和分布存储器型两大类，共享型集中设置存储器为各处理机公用，分布型则将存储器附设于各处理机.迄今，大多并行机是MIMD机，它们有单程序多数据(Single-Program-Multiple-Data缩写为SPMD)和多程序多数据(MPMD)两种计算模式，各处理机分别执行同一和不同程序处理各自的数据集.针对不同类型及计算模式的并行机需设计不同类型的算法，好的算法应考虑到并行机的处理机之间的通信方式与能力这一影响效率的重要因素。

并行算法可以分成三大类：SIMD算法。同步MIMD算法，同步指算法中有些进程的某些步骤必须在完成其他进程的一些步骤之后方可执行。异步算法，其各进程之间不需同步，基本上是混乱迭代法.问题是算法怎样设计与分析。并行计算依赖于一个简单事实：独立的计算可以同时执行，所谓独立计算是指其每个结果元只出现一次的计算.由此产生“分而治之”和“重新排序”两种非常基本的并行算法设计思想。

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

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

多处理机

多处理机（Multi processor）是具有多个处理机的计算机，能够大大提高计算机的处理速度。

共享存储器结构:多个处理单元通过网络（内部连接）共享集中的主存储器，主存储器由多个并行的存储体组成，而每个CU都有自己的控制单元（这是与并行处理机的不同点）。系统资源易管理、利用，程序员易编程；但是处理机数目少，不易扩充。

分布式存储多处理机：每个处理机都有自己的控制器、自己的存储单元，CU及存储器等构成多个较为独立的部分，各个部分通过网络（内部连接）协调工作。其特点是结构灵活、易扩充，但是，任务传输以及任务分配算法复杂，通常要设计专有算法。

使用多台计算机协同工作来完成所要求的任务的计算机系统都是多处理机系统。传统的狭义多处理机系统是指利用系统内的多个CPU并行执行用户多个程序，以提高系统的吞吐量或用来进行冗余操作以提高系统的可靠性。

全国各地天气预报查询

上海市

市辖区

云南省

临沧市