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

1、用OpenMP进行共享内存编程分布式内存系统OpenMPn与Pthreads 一样，OpenMP是一个针对共享内存并行编程的API。nOpenMP中的“MP”代表“多处理”。nOpenMP是为共享内存系统而设计的：在系统中每个线程都有可能访问所有可访问的内存区域。共享内存系统n当使用OpenMP编程时，我们将系统看做一组核或CPU的集合，它们都能访问主存，如图5-1所示。OpenMP与Pthreadsn尽管OpenMP和Pthreads都是针对共享内存编程的API，但它们有许多本质的不同。nPthreads要求程序员显式地明确每个线程的行为。n相反，OpenMP有时允许程序员只需要简单地声明一

2、块代码应该并行执行，而由编译器和运行时系统来决定哪个线程具体执行哪个任务。OpenMP与PthreadsnPthreads（与MPI一样）是一个能够被链接到C程序的函数库，因此只要系统有Pthreads库，Pthreads程序就能够被任意C编译器使用。n相反，OpenMP要求编译器支持某些操作，所以完全有可能你使用的编译器无法把OpenMP程序编译成并行程序。OpenMP与PthreadsnPthreads更底层，并且提供了虚拟地编写任何可知线程行为的能力。然而，这个功能有一定的代价：每个线程行为的每一个细节都得由我们自己来定义。n相反，OpenMP允许编译器和运行时系统来决定线程行为的一些细

3、节，因此使用OpenMP来编写一些并行行为更容易。但代价是很难对一些底层的线程交互进行编程。预备知识nOpenMP提供“基于指令”的共享内存API。这意味着：在C和C+中，有一些特殊的预处理器指令pragman在系统中加入预处理器指令一般是用来允许不是基本C语言规范部分的行为。n不支持pragma的编译器就会忽略pragma指令提示的那些语句，这样就允许使用pragma的程序在不支持它们的平台上运行。n因此，在理论上，如果你仔细编写一个OpenMP程序，它就能够在任何有C编译器的系统上被编译和运行，而无论编译器是否支持OpenMP。Pragman在C和C+中，预处理器指令以#pragma开头。

4、n与所有的预处理器指令一样，pragma的默认长度是一行，因此如果有一个pragma在一行中放不下，那么新行需要被“转义”前面加一个反斜杠“”。n#pragma后面要跟什么内容，完全取决于正在使用哪些扩展（比如OpenMP）。运行OpenMP程序n应该注意到线程正在竞争访问标准输出，因此不保证输出会按线程编号的顺序出现. / omp_hello 4running with 4 threadsHello from thread 0 of 4Hello from thread 1 of 4Hello from thread 2 of 4Hello from thread 3 of 4Hello f

5、rom thread 1 of 4Hello from thread 2 of 4Hello from thread 0 of 4Hello from thread 3 of 4Hello from thread 3 of 4Hello from thread 1 of 4Hello from thread 2 of 4Hello from thread 0 of 4possibleoutcomes程序n我们来看一下程序5-1中的源代码。n除了指令集合外，OpenMP由一个函数和宏库组成，因此我们通常需要包含一个有原型和宏定义的头文件。OpenMP的头文件是omp.h，程序的第3行包含了它。指

6、定线程数n在Pthreads程序中，我们在命令行里指定线程数，OpenMP程序也经常这么做。n在第9行，使用stdlib.h中的strtol函数来获得线程数。这个函数的语法是：n第一个参数是一个字符串（在我们的例子中，它是命令行参数），最后的参数是字符串所表示的数的基数（在我们的例予中是10（十进制）。我们不使用第二个参数，因此只是传人一个NULL（空）指针。OpenMP pragmasn程序的第11行是第一条OpenMP指令，使用它来提示程序应该启用一些线程。n每个被启动的线程都执行Hello函数，并且当线程从Hello调用返回时，它们应该被终止，即在执行return语句时线程应该被终止。与

7、Pthreads比较n程序的代码上有许多重大的改变。n在Pthreads中，我们必须写许多代码来派生(folk)和合并(join)多个线程：需要为每个线程的特殊结构分配存储空间，需要使用一个for循环来启动每个线程，并使用另一个for循环来终止这些线程。n因此，很明显OpenMP比Pthreads层次更高。OpenMP pragmasnOpenMP的pragma总是以 # pragma omp 开头n在pragma后面的第一条指令是一条parallel指令。n使用parallel是用来表明之后的结构化代码块（也可以称为基本块）应该被多个线程并行执行。结构化代码块n一个结构化代码块是一条c语句或

8、者只有一个入口和一个出口的一组复合c语句，但在这个代码块中允许调用exit函数。n这个定义简单地禁止分支语句进入或离开结构化代码块。parallel指令n最基本的parallel指令可以以如下简单的形式表示：n运行结构化代码块的线程数将由运行时系统决定。但如前面提到的那样，通常会在命令行里指定线程数，因此为parallel指令增加了num_threads子句。子句n在OpenMP中，子句只是一些用来修改指令的文本。nnum_threads子句被添加到parallel指令中，这样就允许程序员指定执行代码块的线程数：注意n要注意的是，程序可以启动的线程数可能会受系统定义的限制。nOpenMP标准并

