高性能科学计算理论和方法课件：第三章PPT.ppt

1、用MPI进行分布式内存编程 分布式内存系统共享内存系统Hello World! (a classic)标注MPI进程n在并行编程中，将进程按照非负整数来进行标注是非常常见的。n如果有p个进程，则这些进程将被编号为0，1，2， ，p-1。n第一个MPI程序MPI程序n首先，这是一个C语言程序， 它包含了C语言的标准头文件stdio.h和string.h，它还有一个像其他C语言程序一样的main函数。n包含了mpi.h头文件。头文件包括了MPI函数的原形、宏定义、类型定义等，它还包括了编译MPI程序所需要的全部定义与声明。n所有MPI定义的标识符都由字符串MPI_开始。下划线后的第一个字母大写，表

2、示函数名和MPI定义的类型。MPI定义的宏和常量的所有字母都是大写的，这样可以区分什么是MPI定义的，什么是用户程序定义的。MPI的组成nMPI_Initn告知MPI系统进行所有必要的初始化设置.nMPI_Finalizen告知MPI系统MPI已经使用完毕，为MPI而分配的任何资源都可以释放了.MPI基本框架通信子n在MPI中，通信子（communicator）指的是一组可以互相发送消息的进程集合nMPI_Init的其中一个目的，是在用户启动程序时，定义由用户启动的所有进程所组成的通信子。这个通信子称为MPI_COMM_WORLD通信子通信子的进程数my rank (正在调用的进程在通信子中的

3、进程号)单程序多数据流(SPMD)n单程序多数据流（Single Program，Multiple Data，SPMD）n注意，我们刚才编译的是单个程序，而不是为每个进程编译不同的程序.n0号进程本质上做的事情与其他进程不同.n当其他进程生成和发送消息时，它负责接收消息并打印出来.nif-else语句使得我们的程序是SPMD的.通信n在第17行和第18行中，除了0号进程外，每个进程都生成了一条要发送给0号进程的消息n第19行和第20行代码将消息发送给0号进程。另一方面，0号进程只是用printf函数简单地将消息打印出来，然后用一个for循环接收并打印由1、2、comm_sz-1号进程发送来的消

4、息n第24行和第25行接收由q号进程发送来的消息，其中，q=1、2、comm_sz-1。通信发送消息前三个参数，msg_buf_p、msg_size和msg_type定义了消息的内容。剩下的参数，dest、tag和communicator定义了消息的目的地。通信发送消息n我们注意到，字符串greeting的大小与msg_size和msg_type所指定的消息的大小并不相同。例如，每条消息的长度为31个字符，但我们分配长度为100个字符的缓冲区来存储greeting字符串。当然，发送消息的大小必须小于或等于缓冲区的大小。通信发送消息n第四个参数dest指定了要接收消息的进程的进程号。第五个参数t

5、ag是个非负int型，用于区分看上去完全一样的消息。通信发送消息nMPI_Send的最后一个参数是一个通信子。所有涉及通信的MPI函数都有一个通信子参数。数据类型通信接收消息前三个参数指定了用于接收消息的内存：msg_buf_p指向内存块，buf_size指定了内存块中要存储对象的数量，buf_type说明了对象的类型。后面的三个参数用来识别消息消息匹配MPI_Sendsrc = qMPI_Recvdest = rrq接收消息n接收者可以在不知道以下信息的情况下接收消息:n消息中的数据量,n消息的发送者,n或者消息的标签.status_p参数MPI_SOURCEMPI_TAGMPI_ERROR

6、MPI_Status*MPI_Status* status;status.MPI_SOURCEstatus.MPI_TAG能接收多少数据？MPI_Get_count(&status, recv_type, &count)MPI_Send和MPI_Recv的语义n当我们将消息从一个进程发送到另一个进程时，会发生什么？一般来说，发送进程组装消息，例如，它为实际要发送的数据添加“信封”信息。n一旦消息组装完毕，如第2章所说，有两种可能性：发送进程可以缓冲消息，也可以阻塞(block)。MPI_Send和MPI_Recv的语义nMPI_Send的精确行为是由MPI实现所决定的n典型的实现方法有一个默认

