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

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子句，我也尝试了参考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 

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

Answer 1

你的方法有很多小问题和大问题。

首先，二分查找速度非常快。在最坏的情况下它只需要log （n）次迭代。即使有一万亿的元素可以搜索，这只是40次迭代！每次迭代都非常简单，基本上只需要一次内存访问。所以我们在大数据集的最坏情况下讨论几微秒的搜索时间。当然，没有污染printf的东西。

另一方面，根据someanswers产卵线程需要大约10微秒。因此，即使对于完美的扩展实现，基于并行化搜索的单一性能也不存在实际性能提升的机会。

查看您的特定代码，您可以在每次迭代中创建两个平行区域。与并行区域和工作共享构造（根据实现和操作系统可能差别很大）相比，每个线程只有很少的工作量。

我发现混合和NUM_THREADS问题。您的更新步骤由两个串行执行组成，其余NUM_THREADS-2间隔通过NUM_THREADS线程进行检查......因此对于NUM_THREADS=4，即使完美的并行执行，您也只能将时间从4个间隔检查减少到3个间隔检查，1.3倍加速在更新步骤。此外，您的代码包含严重的竞争条件：在第二个并行循环中修改low是一个非常糟糕的主意，因为其他线程正在根据low同时检查其间隔。

如果要切实提高在已排序的连续数据中搜索的性能，请检查these slides。如果你想使用OpenMP /线程来加速你的应用程序，你应该在更粗糙的级别上进行处理。