c - 使用 OpenMP 的 n 元搜索没有加速

Question

我正在为 n 元搜索编写代码，即将搜索空间分成 n 个部分。 将并行代码与没有 OpenMP 指令的代码(即串行执行)进行比较时，我发现并行代码比串行代码慢很多次。多次执行这两个程序后，我发现并行代码几乎没有加速，但不是每次都如此。这可能是由于缓存层次结构。我在具有 4GB RAM 的四核处理器上运行程序。

根据 No speedup with OpenMP 上的回答内存限制性能和负载平衡不适用于数组 SIZE 100 等小问题。我没有使用任何同步。我还尝试将数组大小增加到 10000000，但并行代码的输出并不总是更快。很多时候串行代码胜过并行代码。

根据 http://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-loop.html可以使用 nowait 子句取消工作共享结构末尾的隐式障碍。我尝试添加 nowait 子句我也尝试了 schedule(dynamic) 和 schedule(auto) 引用 https://software.intel.com/en-us/articles/openmp-loop-scheduling但仍然是同样的问题。

代码:

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

#define SIZE 100
#define NUM_THREADS 4

int* a;
int num;


void nary(int num)
{
    int found = 0, low = 0, high = SIZE, step;
    int i = 0;
    while(!found && low <= high)
    {
        step = (high-low)/NUM_THREADS;
        printf("Low :- %d\tHigh :- %d\tStep :- %d\n", low,high,step);
        printf("\n");

        #pragma omp parallel for num_threads(NUM_THREADS) shared(low,high,step)
        for (i = 0; i < NUM_THREADS; ++i)
        {
            printf("First element :- %d by thread :- %d\n", a[low+step*i],omp_get_thread_num());
            if (a[low+step*i] == num)
            {
                found = 1;
            }
        }

        printf("\n");
        /* First block */
        if (a[low+step] > num)
        {
            high = low + step - 1;
            printf("First \nLow :- %d \nHigh :- %d\n\n",low,high);
        }

        /* Last block */
        else if (a[low+step*(NUM_THREADS-1)] < num)
        {
            low = low + step * (NUM_THREADS-1) + 1;
            printf("Last\nLow :- %d \nHigh :- %d\n\n",low,high);
        }
        /* Middle blocks */
         else{
            #pragma omp parallel for num_threads(NUM_THREADS) schedule(static) shared(low,high,step)
            for (i = 1; i < (NUM_THREADS-1); ++i)
            {
                if (a[low+step*i] < num && a[low+step*(i+1)] > num)
                {
                    low = low + step*i + 1;
                    high = low + step*(i+1) - 1;
                }
            }
            printf("middle\nLow :- %d \nHigh :- %d\n\n",low,high);
        }
    }
    if (found == 1)
    {
        printf("Element found\n");
    }
    else
    {
        printf("Element Not found\n");
    }

}

int main()
{
    int i = 0;
    int startTime = omp_get_wtime();

    /* Dynamically allocate memory using malloc() */
    a = (int*)malloc(sizeof(int) * SIZE);
    #pragma omp parallel for schedule(static)
    for (i = 0; i < SIZE; ++i)
    {
        a[i] = i;

    }

    printf("Enter the element to be searched :- \n");
    scanf("%d", &num);

    nary(num);


    printf("\nExecution time :- %f\n", omp_get_wtime()-startTime);
    return 0;
}

并行执行输出:

Enter the element to be searched :- 
20
Low :- 0    High :- 100 Step :- 25

First element :- 0 by thread :- 0
First element :- 50 by thread :- 2
First element :- 25 by thread :- 1
First element :- 75 by thread :- 3

First 
Low :- 0 
High :- 24

Low :- 0    High :- 24  Step :- 6

First element :- 6 by thread :- 1
First element :- 18 by thread :- 3
First element :- 0 by thread :- 0
First element :- 12 by thread :- 2

Last
Low :- 19 
High :- 24

Low :- 19   High :- 24  Step :- 1

First element :- 20 by thread :- 1
First element :- 21 by thread :- 2
First element :- 19 by thread :- 0
First element :- 22 by thread :- 3

middle
Low :- 19 
High :- 24

Element found

Execution time :- 26.824379

串行执行输出:

Enter the element to be searched :- 
20
Low :- 0    High :- 100 Step :- 25

First element :- 0 by thread :- 0
First element :- 25 by thread :- 0
First element :- 50 by thread :- 0
First element :- 75 by thread :- 0

First 
Low :- 0 
High :- 24

Low :- 0    High :- 24  Step :- 6

First element :- 0 by thread :- 0
First element :- 6 by thread :- 0
First element :- 12 by thread :- 0
First element :- 18 by thread :- 0

Last
Low :- 19 
High :- 24

Low :- 19   High :- 24  Step :- 1

First element :- 19 by thread :- 0
First element :- 20 by thread :- 0
First element :- 21 by thread :- 0
First element :- 22 by thread :- 0

middle
Low :- 19 
High :- 24

Element found

Execution time :- 4.349347

这背后的原因是什么？是因为代码中有很多条件语句还是条件 block 中的for循环？

Answer 1

您的方法中存在许多大大小小的问题。

首先，二分查找非常快。在最坏的情况下它只需要 log₂(n) 次迭代。即使要搜索 1 万亿个元素，也只需 40 次迭代!每次迭代都非常简单，基本上只需要一次内存访问。所以我们谈论的是在大型数据集的最坏情况下几微秒的搜索时间。也就是说，当然，不会用 printf 污染这些东西。 .

另一方面，根据 some，产生一个线程大约需要 10 微秒。 answers .因此，即使对于完美的缩放实现，也没有任何基于并行化单个搜索的性能改进的现实机会。

查看您的特定代码，您在每次迭代中创建了两个并行区域。与并行区域和 omp for 的开销相比，每个线程只有很少量的工作。工作共享结构(根据实现和操作系统的不同可能会有很大差异)。

我发现 arity 和 NUM_THREADS 的混合有问题的。您的更新步骤包括两个串行执行和剩余的 NUM_THREADS-2间隔由 NUM_THREADS 检查线程...所以对于NUM_THREADS=4 ，即使是完美的并行执行，您也只是将时间从 4 次间隔检查减少到 3 次间隔检查，更新步骤的速度提高了 1.3 倍。

此外，您的代码包含严重的竞争条件:修改 low在第二个并行循环中是一个非常糟糕的主意，因为其他线程正在根据 low 同时检查它们的间隔。 .

如果您想实际提高搜索排序的连续数据的性能，请查看 these slides .如果您想使用 OpenMP/线程加速您的应用程序，您可能应该在更粗粒度的级别上进行处理。