7、的消息“截止”大小（“cutoff” message size）。如果一条消息的大小小于“截止”大小，它将被缓冲；如果大于截止大小，那么MPI_Send函数将被阻塞。n与MPI_Send不同，MPI_Recv函数总是阻塞的，直到接收到一条匹配的消息。潜在的陷阱n如果一个进程试图接收消息，但没有相匹配的消息，那么该进程将会被永远阻塞在那里，即进程悬挂n如果调用MPI_Send发生了阻塞，并且没有相匹配的接收，那么发送进程就悬挂起来用MPI来实现梯形积分法梯形积分法梯形积分法如果称最左边的端点为x0，最右边的端点为xn，则有：串行程序的伪代码并行化梯形积分法n回想一下，可以用四个基本步骤去设计一个

8、并行程序：n1）将问题的解决方案划分成多个任务。n2）在任务间识别出需要的通信信道。n3）将任务聚合成复合任务。n4）在核上分配复合任务。梯形积分法的任务和通信n对于梯形积分法，我们可以识别出两种任务：一种是获取单个矩形区域的面积，另一种是计算这些区域的面积和。然后利用通信信道将每个第一种任务与一个第二种任务相连接并行伪代码/我们简单地假设comm_sz能整除n，则这个程序的伪代码如下所示注意n注意，我们对标识符的选择，是为了区分局部变量与全局变量。局部变量只在使用它们的进程内有效。梯形积分法程序中的例子有：local_a、local_b和local_n。如果变量在所有进程中都有效，那么该变量

9、就称为全局变量。该程序中的例子有：变量a、b和n。First version (1)First version (2)First version (3)I/O处理n现有版本的并行梯形积分法程序有个严重的不足：它只能用1024个梯形计算0,3区间内的积分。与简单地输入三个新值相比，编辑和重新编译代码这种做法的工作量相当大。因此我们需要解决用户输入的问题。当讨论并行程序输入的同时，我们也一并将输出问题考虑进来。输出n在“问候”程序和梯形积分法程序中，假定0号进程将结果写到标准输出stdout，即它对printf函数的调用是我们所希望的行为n几乎所有的MPI实现都允许MPI_COMM_WORLD里的

10、所有进程都能访问标准输出stdout和标准错误输出stderr，所以，大部分的MPI实现都允许所有进程执行printf和fprintf(stderr，)。输出n但是，大部分的MPI实现并不提供对这些I/O设备访问的自动调度。也就是说，如果多个进程试图写标准输出stdout，那么这些进程的输出顺序是无法预测的，甚至会发生一个进程的输出被另一个进程的输出打断的情况。n例如，假设运行一个MPI程序，每个进程只是简单地打印一条消息输出例子每个进程只是简单地打印一条消息.Running with 6 processesunpredictable output输出n这一现象产生的原因是MPI进程都在相互“

11、竞争”，以取得对共享输出设备、 标准输出stdout的访问。我们不可能预测进程的输出是以怎样的顺序排列。这种竞争会导致不确定性，即每次运行的实际输出可能会变化。输入n与输出不同，大部分的MPI实现只允许MPI_COMM_WORLD中的0号进程访问标准输入stdin。n例如，在梯形积分法的并行程序中的Get_input函数，0号进程只是简单地读取a、b和n的值，并将这三个值发送给其他每个进程。除了0号进程发送数据给其他进程、其他进程只是接收数据外读取用户输入的函数读取用户输入的函数n为了使用该函数，我们可以在主程序中简单地插入对该函数的调用。要注意的是，我们必须在初始化my_rank和comm_

12、sz后，才能调用该函数：集合通信树形结构通信n想一想我们编写的梯形积分法程序，我们就会发现几件可以提高程序性能的事。其中最明显的就是在每个进程都完成了它那部分积分任务之后的“全局求和”（global sum）。n正如我们在第1章中见到的那样，可以使用一棵像图3-6所描绘的二叉树结构。树形结构通信树形结构通信n在图3-6中，一开始1号进程、3号进程、5号进程、7号进程将它们的值分别发送给0号进程、2号进程、4号进程、6号进程。然后0号进程、2号进程、4号进程、6号进程将接收到的值加到它们自己原有的值上，整个过程重复两次：n1）a. 2号进程和6号进程将它们的新值分别发送给0号进程和4号进程。n

