OpenMP 任务：使用二进制搜索在列表中搜索多个键

Question

我正在尝试使用 OpenMP 任务构造同时搜索数组中的多个键。但是我的并行代码好像比串行代码慢很多。
能否请您提出更改建议以使并行代码更快？

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

int binary_search(int array[],int key,int size){
  int low=0,high=size-1;
  while(low<=high){
    int mid = (low+high)/2;
    if(array[mid]==key){
      return 1;
    }else if(key<array[mid]){
      high = mid-1;
    }else{
      low = mid+1;
    }
  }
  return 0;
}

void main(){
  int size=10000000;

  int *array = (int*)malloc(size*sizeof(int));

  // Initializes the array
  for(int i=0;i<size;i++){
    array[i] = i;
  }

  // exists array stores if the ith key is in the Original array or not
  int *exists = (int*)calloc(size,sizeof(int));

  // SERIAL REGION
  double end,start = omp_get_wtime();
  for(int key=0;key<(size);key++){
      exists[key] = binary_search(array,key,size);
  }
  end = omp_get_wtime();

  printf("\nSerial execution time : %lf\n",end-start);


  // Reset the exists array to 0 values
  for(int i=0;i<size;i++){
    exists[i]=0;
  }

  // PARALLEL REGION
  start = omp_get_wtime();
  #pragma omp parallel default(none) shared(array,size,exists)
  {
    #pragma omp single
    {
      for(int key=0;key<(size);key++){
        #pragma omp task shared(array,size,exists) firstprivate(key)
        {
          exists[key]=binary_search(array,key,size);
        }
      }
    }
  }
  end = omp_get_wtime();

  printf("\nParallel execution time : %lf\n",end-start);
}

这是结果：

串行执行时间：1.383815
并行执行时间：10.438401

编译器：GCC 5.4.0
核心数：8 核
提前谢谢你..
已编辑：包括 John Bollinger 建议的更改。

Answer 1

我看到的最大问题是#pragma omp critical。这将导致大量不必要的锁定。您不需要临界区，因为 exists 的元素不会被并行区域内的多个线程访问。获取和释放锁的成本相当高，而且你正在做的事情相对较多，所以这似乎完全解释了性能问题。

此外，您不需要在并行构造的末尾使用 #pragma omp taskwait，因为绑定到并行区域的所有显式任务都保证在控制权从构造传递出去之前完成。但我怀疑这会导致任何性能问题。

更新

我做了一些实验：

原始代码对我来说表现出比问题中描述的更明显的性能差异：~0.39 s vs ~14.3 s.
我从用于生成任务的 omp single 线程切换到 omp for，在我的 12-[=56= 上产生了大约一个数量级的并行性能提升] 机器。然而，各个运行的并行性能差异很大，从 0.1 秒到 1.8 秒不等。
可能并不奇怪，当我去掉外部 omp parallel 区域并将循环注释为 omp parallel for
时，我看到了与之前类似的性能
我从并行代码（~0.09 秒；偶尔 < 0.05 秒）中得到了显着的改进，因为我摆脱了显式任务，只依赖于并行 for。
我将原始代码中的问题大小缩小了两倍、四倍和八，并观察到线性缩放的时间。

这告诉我，至少在我的实现中，显式任务会带来相当大的开销。我并不觉得这特别令人惊讶。认识到为了创建一个显式任务，这样做的线程必须分配和初始化一个对象来纪念任务的数据和执行环境，并且必须将该对象排入共享任务队列（需要同步）。然后，执行这样一个任务的线程必须将任务数据出列，并设置数据和执行环境，然后才能执行任务的实际工作。

在这种情况下，对于主体耗时约 40 纳秒的任务，所有这些似乎耗时约 1 微秒。 take-home 消息将避免 fine-grained 显式任务。

OpenMP 任务：使用二进制搜索在列表中搜索多个键

OpenMP Tasks : Searching multiple Keys in a list using Binary Search

c

parallel-processing

optimization

openmp

binary-search