9、不保证实际情况下能够启thread_count个线程。n然而，目前大部分的系统能够启动数百甚至数千个线程，因此除非你试图启动许多线程，否则一般情况下我们几乎总能够得到需要数目的线程。一些术语n在parallel指令之前，程序只使用一个线程。而当程序开始执行时，线程开始启动。当程序到达parallel指令时，原来的线程继续执行，另外thread_count -1个线程被启动。n在OpenMP语法中，执行并行块的线程集合（原始的线程和新的线程）称为线程组(team)，原始的线程称为主线程(master)，额外的线程称为从线程(slave)。一些术语n每个线程组中的线程都执行parallel指令后的

10、代码块，因此在我们的例子中，每个线程都调用Hello函数。n当代码块执行完时，即在我们的例子中，当线程从Hello调用中返回时，有一个隐式路障。隐式路障n隐式路障意味着完成代码块的线程将等待线程组中的所有其他线程完成代码块.n在我们的例子中，一个已经完成Hello调用的线程将等待线程组中所有其他线程返回。当所有线程都完戍了代码块，从线程将终止，主线程将继续执行之后的代码。n在我们的例子中，主线程将执行第14行的return语句，程序将终止。私有局部变量n因为每个线程有它自己的栈，所以一个执行Hello函数的线程将在函数中创建它自己的私有局部变量。n在我们的例子中，当函数被调用时，通过调用Ope

11、nMP函数omp_get_thread_num和omp_get_num_threads，每个线程将分别得到它的编号或id，以及线程组中的线程数。n线程的编号是一个整数，范围是0、1、thread_count-1。这些函数的语法是：错误检查n为了使代码更为紧凑、可读性更强，我们的程序不做任何错误检查。当然，这是危险的，而且实际上，试图预测错误并对它们进行检查是一个十分好的主意，甚至可以说是必需的。n在这个例子中，首先一定要检查命令行参数的存在，如果存在的话，在调用strtol后应该检查值是否是正的。还要检查被parallel指令实际创建的线程数与thread_count是否一样。错误检查n 第二

12、个潜在问题的来源是编译器。如果编译器不支持OpenMP，那么它将只忽略parallel指令。n然而，试图包含omp.h头文件以及调用omp_get_thread_num和omp_get_num_threads将引起错误。为了处理这些问题，可以检查预处理器宏_OPENMP是否定义。如果定义了，则我们能够包含omp.h并调用OpenMP函数。我们可能对程序做下列修改。错误检查n我们能够在试图包含omp.h之前先检查_OPENMP的定义# include #ifdef _OPENMP# include #endif错误检查n还有，我们可以首先检查是否_OPENMP定义，从而取代只调用OpenMP函数

13、：# ifdef _OPENMP int my_rank = omp_get_thread_num ( ); int thread_count = omp_get_num_threads ( );# else int my_rank = 0; int thread_count = 1;# endif梯形积分法The Trapezoidal Rule梯形积分法n我们来看一个更实用（也更复杂）的例子：用梯形积分法估计曲线下方所包围的面积。串行算法n 再回忆一下，如果每个子区间有同样的宽度h，并且定义h=(b-a)/n，x_i=a+i*h，i=0，1，n，那么近似值将是：Foster的并行程序设计方

14、法n(1)识别两类任务： a. 单个梯形面积的计算。 b梯形面积的求和。n(2)在1(a)的任务中，没有任务间的通信，但这一组任务中的每一个任务都与1(b)中的任务通信。Foster的并行程序设计方法n(3)假设梯形的数量远大于核的数量，于是通过给每个线程分配连续的梯形块（和每个核一个线程）来聚集任务。n这能有效地将区间a，b划分成更大的子区间，每个线程对它的子区间简单地应用串行梯形积分法。Foster的并行程序设计方法n(4)累加线程的结果。n很明显，其中一个解决方案是使用一个共享变量作为所有线程的和，每个线程可以将它计算的部分结果累加到共享变量中。让每个线程执行类似下面的语句： globa

15、l_result += my_result ;n但是，这可能会导致一个错误的global_result值如果两个（或更多）线程试图同时执行这条语句，那么结果将是不可预计的。例子n假设global_result已经被初始化为0，线程0已经计算出my_result =1，线程1已经计算出my_result =2。而且，假设线程根据以下时间表执行语句 global_result+=my_ result;临界区n实际运行时，事件的序列可能会不同，但除非一个线程在其他线程开始时完成了计算，否则结果都将是不正确的。n这其实是一个竞争条件(race condition)的例子：多个线程试图访问一个共享资源，

