c - 并行二分查找的性能比串行版本差

Question

我编写了下面的代码，它在数组中执行一定数量的二分搜索。我使用 OpenMP 对其进行了并行化，似乎添加的线程越多，完成所需的时间就越多。该程序将应用 Bsearch 的数组长度和 search 数组的长度作为 args，其中第一个数组中要搜索的值已初始化。并行化应用于所有三个 for 循环。

我在具有 20 个核心的单个节点上的 HPC 集群上运行此程序，脚本如下:

for threads in 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ; do
    export OMP_NUM_THREADS=${threads}
    ./binary_search_parallel.x 1000000000 100000000
done

我的问题是程序根本无法扩展:添加线程越多，花费的时间就越多。串行版本的性能更好。有人知道问题出在哪里吗？或者事实可能是没有足够的性能吞吐量来应对并行开销？

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

#define CPU_TIME (clock_gettime( CLOCK_PROCESS_CPUTIME_ID, &ts ), (double)ts.tv_sec + \
          (double)ts.tv_nsec * 1e-9)


int mybsearch(int *data, int low, int high, int Key)
 {

   int register mid;

   mid = (low + high) / 2;
   while(low <= high) {     


     if(data[mid] < Key)
       low = mid + 1; 
     else if(data[mid] > Key)
       high = mid - 1;
     else 
       return mid;

     mid = (low + high) / 2;
   }

   /* if ( Key == data[low] ) */
   /*   return 0; */
   /* else */
     return -1;
 }

#define N_DEFAULT  (1024*1024*128)
#define N_search_DEFAULT (N_DEFAULT / 10)

int main(int argc, char **argv)
{
  int N, Nsearch, i, n_threads = 1;
  int *data, *search;

  #ifndef _OPENMP
    printf("serial binary search\n");
  #else
  #pragma omp parallel
  {
    #pragma omp master
    {
      n_threads = omp_get_num_threads();
      printf("omp binary search with %d threads\n", n_threads );
    }
  }
  #endif

  if(argc > 1)
    N = atoi( *(argv+1) );
  else
    N = N_DEFAULT;

  if(argc > 2)
    Nsearch = atoi ( *(argv + 2) );
  else
    Nsearch = N_search_DEFAULT;

  printf("performing %d lookups on %d data..\n", Nsearch, N);

  printf("set-up data.."); fflush(stdout);
  data = (int*)malloc(N * sizeof(int));

  #if defined(_OPENMP)
   #pragma omp parallel for
      for (i = 0; i < N; i++)
        data[i] = i;
  #else
    for(i = 0; i < N; i++)
      data[i] = i;
  #endif

  printf(" set-up lookups.. "); fflush(stdout);  
  search = (int*)malloc(Nsearch * sizeof(int));
  srand(time(NULL));

  #if defined(_OPENMP)
    #pragma omp parallel for
      for (i = 0; i < Nsearch; i++)
        search[i] = rand() % N;
  #else
    for (i = 0; i < N; i++)
      search[i] = rand() % N;
  #endif


  int found = 0;
  double tstart, tstop;
  struct timespec ts;

  printf("\nstart cycle.. "); fflush(stdout);
  tstart = CPU_TIME;

  #if defined(_OPENMP)
    #pragma omp parallel for
      for (i = 0; i < Nsearch; i++)
        if( mybsearch(data, N, search[i]) >= 0)
          found++;
  #else
    for ( i = 0; i < Nsearch; i++)
      if(mybsearch(data, N, search[i]) >= 0)
        found++;
  #endif

  tstop = CPU_TIME;

  printf("time elapsed: %g\n", tstop - tstart);

  //free(data);
  //free(search);

  return 0;
 }

Answer 1

20个硬件线程来自同一个套接字？您的机器有 NUMA(非统一内存访问)架构吗？

也许这可能是您的瓶颈:内存访问的时间。如果您的机器是 NUMA，一旦并行初始化数据，由于内存位置错误，您可能会付出大量执行时间。

在 48 核 NUMA 计算机(8 NUMA 节点 x 6 核)上对代码进行测试时，如果出现以下情况，则可扩展性较差

1. 您不会将线程固定到核心(如果使用的线程数小于或等于单个插槽中的核心数)
2. 您使用多个 NUMA 内存组。您的代码的内存访问模式非常不规则，数据可以位于任何 NUMA 节点中。

这里是 10000000 10000000 参数的一些计时(以秒为单位):

• 序列号:~6,57
• 固定(带有任务集)序列号:~5,27
• 并行

• 固定并行 (OMP_PLACES=cores OMP_PROC_BIND=close)

您可以注意到，每次包含新的 NUMA 节点(7、13、19、25、31、37 和 43 个线程)时，秒数都会增加。从第二个并行解决方案到第一个并行解决方案的平均时间较短，因为在第二个解决方案中，我们对使用的 NUMA 节点数量有一些控制(由于线程固定)，从而减少了线程迁移到距离太远的另一个 NUMA 节点的机会。数据实际所在的节点。