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