16、并且至少其中一个访问是更新该共享资源，这可能会导致错误。n引起竞争条件的代码global_result+=my_result，称为临界区。临界区是一个被多个更新共享资源的线程执行的代码，并且共享资源一次只能被一个线程更新。互斥访问n显然需要一些机制来确保一次只有一个线程执行global_result+=my_result，并且第一个线程完成操作前，没有其他的线程能开始执行这段代码。n在Pthreads中，使用互斥量或信号量。在OpenMP中，使用critical指令：n这条指令告诉编译器需要安排线程对下列的代码块进行互斥访问，即一次只有一个线程能够执行下面的结构化代码。第一个OpenMP梯形积

17、分法程序主函数说明n在main函数中，第16行之前的代码是单线程的，它简单地获取线程数和输入(a、b和n).n第16行里，parallel指令明确Trap函数应该被thread_count个线程执行。n在从Trap调用返回后，任何被parallel指令启动的新线程将终止，程序只用一个线程恢复执行。这个线程打印结果并终止。Trap函数n在Trap函数中，每个线程获取它的编号，以及在线程组中被parallel指令启动的线程总数。然后，每个线程确定下列值： (1)梯形底的长度（第32行）。 (2)给每个线程分配的梯形数（第33行）。 (3)区间的左、右端点（第34行和第35行）。 (4)对globa

18、 l_result贡献的部分和（第3641行）。n在第43行和第44行，线程通过将它们的部分和结果增加到global_result来完成操作。关于整除n除非能被thread_count整除，否则我们将使用小于n个的梯形来信算global_result。n例如，如果n=14，thread_count=4，则每个线程将计算 local_n=n /thread_count =14/4 =3n因此每个线程将只使用3个梯形， global_result将由4x3 =12个梯形计算出，而不是14个。n所以在错误检查（在程序中没有显示）时，我们用如下操作来检查n是否被thread_count整除：变量的作用

19、域SCOPE OF VARIABLES回顾n在串行编程中，变量的作用域由程序中的变量可以被使用的那些部分组成。n例如，在C函数开始处被声明的变量有“函数范围”的作用域，即它只能够在函数体中被访问。n另一方面，一个在.C文件开始处被声明的变量有“文件范围”的作用域，表示任何在文件中声明该变量的函数都能够访问这个变量。在OpenMP中，变量的作用域n在OpenMP中，变量的作用域涉及在parallel块中能够访问该变量的线程集合。n一个能够被线程组中的所有线程访问的变量拥有共享作用域，而一个只能被单个线程访问的变量拥有私有作用域。n在“hello，world”程序中，被每个线程使用的变量（my_r

20、ank和thread_count）在Hello函数中被声明，这个函数在parallel块中被调用。结果，被每个线程使用的变量在线程的（私有）栈中分配，因此所有的变量都有私有作用域。共享作用域n在main函数中声明的变量（a、b、n、global_result和thread_count）对于所有线程组中被parallel指令启动的线程都是可访问的。n在parallel块之前被声明的变量的缺省作用域是共享的n在Trap函数中，尽管global_result_p是私有变量，但它引用了global_result变量，这个变量是在main函数中并且在parallel指令之前声明的变量。n对于*globa

21、l_result_p，拥有共享作用域是很重要的。变量的作用域总结n在parallel指令前已经被声明的变量，拥有在线程组中所有线程间的共享作用域，而在块中声明的变量（例如，函数中的局部变量）中有私有作用域。n另外，在parallel块开始处的共享变量的值，与该变量在parallel块之前的值一样。在parallel块完成后，该变量的值是块结束时的值。归约子句THE REDUCTION CLAUSE另一个想法n如果开发实现梯形积分法的串行程序，我们可能会使用一个有些许不同的函数原型，而不是n我们可能会定义：n对函数的调用将会是n这更容易理解，对于除了指针的忠实拥护者之外的人，这种方法可能更有吸引

22、力。另一个想法（2）n保留指针版本是因为我们需要将每个线程的局部计算结果加到global_result。然而，我们可能更倾向予以下的函数原型：n除了没有临界区外，Local_trap的函数体与程序5-2中Trap的函数体是一样的。nPragma omp parallel 指令修正为：问题？解决方法？n！对Local_trap的调用一次只能够被一个线程执行，所以这就相当于强制各个线程顺序执行梯形积分法。n可以通过在parallel块中声明一个私有变量和将临界区移到函数调用之后来避免这个问题：I dont like it.Neither do I.I think we can do better.

23、归约操作符nOpenMP提供了一个更为清晰的方法来避免Local_trap的串行执行：将global_result定义为一个归约( reduction)变量。n归约操作符(reduction operator)是一个二元操作（例如：加法和减法），归约就是将相同的归约操作符重复地应用到操作数序列来得到一个结果的计算。n另外，所有操作的中间结果存储在同一个变量里：归约变量(reduction variable)。归约例子n例如，如果A是一个有n个int型整数的数组，计算：n是一个归约，归约操作符是加法。归约子句语法nreduction子句的语法是：n在C语言中，operator可能是操作符n中的任

