并行程序设计

1、第一章 并行计算机1.1 1.1 对计算机速度的需求对计算机速度的需求1.2 1.2 并行计算机的类型并行计算机的类型1.3 1.3 消息传递多计算机的体系结构特征消息传递多计算机的体系结构特征1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台1.5 1.5 提高计算机速度的潜力提高计算机速度的潜力1.1 The Demand For Computational Speed1.1 The Demand For Computational Speed A grand challenge problem is one that cannot be A grand challe

2、nge problem is one that cannot be solved in a reasonable amount of time with solved in a reasonable amount of time with todaytodays computers.s computers. Examples:Examples: Global weather forecasting Global weather forecasting Modeling the motion of astronomical bodies Modeling the motion of astron

3、omical bodies Modeling large DNA structure Modeling large DNA structure科学和工程领域有数值建模和模拟，需对大科学和工程领域有数值建模和模拟，需对大量数据进行多次重复计算，计算必须在合理量数据进行多次重复计算，计算必须在合理时间内完成，故需要很高计算速度。时间内完成，故需要很高计算速度。1.1 The Demand For Computational Speed1.1 The Demand For Computational SpeedWhatever the computational speed of current W

4、hatever the computational speed of current processors, there will be applications that processors, there will be applications that requires more computational power.requires more computational power. Human nature: Human nature:不断想象那些超过计算机系统能不断想象那些超过计算机系统能力的新应用，从而需要比目前可提供的更高速力的新应用，从而需要比目前可提供的更高速度。度。并

5、行编程有时有助于求解更精确的解并行编程有时有助于求解更精确的解并行计算机比单机有更大的主存储器容量，使并行计算机比单机有更大的主存储器容量，使得需要较大主存储器容量的求解问题得到解决。得需要较大主存储器容量的求解问题得到解决。1.1 The Demand for Computational Speed1.1 The Demand for Computational SpeedThe ideal effect of parallel computer:The ideal effect of parallel computer:n n台计算机应能提供台计算机应能提供n n倍的单机速度，不论当前倍的

6、单机速度，不论当前计算机速度为多少，可期待求解的问题以计算机速度为多少，可期待求解的问题以1/n1/n时时间完成。间完成。实际很难达到：实际很难达到： 求解问题常不能完全分解成各自独立的部求解问题常不能完全分解成各自独立的部 分，各部分之间有交互（数据传送、同步）分，各部分之间有交互（数据传送、同步） 但仍可达到实质性改善。但仍可达到实质性改善。结论：结论：Future is parallelFuture is parallel云计算案例云计算案例20082008年年3 3月月1919日上午日上午1010点，美国国家档案馆公开了希点，美国国家档案馆公开了希拉里拉里. .克林顿在克林顿在1993

7、200119932001年作为第一夫人期间的白宫年作为第一夫人期间的白宫日程档案。日程档案。华盛顿邮报希望将这些档案在第一时间上传到互联网，华盛顿邮报希望将这些档案在第一时间上传到互联网，以便公众查询。具有极高的社会关注度和新闻时效性。以便公众查询。具有极高的社会关注度和新闻时效性。这些档案是不可检索的低质量这些档案是不可检索的低质量PDFPDF文件，若想将其转文件，若想将其转换为可以检索并便于浏览的文件格式，需要进行再处换为可以检索并便于浏览的文件格式，需要进行再处理。理。据估算，仅每一页的操作，以报社现有的计算能力就据估算，仅每一页的操作，以报社现有的计算能力就需要需要3030分钟。分钟。

8、华盛顿邮报将档案的转换工程交给华盛顿邮报将档案的转换工程交给Amazon EC2 Amazon EC2 (Elastic Compute Cloud)(Elastic Compute Cloud)。 Amazon EC2Amazon EC2同时使用同时使用200200个虚拟服务器实例，每个服务器的单页平均处理时间个虚拟服务器实例，每个服务器的单页平均处理时间都缩短为都缩短为1 1分钟，并在分钟，并在9 9小时内将所有档案转换完毕，小时内将所有档案转换完毕，以最快的速度将这些第一手资料呈现给读者。以最快的速度将这些第一手资料呈现给读者。大数据时代央视著名“对话”栏目专题讨论大数据技术央视著名“对

