《并行程序设计导论》04openmp

循环调度

parallel for指令中，将各次循环分配给线程的操作是由系统完成的。然而，大部分openmp实现只是粗略地使用块分割。一个更好的分配方案是轮流分配线程的工作（循环划分）。在循环划分中，歌词迭代被轮流地一次一个地分配给线程。不难发现，一个好的迭代分配能够对性能有很大的影响。在openmp中，将循环分配给线程称为调度，schedule子句用于在parallel for或者for指令中进行迭代分配。

schedule子句

sum=0.0;
#pragma omp parallel for num_threads(thread_count)\
reduction(+:sum) schedule(static,1)
for(i=0;i<=n;i++)
{
    sum+=f(i);
} 

一般而言，schedule子句有如下形式

schedule(<type>[,<chunksize>])

type可以是以下任一种
static。迭代能够在循环执行前分配给线程。
dynamic或guided。迭代在循环执行时被分配给线程，因此在一个线程完成了它的当前迭代集合后，他能从运行时系统中请求更多。
auto。编译器和运行时系统决定调度方式。
runtime。调度在运行时决定。
chunksize是一个正整数。在openmp中，迭代块是在顺序循环中连续执行的一块迭代语句，块中的迭代次数是chunksize。只有static dynamic和guided调度有chunksize。

static调度类型

系统以轮转的方式分配chunksize块个迭代给每个线程。
假设，有12个迭代0,1,2,…,10,11和三个线程，如果在parallel for或for指令中
使用schedule(static,1),迭代分配如下
thread 0: 0,3,6,9
thread 1: 1,4,7,10
thread 2: 2,5,8,11
如果使用schedule(static,2),迭代分配如下：
thread 0: 0,1,6,7
thread 1: 2,3,8,9
thread 2: 4,5,10,11
如果使用schedule(static,4),迭代分配如下：
thread 0: 0,1,2,3
thread 1: 4,5,6,7
thread 2: 8,9,10,11
因此子句schedule(static,total_iterations/thread_count)就相当于被大部分openmp实现所使用的缺省调度。这里的chunksize可以被忽略，如果被忽略，就近似于total_iterations/thread_count

dynamic和guided调度类型

在dynamic调度中，迭代也被分成chunksize个连续迭代的块，每个线程执行一块，并且当一个线程完成一块时，它将从运行时系统请求另一块，直到所有的迭代完成。chunksize可以被忽略。如果忽略了，chunksize为1.
在guided调度中，每个线程也执行一块，并且当一个线程完成一块时，请求另一块，然而，当块完成后，新块的大小会变小。如果没有指定chunksize大小，那么块的大小为1；如果指定了，那么快的大小就是chunksize，除了最后一块的小大可以比chunksize小。未指定size大小（最后迭代块大小最小会降到1）。
C同学解释：guided指定迭代块的最小值，迭代块一直缩小，知道缩小到chunksize大小，所以书上面说除了最后一块的大小可以比chunksize小。那么每块的大小是剩余循环次数除以线程数，
例如20个循环3个线程，chunksize=2
chunksize为7，5，3，2，2，1先由系统决定好，但它是动态分配，这三个数字会放到一个队列里，谁先做完谁先取。

环境变量

环境变量是能够被运行时系统所访问的命名值，即他们在程序的环境中是可得的。一些经常被使用的环境变量是PATH，HOME和SHELL。PATH变量明确了当寻找一个可执行文件时shell应该搜索哪些目录。HOME变量指定用户主目录的位置，SHELL变量指定用户shell的可执行位置。

runtime调度类型

当schedule(runtime)指定时，系统使用环境变量OMP_SCHEDULE在运行时来决定如何调度循环。就相当于用一个变量来概括所有的循环调度。
OMP_SCHEDULE环境变量会呈现任何被static,dynamic或guided调度所使用的值。
假设在程序中有一条parallel for指令，并且它已经被schedule(runtime)修改了，那么如果使用bash shell，就能通过执行以下命令将一个循环分配所得到的迭代分配给线程
export OMP_SCHEDULE=“static,1”;

现在，当开始执行程序时，系统将调度for循环的迭代，就如同使用子句schedule(static,1)修改了parallel for指令那样。

调度选择

如果需要并行化一个for循环，那么我们如何决定使用哪一种调度和chunksize的大小？
每一种schedule子句有不同的系统开销。

guided调度开销>dynamic调度开销>static调度开销

因此，如果不用schedule子句就可以达到令人满意的性能，就需要进行多余操作。
最优调度方式是由线程的个数和迭代的次数共同决定的。
如果我们断定默认的调度方式性能低下，那么我们会做大量的实验来寻找最优的调度方式和迭代次数。
但在某些情况下，应该优先考虑有些调度
如果循环的每次迭代需要几乎相同的计算量，那么可能默认的调度方式能提供最好的性能。
如果随着循环的进行，迭代的计算量线性递增或递减，那么采用比较小的chunksize的static调度可能会提供最好的性能。
如果每次迭代的开销实现不能确定，那么可能需要尝试使用多种不同的调度策略。在这种情况下，应当使用schedule(runtime)子句，通过赋予环境变量OMP_SCHEDULE不同的值来比较不同调度策略下程序的性能。