24、意一个+, *, -, &, |, , &, |注意问题n减法不满足交换律和结合律。n例如：串行代码n在result中存储的结果是-10。然而，如果我们将迭代划分到两个线程中去执行，线程0将减1和2，线程1将减3和4，那么线程0将算出-3，线程1将算出-7。n显然，-3 -（-7）=4。注意问题2n如果一个归约变量是一个float或double型数据，那么当使用不同数量的线程时，结果可能会有些许不同。这是由于浮点数运算不满足结合律。n例如，如果a、b和c是浮点数，那么（a+b）+c可能不会准确地等于a+(b+c)。reduction子句中变量的作用域n当一个变量被包含在一个re

25、duction子句中时，变量本身是共享的。n然而，线程组中的每个线程都创建自己的私有变量。n在parallel块里，每当一个线程执行涉及这个变量的语句时，它使用的其实是私有变量。当parallel块结束后，私有变量中的值被整合到一个共享变量中。最新版本代码n代码明确了global_result是一个归约变量，加号(“+”)指示归约操作符是加法。nOpenMP为每个线程有效地创建了一个私有变量，运行时系统在这个私有变量中存储每个线程的结果。OpenMP也创建了一个临界区，并且在这个临界区中，将存储在私有变量中的值进行相加。因此，对Local _trap的调用能够并行执行。parallel for

26、指令The “Parallel For” DirectiveParallel forn作为梯形积分法显式并行化的替代方案，OpenMP提供了parallel for指令。运用该指令，我们能够并行化串行梯形积分法：Parallel forn与parallel指令一样，parallel for指令生成一组线程来执行后面的结构化代码块。n在parallel for指令之后的结构化块必须是for循环。n另外，运用parallel for指令，系统通过在线程间划分循环迭代来并行化for循环。因此，parallel for指令与parallel指令非常不同，因为在parallel指令之前的块，一般来说其工

27、作必须由线程本身在线程之间划分。线程间的缺省划分方式n在一个已经被parallel for指令并行化的for循环中，线程间的缺省划分方式是由系统决定的。n大部分系统会粗略地使用块划分，即如果有m次迭代，则大约m/thread_count欢迭代被分配到线程0，接下来的m/thread_count次被分配到线程1，以此类推。Parallel for中变量的作用域n在parallel指令中，所有变量的缺省作用域是共享的。n但在parallel for中，如果循环变量i是共享的，那么变量更新i+也会是一个无保护的临界区。n因此，在一个被parallel for指令并行化的循环中，循环变量的缺省作用域是

28、私有的，在我们的代码中，每个线程组中的线程拥有它自己的i的副本。遐想n这是一个十分美好的遐想：通过添加一条简单的parallel for指令，就可能并行化由大量的for循环所组成的串行程序。n也可能通过不断地在每个循环前放置parallel for指令，来增量地并行化一个串行程序。警告n首先，OpenMP只会并行化for循环，它不会并行化while或do - while循环。这似乎不是一个很大的限制，因为任何使用while或do - while循环的代码都能够被转化为等效的使用for循环的代码。n另外， OpenMP只能并行化确定迭代次数的for循环，包括：n由for语句本身来确定；n在循环执

29、行之前确定。不能被并行化的例子n例如，“无限循环”：n类似地，循环n也不能被并行化，因为迭代的次数不能只从for语句中来决定。这个for循环也不是一个结构化块，因为break添加了另一个从循环退出的出口。典型结构的for循环n事实上，OpenMP只能够并行化具有典型结构的for循环。限制n典型结构的for循环符合一些十分明显的限制：1.变量index必须是整型或指针类型（例如，它不能是float型浮点数）。2.表达式start、end和incr必须有一个兼容的类型。例如，如果index是一个指针，那么incr必须是整型。3.表达式start、end和incr不能够在循环执行期间改变。4. 在循

30、环执行期间，变量index只能够被for语句中的“增量表达式”修改。数据依赖性n如果for循环不能满足上述所列举规则中的任何一条，那么编译器将简单地拒绝它。例如，假设我们试图编译一个线性查找程序：n编译器将报告：隐藏的数据依赖性n一个更隐匿的问题发生在如下的循环中：在该循环中，迭代中的计算依赖于一个或更多个先前的迭代结果。n例如，计算前n个斐波那契(Fibonacci)数Fibonacci数列的并行化1 1 2 3 5 8 13 21 34 551 1 2 3 5 8 0 0 0 0this is correctbut sometimeswe get thisfibo 0 = fibo 1 =

31、 1;for (i = 2; i n; i+) fibo i = fibo i 1 + fibo i 2 ; fibo 0 = fibo 1 = 1;# pragma omp parallel for num_threads(2) for (i = 2; i n; i+) fibo i = fibo i 1 + fibo i 2 ; note 2 threads究竟发生了什么？n似乎运行时系统将fibo2、fibo3、fibo4和fibo5的计算分配给了一个线程，将fibo6、fibo7、fibo8、fibo9分配给了另一个线程。n在程序的一些运行结果中，结果之所以正确是因为被分配给fibo2

