1、并行算法1 / Ch12022-6-22Parallel Algorithms Chapter 1 Foundation of Parallel AlgorithmsSpring, 2018并行算法2 / Ch12022-6-22主要内容主要内容n1.1 并行计算机体系结构并行计算机体系结构并行计算机的分类并行计算机的分类并行计算机的互连方式并行计算机的互连方式n1.2 并行计算模型并行计算模型 PRAM模型模型异步异步APRAM模型模型BSP模型模型LogP模型模型n1.3 并行算法的一般概念并行算法的一般概念并行算法的定义和分类并行算法的定义和分类相关性与可并行化相关性与可并行化并行算法的
2、表示并行算法的表示并行算法的复杂度并行算法的复杂度并行算法的并行算法的WT表示表示加速比性能定律加速比性能定律并行算法的同步和通讯并行算法的同步和通讯并行算法3 / Ch12022-6-221.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类nFlynn分类（分类（1966年）年） (1)单指令流单数据流机单指令流单数据流机SISD，即传统的单处理机，即传统的单处理机 (2)单指令流多数据流机单指令流多数据流机SIMD (3)多指令流单数据流机多指令流单数据流机MISD，实际中不存在的机器，实际中不存在的机器 (4)多指令流多数据流机多指令流多数据流机MIMDn并行
3、机的结构模型并行机的结构模型实际的机器体系结构 SIMD (Single Instruction Multiple Data, 单指令流多数据流机) PVP (Parallel Vector Processor, 并行向量机) SMP (Symmetric Multiprocessor, 对称多处理机) MPP (Massively Parallel Processor, 大规模并行处理机) COW (Cluster of Workstation, 工作站机群) DSM (Distributed Shared Memory, 分布共享存储多处理机) 注：SIMD是专用并行机，后5种属于MIMD
4、并行机。并行算法4 / Ch12022-6-22SISD computer -Von Neumanns model1.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类SIMD computer并行算法5 / Ch12022-6-22Symmetric multiprocessor MIMD-SM1.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类Massively parallel processor MIMD-DM并行算法6 / Ch12022-6-22Cluster of workstations MIMD-DM1.1 并行计算机的体
5、系结构并行计算机的体系结构: 并行计算机分类并行计算机分类并行算法7 / Ch12022-6-22VPVPVP交叉开关交叉开关SM(a) PVPP/CP/CP/C总线或交叉开关总线或交叉开关SM(b) SMP, 物理上单一地址空间物理上单一地址空间P/CP/CP/C定制网络定制网络LMLMLM(c) MPP, 物理物理/逻辑上多地址空间逻辑上多地址空间P/CP/CP/C定制网络定制网络LMLMLM虚拟分布共享存储虚拟分布共享存储(DSM) (d) DSM (MPP/Cluster),逻辑上单一地址空间逻辑上单一地址空间结构模型物理机模型P/CP/CP/C定制定制/标准网络标准网络LMLMLM(
6、e) Cluster/COW, 物理物理/逻辑上多地址空间逻辑上多地址空间1.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类并行算法8 / Ch12022-6-22SMPMPPMPPWANLMDSMSM(h) Grid (Cluster of Clusters)SMPSMPSMPSAN/LANSMSMSMMPPMPPMPPSAN/LANDSMDSMDSM(f) SMP-Cluster(g) DSM-Cluster结构模型物理机模型1.1 并行计算机的体系结构并行计算机的体系结构: 并行计算机分类并行计算机分类并行算法9 / Ch12022-6-221.1 并行计算
7、机的体系结构并行计算机的体系结构: 互连方式互连方式n静态互连网络静态互连网络(固定连接固定连接) connected graph vertices = processing nodes edges = communication links(1)一维线性连接LA(1-D Linear Array)一维阵列 不带环绕的1-D LA，带环绕的1-D LA(2)网孔连接MC (Mesh Connected)二维阵列 不带环绕的MC，带环绕的MC并行算法10 / Ch12022-6-221.1 并行计算机的体系结构并行计算机的体系结构: 互连方式互连方式n静态互连网络静态互连网络 (3)树形连接TC
8、(Tree Connected) 二叉树， 胖树并行算法11 / Ch12022-6-221.1 并行计算机的体系结构并行计算机的体系结构: 互连方式互连方式n静态互连网络静态互连网络 (4)树网连接MT(Mesh of tree) 并行算法12 / Ch12022-6-221.1 并行计算机的体系结构并行计算机的体系结构: 互连方式互连方式n静态互连网络静态互连网络(5)金字塔连接(Pyramid)(6)超立方连接HC (Hypercube Connected) 3立方， 4立方(7)立方环连接CCC (Cube Connected-Cycles)(8)洗牌交换连接SE(Shuffle Ex
9、change)(9)蝶形连接(Butterfly Connected)并行算法13 / Ch12022-6-221.1 并行计算机的体系结构并行计算机的体系结构: 互连方式互连方式n静态互连网络静态互连网络: 嵌入嵌入将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中并行算法14 / Ch12022-6-221.1 并行计算机的体系结构并行计算机的体系结构: 互连方式互连方式n静态互连网络静态互连
10、网络: 嵌入嵌入0 01 10 01 10 01 10 00 00 00 00 00 00 00 00 01 10 01 11 11 10 01 11 10 00 00 01 10 00 00 01 11 11 11 10 01 11 11 10 00 01 10 00 00 01 10 00 01 11 11 11 11 11 11 11 10 01 10 01 10 01 10 01 11 11000100110111010110011011111111001000101011101100000000100110010并行算法15 / Ch12022-6-221.1 并行计算机的体系结构并
11、行计算机的体系结构: 互连方式互连方式n动态互连网络动态互连网络(非固定连接非固定连接)(1)总线Bus(2)交叉开关Crossbar Switcher：一种高带宽网络(3)多级互连网络Multistage Interconnection Network 一种大型开关网络 并行算法16 / Ch12022-6-22主要内容主要内容n1.1 并行计算机体系结构并行计算机体系结构并行计算机的分类并行计算机的分类并行计算机的互连方式并行计算机的互连方式n1.2 并行计算模型并行计算模型 PRAM模型模型异步异步APRAM模型模型BSP模型模型LogP模型模型n1.3 并行算法的一般概念并行算法的一般
12、概念并行算法的定义和分类并行算法的定义和分类相关性与可并行化相关性与可并行化并行算法的表示并行算法的表示并行算法的复杂度并行算法的复杂度并行算法的并行算法的WT表示表示加速比性能定律加速比性能定律并行算法的同步和通讯并行算法的同步和通讯并行算法17 / Ch12022-6-221.2 并行计算模型并行计算模型: PRAM模型模型n描述描述由由FortuneFortune和和Wyllie1978Wyllie1978年提出，称为并行随机存取机器年提出，称为并行随机存取机器PRAMPRAM，又称又称SIMD-SMSIMD-SM模型。有一个集中的共享存储器和一个指令控制器模型。有一个集中的共享存储器和
13、一个指令控制器，通过，通过SMSM的的R/WR/W交换数据，隐式同步计算。交换数据，隐式同步计算。n假设假设SMSM的容量无限的容量无限有限有限/ /无限个功能相同的处理器无限个功能相同的处理器本地指令和本地指令和SMSM的的R/WR/W操作都取单位时间操作都取单位时间n结构图结构图Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory并行算法18 / Ch12022-6-221.2 并行计算模型并行计算模型: PRAM模型模型n分类分类(1)(1)PRAM-CRCWPRAM-CRCW并发读并发写并发读并发写CPRAM-CPRA
14、M-CRCW(CommonCRCW(Common PRAM-CRCW) PRAM-CRCW)：仅允许写入相同数据：仅允许写入相同数据PPRAM-PPRAM-CRCW(PriorityCRCW(Priority PRAM-CRCW) PRAM-CRCW)：仅允许优先级最高的处理器：仅允许优先级最高的处理器写入写入APRAM-APRAM-CRCW(ArbitraryCRCW(Arbitrary PRAM-CRCW) PRAM-CRCW)：允许任意处理器自由写入：允许任意处理器自由写入 (2)(2)PRAM-CREWPRAM-CREW并发读互斥写并发读互斥写 (3)(3)PRAM-EREWPRAM-
15、EREW互斥读互斥写互斥读互斥写 n计算能力比较计算能力比较PRAM-CRCWPRAM-CRCW是最强的计算模型，是最强的计算模型，PRAM-EREWPRAM-EREW可可logplogp倍模拟倍模拟PRAM-CREWPRAM-CREW和和PRAM-CRCWPRAM-CRCW。令。令TmTm是在模型是在模型M M上的运行时间，则：上的运行时间，则： 1979 1979年，年，EckstainEckstain曾经使用二叉树方法来解决冲突问题曾经使用二叉树方法来解决冲突问题 解决读冲突：只允许一个解决读冲突：只允许一个PEPE从共享存储单元取内容。从共享存储单元取内容。 解决写冲突：用树作一种竞赛
16、机构，确保仅有一个解决写冲突：用树作一种竞赛机构，确保仅有一个PEPE在写。在写。CRCWCREWEREWTTT)log()log(pTOpTOTCRCWCREWEREW并行算法19 / Ch12022-6-221.2 并行计算模型并行计算模型: PRAM模型模型n优点优点适合并行算法表示和复杂性分析，易于使用，隐藏了并适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节行机的通讯、同步等细节。n缺点缺点不适合不适合MIMDMIMD并行机，忽略了并行机，忽略了SMSM的竞争、通讯延迟等因素的竞争、通讯延迟等因素n推广推广存储竞争模型：存储竞争模型：将Memory分成一些模块，
17、每个模块一次可处理一个访问，可以在模块级处理存储器的竞争。延迟模型：延迟模型：考虑了信息的产生到能够使用之间的通信延迟 。局部局部PRAMPRAM模型：模型：考虑了存储带宽，假定每个PE均有无限局存，而访问全局存储器是十分昂贵的。 分层存储模型：分层存储模型：将存储器视为分层的存储模块，每个模块由其大小及传送时间表征。异步异步PRAMPRAM模型模型并行算法20 / Ch12022-6-221.2 并行计算模型并行计算模型: SIMD-IN模型模型n描述描述又称又称SIMD-DMSIMD-DM模型，分布式存储，处理器通过互连网络相连，用模型，分布式存储，处理器通过互连网络相连，用传递数据方式实
18、现通讯，算法时间复杂性考虑计算和选路传递数据方式实现通讯，算法时间复杂性考虑计算和选路( (时间时间) )，结构图如下：，结构图如下： n常见模型常见模型SIMD-LC SIMD-LC 一维线性连接一维线性连接SIMD-MC SIMD-MC 网孔连接网孔连接SIMD-TC SIMD-TC 树形连接树形连接SIMD-MT SIMD-MT 树网连接树网连接SIMD-HC SIMD-HC 超立方连接超立方连接SIMD-CCC SIMD-CCC 立方环连接立方环连接SIMD-SE SIMD-SE 洗牌交换连接洗牌交换连接并行算法21 / Ch12022-6-221.2 并行计算模型并行计算模型: 异步
19、异步APRAM模型模型n描述描述又称分相（又称分相（PhasePhase）PRAMPRAM或或MIMD-SMMIMD-SM。每个处理器有其局。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过器异步执行；处理器通过SMSM进行通讯；处理器间依赖关进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。系，需在并行程序中显式地加入同步路障。n指令类型指令类型( (1)1)全局读全局读 (2)(2)全局写全局写 (3)(3)局部操作局部操作 (4)(4)同步同步 并行算法22 / Ch12022-6-221.
20、2 并行计算模型并行计算模型: 异步异步APRAM模型模型n计算过程计算过程由同步障分开的全局相组成由同步障分开的全局相组成 ，*号表示局部操作。号表示局部操作。并行算法23 / Ch12022-6-221.2 并行计算模型并行计算模型: 异步异步APRAM模型模型n计算时间计算时间 设局部操作为单位时间；全局读设局部操作为单位时间；全局读/ /写平均时间为写平均时间为d d，d d随着处理器随着处理器数目的增加而增加；同步路障时间为数目的增加而增加；同步路障时间为B=B=B(pB(p) )非降函数。非降函数。 令令 为全局相内各处理器执行时间最长者，则为全局相内各处理器执行时间最长者，则AP
21、RAMAPRAM上的计算上的计算时间为时间为 n优缺点优缺点 易编程和分析算法的复杂度，其上并行算法比较有限，不适合易编程和分析算法的复杂度，其上并行算法比较有限，不适合MIMD-DMMIMD-DM模型。模型。 pht同步障次数BtTph并行算法24 / Ch12022-6-221.2 并行计算模型并行计算模型: BSP模型模型n描述描述由由Valiant(1990)提出的，提出的，“块块”同步模型，是一种异同步模型，是一种异步步MIMD-DM模型，支持消息传递系统，块内异步并模型，支持消息传递系统，块内异步并行，块间显式同步。行，块间显式同步。 n模型参数模型参数p：处理器数：处理器数(带有
22、存储器带有存储器)L：同步障时间：同步障时间(Barrier synchronization time)g：选路器吞吐率（带宽因子）发送一个消息所用的时：选路器吞吐率（带宽因子）发送一个消息所用的时间，带宽因子间，带宽因子(time steps/packet) = 1/bandwidth并行算法25 / Ch12022-6-221.2 并行计算模型并行计算模型: BSP模型模型n计算过程计算过程 由若干超级步组成，由若干超级步组成， 每个超级步计算模式为右图每个超级步计算模式为右图n优缺点优缺点 强调了计算和通讯的分离，强调了计算和通讯的分离， 提供了一个编程环境，易于提供了一个编程环境，易于
23、 程序复杂性分析。但需要显程序复杂性分析。但需要显 式同步机制，限制至多式同步机制，限制至多h h条条 消息的传递等。消息的传递等。并行算法26 / Ch12022-6-221.2 并行计算模型并行计算模型: LogP模型模型n描述描述由由Culler(1993)年提出的，是一种分布存储的、点到点年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。隐式同步。n模型参数模型参数L(Latency)：通迅延迟通迅延迟o(overhead)：通讯额外开销通讯额外开销g(gap)：g=1/bandwidth,处理器
24、可连续进行消息发送或接收的处理器可连续进行消息发送或接收的最小时间间隔最小时间间隔P：#processors注：注：L和和g反映了通讯网络的容量反映了通讯网络的容量 并行算法27 / Ch12022-6-221.2 并行计算模型并行计算模型: LogP模型模型n优缺点优缺点 捕捉了捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。算法描述、设计和分析。 nBSP vs. LogPBSPLogP
25、：BSP块同步块同步BSP子集同步子集同步BSP进程对同步进程对同步LogPBSP可以常数因子模拟可以常数因子模拟LogP，LogP可以对数因子模拟可以对数因子模拟BSPBSPLogP + Barriers OverheadBSP提供了更方便的程设环境，提供了更方便的程设环境，LogP更好地利用了机器资源更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程似乎更简单、方便和符合结构化编程 并行算法28 / Ch12022-6-221.2 并行计算模型并行计算模型: 各种计算模型比较各种计算模型比较 模型属性PRAMAPRAMBSPLogPC3体系结构SIMD-SMMIMD-SMMIMD-
26、DMMIMD-DMMIMD-DM计算模式同步异步异步异步异步同步方式自动同步路障同步路障同步隐式同步路障同步模型参数单位时间步d,读/写时间B,同步时间p,处理器数g,带宽因子l,同步间隔L,通信延迟o,额外开销g,带宽因子P,处理器数l,信包长度s,发送建立时间h,通信延迟计算粒度细粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式读/写共享变量读/写共享变量发送/接收消息发送/接收消息发送/接收消息地址空间全 局 地 址 空间单地址空间单/多地址空间单/多地址空间多地址空间并行算法29 / Ch12022-6-22主要内容主要内容n1.1 并行计算机体系结构并行计算机体系
27、结构并行计算机的分类并行计算机的分类并行计算机的互连方式并行计算机的互连方式n1.2 并行计算模型并行计算模型 PRAM模型模型异步异步APRAM模型模型BSP模型模型LogP模型模型n1.3 并行算法的一般概念并行算法的一般概念并行算法的定义和分类并行算法的定义和分类相关性与可并行化相关性与可并行化并行算法的表示并行算法的表示并行算法的复杂度并行算法的复杂度并行算法的并行算法的WT表示表示加速比性能定律加速比性能定律并行算法的同步和通讯并行算法的同步和通讯并行算法30 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 定义和分类定义和分类n并行算法并行算法 一组可同
28、时执行且可互相协作的诸进程的集合。n分类分类 VLSI并行算法：在VLSI计算模型上开发的并行算法 、匹配等符号处理基于排序、选择、搜索非数值算法：基于代数等数学运算数值算法：各进程可以独立执行异步算法：进程执行需要相互等待同步算法：环境下网格计算：元计算网络计算：工作站机群局网环境下分布算法InternetCOW/法等如：随机算法、智能算非确定算法：时间复杂性确定的以及算法结果求解过程为确定的步骤确定算法：/并行算法31 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的表示并行算法的表示npar-do语句语句 for i=1 to n par-do 或
29、for i=1 to n do in parallel . . . . . . end for end fornfor all语句语句 for all Pi, where 0ik do . . . end for并行算法32 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的复杂度并行算法的复杂度n串行算法的度量串行算法的度量一些记号一些记号平均情形复杂度、最坏情形复杂度平均情形复杂度、最坏情形复杂度并行算法33 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的复杂度并行算法的复杂度n并行算法复杂性的度量并行算法复杂性的
30、度量运行时间t(n)：计算时间tc和选路(路由)时间tr处理器数目p(n)成本c(n)：c(n)=t(n)p(n)成本最优性：若c(n)等于在最坏情形下串行算法所需要的时间，则并行算法是成本最优的。加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)为求解问题的最快的串行算法在最坏情形下所需的运行时间，tp(n)为求解同一问题的并行算法在最坏情形下的运行时间。 注：(1)加速比Sp(n)反映算法的并行性对运行时间的改进程度。 (2)若Sp(n)=p(n)，则达到线性加速；若Sp(n)p(n)，则为超线性加速(一般出现在某些特殊的应用中，如并行搜索等)。并行效率Ep(n)：Ep(
31、n)=Sp(n)/p(n)， 0Ep(n)用p台处理器去完成并行算法A的第i时刻工作量，需时间 =用p台处理器模拟并行算法A的总时间为 )(1 (nTiipWi)()(11)(1)(1)(1nTpnWpWpWpWnTiinTiinTii并行算法35 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的并行算法的WT表示表示nBrent定理定理 注： (1)揭示了并行算法工作量和运行时间的关系； (2)提供了并行算法的WT(Work-Time)表示方法； (3)告诉我们：设计并行算法时应尽可能将每个时间步的工作量均匀地分摊给p台处理器，使各处理器处于活跃状态。并
32、行算法36 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的并行算法的WT表示表示n例1 令n=2k(k=0)，求n个数和的并行算法。算法运行时间：t(n)=O(logn)总运算量:由Brent定理知: t(n)=O(n/p+logn) )(12)()()()(log1)3()2()1(nOnnnWnWnWnWnhh并行算法37 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的并行算法的WT表示表示并行算法38 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 加速比性能定律加速比性能定律nA
33、mdahls Law: Base on Fixed Problem Size适用于实时应用问题。适用于实时应用问题。当问题的计算负载或规模固定时，我们必须通过增加处理器数目当问题的计算负载或规模固定时，我们必须通过增加处理器数目来降低计算时间；来降低计算时间；设设 f 是算法中不能并行的串行部分比例，是算法中不能并行的串行部分比例，Ws和和Wp分别是串行分别是串行和并行部分的工作量，则总工作量和并行部分的工作量，则总工作量W=fW+(1-f)W=Ws+Wp；Amdahls law表明：加速比受到算法中串行工作量的限制。表明：加速比受到算法中串行工作量的限制。n公式推导公式推导pWffWTWff
34、WTps)1 ()1 (fpfpfpfppWffWWSpp11) 1(11)1 ( 并行算法39 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 加速比性能定律加速比性能定律nGustafsons Law: Base on Fixed Execution Time适用于要求精度高的应用，通过加大计算量来提高计算精度。适用于要求精度高的应用，通过加大计算量来提高计算精度。Gustafsons Law表明：随着处理器数目的增加，串行执行部分表明：随着处理器数目的增加，串行执行部分f不再是并行算法的瓶颈。不再是并行算法的瓶颈。放大问题工作量或规模的加速公式推导：放大问题工
35、作量或规模的加速公式推导： 与与p成线性关系。成线性关系。) 1()1 (/pfpfpfWWpWWppWWpWWSpspspspsppS并行算法40 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 加速比性能定律加速比性能定律nSun & Nis Law: Base on Memory Bounding充分利用存储空间等计算资源，尽量增大问题规模以产生更好充分利用存储空间等计算资源，尽量增大问题规模以产生更好/更精确的解。是更精确的解。是Amdahl定律和定律和Gustafson定律的推广。定律的推广。公式推导：公式推导： 设单机上的存储器容量为设单机上的存储器容量
36、为M，其工作负载，其工作负载W=fW+(1-f)W 当并行系统有当并行系统有p个结点时，个结点时，存储容量扩大了存储容量扩大了pM，用用G(p)表示表示系系统的存储容量增加统的存储容量增加p倍时倍时工作负载的增加量工作负载的增加量。则存储容量扩大后。则存储容量扩大后的工作负载为的工作负载为W=fW+(1-f)G(p)W，所以，存储受限的加速为，所以，存储受限的加速为 特别地：特别地： 当当G(p)=1时，时， 为为Amdahl定律；定律； 当当G(p)=p时，时， 为为Gustafson定律；定律；ppGffpGffpWpGffWWpGffWSp/ )()1 ()()1 (/)()1 ()()
37、1 ( pffSSpp/ )1 (1 ) 1( pfpSSpp并行算法41 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的同步并行算法的同步n同步概念同步概念同步是在时间上强使各执行进程在某一点必须互相等待，确保各同步是在时间上强使各执行进程在某一点必须互相等待，确保各进程的正常顺序和对共享可写数据的正确访问；进程的正常顺序和对共享可写数据的正确访问；可用软件、硬件和固件的办法来实现。可用软件、硬件和固件的办法来实现。n同步语句示例同步语句示例算法算法1.3 APRAM上的求和算法上的求和算法 输入：输入：A=(a0,an-1),处理器数处理器数p 输出
38、：输出：S=ai Begin (1)S=0 (2.3) lock(S) (2)for all Pi where 0ip-1 do S=S+L (2.1) L=0 (2.4) unlock(S) (2.2) for j=i to n step p do end for L=L+aj End end for算法的时间复杂度：算法的时间复杂度：O(n/p+p) 并行算法42 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的同步并行算法的同步并行算法43 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的通讯并行算法的通讯n通讯
39、通讯共享存储多处理器使用：共享存储多处理器使用： global read(X,Y) /将将SM中的中的X读入读入LM中的中的Y global write(U,V) /将将LM中的中的U写入写入SM中的中的V分布存储多计算机使用：分布存储多计算机使用： send(X,i) /处理器处理器P发送发送X给处理器给处理器Pi receive(Y,j) /处理器处理器P等待从等待从Pj接收数据并存入接收数据并存入LM中的中的Yn通讯语句示例通讯语句示例算法算法1.5 分布存储多计算机上矩阵向量乘法分布存储多计算机上矩阵向量乘法,通讯链为环通讯链为环 输入：处理器数输入：处理器数p, A按列划分为按列划分
40、为p个个B=Ai=A1.n,(i-1)r+1.ir, x划分为划分为w=xi=x(i-1)r+1.ir, r=n/p, i=1p 输出：输出：P1保存乘积保存乘积AX Begin (1) Compute z=Bw (2) if i=1 then y=0 else receive(y,left) endif (3) y=y+z (4) send(y,right) (5) if i=1 then receive(y,left) End 并行算法44 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的通讯并行算法的通讯n计算过程图示计算过程图示并行算法45 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的通讯并行算法的通讯n算法的复杂度算法的复杂度并行算法46 / Ch12022-6-221.3 并行算法的一般概念并行算法的一般概念: 并行算法的通讯并行算法的通讯并行算法47 / Ch12022-6-22 End of Chapter 1
