并行算法复习

《并行算法复习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1•并行算法:一些可同时执行的诸进程的集合，这些进程相互作用和相互协调。2•并行与并发的关系：并行v并发并发是指两个或者多个事件在同一时间间隔内发生。在单处理机系统中，每一时刻仅能有一道程序执行，宏观上多道程序在同时运行，微观上这些程序是分时交替执行。3•并行与分布式的关系：网络；并行更注重性能，而分布式更注重透明共享。4•并行与网格计算（普适计算）的关系：网格通过网络连接地理上分布的各类计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚拟的高性能计算环境，让人们透明地使用这

2、些资源和功能。它们•并行计算存在规模上的差显。5•并行与云计算的关系：云计算以开放的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务，让互联网这片“云”上的各种计算机共同组成数个庞大的数据中心及计算屮心。云计算把计算及存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、应用软件、开发平台等资源都來自互联网上的虚拟化计算中心，该数据中心负责対分布在互联网上的各种资源进行分配、负载的均衡、软件的部署、安全的控制等。6•为什么要研究并行算法？（1）CPU的发展速度：MooreL

3、aw0（2）“深蓝”计算机以3.5:2.5战胜卡斯帕罗夫。（3）需求：快速（天气预报），提高计算精度，与理论、实验并重的科学方法（代替核武器实验）7•并行计算机分类1.SISD,SingleInstructionStream&SingleDataStream:特征：串行的和确定的。指令系统:CISC,RISC2.SIMD,SingleInstructionStream&MultipleDataStream:特征：同步的；确定的；适合于指令/操作级并行。1）阵列处理机（资源重复）；2）流水线处理机（时间重叠）.

4、3・MISD,MultipleInstructionStream&SingleDataStream:4.MIMD,MultipleInstructionStream&MultipleDataStream共享存储MIMD,也称对称多处理机（SMP,SymmetryMultiProcessors）,属于紧密耦合的多处理机系统适合于小粒度并行分布式共享存储MIMD,也称为非一致内存访问（NUMA,Non-UniformMemoryAccess），属于松耦合的多处理机系统（共享虚拟存储技术），适合于屮小粒度并行分布式

5、存储MIMD1）.大规模并行系统MPP（MassivelyParallelProcessing）CM・5、曙光1000、神州・II巨型机可以最大限度地增加处理机的数量，但结点间需要依赖消息传递进行通信，适合于中小粒度并行2)・群集系统Cluster特点：适合于粗粒度并行8•网络直径(networkdiameter)：网络中最远的两台处理机间的距离，即处理机间通信所需要跨越的网络边的条数的最人值。9•等分宽度(bisectionwidth):网络分成两个相等部分(节点数相等或至多差1)所需要去掉的网络边的条数。

6、1()•并行计算机的处理机互连方式网络直径等分宽度网络接口总线结构一维阵列结构n-112网格结构2n-2n4超立方体结构(q维)qq叠网结构2q2q2丫】(q+1)行，每行冇2Q个节点11•并行计算模型，并行算法设计，并行计算机之间的关系如图。12•并行计算模型的作用：(1)为并行算法的研究提供了一个基础。(2)为并行算法的设计与分析提供了一种简单、方便的框架，避开了硬件上许多繁琐的细节。(3)便得设计的并行算法具有一定的生命力，可以适用于多种具体的并行计算机。13.LogP模型：面向分布式存储，点对点通信的

7、多计算机系统的并行计算模型。参数说明：(1)L(Latency)：源处理机为Fl标处理机Z间进行消息通信所需等待延迟吋间的上限。(2)o(overhead)：处理机用于发送或接收每个消息的时间开销。(3)g(g叩)：一台处理机进行连续发送或接收消息的最小时间间隔。(4)P(Processor)：处理机数量。特点：(1)只支持P2P通信，不关心拓扑结构(2)消息的传输吋间2o+L(3)只支持短消息(4)LogGP支持长消息通信：tu+n*t0心消息发送的启动时间，*是传输单位字节消息传递时间14•并行算法的目标

8、:山串行的“深而窄”变为“浅而深”15•并行算法的分类1・流水线技术基本思想是把一个计算任务t,分成一系列子任务，使得一旦前一子任务完成F—个子任务就可以立即开始。eg：冇多个实例需要执行冇一系列数据需要处理，并且每个数据需要多次进行操作一个进程在执行完Z前，能够传递执行下一个进程的消息2.分治策略：分而治之的原则是把一个问题分裂为若干个较小的了问题,这些问题可彼此独立地并行求解。它是设计并行算法的