32、、fibo3、fibo4和fibo5的线程在另一个线程开始前就完成了计算。n然而，对于其他运行结果，当第二个线程计算fibo6时，第一个线程还没有计算出fibo4和fibo5。系统将fibo的入口初始化为0，第二个线程使用值fibo4 =0和fibo5 =0来计算fibo6。然后它继续使用fibo5 =0和fibo6 =0来计算fibo7，以此类推。两个要点n(1) OpenMP编译器不检查被parallel for指令并行化的循环所包含的迭代间的依赖关系，而是由程序员来识别这些依赖关系。n(2) 一个或更多个迭代结果依赖于其他迭代的循环，一般不能被OpenMP正确地并行化。寻找循环依赖n当我

33、们试图使用一个parallel for指令时，首先应该注意的是：要小心发现循环依赖。n我们不需要担心一般的数据依赖。例如，在下列循环中：值估计值估计OpenMP solution #1n可以清楚地看到，在第k次迭代中对第7行的factor的更新和接下来的第k+1次迭代中对第6行的sum的累加是一个循环依赖。n如果第k次迭代被分配给一个线裎，而第k+1次迭代被分配给另一个线程，则我们不能保证第6行中factor的值是正确的。solution #1的修复？还有错误？n在一个已经被parallel for指令并行化的块中，缺省情况下任何在循环前声明的变量（唯一的例外是循环变量）在线程间都是共享的。因

34、此factor被共享。n例如，线程0可能会给它赋值1，但在它能用这个值更新sum前，线程1可能给它赋值-1了。OpenMP solution #2n除了消除计算factor时的循环依赖外，我们还需要保证每个线程有它自己的factor副本。n就是说，为了使代码正确，我们需要保证factor有私有作用域。通过添加一个private子句到parallel指令中来实现这一目标。注意的地方n一个有私有作用域的变量的值在parallel块或者parallel for块的开始处是未指定的。它的值在parallel或parallel for块完成之后也是未指定的。子句defaultn与其让OpenMP决定每个

35、变量的作用域，还不如让程序员明确块中每个变量的作用域。如果我们添加子句n到parallel或parallel for指令中，那么编译器将要求我们明确在这个块中使用的每个变量和已经在块之外声明的变量的作用域。（在一个块中声明的变量时私有的，因为它们会被分配给线程的栈）子句defaultn在这个例子中，我们在for循环中使用4个变量。由于default子句，我们需要明确每个变量的作用域。更多关于OpenMP的循环：排序More About Loops in OpenMP: Sorting冒泡排序冒泡排序中的循环依赖n在外部循环中有一个循环依赖，在外部循环的任何一次迭代中，当前列表的内容依赖于外部循

36、环的前一次迭代。n例如，如果在算法开始时，a =3，4，1，2，那么外部循环的第二次迭代将对列表3，1，2进行操作，因为4在第一次迭代中应该已经被移动到列表的最后了。但如果前两次迭代同时执行，则有可能第二次迭代的有效列表包含4。n内部循环的循环依赖也很容易发现。奇偶变换排序n奇偶变换排序是一个与冒泡排序相似的算法，但它相对来说更容易并行化。奇偶变换排序的例子奇偶变换排序的循环依赖n外部循环有一个循环依赖。我们尚不清楚如何消除这个循环依赖，因此并行化外部for循环不是一个好的选择。n 但是，内部for循环并没有任何循环依赖。例如，在偶阶段循环中，若变量i是奇数，所以对于两个不同的i值，例如，i

37、=j和i=k，j-1，j和k-1，k将是不同的。并行化奇偶变换排序潜在的问题n首先，尽管任何一个偶阶段迭代并不依赖任何这个阶段的其他迭代，但是还需要注意，对p阶段和p+1阶段却不是这样的。n我们需要确定在任何一个线程开始p+1阶段之前，所有的线程必须先完成p阶段。然而，像parallel指令那样，parallel for指令在循环结束处有一个隐式的路障，因此，在所有的线程完成当前阶段（即阶段p）之前，没有线程能够进入下一个阶段，即p+1阶段。潜在的问题2n创建和合并线程的开销。OpenMP实现可能会在每一遍外部循环都创建和合并thread_count个线程。n下表显示了当输入列表包含20 00

38、0个元素时，在我们系统上运行1、2、3、4个线程的运行时间。是否能做得更好？n每次执行内部循环时，使用同样数量的线程。因此只创建一次线程，并在每次内部循环的执行中重用它们，这样做可能更好。nOpenMP提供了允许这样做的指令。用parallel指令在外部循环前创建thread_count个线程的集合。然后，我们不在每次内部循环执行时创建一组新的线程，而是使用一个for指令，告诉OpenMP用已有的线程组来并行化for循环。并行化奇偶变换排序的第二个版本性能的提升n与parallel for指令不同的是，for 指令并不创建任何线程。它使用已经在parallel块中创建的线程。在循环的末尾有一个