13、b. 0号进程和4号进程将接收到的值加到它们的新值上。n2）a. 4号进程将它最新的值发送给0号进程。n b. 0号进程将接收到的值加到它最新的值上。另外的配对方式MPI_Reducen由于存在各种可能性，指望MPI程序员都能编写出最佳的全局求和函数是不合理的。所以，MPI中包含了全局求和的实现，以便帮助程序员摆脱无止境的程序优化。n“全局求和函数”需要通信。然而，与MPI_Send函数和MPI_Recv函数两两配对不同，全局求和函数可能会涉及两个以上的进程。事实上，在梯形积分法程序中，它涉及MPI_COMM_WORLD中所有的进程。MPI_Reducen在MPI里，涉及通信子中所有进程的通信

14、函数称为集合通信（collective communication）。n为了区分集合通信与类似MPI_Send和MPI_Recv这样的函数，MPI_Send和MPI_Recv通常称为点对点通信（pointtopoint communication）。MPI_Reducen全局求和函数只是集合通信函数类别中的一个特殊例子而已。例如，我们可能并不是想计算分布在各个进程上的comm_sz值的总和，而是想知道最大值或最小值，或者总的乘积，或者其他许多可能情况中的任何一个所产生的结果nMPI对全局求和函数进行概括，使这些可能性中的任意一个都能用单个函数来实现：MPI_Reducen这个函数的关键在于第5

15、个参数，operator。它的类型为MPI_Op，是一个像MPI_Datatype和MPI_Comm一样的预定义MPI类型。这个类型有多个预定义值MPI_ReduceMPI_Reducen在梯形积分法程序中，我们要使用的运算符为MPI_SUM，将这个值赋给operator参数后，就可以将梯形积分法程序中的第1828行的代码用单个函数调用代替：MPI_Reducen如果count参数大于1，那么MPI_Reduce函数可以应用到数组上，而不仅仅是应用在简单的标量上。下面的代码可以用于一组N维向量的加法，每个进程上有一个向量：集合通信vs.点对点通信n在通信子中的所有进程都必须调用相同的集合通信函

16、数。n例如，试图将一个进程中的MPI_Reduce调用与另一个进程的MPI_Recv调用相匹配的程序会出错，此时程序会被悬挂或者崩溃。集合通信vs.点对点通信n每个进程传递给MPI集合通信函数的参数必须是“相容的”。n例如，如果一个进程将0作为dest_process的值传递给函数，而另一个传递的是1，那么对MPI_Reduce调用所产生的结果就是错误的，程序可能被悬挂起来或者崩溃。集合通信vs.点对点通信n参数output_data_p只用在dest_process上。n然而，所有进程仍需要传递一个与output_data_p相对应的实际参数，即使它的值只是NULL。集合通信vs.点对点通信

17、n点对点通信函数是通过标签和通信子来匹配的。n集合通信函数不使用标签，只通过通信子和调用的顺序来进行匹配。例如，看看表3-3所示的MPI_Reduce调用例子(1)假设每个进程调用MPI_Reduce函数的运算符都是MPI_SUM，那么目标进程为0号进程。粗略地看一下整张表，在两次调用MPI_Reduce后，b的值是3，而d的值是6。例子(2)n但是，内存单元的名字与MPI_Reduce的调用匹配无关，函数调用的顺序决定了匹配方式。n所以b中所存储的值将是1+2+1=4，d中存储的值将是2+1+2=5。别名问题n我们也许会冒风险使用同一个缓冲区同时作为输入和输出调用MPI_Reduce。例如，

18、我们想求得所有进程里x的全局总和，并且将x的结果放在0号进程里，也许会试着这样调用：别名问题n但在MPI里，这种调用方式是非法的。它的结果是不可预测的：它可能产生一个错误结果，也可能导致程序崩溃，但也可能产生正确的结果。n它之所以是非法的，主要原因是它涉及输出参数的别名。两个参数如果指向的是同一块内存，它们之间就存在别名问题。MPI禁止输入或输出参数作为其他参数的别名。MPI_Allreducen梯形积分法程序中，我们只打印结果，所以只用一个进程来得到全局总和的结果是很自然的。n然而，不难想象这样一个情况，即所有进程都想得到全局总和的结果，以便可以完成一个更大规模的计算。n例如，用一棵树来计算

19、全局总和，我们可以通过“颠倒”（reverse）整棵树来发布全局总和MPI_AllreducenMPI提供了一个MPI_Reduce的变种，可以令通信子中的所有进程都存储结果：参数表其实与MPI_Reduce的是相同的，除了没有dest_process这个参数，因为所有进程都能得到结果Broadcastn在梯形积分法程序中，如果用树形结构的通信来代替0号进程的循环接收消息，从而提升全局求和的性能，那么我们应该也可以将类似的方法用于输入数据的发布。n事实上，如果简单地在树形全局求和里“颠倒”通信，我们可以得到如图3-10所示的树形结构通信图，并且能够将这个结构用于输入数据的发布。A tree-s

