并行计算的基本概念.doc

并行计算的基本概念转贴 2008-02-25 09:57:261、 并行计算：并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统，它是将多个处理器通过网络连接以一定的方式有序地组织起来。2、 指令流：机器执行的指令序列；3、 数据流：由指令流调用的数据序列，包括输入数据和中间结果。4、 SIMD计算机：有一个控制部件和许多处理单元,所有的处理单元在控制部件的统一控制下工作。控制部件向所有的处理单元广播同一条指令，所有的处理单元同时执行这条指令，但是每个处理单元操作的数据不同。5、 MIMD计算机 没有统一的控制部件，含有多个处理器，各处理器可以独立地执行不同的指令，每个处理器都有控制部件，各处理器通过互连网络进行通信。6、 并行向量处理机（PVP） 在并行向量处理机中有少量专门定制的向量处理器。每个向量处理器有很高的处理能力。并行向量处理机通过向量处理和多个向量处理器并行处理两条途径来提高处理能力。7、 大规模并行处理机（MPP） 大规模并行处理机一般指规模非常大的并行计算机系统，含有成千上万个处理器。它一般采用分布的存储器，存储器一般为处理器私有，各处理器之间用消息传递的方式通信。大规模并行处理机的互连网络一般是专门设计定制的。8、 分布式共享存储器多处理机（DSM） 分布式共享存储器多处理机的主要特点是它的存储器在物理上是分布在各个结点中的，但是通过硬件和软件为用户提供一个单一地址的编程空间，即形成一个虚拟的共享存储器。它通过高速缓存目录支持分布高速缓存的一致性。9、 机群(COW或NOW) 是由高档商品微机（包括工作站）用高速商品互连网络（有的商用机群也使用定制的网络）连接而成，每个结点都是一台完整的计算机（可能没有鼠标、显示器等外设）。10、 对称多处理机（SMP） 对称多处理机的最大特点是其中的各处理器完全平等，无主从之分。所有的处理器都可以访问任何存储单元和I/O设备。存储器一般使用共享存储器，只有一个地址空间。因为使用共享存储器，通信可用共享变量（读写同一内存单元）来实现。11、 UMA UMA是Uniform Memory Access（均匀存储访问）模型的缩写。在这种并行机中所有的处理器均匀共享物理存储器。所有处理器访问任何存储字需要相同的时间（此即为均匀存储访问名称的来源）。每台处理器可以有私有高速缓存。UMA结构适用于通用或分时应用。12、 NUMA NUMA是Nonuniform Memory Access（非均匀存储访问）模型的缩写。在NUMA中，共享存储器在物理上是分布的，所有的本地存储器构成了全局地址空间。NUMA与UMA的区别在于处理器访问本地存储器和群内共享存储器比访问远程存储器或全局共享存储器快。13、 COMA COMA是Cache-Only Memory Architecture（全高速缓存存储结构）模型的缩写。COMA实际是NUMA的一种特例，将NUMA中的分布存储器换成高速缓存就得到了COMA。在COMA中，每个结点上没有存储层次结构，所有的高速缓存构成了全局地址空间。访问远程高速缓存要借助分布的高速缓存目录。14、 CC-NUMA CC-NUMA是Cache-Coherent Nonuniform Memory Access（高速缓存一致性非均匀存储访问）模型的缩写。CC-NUMA结构的并行机实际上是将一些SMP机作为结点互连起来而构成的并行机，绝大多数商用CC-NUMA多处理机系统使用基于目录的高速缓存一致性协议；它的存储器在物理上是分布的，所有的局部存储器构成了共享的全局地址空间。15、 NORMA NORMA是No-Remote Memory Access（非远程存储访问）模型的缩写。在NORMA中，所有的存储器都是处理器私有的，仅能由其处理器访问。各处理器之间通过消息传递方式通信。16、 静态网络（Static Networks） 静态网络是指结点间有着固定连接通路且在程序执行期间，这种连接保持不变的网络17、 动态网络（Dynamic Networks） 动态网络是用开关单元构成的，可按应用程序的要求动态地改变连接状态的网络18、 互连函数 为了反映不同互连网络的连接特性，每种互连网络可以用一组互连函数来描述。用整数 分别表示互连网络的 个输入端和 个输出端。记互连函数为 ，它表示输入端 与输出端 相连。19、 总线 总线（Bus）实际上是连接处理器、存储器和I/O等外围设备的一组导线和插座。总线的一个特点是：它在某一时刻只能用于一对源和目的之间传输数据。当有多对源和目的请求使用总线时，必须由总线仲裁逻辑进行总线仲裁，即确定先为哪一对源和目的服务。20、 交叉开关 交叉开关（Crossbar Switcher）是一种高带宽网络，它可以在输入端和输出端之间建立动态连接，在每个输入端和输入端的交叉点上都有交叉点开关。该开关可以根据需要置为“开”或“关”状态，从而使不同的输入端和输出端导通。 交叉开关允许 对源和目的同时用互不重叠的通道进行通信，也允许一个输入端向多个输出端同时发送信息。在并行系统中，交叉开关可以用来连接处理器和处理器，也可以用来连接处理器和存储器。21、 多级互连网络 为了构造大型网络，可以把交叉开关级联起来，构成多级互连网络（Multistage Interconnection Network, MIN）22、 消息（Message） 是结点间通信的逻辑单位。它由任意数目的长度固定的包组成。23、 包（Packet） 是包含寻径目的地址的基本单位。包的长度由使用的协议决定。由于不同的包可能异步地到达目的结点，因此属于一个消息的每个包需要一个唯一的序号，以便在目的结点可以将包按照正确的顺序重新装配起来。24、 片（flit） 将包分成一些固定长度的片（flit），寻径信息和序号形成头片，其余的片是数据片。25、 网络寻径算法 决定消息从源结点到目的结点的路径的算法称为网络寻径算法。26、 存储转发（Store-and-Forward） 为一种寻径方式，在这种方式下，消息被分成包来传送，包是信息传输的基本单位。包从源结点通过一系列中间结点到达目的结点，每个结点有一个包缓冲区。当包到达一个中间结点A时，A把整个包全部接收下来放入其包缓冲区中，然后在寻径算法的控制下选择下一个中间结点B，当从A到B的通道空闲并且B的包缓冲区可用时，A把包发向B。不断地存储和转发，包就可以到达目的结点。所有的包到达目的结点后，目的结点再把包组装成原来的消息。27、 虫蚀寻径（Wormhole） 是寻径的一种方式。包被分成更小的片进行传输，头片包含了这个包的所有寻径信息，其它片是数据片。与结点相连的硬件寻径器中有片缓冲区。同一个包中所有的片像不可分离的同伴一样以流水方式顺序地传送。28、 单播（unicast） 一对一的通信模式，一个源结点发送消息到一个目的结点种通信。29、 选播（multicast） 一到多的通信模式，一个源结点发送同一个消息到多个目的结点30、 广播（broadcast） 一到全体的通信模式，一个源结点发送同一个消息到全部结点31、 会议（conference） 即多对多的通信模式。32、 数据并行性 是并行性的一种表现行为，并行在不同的数据上进行相同的操作。33、 任务并行性 将任务分解成一些子任务，只要所有必需的子任务已经完成，后续子任务就可以进行，很多的子任务都可以并行的执行。这种并行性表现为子任务的并行执行。34、 流水并行性 是指在同一个数据流上同时的执行多个程序（后续的程序处理的是前面程序处理过的数据流）35、 递归分解 通常用来对采用Divide-and-conquer(分治)方法的问题进行任务分解。这种方法将任务分解为独立的子任务，这个分解的过程会递归的进行。问题的答案是所有的子任务的答案的组合。36、 静态负载平衡技术 在算法的实际执行前将计算任务分配给处理器；37、 动态负载平衡 在算法的实际执行过程中将计算任务分配给处理器38、 PCAM PCAM是Partitioning（划分）、Communication（通信）、Agglomeration（组合）和Mapping（映射）的缩写，它们表示了使用此法设计并行算法的四个阶段：任务划分、通信分析、任务组合和处理器映射，简称划分、通信、组合、映射。39、 并行计算模型 通常指从并行算法的设计和分析出发，将各种并行计算机（至少某一类并行计算机）的基本特征抽象出来，形成一个抽象的计算模型。算法（Algorithm）是解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定问题的一系列运算。41、 并行算法（Parallel Algorithm） 是一些可同时执行的多个进程的集合，这些进程相互作用和协调工作，从而达到对给定问题的求解。42、 数值计算（Numerical Computing） 是指基于代数关系运算的一类诸如矩阵计算、多项式求值、求解线性方程组等数字计算问题。求解数值计算问题的算法称为数值算法（Numerical Algorithm）。43、 非数值计算（Non-numerical Computing） 是指基于比较关系运算的一类计算问题，比如排序、选择、搜索和匹配等符号处理问题。求解非数值计算问题的算法称为非数值算法（Non-numerical Algorithm）。44、 同步算法(Synchronized Algorithm) 是指算法的各个进程的执行必须相互等待的一类算法。45、 异步算法（Asynchronized Algorithm） 是指算法的各个进程的执行不必相互等待的一类算法。46、 分布算法（Distributed Algorithm） 是指由通信链路连接的多个节点协同完成问题求解的一类算法。47、 确定性算法(Deterministic Algorithm) 是指算法的每一步都能明确的指明下一步的动作的一类算法。48、 随机算法（Randomized Algorithm） 是指算法的每一步都随机的从指定范围内选取若干参数，由此确定算法的下一动作的一类算法。49、 同步（Synchronization） 是在时间上强制使一组执行中的进程在某一点相互等待。在并行算法的各进程异步执行过程中，为了确保各处理器的正确工作顺序以及对共享资源的正确访问（资源的互斥访问），程序员需要在算法中恰当的位置设置同步点。同步可以用软件、硬件或固件的方法来实现。50、 通信（Communication） 是多个并发执行的进程在空间上进行数据交换。51、 PRAM（Parallel Random Access Machine，随机存取并行机器）模型 也称为共享存储的SIMD模型，是一种抽象的并行计算模型。在这种模型中，假定存在一个容量无限大的共享存储器，有有限个或无限个功能相同的处理器，且他们都具有简单的算术运算和逻辑判断功能，在任何时刻个处理器都可以通过共享存储单元相互交互数据。52、 APRAM模型，分相（Phase） PRAM模型是一个APRAM（Asynchronous Parallel Random Access Machine，异步随机存取并行机器）模型。它由p个处理器组成，特点是每个处理器都有自己的局部存储器、局部时钟和局部程序，处理器之间的通信通过全局共享存储器进行。每个全局时钟，所以各处理器异步的独立执行各自的程序，处理器之间任何时间上的依赖关系（执行次序）需要明确的在各处理器的程序中加入同步障碍语句（Synchronization Barrier）来实现，一条指令可以在非确定（无界）但有限的时间内完成。53、 BSP模型 为一“大”同步分布存储的MIMD计算模型，它通过处理器/存储器模块数p、处理器/存储器模块之间点对点传递消息的路由器器吞吐率g（也称为带宽因子）、全局同步之间的时间间隔L表示54、 LogP模型 是一种分布存储的、点到点通信的多处理机模型，其中通信网络由4个主要参数来描述：L(Latency) 表示源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限；o(overhead)表示处理机准备发送或接收每个消息的时间开销；g(gap)表示一台处理机连续两次发送或接收消息时的最小时间间隔；P(Processor)处理机/存储器模块个数55、 C3(Computation, Communication, Congestion)模型，它是一种与体系结构无关的粗粒度的并行计算模型，以的并行集群系统为目标，旨在反映计算复杂度、通信模式和资源（信道）冲突对粗粒度网络并行算法的影响。模型的5个参数分别为处理器个数p、网络延迟h、网络的对分宽度b、建立一个消息时的开销的启动时间s、消息包的长度L56、 BDM模型，是一种块分布存储模型(BDM, Block Distributed Model)。它是共享存储编程模式与基于消息传递的分布存储系统之间的桥梁模型。主要的4个参数为：处理器个数p；处理机从发出访问请求到得到远程数据的最大延迟时间、局部存储器中连续的M个字；处理机发送数据到网络或从网络接收数据的时间57、 程序运行时间，一个程序的串行运行时间是程序在一个串行计算机上开始执行到执行完成之间所经过的时间段的长度。而并行运行时间则定义为并行计算开始到最后一个处理器完成它的计算任务之间的时间段的长度58、 加速比，是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或者串行程序）的执行速度加快了多少倍。59、 效率被用来衡量一个处理器的计算能力被有效利用的比率，由加速比与处理器的比值表示。60、 开销定义为一个并行系统在解一个问题的时候，并行运行时间与所用的处理器的乘积。61、 任务粒度，并行子任务的大小一种度量62、 一个并行系统的额外开销函数，指并行开销和解相同问题的已知的最快的串行算法的运行时间的差63、 可扩展性，最直接的含义是在确定的应用背景下，计算机系统（算法或者程序设计等）的性能随着处理器数目得增加而成比例的增高的能力64、 并行计算的速度，为问题规模与并行运行时间的比值65、 条带状划分就是把矩阵按照行或列分成几部