9、话”节目4月14和21日邀请了牛津大学教授、大数据领域权威专家、大数据时代作者维克托迈尔-舍恩伯格，以及美国大数据存储技术公司LSI总裁阿比分别做客“对话”节目，做了两期大数据专题谈话节目“谁在引爆大数据”、“谁在掘金大数据”4月14日“对话”节目专题访谈：谁在引爆大数据http:/ 4月21日“对话”节目专题访谈：谁在掘金大数据http:/ 1.2 并行计算机的类型并行编程：并行编程：多个处理器协同求解一个问题，将多个处理器协同求解一个问题，将整个求解问题分成若干部分，每部分各由一个整个求解问题分成若干部分，每部分各由一个处理器并行地计算，编写这种形式的程序，称处理器并行地计算，编写这种形式

10、的程序，称为并行编程。为并行编程。并行计算机：并行计算机：是并行编程的计算平台，可以是是并行编程的计算平台，可以是具有多个内部处理器的单计算机或是以某种方具有多个内部处理器的单计算机或是以某种方式互连的若干台独立的计算机。式互连的若干台独立的计算机。 A Parallel Computer is a collection of A Parallel Computer is a collection of processing elements that communicate and processing elements that communicate and cooperate to s

11、olve large problem erate to solve large problem fast.1.2 并行计算机的类型1.2.1 1.2.1 共享存储器多处理机系统共享存储器多处理机系统 Share Memory Multiprocessor SystemShare Memory Multiprocessor System1.2.2 1.2.2 消息传递多计算机系统消息传递多计算机系统 Message-Passing MulticomputerMessage-Passing Multicomputer1.2.3 1.2.3 分布式共享存储器系统分布式共享存储器系统

12、 Distributed Shared MemoryDistributed Shared Memory1.2.4 MIMD1.2.4 MIMD和和SIMDSIMD分类法分类法 MIMD and SIMD ClassificationsMIMD and SIMD Classifications1.2.1 Shared Memory Multiprocessor System1.2.1 Shared Memory Multiprocessor System普通计算机普通计算机ProcessorMemory共享存储器多处理机模型共享存储器多处理机模型MMMInterconnection networ

13、kPPP UMAUMA（均匀存储访问）模型（均匀存储访问）模型 物理存储器被所有节点共享；物理存储器被所有节点共享； 所有节点访问任意存储单元的所有节点访问任意存储单元的时间相同时间相同； 发生访存竞争时，仲裁策略平等对待每个节发生访存竞争时，仲裁策略平等对待每个节 点，即每个节点点，即每个节点机会均等机会均等； 各节点的各节点的CPUCPU可带有可带有局部私有高速缓存局部私有高速缓存； 外围外围I/OI/O设备也可以共享，且每个节点有平等设备也可以共享，且每个节点有平等 的访问权利。的访问权利。1.2.1 Shared Memory Multiprocessor System1.2.1 Sh

14、ared Memory Multiprocessor System NUMANUMA（非均匀存储访问）模型（非均匀存储访问）模型 物理存储器被所有节点共享，任意节点可以直接访问物理存储器被所有节点共享，任意节点可以直接访问 任意内存模块；任意内存模块； 节点访问内存模块的节点访问内存模块的速度不同速度不同，访问本地存储模块的，访问本地存储模块的速度一般是访问其它节点内存模块的速度一般是访问其它节点内存模块的3 3倍以上；倍以上； 发生访存竞争时，仲裁策略对节点可能是发生访存竞争时，仲裁策略对节点可能是不等价的不等价的； 各节点的各节点的CPUCPU可带有可带有局部私有高速缓存局部私有高速缓存

15、（cachecache）； 外围外围I/OI/O设备也可以共享，但对各节点是不等价的设备也可以共享，但对各节点是不等价的。1.2.1 Shared Memory Multiprocessor System1.2.1 Shared Memory Multiprocessor System处理器和存储器之间的连接是通过某种互连网络实现的。处理器和存储器之间的连接是通过某种互连网络实现的。共享存储器的多处理机系统使用共享存储器的多处理机系统使用单地址空间单地址空间：整个主存储器系统中：整个主存储器系统中的每一个单元有一个唯一的地址。的每一个单元有一个唯一的地址。将单处理机将单处理机虚存储器虚存储器的

16、概念应用其上，实现虚实地址转换。每个存的概念应用其上，实现虚实地址转换。每个存储器单元仍只有一个唯一的实地址，但各处理器能使用不同的虚地储器单元仍只有一个唯一的实地址，但各处理器能使用不同的虚地址对它进行访问。址对它进行访问。访问共享存储器中的共享数据需小心，要考虑是否会产生冲突，有访问共享存储器中的共享数据需小心，要考虑是否会产生冲突，有一些类似操作系统的机制保证对一些类似操作系统的机制保证对共享数据共享数据的访问是安全的（如加锁、的访问是安全的（如加锁、信号量等）。信号量等）。对共享存储器进行编程有对共享存储器进行编程有多种方法多种方法，如可用全新的并行编程语言、，如可用全新的并行编程语言

