1、第二章第二章 并行硬件和并行软件1背景知识2串行硬件和软件输入输出程序一次只执行单个任务3“经典”的冯诺依曼结构4主存（Main memory）n主存中有许多区域，每个区域都可以存储指令和数据。n每个区域都有一个地址，可以通过这个地址来访问相应的区域及区域中存储的数据和指令。5中央处理单元(CPU)n中央处理单元中央处理单元分为控制单元和算术逻辑单元（Arithmetic Logic Unit，ALU）。n控制单元控制单元负责决定应该执行程序中的哪些指令。nALU负责执行指令。add 2+26关键术语n寄存器CPU中的数据和程序执行时的状态信息存储在特殊的快速存储介质中n程序计数器控制单元中一
2、个特殊的寄存器，用来存放下一条指令的地址。n总线指令和数据通过CPU和主存之间的互连结构进行传输。这种互连结构通常是总线，总线中包括一组并行的线以及控制这些线的硬件。7memoryCPUfetch/read当数据或指令从主存传送到CPU时，我们称数据或指令从内存中取出或者读出。8memoryCPUwrite/store当数据或指令从CPU传送到主存中时，我们称数据或指令写入或者存入内存中。9冯诺依曼瓶颈主存和CPU之间的分离称为冯诺依曼瓶颈。这是因为互连结构限定了指令和数据访问的速率。程序运行所需要的大部分数据和指令被有效地与CPU隔离开。10一个操作系统“进程”n进程是运行着的程序的一个实例
3、。n一个进程包括如下实体:n可执行的机器语言程序.n一块内存空间.n操作系统分配给进程的资源描述符.n安全信息.n进程状态信息.11多任务n大多数现代操作系统都是多任务的。 这意味着操作系统提供对同时运行多个程序的支持。n这对于单核系统也是可行的，因为每个进程只运行一小段时间（几毫秒），亦即一个时间片。在一个程序执行了一个时间片的时间后，操作系统就切换执行其他程序12多任务n在一个多任务操作系统中，如果一个进程需要等待某个资源，例如需要从外部的存储器读数据，它会阻塞。这意味着，该进程会停止运行，操作系统可以运行其他进程。例如：航班预定系统在一个用户因为等待座位图而阻塞时，可为另一个用户提供可用
4、的航线查询。13线程n线程包含在进程中。n线程为程序员提供了一种机制，将程序划分为多个大致独立的任务，当某个任务阻塞时能执行其他任务。n此外，在大多数系统中，线程间的切换比进程间的切换更快。14一个进程和两个线程the “master” thread（主线程）starting a threadIs called forking（派生）（派生）terminating a threadIs called joining（合并）（合并）15对冯诺依曼模型的改进16缓存 (Cache)nCPU Cache 是一组相比于主存，CPU能更快速地访问的内存区域。nCPU Cache位于与CPU同一块的芯片或
5、者位于其他芯片上，但比普通的内存芯片能更快地访问。17局部性原理n程序访问完一个存储区域往往会访问接下来的区域，这个原理称为局部性。n空间局部性访问附近的位置n时间局部性访问在不久的将来18局部性原理float z1000;sum = 0.0;for (i = 0; i 1000; i+) sum += zi;19缓存的分层（level）L1L2L3最小 & 最快最大 & 最慢20Cache命中（hit）L1L2L3x sumy z totalA radius r1 centerfetch x21Cache缺失（miss）L1L2L3y sumr1 z totalA radius center
6、fetch xx主存22与缓存有关的问题n当CPU向Cache中写数据时，Cache中的值与主存中的值就会不同或者不一致(inconsistent)。n有两种方法来解决这个不一致性问题：写直达(write-through) 和写回(write-back) 23与缓存有关的问题n在写直达(write-through) Cache中，当CPU向Cache写数据时，高速缓存行会立即写入主存中。n在写回(write-back) Cache中，数据不是立即更新到主存中，而是将发生数据更新的高速缓存行标记成脏（dirty）。当发生高速缓存行替换时，标记为脏的高速缓存行被写入主存中。24缓存映射n全相联(f
7、ully associative) Cache每个高速缓存行能够放置在Cache中的任意位置。n直接映射(directed mapped) Cache每个高速缓存行在Cache中有唯一的位置。nn路组相联(n-way set associated)每个高速缓存行都能放置到Cache中n个不同区域位置中的一个。25n路组相联n当内存中的行（多于一行）能被映射到Cache中的多个不同位置（全相联和n路组相联）时，需要决定替换或者驱逐Cache中的哪一行。x26例子假设主存有16行，分别用015标记，Cache有4行，用03标记。在全相联映射中，主存中的0号行能够映射到Cache中的0、1、2、3任
8、意一行。在直接映射Cache中，可以根据主存中高速缓存行的标记值除以4求余，获得在Cache中的索引。因此主存中0、4、8号行会映射到Cache的0号行，主存中的1、5、9号行映射到Cache的1号行，以此类推。27虚拟内存(1)n如果运行一个大型的程序，或者程序需要访问大型数据集，那么所有的指令或者数据可能在主存中放不下。n利用虚拟存储器（或虚拟内存），使得主存可以作为辅存的缓存。28虚拟内存(2)n虚拟内存通过在主存中存放当前执行程序所需要用到的部分，来利用时间和空间局部性.29虚拟内存(3)n交换空间（swap space）那些暂时用不到的部分存储在辅存的块中，称为交换空间。n页(pag
9、e) 数据块和指令块.n页通常比较大.n大多数系统采用固定大小的页，从416kB不等.30虚拟内存(4)program Aprogram Bprogram Cmain memory31虚拟页号n在编译程序时，给程序的页赋予虚拟页号。n当程序运行时，创建一张将虚拟页号映射成物理地址的表。n程序运行时使用到虚拟地址，这个页表就用来将虚拟地址转换成物理地址。假如页表的创建由操作系统管理，那么就能保证程序使用的内存不会与其他程序使用的内存重叠32页表n假如虚拟地址有32位，页大小是4KB = 4096字节，那么可以用12位来标识页中的每个字节。因此，可以用虚拟地址的低12位来定位页内字节，而剩下的位用
10、来定位页。表2-233思考题n在表2-2中，虚拟地址由12位字节偏移量和20位的虚拟页号组成。如果一个程序运行的系统上拥有这样的页大小和虚拟地址空间，这个程序有多少页？34转译后备缓冲区（ TLB ）n尽管多个程序可以同时使用主存了，但使用页表会增加程序总体的运行时间。n为了解决这个问题，处理器有一种专门用于地址转换的缓存，叫做转译后备缓冲区（TranslationLookaside Buffer，TLB）。35转译后备缓冲区(2)nTLB在快速存储介质中缓存了一些页表的条目（通常为16512条）。n页面失效假如想要访问的页不在内存中，即页表中该页没有合法的物理地址，该页只存储在磁盘上，那么这
11、次访问称为页面失效（page fault）。36指令级并行(ILP)n指令级并行(InstructionLevel parallelism，ILP)通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。37指令级并行(2)n有两种主要方法来实现指令级并行：流水线和多发射。n流水线指将功能单元分阶段安排。n多发射指让多条指令同时启动。38流水线39流水线例子(1)n举一个关于计算的例子，假如我们想要将浮点数9.87104和6.54103相加，我们可以使用如下步骤：40流水线例子(2)n如果每次操作花费1纳秒,那么加法操作需要花费7纳秒nfor循环需要花费7000纳秒.41流水线例子(3
12、)另一个方案n将浮点数加法器划分成7个独立的硬件或者功能单元。n第一个单元取两个操作数，第二个比较指数，以此类推。n假设一个功能单元的输出是下面一个功能单元的输入，那么加法功能单元的输出是规格化结果功能单元的输入。42流水线例子(4)另一个方案43流水线例子(5)另一个方案n在时间5后，流水循环每1纳秒产生一个结果，而不再是每7纳秒一次。所以，执行for循环的总时间从7000纳秒降低到1006纳秒，提高了近7倍。44思考题2n当讨论浮点数加法时，我们简单地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都耗费2纳秒，其余的每个操作耗费1纳秒。 a. 在上述假设下，每个浮点数加法要耗费多
13、少时间？ b.非流水线1000对浮点数的加法要耗费多少时间？ c.流水线1000对浮点数加法要耗费多少时间？45思考题2nd. 如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别非常大。假设从一级缓存上取数据/指令要耗费2纳秒，从二级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执行某条指令，取其中一个操作数时，发生了一次一级缓存失效，那么流水线会发生什么情况？如果又发生二级缓存失效，又会怎样？46思考题2的答案na. nb. 9 1000 = 9000 nanoseconds47思考题2的答案nc. 9 + 999 2 = 2007ns
14、48思考题2的答案nd. 49多发射(1)n多发射处理器通过复制功能单元来同时执行程序中的不同指令。adder #1adder #2z0z2z1z3for (i = 0; i 0) w = x ;e l s e w = y ;Z 应该是正数如果系统预测错误，需要回退机制，然后执行w=y.53硬件多线程n指令级并行是很难利用的，因为程序中有许多部分之间存在依赖关系。n硬件多线程(hardware multithreading)为系统提供了一种机制，使得当前执行的任务被阻塞时，系统能够继续其他有用的工作。n例如，如果当前任务需要等待数据从内存中读出，那么它可以通过执行其他线程而不是继续当前线程来发
15、掘并行性.54硬件多线程(2)n细粒度(fine-grained)在细粒度多线程中，处理器在每条指令执行完后切换线程，从而跳过被阻塞的线程。n优点: 能够避免因为阻塞而导致机器时间的浪费.n缺点: 执行很长一段指令的线程在执行每条指令的时候都需要等待.55硬件多线程(3)n粗粒度(coarse grained)只切换那些需要等待较长时间才能完成操作（如从主存中加载）而被阻塞的线程。n优点: 不需要线程间的立即切换.n缺点: 处理器还是可能在短阻塞时空闲，线程间的切换也还是会导致延迟.56硬件多线程(4)n同步多线程(Simultaneous Multithreading，SMT)是细粒度多线程
16、的变种。n它通过允许多个线程同时使用多个功能单元来利用超标量处理器的性能。如果我们指定“优先”线程，那么能够在一定程度上减轻线程减速的问题。57并行硬件并行硬件58并行硬件n因为有多个复制的功能单元，所以多发射和流水线可以认为是并行硬件。但是，这种并行性通常对程序员是不可见的，所以我们仍把它们当成基本的冯诺依曼结构的扩展。n我们的原则是，并行硬件应该是仅限于对程序员可见的硬件。换句话说，如果能够通过修改源代码而开发并行性或者必须修改源代码来开发并行性，那么我们认为这种硬件是并行硬件59Flynn分类法SISDSingle instruction streamSingle data stream
17、(SIMD)Single instruction streamMultiple data streamMISDMultiple instruction streamSingle data stream(MIMD)Multiple instruction streamMultiple data streamclassic von Neumannnot covered60SIMDn单指令多数据流(Single Instruction，Multiple Data，SIMD)系统是并行系统。n顾名思义，SIMD系统通过对多个数据执行相同的指令从而实现在多个数据流上的操作。61SIMD例子control
18、 unitALU1ALU2ALUnfor (i = 0; i n; i+) xi += yi;x1x2xnn data itemsn ALUs62SIMDn如果ALU的数目小于数据的个数，怎么办？n将数据分组，然后迭代计算n例如， m = 4 ALUs，n = 15 个数据RoundALU1ALU2ALU3ALU41X0X1X2X32X4X5X6X73X8X9X10X114X12X13X1463SIMD的缺点n所有的ALU要么执行相同的指令，要么同时处于空闲状态的要求会严重地降低SIMD系统的整体性能。n在“经典”的SIMD系统中，ALU必须同步操作，即在下一条指令开始执行之前，每个ALU必须
19、等待广播。n此外，ALU没有指令存储器，所以ALU不能通过存储指令来延迟执行指令。nSIMD并行性在大型数据并行问题上非常有用，但是在处理其他并行问题时并不优秀。64向量处理器n向量处理器的重要特点是能够对数组或者数据向量进行操作，而传统的CPU是对单独的数据元素或者标量进行操作。n向量寄存器.n能够存储由多个操作数组成的向量，并且能够同时对其内容进行操作。向量的长度由系统决定，从4到128个64位元素不等。65向量处理器(2)n向量化和流水化的功能单元.n对向量中的每个元素需要做同样的操作，或者某些类似于加法的操作，这些操作需要应用到两个向量中相应的元素对上。因此，向量操作是SIMD.n向量
20、指令.n在向量上操作而不是在标量上操作的指令.66向量处理器(3)n交叉存储器.n内存系统由多个内存“体”组成，每个内存体能够独立访问.n在访问完一个内存体之后，再次访问它之前需要有一个时间延迟，但如果接下来的内存访问是访问另一个内存体，那么它很快就能访问到。所以，如果向量中的各个元素分布在不同的内存体中，那么在装入/存储连续数据时能够几乎无延迟地访问。67向量处理器(4)n步长式存储器访问和硬件散射/聚集.n在步长式存储器访问中，程序能够访问向量中固定间隔的元素，例如能够以跨度4访问第一个元素、第五个元素、第九个元素等。68向量处理器优点n速度快而且容易使用；n向量编译器擅长于识别向量化的代
21、码；n它们能识别出不能向量化的循环而且能提供循环为什么不能向量化的原因；因此，用户能对是否重写代码以支持向量化做出明智的决定；n向量系统有很高的内存带宽；n每个加载的数据都会使用，不像基于Cache的系统不能完全利用高速缓存行中的每个元素。69向量处理器缺点n不能处理不规则的数据结构和其他的并行结构n可扩展性差。可扩展性是指能够处理更大问题的能力。70图形处理单元（ GPU ）n实时图形应用编程接口使用点、线、三角形来表示物体的表面。71GPUsn使用图形处理流水线(graphics processing pipeline)将物体表面的内部表示转换为一个像素的数组。 这个像素数组能够在计算机屏
22、幕上显示出来。n流水线的许多阶段是可编程的。可编程阶段的行为可以通过着色函数（shader function）来说明。n典型的着色函数一般比较短，通常只有几行C代码.72GPUsn因为着色函数能够应用到图形流中的多种元素（例如顶点）上， 所以一般是隐式并行的。nGPU可以通过使用SIMD并行来优化性能。 现在所有的GPU都使用SIMD并行。n需要强调的是，GPU不是纯粹的SIMD系统。 尽管在一个给定核上的ALU使用了SIMD并行，但现代的GPU有几十个核，每个核都能独立地执行指令流。73MIMD系统n多指令多数据流（Multiple Instruction，Multiple Data，MIM
23、D）系统支持同时多个指令流在多个数据流上操作。nMIMD系统通常包括一组完全独立的处理单元或者核，每个处理单元或者核都有自己的控制单元和ALU。74共享内存系统n在共享内存系统中，一组自治的处理器通过互连网络（internection network）与内存系统相互连接。n每个处理器能够访问每个内存区域。n处理器通过访问共享的数据结构来隐式地通信。75共享内存系统(2)n最广泛使用的共享内存系统使用一个或者多个多核处理器.n(一个多核处理器在一块芯片上有多个CPU或者核)76共享内存系统(3)Figure 2.377一致内存访问(UMA)多核系统Figure 2.5每个核访问内存中任何一个区域
24、的时间都相同.78非一致内存访问(NUMA)多核系统Figure 2.6访问与核直接连接的那块内存区域比访问其他内存区域要快很多，因为访问其他内存区域需要通过另一块芯片.79分布式内存系统n集群(clusters)n由一组商品化系统组成（例如PC），通过商品化网络连接（例如以太网）。n实际上，集群系统中的节点是通过通信网络相互连接的独立计算单元.80分布式内存系统Figure 2.481互连网络n互连网络（interconnection network）在分布式内存系统和共享内存系统中都扮演了一个决定性的角色，即使处理器和内存无比强大，但一个缓慢的互连网络会严重降低除简单并行程序外所有程序的整
25、体性能。n分两类：共享内存互连网络和分布式内存互连网络82共享内存互连网络n总线（bus）互联n总线是由一组并行通信线和控制对总线访问的硬件组成的.n总线的核心特征是连接到总线上的设备共享通信线.n因为通信线是共享的，因此随着连接到总线设备的增多，争夺总线的概率增大，总线的预期性能会下降.83共享内存互连网络n交换互连网络n使用交换器（switch）来控制相互连接设备之间的数据传递.n交叉开关矩阵（crossbar） n交叉开关矩阵允许在不同设备之间同时进行通信，所以比总线速度快.n但是，交换器和链路带来的开销也相对高。一个小型的基于总线系统比相等规模的基于交叉开关矩阵系统便宜. 84Figu
26、re 2.7(a)图2-7a是一个交叉开关矩阵（crossbar），线表示双向通信链路，方块表示核或者内存模块，圆圈表示交换器(b)图2-7b表示单个交换器有两种不同的设置(c)图2-7c显示了，当P1向M4写数据，P2从M3中读数据，P3从M1中读数据，P4向M2中写数据时，各个交换器的配置情况85分布式内存互连网络n两种n直接互连n在直接互连中，每个交换器与一个处理器-内存对直接相连，交换器之间也相互连接.n间接互连n在间接互连网络中，交换器不一定与处理器直接连接.86直接互连网络87Figure 2.8环(ring)二维环面网格(toroidal mesh)二维环面网格的交换器需要能够支
27、持5个链路而不只是3个等分宽度(bisection width)n衡量“同时通信的链路数目”或者“连接性”的一个标准是等分宽度(bisection width)。n为了理解这个标准，想象并行系统被分成两部分，每部分都有一半的处理器或者节点。在这两部份之间能同时发生多少通信呢？88环的等分宽度89Figure 2.9一个二维环面网格的等分90Figure 2.10定义(Definitions)n带宽 n链路的带宽(bandwidth)是指它传输数据的速度。通常用兆位每秒或者兆字节每秒来表示.n等分带宽n等分带宽(bisection bandwidth)通常用来衡量网络的质量。它与等分宽度类似。但
28、是，等分带宽不是计算连接两个等分之间的链路数，而是计算链路的带宽。91全相连网络n理想的直接互连网络是全相连网络，即每个交换器与每一个其他的交换器直接连接。但是，为节点数目较多的系统构建这样的互连网络是不切实际的92Figure 2.11bisection width = p2/4impractical超立方体n超立方体是一种已经用于实际系统中的高度互连的直接互连网络。n递归构建:n一维超立方体是有两个处理器的全互连系. n二维超立方体是由两个一维超立方体组成，并通过“相应”的交换器互连. n相似地，三维超立方体由两个二维超立方体构建93超立方体94Figure 2.12one-three-d
29、imensionaltwo-超立方体n维度为d的超立方体有p=2d个节点，并且在d维超立方体中，每个交换器与一个处理器和d个交换器直接连接。这样的超立方体的等分宽度是p/2，所以它比环或者环面网格连接性更高，但需要更强大的交换器，因为每个交换器必须支持1+d=1+log2(p)条连线，而二维环面网格的交换器只需要5条连线。 所以构建一个p个节点的超立方体互连网络比构建一个二维环面网格更昂贵。95间接互连网络n间接互连为直接互连提供了一个替代的选择。在间接互连网络中，交换器不一定与处理器直接连接。它们通常由一些单向连接和一组处理器组成，每个处理器有一个输入链路和一个输出链路，这些链路通过一个交换
30、网络连接。n交叉开关矩阵和omega网络是间接网络中相对简单的例子。96一个通用的间接网络97Figure 2.13交叉开关互连网络98Figure 2.14交叉开关矩阵通过单向链路共享分布式内存omega网络nomega网络比交叉开关矩阵便宜。omega网络使用了1/2plog2（p）个交换器， 每个交换器是一个22交叉开关矩阵交换器，所以总共使用了2plog2(p)个交换器，而交叉开关矩阵使用p2个交换器n一个pp大小的交叉开关矩阵的等分宽度是p，而一个omega网络的等分宽度是p/2。99思考题n请写出不同的分布式内存互连形式的总链路数的表达式。100互连网络互连网络节点数节点数链路数链
31、路数环P二维环面网格p=q2全互连网络p超立方体p=2d交叉开关矩阵pomega网络p=2d101思考题na.除了没有循环链接（“wraparound” link）， 平面网格（planar mesh）和二维环面网格(toroidal mesh)是相似的。请问一个平面网格的等分宽度是多少？nb.三维网格与平面网格是相似的，除了三维网格拥有深度这个特性外。请问一个三维网格的等分宽度是多少？102na. 假设节点数p = q q ，则等分宽度是qnb.假设节点数p = q q q ，则等分宽度是q q103思考题na. 请画出一个四维超立方体结构。nb. 请用超立方体的归纳定义来解释为何超立方体的
32、等分宽度为p/2。104105 由于d维的超立方体有2d个节点，我们需要剪掉2d个链路. 而 (d + 1)-维的超立方体有p=2d+1个节点, 则2d= p/2更多的定义n当传送数据时，我们关心数据到达目的地需要花多少时间.n延迟（latency）n延迟是指从发送源开始传送数据到目的地开始接收数据之间的时间.n带宽(bandwidth)n带宽是指目的地在开始接收数据后接收数据的速度.106107消息传送的时间= l + n / b延时 (秒)带宽 (字节每秒)消息的长度(字节)Cache 一致性108nCPU Cache是由系统硬件来管理的，程序员对它不能进行直接的控制.Figure 2.1
33、7假如共享内存系统中有两个核，每个核有各自私有的数据Cache，见图2-17Cache 一致性109y0的内存区域会最终得到值2，y1的内存区域会得到值6，z1 = ?x是一个共享变量并初始化为2，y0是核0私有的，y1和z1是核1私有的Cache 一致性nz1会获得什么值就不是很清楚了。n第一感觉可能是，既然核0在z1赋值前将x更新为7，所以z1可以得到47=28。n但是，在时间0时，x已经在核1的Cache中。除非出于某些原因，x清除出核0的Cache，然后再重新加载到核1的Cache中；若没有上述情况，通常还是会使用原来的值x=2，而z1也会得到42=8。n有两种主要的方法来保证Cach
34、e的一致性：监听Cache一致性协议和基于目录的Cache一致性协议110监听Cache一致性协议n监听协议的想法来自于基于总线的系统：当多个核共享总线时，总线上传递的信号都能被连接到总线的所有核“看”到n当核0更新它Cache中x的副本时，如果它也将这个更新信息在总线上广播，并且假如核1正在监听总线，那么它会知道x已经更新了，并将自己Cache中的x的副本标记为非法的。 这就是监听Cache一致性协议大致的工作原理111基于目录的Cache一致性协议n目录存储每个内存行的状态。一般地，这个数据结构是分布式的，在我们的例子中，每个核/内存对负责存储一部分的目录。这部分目录标识局部内存对应高速缓
35、存行的状态。n当一个高速缓存行被读入时，如核0的Cache，与这个高速缓存行相对应的目录项就会更新，表示核0有这个行的副本。 当一个变量需要更新时，就会查询目录，并将所有包含该变量高速缓存行置为非法。112并行软件n通常，在运行共享内存系统时，会启动一个单独的进程，然后派生（folk）出多个线程。所以当我们谈论共享内存程序时，我们指的是正在执行任务的线程。n另一方面，当我们运行分布式内存程序时，我们使用的是多个处理器，所以我们指的是正在执行任务的进程。113单程序多数据流(SPMD)nSPMD程序不是在每个核上运行不同的程序，相反，SPMD程序仅包含一段可执行代码，通过使用条件转移语句，可以让
36、这一段代码在执行时表现得像是在不同处理器上执行不同的程序。114if (Im thread/process i) do this;else do that;SPMDnSPMD程序能够实现任务并行，也能够实现数据并行，比如115进程或线程的协调n只有在极少数的情况下，获取好的并行性能是容易的。例如，假设有两个数组，我们想要将它们相加116double xn, yn;for (i = 0; i my_val = %dn , my_rank , my_x ) ;. . .Thread 0 my_val = 7Thread 1 my_val = 19Thread 1 my_val = 19Thread
37、 0 my_val = 7因为线程独立执行并且独立地与操作系统交互，执行一个线程完成一段语句所花的时间在不同次的执行也是不同，所以语句执行的顺序是不能预测的。非确定性n当线程或者进程尝试同时访问一个资源时，这种访问会引发错误，我们经常说程序有竞争条件（race condition），因为线程或者进程处于竞争状态下。n举个例子。假设每个线程计算一个int型整数，这个int型整数存储在私有变量my_val中。假设想要将my_val的值加到共享内存的x位置中，x初始化为0。两个线程都要执行下面的代码：123非确定性124my_val = Compute_val ( my_rank ) ;x += m
38、y_val ;在这个例子中，线程竞争执行x+=my_val。在这种情况下，除非一个线程在另一个线程开始前，计算完成x+=my_val，结果才是正确的。非确定性n一次只能被一个线程执行的代码块称为临界区(critical section)，通常是程序员的责任来保证互斥地访问临界区。换句话说，我们需要保证如果一个线程在临界区中执行代码，其他线程需要被排除在临界区外。n保证互斥执行的最常用机制是互斥锁（mutual exclusion clock），或者互斥量(mutex)，或者锁(lock)。因此，为了保证代码正常运行，我们必须修改代码为125非确定性n这保证了每次只有一个线程执行语句x+=my_
39、val。 这段代码在线程上没有施加任何预定的顺序。或者线程0或者线程1能够先执行x+=my_val。126my_val = Compute_val ( my_rank ) ;Lock(&add_my_val_lock ) ;x += my_val ;Unlock(&add_my_val_lock ) ;忙等待n可以用忙等待来替代互斥量的方式n在忙等待（busywaiting）时，一个线程进入一个循环，这个循环的目的只是测试一个条件。在我们的例子中，假设共享变量ok_for_1初始化为false，下面的代码能够保证只有在线程0将ok_for_1置为ture 后，线程1才能更新x：127忙等待12
40、8my_val = Compute_val ( my_rank ) ;i f ( my_rank = 1) while ( ! ok_for_1 ) ; /* Busywait loop */x += my_val ; /* Critical section */i f ( my_rank = 0) ok_for_1 = true ; /* Let thread 1 update x */分布式内存程序n在分布式内存程序中，各个核能够直接访问自己的私有内存。目前已经有了许多可以使用的分布式内存编程API。但是，最广泛使用的是消息传递。n分布式内存程序通常执行多个进程而不是多个线程。这是因为在分
41、布式内存系统中，典型的“执行的线程”是在独立的CPU中独立的操作系统上运行的，目前还没有软件架构可以启动一个简单的“分布式”进程，使该进程能在系统中的各个节点上再派生出更多的线程来。129消息传递(message-passing)n消息传递的API（至少）要提供一个发送和一个接收函数。进程之间通过它们的序号（rank）互相识别。序号的范围从0p-1，其中p表示进程的个数。n例如，进程1（也可称为1号进程）可以使用下面的伪代码向进程0发送消息：130消息传递(message-passing)131char message 1 0 0 ;. . .my_rank = Get_rank ( ) ;i
42、 f ( my_rank = 1) sprintf ( message , Greetings from process 1 ) ; Send ( message , MSG_CHAR , 100 , 0 ) ; e l s e i f ( my_rank = 0) Receive ( message , MSG_CHAR , 100 , 1 ) ; printf ( Process 0 Received: %sn , message ) ;输入和输出n在分布式内存程序中，只有进程0能够访问stdin。在共享内存程序中，只有主线程或者线程0能够访问stdin。n在分布式内存和共享内存系统中，所
43、有进程/线程都能够访问stdout和stderr。132输入和输出n因为输出到stdout的非确定性顺序，大多数情况下，只有一个进程/线程会将结果输出到stdoutn但输出调试程序的结果是个例外，在这种情况下，允许多个进程/线程写stdout。调试程序输出在生成输出结果时，应该包括进程/线程的序号或者进程标识符133输入和输出n只有一个进程/线程会尝试访问一个除stdin、stdout或者stderr外的文件。所以，例如，每个进程/线程能够打开自己私有的文件进行读、写，但是没有两个进程/线程能打开相同的文件。134135性能（Performance）加速比136n核的数目= pn串行运行时间=
44、 Tserialn并行运行时间= TparallelTparallel = Tserial / p线性加速比（linear speedup）并行程序的加速比(speedup)n实际上，我们不可能获得线性加速比，因为多个进程/线程总是会引入一些代价。例如，共享内存程序通常都有临界区，需要使用一些互斥机制，如互斥量。所以，我们定义并行程序的加速比(speedup)是：137Tserial TparallelS = 并行程序的效率(Efficiency)nS/p的值，有时也称为并行程序的效率。如果替换公式中的S，可以看到效率可以表示为：138E = Tserial TparallelS p = p
45、= Tserial p Tparallel.例子加速比和效率139Tparallel 、 S、E依赖于p，即进程或者线程的数目例子问题规模与加速比和效率140Tparallel 、 S、E依赖于p，即进程或者线程的数目在这个例子中，我们可以看到当问题的规模变大时，加速比和效率增加；当问题的规模变小时，加速比和效率降低。开销的影响n许多并行程序将串行程序的任务分割开来，在进程/线程之间分配，并增加了必需的“并行开销”，如互斥或通信。因此，如果用Toverhead表示并行开销，那么141Tparallel = Tserial / p + Toverhead阿姆达尔定律（Amdahls law）n大
46、致上，除非一个串行程序的执行几乎全部都并行化，否则，不论有多少可以利用的核，通过并行化所产生的加速比都会是受限的。142例子143n假设，一个串行程序中，可以并行化其中的90%n进一步假设，并行化是“理想”的，也就是说，如果使用p个核，则程序可并行化部分的加速比就是pnTserial = 20 秒n可并行部分（即90%的部分）的运行时间就是0.9 x Tserial / p = 18 / p例子（续）144n不可并行化部分的运行时间为n程序并行版本的全部运行时间为0.1 x Tserial = 2Tparallel = 0.9 x Tserial / p + 0.1 x Tserial = 1
47、8 / p + 2例子（续）1450.9 x Tserial / p + 0.1 x TserialTserialS =18 / p + 220加速比可扩展性n粗略地讲，如果一个技术可以处理规模不断增加的问题，那么它就是可扩展的。n如果在增加进程/线程的个数时，可以维持固定的效率，却不增加问题的规模，那么程序称为强可扩展的（strongly scalable）。n如果在增加进程/线程个数的同时，只有以相同倍率增加问题的规模才能使效率值保持不变，那么程序就称为弱可扩展的（weakly scalable）。146思考题假定Tserialn， Tparallel =n/p+log2(p)，时间单位为
48、毫秒。如果以倍率k增加p，那么为了保持效率值的恒定，需要如何增加n？请给出公式。该并行程序是可扩展的吗？147148计时n当你在阅读一篇讲述并行程序运行时间的文章时，文章中的运行时间通常指的是“墙上时钟”时间。这个时间指的是代码从开始执行到执行结束的总耗费时间，这可能是我们比较关心的。149计时150theoretical functionMPI_Wtimeomp_get_wtime例如，MPI中的MPI_Wtime函数，共享内存编程OpenMP API中的函数是omp_get_wtime。这两个函数返回的都是墙上时钟时间，而不是CPU时间。Get_current_time()是一个虚构的函数
49、，在实际的程序中，该函数的使用取决于具体的API计时n当我们对并行程序计时时，下面的代码段可能会被多个进程/线程执行，这将导致最后输出p个运行时间。151然而，我们通常感兴趣的都是单个时间，即从第一个进程/线程开始执行，到最后一个进程/线程结束之间花费的时间计时152153并行程序设计Parallel program designFoster方法n1. 划分（partitioning）。将要执行的指 令和数据按照计算部分拆分成多个小任务。这一步的关键在于识别出可以并行执行的任务。154Foster方法n2. 通信（communication）。确定上一步所识别出来的任务之间需要执行那些通信。1
50、55Foster方法n3. 凝聚或聚合（agglomeration or aggregation）。将第一步所确定的任务与通信结合成更大的任务。n例如，如果任务A必须在任务B之前执行，那么将它们聚合成一个简单的复合任务可能更为明智。156Foster方法n4. 分配（mapping）。将上一步聚合好的任务分配到进程/线程中。这一步还要使通信量最小化，使各个进程/线程所得到的工作量大致均衡。157示例 - 直方图158n1.3,2.9,0.4,0.3,1.3,4.4,1.7,0.4,3.2,0.3,4.9,2.4,3.1,4.4,3.9,0.4,4.2,4.5,4.9,0.9串行程序 - 输入n