39、隐式的路障。代码的结果（最终列表）将因此与原有的并行化代码所得到的结果一样。快17%练习n用OpenMP编写完整的奇偶变换并行排序程序n提示：循环调度Scheduling Loops回顾n 当第一次遇到parallel for指令时，我们看到将各次循环分配给线程的操作是由系统完成的。n然而，大部分的OpenMP实现只是粗略地使用块分割：如果在串行循环中有n次迭代，那么在并行循环中，前n/thread_count个迭代分配给线程0，接下来的n/thread_count个迭代分配给线程1，以此类推。n不难想到，这种分配方式肯定不是最优的。一个例子n例如，假设我们想要并行化循环：n同时，假设对f函数

40、调用所需要的时间与参数i的大小成正比，那么与分配给线程0的工作相比，分配给线程thread_count -1的工作量相对较大。循环划分n一个更好的分配方案是轮流分配线程的工作（循环划分）。n在循环划分中，各次迭代被“轮流”地一次一个地分配给线程：假设t= thread_count。那么一个循环划分将如下分配各次迭代：测试程序n为了了解这样的分配是如何影响性能的，我们编写了如下程序：测试结果n每次函数f(i)调用i次sin函数。例如，执行f(2i)的时间几乎是执行f(i)的时间的两倍。nn = 10,000none threadnrun-time = 3.67 seconds.测试结果nn =

41、10,000ntwo threadsndefault assignment nrun-time = 2.76 secondsnspeedup = 1.33nn = 10,000ntwo threadsncyclic assignment nrun-time = 1.84 secondsnspeedup = 1.99schedule子句n我们看到一个好的迭代分配能够对性能有很大的影响。在OpenMP中，将循环分配给线程称为调度，schedule子句用于在parallel for或者for指令中进行迭代分配。schedule子句n缺省调度(Default schedule):n循环调度(Cycli

42、c schedule):schedule子句的类型n一般而言，schedule子句有如下形式：ntype可以是下列任意一个： 1. static。迭代能够在循环执行前分配给线程。 2. dynamic或guided。迭代在循环执行时被分配给线程，因此在一个线程完成了它的当前迭代集合后，它能从运行时系统中请求更多。 3. auto。编译器和运行时系统决定调度方式。 4. runtime。调度在运行时决定。nchunksize是一个正整数。在OpenMP中，迭代块是在顺序循环中连续执行的一块迭代语句，块中的迭代次数是chunksize。static调度类型n对于static调度，系统以轮转的方式分

43、配chunksize块个迭代给每个线程。twelve iterations, 0, 1, . . . , 11, and three threadsstatic调度类型twelve iterations, 0, 1, . . . , 11, and three threadsstatic调度类型twelve iterations, 0, 1, . . . , 11, and three threadsdynamic调度类型n在dynamic调度中，迭代也被分成chunksize个连续迭代的块。n每个线程执行一块，并且当一个线程完成一块时，它将从运行时系统请求另一块，直到所有的迭代完成。nChu

44、nksize可以被忽略。当它被忽略时，chunksize为1。guided调度类型n在guided调度中，每个线程也执行一块，并且当一个线程完成一块时，将请求另一块。n然而，在guided调度中，当块完成后，新块的大小会变小。n在guided调度中，如果没有指定chunksize，那么块的大小为1；如果指定了chunksize，那么块的大小就是chunksize，除了最后一块的大小可以比chunksize小。例子n例如，在我们的系统上，如果用parallel for指令和schedule(guided)子句来运行梯形积分法程序那么当n=10 000并且thread_count =2时，迭代将如

45、表5-3那样分配。n块的大小近似等于剩下的迭代数除以线程数。第一块的大小为9999/25000，因为有9999个未被分配的迭代。第二块的大小为4999/22500，以此类推。runtime调度类型n当schedule(runtime)指定时，系统使用环境变量OMP_SCHEDULE在运行时来决定如何调度循环。nOMP_SCHEDULE环境变量会呈现任何能被static、dynamic或guided调度所使用的值。n例如，假设在程序中有一条parallel for指令，并且它已经被schedule(runtime)修改了，那么如果使用bash shell，就能通过执行以下命令将一个循环分配所得到

46、的迭代分配给线程：n现在，当开始执行程序时，系统将调度for循环的迭代，就如同使用子句schedule(static，1)修改了parallel for指令那样。 调度选择n如果需要并行化一个for循环，那么我们如何决定使用哪一种调度和chuncksize的大小？n实际上，每一种schedule子句有不同的系统开销。ndynamic调度的系统开销要大于static调度，而guided调度的系统开销是三种方式中最大的。因此，如果不使用schedule子句就已经达到了令人满意的性能，就不需要再进行多余的工作。调度选择n在本节开始提供的例子中，在程序使用两个线程的情况下，使用schedule(sta

47、tic，1)代替默认调度时，加速比从1. 33增加到1.99。n因为在两个线程的条件下，加速比几乎不可能比1.99更好，所以我们可以不用再尝试其他的调庋方式，至少在只用两个线程并且迭代数为10 000的情况下是这样。调度选择的一些准则n如果循环的每次迭代需要几乎相同的计算量，那么可能默认的调度方式能提供最好的性能。n如果随着循环的进行，迭代的计算量线性递增（或者递减），那么采用比较小的chuncksize的static调度可能会提供最好的性能。n如果每次迭代的开销事先不能确定，那么就可能需要尝试使用多种不同的调度策略。在这种情况下，应当使用schedule( runtime)子句，通过赋予环境