20、tructured broadcast.Broadcastn在一个集合通信中，如果属于一个进程的数据被发送到通信子中的所有进程，这样的集合通信就叫做广播（broadcast）。MPI的广播函数：进程号为source_proc的进程将data_p所引用的内存内容发送给了通信子comm中的所有进程。Broadcastn修改Get_input函数，用MPI_Bcast函数，来取代MPI_Send和MPI_Recv函数。Broadcastn对MPI_Bcast函数，data_p参数在进程号为source_proc的进程中是一个输入参数，在其他进程中是一个输出参数。n因此，当集合通信函数中的某个参数被标

21、记为输入/输出（in/out）时，意味着可能在某些进程中它是输入参数，而在其他进程中是一个输出参数。数据分发n如果我们想编写一个程序，用于计算向量和：用串行加法来计算向量求和如何用MPI实现这个程序呢？n计算工作由向量的各个分量分别求和组成，所以我们可能只是指定各个任务求和的对应分量。这样，各个任务间没有通信，向量的并行加法问题就归结为聚合任务以及将它们分配到核上。n如果分量的个数为n，并且我们有comm_sz个核或者进程，那么可以简单地将连续local_n个向量分量所构成的块，分配到每个进程中。向量的划分n表3-4的左4列显示了当n=12且comm_sz=3时的例子。这种做法通常称为向量的块

22、划分。向量的划分n向量块划分的另一个方法是循环划分。在循环划分中，我们用轮转的方式去分配向量分量。0号进程得到了向量的0号分量，1号进程得到了1号分量，2号进程得到了2号分量，0号进程又得到了3号分量，以此类推。向量的划分n第三种划分方法叫块-循环划分。基本思想是，用一个循环来分发向量分量所构成的块，而不是分发单个向量分量。所以首先要决定块的大小。向量求和的并行实现n一旦决定如何划分向量，就能很容易地编写向量的并行加法函数：每个进程只要简单地将它所分配到的向量分量加起来。散射n现在假设我们想测试向量加法函数。先读取向量的维度，然后读取向量x和向量y是很方便的。n如何分配向量分量：0号进程读入向

23、量，然后将它们广播给其他进程？散射n但这种方法很浪费。如果有10个进程，向量有1万个分量，那么每个进程都需要为1万个分量的向量分配存储空间，但每个进程只在含有1000个分量的子向量上进行操作。n例如，假设我们使用块划分法，那么如果0号进程只是将10001999号分量发送给1号进程，将20002999号分量分配给2号进程，以此类推。用这种方法，19号进程将只需要为它们实际使用的向量分量分配存储空间。散射n因此，0号进程读入整个向量，但只将分量发送给需要分量的其他进程。散射n如果通信子comm包含comm_sz个进程，那么MPI_Scatter函数会将send_buf_p所引用的数据分成comm_

24、sz份，第一份给0号进程，第二份给1号进程，第三份给2号进程，以此类推。n例如，假如我们使用块划分法，并且0号进程已经将一个有n个分量的向量整个读入send_buf_p中，则0号进程将得到第一组local_n=n/comm_sz个分量，1号进程将得到下一组local_n个分量，以此类推。散射n每个进程应该将它本地的向量作为recv_buf_p参数的值，将local_n作为recv_count参数的值。send_type和recv_type参数的值都应该是MPI_DOUBLE，src_proc参数的值应该是0。n注意：send_count参数的值也应该是local_n，因为send_count参

25、数表示的是发送到每个进程的数据量，而不是send_buf_p所引用的内存的数据量。一个读取分发向量的函数聚集n除非看见向量加法的结果，否则测试程序是无用的。所以我们需要编写一个可以打印分布式向量的函数。n这个函数将向量的所有分量都收集到0号进程上，然后由0号进程将所有分量都打印出来。这个函数中的通信由MPI_Gather来执行聚集在0号进程中，由send_buf_p所引用的内存区的数据存储在recv_buf_p的第一个块中，在1号进程中，由send_buf_p所引用的内存区的数据存储在recv_buf_p的第二个块里，以此类推分布式向量打印函数分布式向量打印函数分布式向量打印函数nrecv_c