17、、系统系统/ /库方法、线程方法等。库方法、线程方法等。1.2.1 Shared Memory Multiprocessor System1.2.1 Shared Memory Multiprocessor SystemMessage_passing multiprocessor modelMessage_passing multiprocessor modelMMMMMMP PP PP PInterconnection NetworkInterconnection NetworkLocalLocalmemorymemory1.2.2 Message-Passing Multicomputer

18、1.2.2 Message-Passing Multicomputer与共享存储器多处理机是专门设计的计算机系统不同，与共享存储器多处理机是专门设计的计算机系统不同，消息传递多计算机系统通过互连网络连接多台消息传递多计算机系统通过互连网络连接多台完整的完整的计计算机构成，每台计算机由一个处理器和算机构成，每台计算机由一个处理器和本地存储器本地存储器组成。组成。主存储器分布在多台计算机中，每台计算机都有自己的主存储器分布在多台计算机中，每台计算机都有自己的地址空间，每个处理器只能访问自己的本地主存储器中地址空间，每个处理器只能访问自己的本地主存储器中的单元，的单元，其他处理器不可访问该本地的主存

19、储器。其他处理器不可访问该本地的主存储器。1.2.2 Message-Passing Multicomputer1.2.2 Message-Passing Multicomputer多台计算机间的通信通过它们间消息在互连网络多台计算机间的通信通过它们间消息在互连网络上传递完成上传递完成-故称消息传递多处理机系统，简称故称消息传递多处理机系统，简称多计算机。多计算机。对消息传递多计算机系统进行编程需将问题分解，对消息传递多计算机系统进行编程需将问题分解，每个部分同时执行以完成求解。有多种方法：使每个部分同时执行以完成求解。有多种方法：使用并行编程语言、扩展的顺序编程语言，使用消用并行编程语言、扩

20、展的顺序编程语言，使用消息传递库例程等。息传递库例程等。1.2.2 Message-Passing Multicomputer1.2.2 Message-Passing Multicomputer优点：优点：容易在物理上加以扩展，易于构成较大规模。容易在物理上加以扩展，易于构成较大规模。易于升级。易于升级。不需要专门的机制来控制对数据的同时访问。不需要专门的机制来控制对数据的同时访问。缺点：缺点：编程时需要程序员在代码中提供显式的消息传递调用。编程时需要程序员在代码中提供显式的消息传递调用。数据不能共享，需拷贝。数据不能共享，需拷贝。1.2.2 Message-Passing Multicom

21、puter1.2.2 Message-Passing Multicomputer1.2.3 Distributed Shared MemoryDistributed Shared memory multiprocessor modelMMMPPPInterconnection Networksharedmemory1.2.3 Distributed Shared Memory模型中本地存储器变为共享存储器模型中本地存储器变为共享存储器共享虚拟共享虚拟存储器存储器每个处理器使用单一的存储器地址空间对整个存每个处理器使用单一的存储器地址空间对整个存储器进行访问储器进行访问当一个处理器要访问的单元不

22、在本地存储器中时，当一个处理器要访问的单元不在本地存储器中时，通过消息传递在处理器与该单元间传送数据通过消息传递在处理器与该单元间传送数据消息传递以消息传递以自动方式自动方式进行。尽管存储器是分布式进行。尽管存储器是分布式的，但给用户的感觉是共享存储器。的，但给用户的感觉是共享存储器。共享虚共享虚拟存储器拟存储器1.2.4 MIMD and SIMD ClassificationFlynnFlynn计算机分类法计算机分类法最早但最流行的分类最早但最流行的分类任何系统都包含两个重要的组成元素：指令任何系统都包含两个重要的组成元素：指令 、数据、数据single instruction strea

23、m-single data streamsingle instruction stream-single data stream（SISD) SISD) computercomputer串行计算机，每条指令一次只对一个数据集执行操作串行计算机，每条指令一次只对一个数据集执行操作single instruction stream-multiple data stream(SIMD) single instruction stream-multiple data stream(SIMD) computercomputer同一指令同时对不同数据集进行并行操作。数据集个数是同时进行操作的同一指令同时对