48、变量OMP_SCHEDULE不同的值来比较不同调度策略下程序的性能。生产者和消费者问题Producers and Consumers生产者和消费者问题n本节将讨论一个不适合用parallel for指令或者for指令来并行化的问题。队列n队列是一种抽象的数据结构，插入元素时将元素插入到队列的“尾部”，而读取元素时，队列“头部”的元素被返回并从队列中被移除。n队列可以看做是在超市中等待付款的消费者的抽象，队列中的元素是消费者。新的消费者到达时排在等待队列的尾部，下一个付款离开等待队列的是排在队列头部的消费者。n当一个新的元素插入到队列的尾部时，通常称这个新的元素“入队”了；当一个元素从队列 的头

49、部被移除时，通常称这个元素“出队”了。队列n队列也是在多线程应用程序中经常使用到的数据结构。n例如，我们有几个“生产者”线程和几个“消费者”线程。n生产者线程“产生”对服务器数据的请求例如当前股票的价格，而消费者线程通过发现和生成数据（例如，当前股票的价格）来“消费”请求。生产者线程将请求入队，而消费者线程将请求从队列中移出。n在这个例子中，只有当消费者线程将请求的数据发送给生产者线程时，进程才会结束。消息传递n生产者和消费者问题模型的另外一个应用是在共享内存系统上实现消息传递。n每一个线程有一个共享消息队列，当一个线程要向另外一个线程“发送消息”时，它将消息放入目标线程的消息队列中。一个线程

50、接收消息时只需从它的消息队列的头部取出消息。n这里我们将实现一个简单的消息传递程序，在这个程序中，每个线程随机产生整数“消息”和消息的目标线程。消息传递n当创建一条消息后，线程将消息加入到合适的消息队列中。当发送消息之后，该线程查看它自己的消息队列以获知它是否收到了消息，如果它收到了消息，它将队首的消息出队并打印该消息。n每个线程交替发送和接收消息，用户需要指定每个线程发送消息的数目。n当一个线程发送完所有的消息后，该线程不断接收消息直到其他所有的线程都已完成，此时所有的线程都结束了。消息传递发送消息Send_msg()n需要注意的是，访问消息队列并将消息人队，可能是一个临界区。n尽管我们还没

51、有深入地研究如何实现消息队列，但我们很有可能需要用一个变量来跟踪队列的尾部。n例如，使用一个单链表来实现消息队列，链表的尾部对应着队列的尾部。然后，为了有效地进行人队操作，需要存储指向链表尾部的指针。n当一条新消息入队时，需要检查和更新这个队尾指针。如果两个线程试图同时进行这些操作，那么可能会丢失一条已经由其中一个线程入队的消息。发送消息Send_msg()nSend_msg()函数的伪代码如下：接收消息Try_receive()n接收消息的同步问题与发送消息有些不同。只有消息队列的拥有者（即目标线程）可以从给定的消息队列中获取消息。n如果消息队列中至少有两条消息，那么只要每次只出队一条消息，

52、那么出队操作和入队操作就不可能冲突。因此如果队列中至少有两条消息，通过跟踪队列的大小就可以避免任何同步（例如critical指令）。接收消息Try_receive()n现在的问题是如何存储队列大小。n如果只使用一个变量来存储队列的大小，那么对该变量的操作会形成临界区。然而可以使用两个变量：enqueued和dequeued，那么队列中消息的个数（队列的大小）就为n唯一能够更新dequeued的线程是消息队列的拥有者。可以看到在一个线程使用enqueued计算队列大小queue_size的同时，另外一个线程可以更新enqueued。接收消息Try_receive()终止检测Done()n接下来，

53、我们探讨如何实现Done函数。首先，我们给出一个“直接”的实现，但这个实现隐藏着问题：n如果线程u执行这段代码，那么很有可能有些线程，如线程v，在线程u计算出queue_size=0后向线程u发送一条消息。当然，线程u在得出queue_size=0后将终止，那么线程v发送给它的消息就永远不会被接收到。终止检测Done()n在我们的程序中，每个线程在执行完for循环后将不再发送任何消息。因此可以增加一个计数器done_sending，每个线程在for循环结束后将该计数器加1，Done的实现如下：启动n当程序开始执行时，主线程将得到命令行参数并且分配一个数组空间给消息队列，每个线程对应着一个消息队