26、ount指的是每个进程接收到的数据量，而不是所有接收到的数据量的总和。n使用MPI_Gather函数的限制与使用MPI_Scatter函数的限制是类似的：只有在使用块划分法，并且每个块的大小相同的情况下，打印函数才能正确运行。全局聚集n如何编写一个MPI程序，完成矩阵和向量的相乘。n如果A=(aij)是一个mn的矩阵，x是一个具有n个分量的向量，那么y=Ax就是一个有m个分量的向量。我们可以用A的第i行与x的点积来求取y的第i个分量：串行矩阵乘法的伪代码C语言数组nC语言的程序员常常用一维数组来“模拟”二维数组。最常见的做法是将一行内容存储在另一行后面。例如，二维数组，stored asC语言

27、数组n这个例子中，如果我们从0开始对行和列进行计数，那么存储在二维数组中的第2行第1列的元素（即9），它在一维数组中的位置为24+1=9。n更为一般的情况是，如果数组有n列，则当使用这种数组结构时，存储在第i行第j列的元素在一维数组中的位置就为in+j。串行矩阵-向量乘法n使用这种一维数组结构，可以得到程序3-11中所示的C语言函数并行矩阵-向量乘法n如何并行化该程序? n一个单独的任务可以是A的一个元素与x的一个分量相乘，并且将这个乘积加到y的一个分量上去。n如果将yi分配给q号进程，将A的第i行也分配给q号进程会很方便，也就是说，对A进行行划分。我们可以用块划分法、循环划分法或块-循环划分

28、法来对行进行划分。并行矩阵-向量乘法nA进行行划分可以使yi的计算包含所需要的A中的元素，所以对y也应该采用块划分。即，如果A的第i行分配给了q号进程，y的第i个分量也应该分配给q号进程。n现在，yi的计算包含了A的第i行中所有的元素，以及x的所有分量，我们可以简单地将所有x的分量分发给每个进程，来使通信量最小化。然而，通常假设对x的划分与对y的划分方法是相同的。并行矩阵-向量乘法n所以，如果x有一个块划分，我们该如何安排使得在执行下列循环前就使每个进程都能访问x中的所有分量呢？n使用已经熟悉的集合通信，我们可以在执行一次MPI_Gather调用后，执行一次MPI_Bcast调用。并行矩阵-向

29、量乘法n在所有可能的情况下，这会涉及两个树形结构的通信，用蝶形通信结构可能会取得更好的效果。所以，MPI提供了这样的一个单独的函数：这个函数将每个进程的send_buf_p内容串联起来，存储到每个进程的recv_buf_p参数中。通常，recv_count指每个进程接收的数据量。所以大部分情况下，recv_count的值与send_count的值相同。并行矩阵向量乘法MPI的派生数据类型n在几乎所有的分布式内存系统中，通信比本地计算开销大很多。例如，从一个节点发送一个double类型的数据到另一个节点，耗费的时间比存储在节点本地内存里的两个double类型数据相加所耗费的时间长很多。n用多条消

30、息发送一定数量的数据，明显比只用一条消息发送等量数据耗时。MPI的派生数据类型n例如，我们可以预料到，下面的这对for循环比单个的发送/接收对要慢得多：MPI的派生数据类型n在MPI中，通过同时存储数据项的类型以及它们在内存中的相对位置，派生数据类型可以用于表示内存中数据项的任意集合。n其主要思想是：如果发送数据的函数知道数据项的类型以及在内存中数据项集合的相对位置，就可以在数据项被发送出去之前在内存中将数据项聚集起来n类似地，接收数据的函数可以在数据项被接收后将数据项分发到它们在内存中正确的目标地址上。MPI的派生数据类型n例如，在梯形积分法程序中，需要调用MPI_Bcast函数三次：一次广

31、播左端点a、一次广播右端点b、一次广播梯形的个数n。n另一种替代方法是：建立一个单独的派生数据类型，该数据类型由两个double类型数据和一个int类型数据组成。这样，只需要调用MPI_Bcast一次。在0号进程中，a、b和n在一次函数调用中被发送出去；而在其他进程中，这些值将在函数调用中被接收。MPI的派生数据类型n正式地，一个派生数据类型是由一系列的MPI基本数据类型和每个数据类型的偏移所组成的。在梯形积分法的例子中，假设在0号进程里变量a、b和n在内存中的位置为如下的地址：那么下面的派生数据类型就可以表示这些数据项：MPI的派生数据类型n每一对数据项的第一个元素表明数据类型，第二个元素是

