并行算法复习.doc

1.并行算法:一些可同时执行的诸进程的集合，这些进程相互作用和相互协调。2.并行与并发的关系：并行并发并发是指两个或者多个事件在同一时间间隔内发生。在单处理机系统中，每一时刻仅能有一道程序执行，宏观上多道程序在同时运行，微观上这些程序是分时交替执行。3.并行与分布式的关系：网络；并行更注重性能，而分布式更注重透明共享。 4.并行与网格计算（普适计算）的关系：网格通过网络连接地理上分布的各类计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚拟的高性能计算环境，让人们透明地使用这些资源和功能。它们与并行计算存在规模上的差异。5.并行与云计算的关系： 云计算以开放的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务，让互联网这片“云”上的各种计算机共同组成数个庞大的数据中心及计算中心。云计算把计算及存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、应用软件、开发平台等资源都来自互联网上的虚拟化计算中心，该数据中心负责对分布在互联网上的各种资源进行分配、负载的均衡、软件的部署、安全的控制等。6.为什么要研究并行算法？（1）CPU的发展速度：Moore Law。（2）“深蓝”计算机以3.5:2.5战胜卡斯帕罗夫。（3）需求：快速（天气预报），提高计算精度，与理论、实验并重的科学方法（代替核武器实验）7.并行计算机分类1. SISD,Single Instruction Stream & Single Data Stream:特征：串行的和确定的。 指令系统: CISC, RISC 2. SIMD,Single Instruction Stream & Multiple Data Stream:特征：同步的；确定的；适合于指令/操作级并行。 1)阵列处理机（资源重复）;2)流水线处理机（时间重叠）.3. MISD,Multiple Instruction Stream & Single Data Stream :4. MIMD,Multiple Instruction Stream & Multiple Data Stream共享存储MIMD，也称对称多处理机（SMP，Symmetry MultiProcessors），属于紧密耦合的多处理机系统 适合于小粒度并行分布式共享存储MIMD，也称为非一致内存访问（NUMA, Non-Uniform Memory Access），属于松耦合的多处理机系统（共享虚拟存储技术）,适合于中小粒度并行分布式存储MIMD 1). 大规模并行系统MPP (Massively Parallel Processing)CM-5、曙光1000、神州-巨型机可以最大限度地增加处理机的数量，但结点间需要依赖消息传递进行通信，适合于中小粒度并行2).群集系统Cluster特点：适合于粗粒度并行8.网络直径（network diameter）：网络中最远的两台处理机间的距离，即处理机间通信所需要跨越的网络边的条数的最大值。9.等分宽度（bisection width）：网络分成两个相等部分（节点数相等或至多差1）所需要去掉的网络边的条数。10.并行计算机的处理机互连方式网络直径等分宽度网络接口总线结构一维阵列结构n-112网格结构2n-2n4超立方体结构(q维)q2q-1q叠网结构2q2q2q-1(q+1)行，每行有2q个节点11.并行计算模型，并行算法设计，并行计算机之间的关系如图。表明，并行算法设计可以从两个方面进行（1）根据并行计算模型设计并行算法，然后将其映射到具体的并行计算机中（2）直接基于具体并行计算机进行并行算法的设计与分析12.并行计算模型的作用：（1）为并行算法的研究提供了一个基础。（2）为并行算法的设计与分析提供了一种简单、方便的框架，避开了硬件上许多繁琐的细节。（3）使得设计的并行算法具有一定的生命力，可以适用于多种具体的并行计算机。13.LogP模型：面向分布式存储，点对点通信的多计算机系统的并行计算模型。参数说明：（1）L（Latency）：源处理机与目标处理机之间进行消息通信所需等待延迟时间的上限。（2）o（overhead）：处理机用于发送或接收每个消息的时间开销。（3）g（gap）：一台处理机进行连续发送或接收消息的最小时间间隔。（4）P（Processor）：处理机数量。特点：（1）只支持P2P通信，不关心拓扑结构（2）消息的传输时间 2o+L（3）只支持短消息（4）LogGP支持长消息通信：t+n*t t消息发送的启动时间，t是传输单位字节消息传递时间14.并行算法的目标:由串行的“深而窄”变为“浅而深”15.并行算法的分类1. 流水线技术基本思想是把一个计算任务t，分成一系列子任务，使得一旦前一子任务完成下一个子任务就可以立即开始。eg:有多个实例需要执行 有一系列数据需要处理， 并且每个数据需要多次进行操作 一个进程在执行完之前， 能够传递执行下一个进程的消息2. 分治策略：分而治之的原则是把一个问题分裂为若干个较小的子问题，这些问题可彼此独立地并行求解。 它是设计并行算法的根本准则 。数据分割：数据分割是指各结点基本执行相同的任务，只是数据不同。此方法常用在计算的各数据之间具有对称性的情况。例如对于向量的加法，可以分割为各个分量的加法。任务分割：任务分割是指总任务由自然的数个子任务组成，将其分摊在各个结点上。例如对于连续的数据处理任务，可以将其分割成数据采集、数据计算和结果输出三个子任务。3.平衡树方法将输入元素作为叶节点构筑一棵平衡二叉树，然后自叶向根往返遍历。假定有n=2m个数，可以用n/2台处理机在O（logn）并行步内解出最大值。4.倍增技术（指针跳跃技术）每当递归调用时，所要处理的数据之间的距离将逐步加倍，经过步k后就可完成距离为2k的所有数据的计算。对于一阶线性递归关系式，我们有 一般情况下，使用n台处理机，计算n个元素值xi（i=1,2，n），需要步计算。5. 加速级联策略为了获得一个快速最优的算法，我们可以将一个最优但相对不快的算法与另一个非常快但不是最优的算法级联（或串联）起来，形成一个加速级联算法 。复杂度运算量对数深度树O（logn）O（n）双对数深度树O（loglogn）O(nloglogn)先运行对数深度树（平衡二叉树），从叶节点向上直到层，复杂度O（loglogn），运算量O（logn）再运行双对数深度树，复杂度O（loglogn），运算量O（n）16.并行算法性能度量 1. 运行时间：从最早开始执行的处理机开始执行算起到最后一台处理机执行完所经过的时间，包括计算时间+通信时间2. 并行度（DOP）：可并行执行的操作数并行度与任务粒度的关系：大则小，小则大3.加速比和效率： T1是指最优串行算法在单处理机上的运行时间；Tp是指并行算法在p台处理机上的运行时间；4. 并行加速比模型 1. Amdahl加速比模型 ：2. Gustafson加速比模型：17.矩阵乘法并行计算（1）静态调度优点：任务分配简单，网络开销小缺点：负载不平衡（2）动态调度特点：每个处理机承担的计算任务是与其计算能力相关联的优点：负载均衡缺点：通信开销较大（3）动静相结合的调度算法特点：兼顾了负载平衡和通信开销设：t消息发送的启动时间，t是传输单位字节消息传递时间运行时间的计算静：4（t+100*100000*t）*2+4*( t+100000*100000*t) 剩余L=100000-4*100=99600动：( t+10*100000*t)*2*99600（4）改进的动静相结合调度 执行单位任务的时间 l,klA.静态调度阶段B.动态调度阶段Eg：n=100000，p=4，k=3，则（p-1）k+1=10A. 每个节点分配100000/10=10000个任务，剩余l=100000-4*10000=60000B. 每个节点分配l/10个任务l-1/10=0.9l0.9l-0.9l/10=0.92l 0.9ml令0.9ml10， 即0.9m1/6000 得到m约为83这时，每次分配1个任务动态调度次数： 83+10=93次开销=（静）4（t+10000*100000*t）*2+（t+100000*100000*t）+(动) （93t+60000*100000*t）*2进一步提高可以采用计算与通信相结合的方式。18.QR分解并行算法(1)标准算法的数对分割方法 Sr（r=1,2,.2n-3）的元素个数依次为 1,1,2,2，n/2-1,n/2-1,n/2,n/2-1,n/2-1,.2,2,1,1 (2)贪婪算法的数对分割算法Givens约化中为消去第（p,q）个元素，不一定必须将变换作用于第p-1、p行，可以作用域任意第k行和p行（kp），只要将第k行上所有第（k，j）（1jq）个元素为0.(3) 网络环境(群集系统)下Givens约化的并行算法设计n(n-1)/2 K2个三角阵，每个三角阵对应于一个子任务各子任务之间及其内部元素之间的Givens变换应满足下列要求：（1） 对于子任务T（j mod 2=1），只有当T已执行完毕后，它才可以执行。（2）对于子任务T（j mod 2=1），只有