OpenMP排序

OpenMP排序

1.冒泡排序

1
2
3
4
5
6
7
for(list_length = n; list.length >= 2; list_length--)				//升序排列
    for(i = 0;i < list_length-1; i++)
        if(a[i] > a[i+1]){
            tmp = a[i];
            a[i] = a[i+1];
            a[i+1] = tmp;
        }

​ 显然，在外部循环中有一个循环依赖，在外部循环的任何一次迭代中，当前列表的内容依赖于外部循环的前一次迭代。例如，如果在算法开始时，a=3,4,1,2，那么外部循环的第二次迭代将对列表3，1，2进行操作，因为4在第一次迭代中应该已经被移动到列表的最后了。但如果前两次迭代同时执行，则可能第二次迭代的有效列表包含4。

​ 内部循环的循环依赖也很容易发现。在第i次迭代中，被比较的元素依赖于第i-1次迭代。如果在第i-1次迭代中a[i-1]和a[i]没有交换，那么第i次迭代将比较a[i]和a[i+1]。另一方面，如果第i-1次迭代交换了a[i-1]和a[i]，那么第i次迭代将比较原始的a[i-1] (现在是a[i]和a[i+1])。例如，假如当前列表是{3，1，2}。那么当i=1时，我们将比较3和2，但如果i=0和i=1次迭代同时发生，则完全有可能i=1次迭代回比较1和2。

​ 我们完全不清楚怎样在不完全重写算法的情况下一处任何一个循环依赖。记住。即使我们总能找到循环依赖，但可能很难甚至不可能移除它。对于并行化for循环而言，parallel for指令不是一个通用的解决方法。

2.奇偶交换排序

​ 奇偶交换排序是一个与冒泡排序相似的算法，但它相对来说更容易并行化。

1
2
3
4
5
6
7
for(phase = 0;phase < n ; phase++)
    if(phase % 2 == 0)
        for(i = 1; i < n ;i += 2)
            if(a[i-1] > a[i]) swap(a[i-1],a[i]);
	else
        for(i = 1;i < n-1 ;i += 2)
            if(a[i] > a[i+1]) swap(a[i],a[i+1]);

列表a存储n个整数，算法对他们进行升序排列。在一个“偶阶段”（phase %2 ==0 ）里，每个偶下标元素a[i]与它左边的元素a[i-1]相比较。如果他们是没有排好序的，就交换它们。在一个“奇阶段”里，每个奇下标元素与它右边的元素相比较。如果他们是没有排好序的，则交换他们。有定理证明：在n个阶段后，列表可以完成排序。

​ 作为一个简单的例子，假设a={9,7,8,6}。表5-1显示了各个阶段的情况。在这个例子中，最后的阶段不是必要的，但算法并不在执行每个阶段前检查列表是否已经有序。

image-20230113174202896

​ 不难看到外部循环有一个循环依赖。例如在a = {9，7，8，6}之前。在阶段0中，内部循环将比较（9，7）和（8，6）这两对中的元素，这两对都会被交换。因此对于阶段1，列表将是{7，9，6，8}，并在阶段1中（9，6）中的元素被比较并交换。然而，如果阶段0和阶段1同时执行，则在阶段1中被检查可能是（7，8），是有序的。此外，我们尚不清楚如何消除这个循环依赖，因此并行化外部for循环不是一个好的选择。

​ 但是，内部for循环并没有任何循环依赖。例如，在偶阶段循环中，变量i是奇数，所以对于两个不同的i值，例如，i=j和i=k，{j-1,j}和{k-1,k}将是不同的。（a[j-1],a[j]）和（a[k-1],a[k]）所产生的比较和可能的交换能够同时进行。

​ 所以，我们试图使用程序5-4的代码并行化奇偶变化排序，但还是会有一些潜在的问题，首先，尽管任何一个偶阶段迭代并不依赖任何这个阶段的其他迭代，但是还需要注意，对p阶段和p+1阶段却并不是这样的。我们需要确定在任何一个线程开始p+1阶段之前，所有的线程必须先完成p阶段。然而，像parallel指令那样，parallel for指令在循环结束处有一个隐式的路障，因此，在所有的线程完成当前阶段（即阶段P之前），没有线程能够进入下一阶段，即p+1阶段。【这里需要注意在MPI中并没有隐式的路障来实现这个功能，需要程序员手动设置路障点】

​ 其次，是创建和合并线程的开销。OpenMP实现可能会在每一遍外部循环都创建和合并thread__count个线程。表5-2的第一行显示了当输入列表包含20000个元素时，在我们系统上运行1，2，3，4个线程的运行时间。

3.程序5-4 奇偶排序的第一个OpenMP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for(phase = 0;phase < n; phase++){
    if(phase %2 ==0)
    	#pragma omp parallel for num_threads(thread_count) default(none) shared(a,n) private(i,tmp)
        for(i=1;i<n;i+=2){
            if(a[i-1]>a[i]){
                tmp = a[i-1];
                a[i-1] = a[i];
                a[i] =tmp;
            }
        }
    else
        #pragma omp parallel for num_threads(thread_count) default(none) shared(a,n) private(i,tmp)
        for(i=1;i<n-1;i+=2){
            if(a[i] > a[i+1]){
                tmp = a[i+1];
                a[i+1] = a[i];
                a[i] = tmp;
            }
        }
}

image-20230113225724364

​ 这些时间耗费并不非常糟糕，但是我们想看看是否能做得更好。每次执行内部循环时，使用同样数量的线程。因此只创建一次线程，并在每次内部循环的执行中重用它们，这样做可能更好。幸运的是，OpenMP提供了允许这样做的指令。用parallel指令在外部循环前创建thread__count个线程的集合。然后，我们不在每次内部循环执行时创建一组新的线程，而是使用一个for指令，告诉OpenMP用已有的线程组来并行化for循环，对原有OpenMP实现的改动显示在程序5-5中。

4.程序5-5 奇偶排序的第二个OpenMP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma omp parallel for num_threads(thread_count) default(none) shared(a,n) private(i,tmp,phase)
for(phase = 0;phase < n; phase++){
    if(phase %2 ==0)
		#pragma omp for
        for(i=1;i<n;i+=2){
            if(a[i-1]>a[i]){
                tmp = a[i-1];
                a[i-1] = a[i];
                a[i] =tmp;
            }
        }
    else
		#pragma omp for
        for(i=1;i<n-1;i+=2){
            if(a[i] > a[i+1]){
                tmp = a[i+1];
                a[i+1] = a[i];
                a[i] = tmp;
            }
        }
}

与parallel for指令不同的是，for指令并不创建任何线程。它使用已经在parallel块中创建的线程。在循环的末尾有一个隐式的路障。代码的结果（最终列表）将因此与原有的并行化代码所取得到的结果一样。

​ 奇偶排序的第二个版本的运行时间显示在表5-2的第二行。当使用两个或更多线程时，使用两条for指令的版本要比使用两条parallel for指令的版本快17%。因此对于这个系统而言，为这点改变所做的小小努力是值得的。

5.总结

  1. 循环依赖总会出现，我们可能会很难去解决它甚至根本无法解决。
  2. 在构造并行区时要尽量减少创建和合并线程的开销

6.参考文献

并行程序导论 （美）Peter S.Pacheco

HPC
OpenMP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！