24、不同数据集进行并行操作。数据集个数是同时进行操作的处理器的数量处理器的数量向量计算机向量计算机multiple instruction stream-single data stream(MISD) multiple instruction stream-single data stream(MISD) computercomputer对单个数据集执行多个不同操作对单个数据集执行多个不同操作multiple instruction stream-multiple data stream(MIMD) multiple instruction stream-multiple data stream

25、(MIMD) computercomputer多个处理器，每个处理器上运行一个指令流，每条指令对不同的数据进行多个处理器，每个处理器上运行一个指令流，每条指令对不同的数据进行操作。操作。二种并行编程软件结构 MPMDmultiple program multiple data SPMD single program multiple data 1.3 ARCHITECTURE FEATURE OF 1.3 ARCHITECTURE FEATURE OF MESSAGE-PASSING MULTICOPUTERSMESSAGE-PASSING MULTICOPUTERS1.3.1 1.3.1 静

26、态网络消息传递多计算机静态网络消息传递多计算机1.3.2 1.3.2 嵌入嵌入1.3.3 1.3.3 通信方法通信方法1.3.1 Static Network Message-Passing 1.3.1 Static Network Message-Passing MulticomputerMulticomputer静态网络：静态网络：static interconnection network are those static interconnection network are those that have direct fixed physical links between tha

27、t have direct fixed physical links between computers(node) computers(node)1.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer1 1、网络性能指标、网络性能指标 带宽带宽 Bandwidth:Bandwidth: the number of bits that can be the number of bits that can be transmitted in unit

28、time. bit/sectransmitted in unit time. bit/sec 网络延迟网络延迟 Network latency:Network latency: the time to make a the time to make a message transfer through the network,message transfer through the network,又叫又叫通信延迟通信延迟，由启动时间和通信时间组成。由启动时间和通信时间组成。1.3.1 Static Network Message-1.3.1 Static Network Message-Pa

29、ssing MulticomputerPassing Multicomputer网络直径网络直径 Diameter:Diameter: the minimum number of the minimum number of links between the two farthest nodes in the links between the two farthest nodes in the work. NoteNote that only the shortest routes are used. that only the shortest routes are used. Diame

30、ter is used to determine the worst case Diameter is used to determine the worst case delays and find the communication lower delays and find the communication lower bound of some parallel algorithms.bound of some parallel algorithms.1.3.1 Static Network Message-1.3.1 Static Network Message-Passing M

31、ulticomputerPassing Multicomputer2 2、Completely Connected NetworkCompletely Connected Network每一结点与所有其他结点均有一条链路每一结点与所有其他结点均有一条链路有限互连的静态网络：有限互连的静态网络： 线线/ /环网络环网络 Line/RingLine/Ring 网格网格/ /圆环形网络圆环形网络 Mesh/TourMesh/Tour 树状网络树状网络 Tree NetworksTree Networks 超立方体网络超立方体网络 Hypercube NetworkHypercube Network1

32、.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer3 3、Ling/RingLing/Ring 线网：由一行结点组成，每个结点限定只能与其邻接线网：由一行结点组成，每个结点限定只能与其邻接 结点连接。每个结点有结点连接。每个结点有2 2条链路，条链路，n n 个结点有个结点有 n-1n-1条链路条链路 Diameter:n-1.Diameter:n-1. 环网：将线网两端的自由结点连接。环网：将线网两端的自由结点连接。 n n 个结点有个结点有 n

33、 n条条 链路链路 . . Diameter: n/2 Diameter: n/21.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer4 4、MeshMesh 二维网格：二维阵列中的每个结点能与其二维网格：二维阵列中的每个结点能与其4 4个最邻近的个最邻近的 结点相连。结点相连。 Diameter of n Diameter of n * * n n Mesh : 2(n Mesh : 2(n -1)-1) 三维网格：每个结点在三维网格：每个结点在

34、xyzxyz三个维上各与两个结点相连三个维上各与两个结点相连 圆环形网络（圆环形网络（tours):tours):将网格中的所有自由端结点与其对将网格中的所有自由端结点与其对立端的结点循环相连。立端的结点循环相连。 在在n n * * n n tours tours 中，总链路数为中，总链路数为2n2n条。条。 1.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer 二维阵列（网格）二维阵列（网格）计算机计算机 / / 处理器处理器1.3.1 Sta

35、tic Network Message-Passing Multicomputer5 5、Tree NetworksTree Networks1.3.1 Static Network Message-1.3.1 Static Network Message-Passing MulticomputerPassing Multicomputer6 6、Hypercube NetworkHypercube Network 每个结点与网络中每一维上的一个结点相连接。每个结点与网络中每一维上的一个结点相连接。 网络直径为网络直径为2 2n.n. 一个一个d d维超立方体中的每一结点，被分配一个维超立方体

