OpenMP: schedule

schedule是为了更好地分配循环中任务的数量,所以也只能用于循环结构,需要注意的是指定不同的任务分配方式对于程序执行效率会有很大的影响。

schedule 总共有 static, dynamic,runtime,guided,auto五种类型(早期版本的 OpenMP 可能没有auto),static的执行效率是这几种类型里效率最高的,简单写下几种类型的特点:

  • static

schedule(static[, chunk_size]) 的形式被指定以后,任务被分成n = [s/chunk_size]+1 份(s 为总循环次数,chunk_size 刚好整除 s 时为 n = s/chunk_size), 这些任务按照 thread_num 从小到大依次分配,进行循环。也就是说 thread 0 总是领到第一份任务,第五份任务(如果共有 4 个 thread 且 n>4)…… 还有一点需要说明的是,所有的任务块都是相邻的,比如 i=1,2,3,而不可能有i=1,2,5这样的区块,这一点对于所有类型都是适用的,不仅限于static

而当 chunk_size 没有指定时, 编译器会分配给各个 thread 尽可能相等的任务,所有的 thread 都只能领到一个区块。

  • dynamic

schedule(dynamic[, chunk_size]) 的形式被指定以后, 任务的分配是动态进行的,每个 thread 领到任务后执行完成再向系统领新的任务,直到所有的区块都被分派完,由于 chunk_size 不一定能整除 s,所以有可能最后一个(指循环序列i的顺序,而不是实际执行的顺序)区块数量少于 chunk_size。

而当 chunk_size 没有指定时, 默认 chunk_size=1。

  • guided

schedule(guided[, chunk_size]),与dynamic很相似,但又有很大的区别,区别在于这里的 chunk_size 是每个区块最小的任务数量(最后一个区块除外),guided[, chunk_size]每次分配的区块任务数量是 Max([剩余循环次数/thread 总数], chunk_size),直到剩余的循环次数小于 chunk_size 为止。

而当 chunk_size 没有指定时, 默认 chunk_size=1。

  • auto

schedule(guided) 被指定时,如何分配任务将取决于当时的系统状况以及具体的编译器,程序将有完全的自由来选择适合的分配方式,至于这种方式是不是最合适的方式,我觉得在一般情况下应该是吧,否则也没有必要新增这个选项。

  • runtime

schedule(runtime)被指定时,如何分配任务只有到程序执行到这个部分的时候才会决定,至于分配的具体方法和 chunk_size 的大小,会根据run-sched-var ICV来确定,如果 ICV 的值是auto,the schedule is implementation defined.(这句不知道怎么理解好,先把原文贴上来)。

我写了一个嵌套循环的Fortran程序来加深对不同类型schedule的理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
program main
use omp_lib
implicit none
integer:: i, j
open(file='schedule_test.txt', unit=32, status='replace')
!$omp parallel do schedule(static) private(i, j)
do i = 1, 10
write(32,*),'i',i,omp_get_thread_num()
do j = 1, i
write(32,*), 'j',j,omp_get_thread_num()
enddo
enddo
!$omp end parallel do
end program main

从上面的程序可以看出,对于不同的循环序列i,工作量是不同的,i越大则在内层循环中的工作量越大,所以简单均分肯定会使不同 thread 的工作量相差不少,整理了一个表格对比一下不同类型的schedule任务执行的结果:

TID static, 2 dynamic, 2 guided, 2 auto runtime
i=1 0 3 3 0 1
2 0 3 3 0 0
3 1 0 3 0 3
4 1 0 1 1 2
5 2 1 1 1 1
6 2 1 0 1 0
7 3 2 0 2 3
8 3 2 2 2 2
9 0 3 2 3 1
10 0 3 3 3 0

表中的数字是 thread_num.注意这不是实际执行的顺序,只是为了方便查看按照循环参数i进行排序。

做一下简单的数学计算,第 i 个循环的工作量是\(1+i=i+1\), 将工作量也整理出一个简单的表格,最后计算一下不同模式下,不同 thread 的工作量:

TID static, 2 dynamic, 2 guided, 2 auto runtime
0 26 9 15 9 21
1 9 13 11 18 18
2 13 17 19 17 14
3 17 26 20 21 12
std 6.30 6.30 3.56 4.44 3.49

从结果来看(std:统计分布的标准差),guidedruntime的分配较好,staticdynamic分配相对不均,当然这只是一个简单程序的分析数据,很多情况下都需要根据具体的程序选择合适的模式