32、该数据项相对于起始位置的偏移。n假设派生类型从a开始，则a的偏移为0，其他元素的偏移从a的起始位置开始算，偏移量以字节为单位。数据项b距离a的偏移是40-24=16字节，数据项c距离a的偏移是n=48-24=24字节。MPI的派生数据类型n我们可以用MPI_Type_create_struct函数创建由不同基本数据类型的元素所组成的派生数据类型：参数count指的是数据类型中元素的个数，所以在我们的这个例子中，它应该为3。每个数组参数都有count个元素。第一个数组，array_of_blocklengths允许单独的数据项可能是一个数组或者子数组。MPI的派生数据类型n但在我们的例子中，没有

33、元素是数组，所以可以简单地定义：nMPI_Type_create_struct的第三个参数array_of_displacements指定了距离消息起始位置的偏移量，单位为字节。所以有：n为了找到这些值，可以使用MPI_Get_address函数：MPI的派生数据类型n返回的是location_p所指向的内存单元的地址。这个特殊类型的MPI_Aint是整数型，它的长度足以表示系统地址。因此，为了取得array_of_displacements里的各个值，我们可以用下面的代码：MPI的派生数据类型narray_of_datatypes存储的是元素的MPI数据类型，我们可以定义：n在这些初始化工作

34、完成之后，就可以通过函数调用建立新的数据类型：MPI的派生数据类型n在使用通信函数中的input_mpi_t之前，我们必须先用一个函数调用去指定（commit）它：n现在，为了使用new_mpi_t这个新的数据类型，需要在每个进程上调用MPI_Bcast：n在构造新数据类型的过程中，MPI实现可能要在内部分配额外的存储空间。因此，当我们使用新的数据类型时，可以用一个函数调用去释放额外的存储空间：使用派生数据类型的Get_input函数n我们采用上述步骤定义了可以被Get_input函数调用的Build_mpi_type函数。这一新的函数以及修改过的Get_input函数见程序3-13使用派生数

35、据类型的Get_input函数使用派生数据类型的Get_input函数MPI程序的性能评估n接下来，我们分析矩阵-向量乘法程序的性能。n通常，我们不会对程序从开始运行到结束运行所耗费的时间感兴趣。n例如，在矩阵-向量乘法中，我们一般不会对输入矩阵和输出乘积结果所花费的时间感兴趣，而只对实际的乘法运算所花费的时间感兴趣。所以需要修改源代码，加入函数调用，统计从乘法运算开始到结束所经过的时间。计时nMPI提供了这样的一个函数，MPI_Wtime，它返回从过去某一时刻开始所经过的秒数：n对一个MPI代码块进行计时：计时n上述的并行程序会为每个进程报告一次时间，但我们需要获得一个总的单独时间。n理想情

36、况是，所有的进程同时开始运行矩阵乘法，当最后一个进程完成运算时，能获取从开始到最后一个进程结束之间的时间开销。换句话讲，并行时间取决于“最慢”进程花费的时间。计时n这一时间并不是完全精确的，因为我们无法保证所有进程都开始于同一个时间点，但也足够接近理想的衡量时间。nMPI的集合通信函数MPI_Barrier能够确保同一个通信子中的所有进程都完成调用该函数之前，没有进程能够提前返回。它的语法是：计时n下面这段代码可以用来对一段MPI程序进行计时并报告运行时间：矩阵-向量乘法程序的计时结果comm_sz为1的时间表示在分布式内存系统中单个核上运行串行程序的时间计时结果n如果固定comm_sz的值，

37、增大n，那么矩阵的大小和程序的运行时间也会增加。n进程数相对较少时，n增大1倍就会使运行时间变为原来的4倍，然而当进程数很多时，此公式就不成立了。计时结果n如果我们固定n、增大comm_sz，那么运行时间会减少。事实上，对于值很大的n来说，进程数加倍大约能减少一半的运行时间。n然而，对值小的n，增大comm_sz获得的效果甚微，例如，当n=1024时，进程数从8增大到16后，运行时间没有出现变化。计时结果n串行程序的运行时间与对应的并行程序的运行时间有共同的联系。回忆一下，n在MPI程序中，并行计算的开销一般来自于通信，还受到问题集的规模和进程数的影响。计时结果n并行程序在进行本地矩阵-向量乘