36、中的每一结点，被分配一个d d 位二进制地址。位二进制地址。 存在有最小距离的无死锁路由算法存在有最小距离的无死锁路由算法 一个一个d d维超立方体由两个维超立方体由两个d-1d-1维超立方体用第维超立方体用第d d维维 链路将两者连接起来组成。链路将两者连接起来组成。1.3.1 Static Network Message-Passing Multicomputer 1.3.1 Static Network Message-Passing Multicomputer1.3.2 嵌入（embedding)嵌入：将一个网络中的结点映射到另一网络。嵌入：将一个网络中的结点映射到另一网络。线形网嵌入

37、到网格线形网嵌入到网格环形网嵌入圆环形网环形网嵌入圆环形网网格嵌入到超立方体中网格嵌入到超立方体中1.3.2 嵌入（embedding)1.3.3 通信方法电路交换电路交换(circuit switching)(circuit switching)包交换包交换(packet switching)(packet switching) 存储转发存储转发(store and forward)(store and forward) 虚拟直通虚拟直通(virtual cut through)(virtual cut through) 虫洞虫洞(wormhole)(wormhole)1.3.3 1.3.3

38、 通信方法通信方法1 1、电路交换、电路交换(circuit switching)(circuit switching) 在源和目的地之间建立通路，传递所在源和目的地之间建立通路，传递所需的链路均被保留，直到消息传递结束。需的链路均被保留，直到消息传递结束。如：简单的电话系统。如：简单的电话系统。 缺点：缺点：在整个传递消息过程中，要强行保在整个传递消息过程中，要强行保留通路中的所有链路，在消息传递结束之留通路中的所有链路，在消息传递结束之前，不允许其他消息使用通路中的任一链前，不允许其他消息使用通路中的任一链路。路。1.3.3 1.3.3 通信方法通信方法2 2、包交换、包交换(packet

39、 switching)(packet switching)存储转发存储转发(store and forward)(store and forward) 消息被分成包，包在被传递到下一结点之消息被分成包，包在被传递到下一结点之前结点内部提供缓冲区保存这些包。如：前结点内部提供缓冲区保存这些包。如：邮递系统。邮递系统。 优点优点：允许一旦当前的包被转发后，其链：允许一旦当前的包被转发后，其链路就可由其他包使用。路就可由其他包使用。 缺点缺点：不论输出链路是否可用，包首先要：不论输出链路是否可用，包首先要存到结点的缓冲区中，导致显著的时间延存到结点的缓冲区中，导致显著的时间延迟。迟。1.3.3 1.

40、3.3 通信方法通信方法2 2、包交换、包交换(packet switching)(packet switching)虚拟直通虚拟直通(virtual cut through)(virtual cut through) 如输出链路可用，消息可直接向前传递而无需存入如输出链路可用，消息可直接向前传递而无需存入结点缓冲区。结点缓冲区。虫洞虫洞(wormhole)(wormhole) 消息被分成更小的单位消息被分成更小的单位片。当连接链路可用时，片。当连接链路可用时，从原结点向下一结点传送的初始消息只是消息的头从原结点向下一结点传送的初始消息只是消息的头片，当所有链路都可用时，消息的各后继片才会被片

41、，当所有链路都可用时，消息的各后继片才会被传送。在各结点间必须有一个请求传送。在各结点间必须有一个请求/ /应答系统。应答系统。 优点：优点：每个结点所需的存储容量较少，时延与通路每个结点所需的存储容量较少，时延与通路长度无关。片中各位可并行传送。长度无关。片中各位可并行传送。1.3.3 通信方法1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台A network of workstations (NOW) or cluster ofworkstations(COW) became a very attractive alternative to expensive su

42、percomputers and parallel computer systems for high-performance computing in early 1990s.1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台采用工作站集群采用工作站集群(Cluster of Workstations,COW)(Cluster of Workstations,COW)的的优点：优点：工作站性能高而价格低工作站性能高而价格低当出现新的高性能处理器，易于采用来升当出现新的高性能处理器，易于采用来升级级COWS.COWS.串行机上的程序简单修改就可在串行机上的程序简单修改就可

43、在COWSCOWS上上运行。运行。1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台并行软件平台：并行软件平台：并行虚拟机并行虚拟机（Parallel Virtual Machine PVM). Parallel Virtual Machine PVM). developed in late 1980developed in late 1980s. Became very s. Became very popular.popular.消息传递接口消息传递接口（Message-passing Inter