54、列。n由于每个线程可以向其他任意的线程发送消息，所以这个数组应该被所有的线程共享，而且每个线程可以向任何一个消息队列插入一条消息。启动n消息队列（至少）可以存储：n 消息列表n 队尾指针或索引n 队首指针或索引n 入队消息的数目n 出队消息的数目启动同步n这里一个重要的问题是：一个或者多个线程可能在其他线程之前完成它的队列分配。n如果这种情况出现了，那么完成分配的线程酉能会试图开始向那些还没有完成队列分配的线程发送消息，这将导致程序崩溃。n因此，我们必须确保任何一个线程都必须在所有的线程都完成了队列分配后才开始发送消息。atomic指令n发送完所有的消息后，每个线程在执行最后的循环以便接收消息

55、之前，需要对done_sendng加1。n显然，对done_sending的增量操作是临界区，可以通过critical指令来保护它。nOpenMP提供了另外一种可能更加高效的指令：atomic指令：atomic指令n与critical指令不同，它只能保护由一条C语言赋值语句所形成的临界区。n此外，语句必须是以下几种形式之一：n可以是以下任意的二元操作符：atomic指令n需要注意的是，只有x的装载和存储可以确保是受保护的，例如在下面的代码中：n其他线程对x的更新必须等到该线程对x的更新结束之后。但是对y的更新不受保护，因此程序的结果是不可预测的。natomic指令的思想是许多处理器提供专门的装

56、载-修改-存储(load - modify - store)指令。使用这种专门的指令而不使用保护临界区的通用结构，可以更高效地保护临界区。临界区n在前面的例子里面，我们看到三个临界区：n然而，我们不需要强制对3个代码块都进行互斥访问，甚至不需要强制对第2个和第3个代码块进行完全的互斥访问。n例如，线程0在向线程1的消息队列写消息的同时，线程1可以向线程2的消息队列写消息。临界区n根据OpenMP的规定，第2个和第3个代码块是被critical指令保护的代码块。n在OpenMP看来，我们的程序有两个不同的临界区：被atomic指令保护的done_sending+和“复合”临界区。在“复合”临界区

57、中，程序读取和发送消息。n 强制线程间的互斥会使程序的执行串行化。OpenMP默认的做法是将所有的临界区代码块作为复合临界区的一部分，这可能非常不利于程序的性能。临界区nOpenMP提供了向critical指令添加名字的选项：n采取这种方式，两个用不同名字的critical指令保护的代码块就可以同时执行。n但！临界区的名字是在程序编译过程中设置的。当我们想让访问不同队列的线程可以同时访问相同的代码块时，被命名的critical指令就不能满足我们的要求了。锁n锁由一个数据结构和定义在这个数据结构上的函数组成，这些函数使得程序员可以显式地强制对临界区进行互斥访问。锁的使用n锁的使用可以大概用下面的

58、伪代码n锁的数据结构被执行临界区的线程所共享，这些线程中的某个线程（如主线程）会初始化锁。而当所有的线程都使用完锁后，某个线程应当负责销毁锁。锁的使用n在一个线程进入临界区前，它尝试通过调用锁函数来上锁(set)。如果没有其他的线程正在执行临界区的代码，那么它将获得锁并进入临界区。当该线程执行完临界区的代码后，它调用解锁函数释放（relinquish或者unset）锁，以便其他线程可以获得锁。n当一个线程拥有锁时，其他的线程都不能进入该临界区。其他线程尝试通过调用锁函数进入该临界区时会被阻塞。如果有多个线程被锁函数阻塞，则当临界区的线程释放锁时，这些线程中的某个线程会获得锁，而其他线程仍被阻塞

59、。简单锁nOpenMP简单锁的类型是omp_lock_t，定义简单锁的函数包括：在消息传递程序中使用锁n在前面对critical指令不足之处的讨论中，我们看到，在消息传递程序中，我们想要确保的是对每个消息队列进行互斥访问，而不是对于一个特定的代码块。n锁可以帮助我们实现这个目的。将omp_lock_t类型的数据成员包含在队列结构中，可以通过简单地调用omp_set_lock函数来确保对消息队列的互斥访问。在消息传递程序中使用锁在消息传递程序中使用锁critical指令、atomic指令、锁的比较n到目前为止，有三种机制可以实现对临界区的访问，很自然地我们想知道在不同的情况下应当采取哪一种方法。

60、n一般而言，atomic指令是实现互斥访问最快的方法。因此，如果临界区由特定形式的赋值语句组成，则使用atomic指令至少不会比使用其他方法慢。critical指令、atomic指令、锁的比较nOpenMP规范允许atomic指令对程序中圻有atomic指令标记的临界区进行强制互斥访问这是未命名的critical指令的工作方式。n如果这种行为不能满足要求（例如，程序中有多个不同的由atomic指令保护的临界区）则应当使用命名的critical指令或者锁。critical指令、atomic指令、锁的比较n不论是未命名的critical指令还是命名的critical指令都十分易于使用。n此外，在我们所使用到的Op