38、法前，需要调用MPI_Allgather函数。在我们的例子中：n根据对计时数据的观察发现，p值较小且n值较大时，公式中起主导地位的是Tserial (n)/pn当n值较小、p值较大时，公式中起主导因素的参数是Tallgather加速比n加速比经常用来衡量串行运算和并行运算时间之间的关系，它表示为串行时间与并行时间的比值：nS(n，p)最理想的结果是p。 如果S(n，p)=p，说明拥有comm_sz=p个进程数的并行程序能运行得比串行程序快p倍。这种被我们称为线性加速比的情况事实上很少出现。加速比在p较小、n较大的情况下，我们获得了近似于线性的加速比，然而，当p较大、n较小时，加速比则远远小于p

39、。最差的一种情况是n=1024和p=16时，只得到了2.4的加速比。效率n另外，并行的效率也是评价并行性能的重要指标之一，它其实是“每个进程”的加速比：效率在p较小、n较大的情况下，有近似线性的效率；相反，在p较大、n较小的情况下，远远达不到线性效率。可扩展性n粗略地讲，如果问题的规模以一定的速率增大，但效率没有随着进程数的增加而降低，那么就可以认为程序是可扩展的。可扩展性n试想两个并行程序A和B，假设p2，不考虑问题的规模，程序A的效率是0.75。 另外一个并行程序B，p2且1000n625p，程序B的效率为n/(625p)。n根据我们的“定义”，两个程序都是可扩展的。对于程序A，维持效率所

40、需要的问题规模递增速率为0；而对于程序B来说，如果增加n的速率与增加p一样快，那么就能够维持一个恒定的效率。可扩展性n若程序可以在不增加问题规模的前提下维持恒定效率，那么此程序称为拥有强可扩展性；n当问题规模增加，通过增大进程数来维持程序效率的，称为弱可扩展性。n程序A是前者，程序B是后者，我们的矩阵-向量乘法显然也是弱可扩展性的。并行排序算法n在分布式内存系统上如何实现并行排序算法？“输入”和“输出”分别是什么？n答案取决于需要排序的键值存储在哪。可以在程序开始或结束时，将键值分布在多个进程中，也可以只分配给一个进程。并行排序算法n假设总共有n个键值，p=comm_sz个进程，给每个进程分配

41、n/p个键值（与前面一样，假定n能被p整除）。n开始时，不对哪些键值分配到哪个进程上加以限制，然而在算法结束时： 每个进程上的键值应该以升序的方式存储。 若0qrp，则分配给进程q的每一个键值应该小 于等于分配给进程r的每一个键值。n所以，如果按照进程编号来进行键值排列（即先是进程0的键值，接着进程1的，以此类推），所有的键值就可以按升序排列。串行冒泡排序奇偶交换排序n冒泡排序的一个变种是奇偶交换排序，该算法更加适合并行化。关键在于去耦的比较一交换。n此算法由一系列阶段组成，这些阶段分2种类型。奇偶交换排序n在偶数阶段，比较交换由以下数对执行：n而奇数阶段则由以下数对进行比较交换：例子n开始：

42、5、9、4、3n偶数阶段；比较-交换(5，9)和(4，3)，获得序列5、9、3、4。n奇数阶段：比较-交换(9，3)，获得序列5、3、9、4n偶数阶段：比较-交换(5，3)和(9，4)，获得序列3、5、4、9。n奇数阶段：比较-交换(5，4)，获得序列3、4、5、9。定理n这个例子需要四个阶段来排序四个元素的列表。一般来说，阶段可能会更少些，下面的这个定理保证了我们至多用n个阶段排序n个元素。n定理：设A是一个拥有n个键值的列表，作为奇偶交换排序算法的输入，那么经过n个阶段后，A能够排好序。奇偶交换排序的串行代码并行奇偶交换排序n奇偶交换排序远比冒泡排序适合并行化，因为在一个阶段内所有的比较-

43、交换都能同时进行。n实现Foster方法有很多可能的办法，这里是其中一个：任务与通信n任务：在阶段j结束时确定ai的值n通信：确定ai的值的任务需要与其他确定ai+1或者ai-1的任务进行通信，同时，在阶段j结束时，ai的值需要用来在阶段j+1结束时确定ai的值并行奇偶交换排序n我们注意到：在排序算法开始和结束阶段，给每个进程分配n/p个键值。n假设我们有p=4个进程，n=16个键值，详见表3-8。对分配给每个进程的键值使用快速的串行排序法，如用c语言库的qsort函数对局部链值进行排序。0(偶数)阶段n试着使进程0和进程1交换数据，进程2和进程3交换数据，那么进程0就会有4个比进程1中数据小

