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

更多关于Openmp的循环：排序

冒泡排序

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存储n个int型整数，算法将他们升序排列。外部循环先找到列表最大元素将他存在a[n-1]中，然后寻找次大的元素并存在a[n-2]中，以此类推。因此，第一遍处理全部的n个元素，第二遍处理除了最大元素外的所有元素，它处理一个n-1个元素的列表，以此类推。
内循环比较当前列表中的连续元素对。当发现一对是无序的时候，就交换他们。
显然，在外部循环中有一个循环依赖，在外部循环中的任何一次迭代中，当前列表的内容依赖于外部循环的前一次迭代。内部循环的循环依赖也容易发现。在第i次迭代中，被比较的元素依赖于第i-1次迭代。我们完全不清楚怎样在不完全重写算法的情况下移除任何一个循环依赖。

奇偶交换排序

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]);
        }
}

列表存储n个整数，算法对他们进行升序排列。在一个偶阶段phase%20里，每个偶下标元素a[i]与它左边的元素a[i-1]相比较。如果他们是没有排好序的，就交换他们。在一个奇阶段phase%21里，每个奇下标元素与它右边的元素相比较。如果他们是没有排好序的，就交换。
不难发现外部循环有循环依赖。例如a=9,7,8,6。在阶段0中，内部循环将比较9和7，8和6，得到7，9，6，8.在阶段1中，将比较9和6.然而，如果阶段0和1同时进行，阶段1比较的就是7和8，因此直接并行外部for不好。但是内部for循环并没有任何循环依赖。

奇偶排序的第一个openmp实现

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;
            }
        }
}

首先会有潜在的问题产生。
首先，尽管任何一个偶阶段迭代并不依赖任何这个阶段的其它迭代，但是还需要注意，对p阶段和p+1阶段却不是这样。我们需要确定在任何一个线程开始p+1阶段之前，所有的线程必须先完成p阶段。然而，像parallel指令那样，parallel for指令在循环结束处有一个隐式路障，因此，在所有的线程完成当前阶段（阶段p）之前，没有线程可以进入下一个阶段。
其次，是创建和合并线程的开销。openmp实现可能会在每一遍外部循环都创建和合并thread_count个线程。

奇偶排序的第二个openmp实现

#pragma omp parallel num_threads(threads_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指令在外部循环前创建thread_count个线程的集合。然后，我们不在每次内部循环执行时，创建一组新的线程，而是使用一个for指令，告诉openmp用已有的线程组来并行化for循环。
与parallel for指令不同的是for指令不创建任何线程。它使用已经在parallel块中创建的线程。在循环的末尾有一个隐式的路障。