44、face, Message-passing Interface, MPI). standard defined in 1990s.MPI). standard defined in 1990s. Both provide a set of user-level libraries for Both provide a set of user-level libraries for message passing. Use with regular message passing. Use with regular programming languages (C, C+, .).program

45、ming languages (C, C+, .).1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台互连手段：互连手段： EthernetEthernet Ring structure Ring structure Star connection Star connection1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台1.4 1.4 用连网计算机作为多计算机平台用连网计算机作为多计算机平台使用使用连

46、网工作站连网工作站作为计算平台与使用作为计算平台与使用静态网络静态网络的的差别：差别： 通信延迟通信延迟 连网工作站的延迟远大于静态连网工作站的延迟远大于静态 链路多计算机的延迟。程序可移植。链路多计算机的延迟。程序可移植。 连网的各工作站可能具有不同的类型和速度。连网的各工作站可能具有不同的类型和速度。1.5 1.5 提高计算速度的潜力提高计算速度的潜力 粒度粒度(Granularity)(Granularity) 加速比加速比(Speedup Factor)(Speedup Factor) 开销开销(Overhead)(Overhead) Amdahl Amdahl定律定律 效率效率(Ef

47、fiency)(Effiency) 代价代价(cost)(cost) 可扩展性可扩展性(Scalability)(Scalability) Gustafson Gustafson定律定律1.5 1.5 提高计算速度的潜力提高计算速度的潜力1 1、粒度（粒度（granularity)granularity) 进程的大小进程的大小 必须将计算分成能同时执行的多个任务或进程，必须将计算分成能同时执行的多个任务或进程，才能改进速度，达到并行。才能改进速度，达到并行。粒度（粒度（granularity):granularity):描述描述process process 的大小。的大小。Coarse gr

48、anularity:Coarse granularity:每个每个processprocess含有大量的顺序含有大量的顺序指令且要用大量时间加以执行。指令且要用大量时间加以执行。Fine granularity:Fine granularity: process process可能只有几条指令。可能只有几条指令。Medium granularity:Medium granularity:每个每个processprocess所含指令数为所含指令数为中等程度。中等程度。1.5 1.5 提高计算速度的潜力提高计算速度的潜力增大粒度，会减少创建进程和进程间的通信代增大粒度，会减少创建进程和进程间的通信

49、代价；但减少了并发进程数和并行性。故需折衷。价；但减少了并发进程数和并行性。故需折衷。计算计算/ /通信比通信比=计算时间计算时间/ /通信时间通信时间用作衡用作衡量粒度大小的指标。量粒度大小的指标。在保持有足够并行性的同时，尽量增大在保持有足够并行性的同时，尽量增大计算计算/ /通信比通信比。1.5 1.5 提高计算速度的潜力提高计算速度的潜力2 2、加速比（加速比（Speedup Factor)Speedup Factor) 单机运行串行程序的时间单机运行串行程序的时间S(n)= S(n)= 含有含有n n个处理器的并行计算机运行并行程序的时间个处理器的并行计算机运行并行程序的时间 = =

50、 t t s s / / t t p p 加速比用来衡量一个多处理机系统和一个单机加速比用来衡量一个多处理机系统和一个单机系统的相对性能。系统的相对性能。1.5 提高计算速度的潜力在理论分析中，也可用在理论分析中，也可用计算步计算步计算加速比。计算加速比。 单机运行串行程序的计算步数单机运行串行程序的计算步数S(n)= S(n)= 使用使用n n个处理器的并行计算步数个处理器的并行计算步数1.5 提高计算速度的潜力线性加速比线性加速比(Linear Speedup) S(n)=n(Linear Speedup) S(n)=n 当计算被分成相等持续时间的进程，每个进程映当计算被分成相等持续时间的进程，每个进程映射到一个处理器上时（假设无开销），就可获得射到一个处理器上时（假设无开销），就可获得最大加速最大加速n n。超线性加速比超线性加速比(Superlinear Speedup)S(n)n(Superlinear Speedup)S(n)n 使用了次优化顺序算法使用了次优化顺序算法 使用了有利于并行的使用了有利于并行的 体系结构（存储器容量）体系结构（存储器容量）1.5 1.5 提高计算速度的潜力提高计算速度的潜力3 3、开销开销（OverheadOverhead）影响加速比的因素影响加速比的因素 一些处理器处于闲置状态。一些处理器处