44、的元素，而进程2则拥有4个比进程3中数据小的元素，这就是表3-8中第3行的情况。1(奇数)阶段n在阶段1，进程1和进程2交换元素，而进程0和进程3是空闲的。如果进程1有着较小的一些元素，而进程2拥有较大的一些元素，那么就得到表3-8中第4行的情况。2(偶数)阶段3(奇数)阶段并行奇偶交换排序n定理：如果由p个进程运行并行奇偶交换排序算法，则p个阶段后，输入列表排序完毕。n并行算法对于人工计算机来说已足够清晰：计算配对进程n怎么计算配对运行的另一个进程的进程号？当一个进程空闲时，它的配对进程又是什么？常量MPI_PROC_NULLnMPI_PROC_NULL是由MPI库定义的一个常量。在点到点通

45、信中，将它作为源进程或者目标进程的进程号，此时，调用通信函数后会直接返回，不会产生任何通信。MPI程序的安全性n如果进程不是空闲的，我们可以通过调用MPI_Send和MPI_Recv来实现通信：n但这可能会导致程序挂起或者崩溃MPI程序的安全性nMPI标准允许MPI_Send以两种不同的方式实现：简单地将消息复制到MPI设置的缓冲区并返回，或者直到对应的MPI_Recv出现前都阻塞。n此外，许多MPI函数都设置了使系统从缓冲到阻塞间切换的阈值，即相对较小的消息就交MPI_Send缓冲，但对于大型数据就选择阻塞模式。n如果每个进程都阻塞在MPI_Send上，则没有进程会去调用MPI_Recv，此

46、时程序就会死锁或挂起，每个进程都在等待一个不会发生的事件发生。MPI程序的安全性n 1)一般来说，怎么才能说一个程序是安全的？n 2)我们怎样修改并行奇偶交换MPI序的通信过程，使其安全？MPI程序的安全性n要解决第1个问题，我们可以用MPI标准提供的另一个函数MPI_Ssend来代替MPI_Send。n函数MPI_Ssend保证了直到对应的接收开始前，发送端一直阻塞。所以，我们通过将MPI_Send替换为MPI_Ssend来检查程序是否安全。如果输入合适的值和comm_sz，程序没有挂起或者崩溃，那就安全。MPI程序的安全性n第二个问题的解决方法是重构通信。n造成程序不安全的最大因素在于多个

47、进程先同时发送消息，再同时接收消息。我们在配对进程之间的数据交换就是其中一个例子。另一个例子是“环状传递”，每个进程q向进程q+1发送消息，进程comm_sz - 1向进程0发送消息：MPI程序的安全性n我们需要重构这两个通信函数，使一些进程先接收消息再发送消息。例如，可以改成n如果comm_sz是偶数，那么这样的改动会取得很好效果。MPI程序的安全性n当comm_sz是奇数时，这个机制可能是不安全的。n假定comm_sz=5。图3-13显示了事件另一种可能的顺序，实线箭头表明完整的通信，虚线箭头表示该通信正在等待完成。MPI程序的安全性nMPI提供了自己调度通信的方法，我们把这个函数称为MP

48、I_SendrecvMPI程序的安全性n调用一次这个函数，它会分别执行一次阻塞式消息发送和一次消息接收，dest和source参数可以不同也可以相同。n它的有用之处在于，MPI库实现了通信调度，使程序不再挂起或崩溃。我们之前的代码很复杂，需要检查进程号是奇数还是偶数，现在可以替换为调用MPI_Sendrecv函数。并行奇偶交换排序算法的重要内容n我们已经设计了如下所示的并行奇偶排序算法：n从安全性的角度看，可以使用MPI_Sendrecv实现消息的接收和发送：并行奇偶交换排序算法的重要内容n计算partner的方法已知，剩下的就是确认保留哪些键值了。比如说，要保留较小的n/p个键值n方法一：对2n/p个键值进行快速排序n方法二：把两个有序的列表进行合并，一旦找到最小的n/p个键值就退出。Merge_low函数并行奇偶排序算法的运行时间可以看到，如果它运行在单核机器上，它会使用排序局部键值所用的串行算法，即快速排序，而不是奇偶交换排序，后者在单核处理器上的运行时间比前者慢。第三章作业