并行二分搜索的性能比串行版本差

Question

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

我运行这个程序在 HPC 集群上，在具有 20 个内核的单个节点上，使用以下脚本：

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个硬件线程来自同一个socket？你的机器有 NUMA（非统一内存访问）架构吗？

也许这可能是您的瓶颈：内存访问的计时。如果您的机器是 NUMA，一旦并行初始化数据，您可能会因为内存位置错误而花费大量执行时间。

在 48 核 NUMA 机器（8 NUMA 节点 x 6 核）上使用您的代码进行测试时，如果

您没有将线程固定到内核（如果使用的线程数小于或等于单个插槽中的内核数）
您使用了多个 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 节点的机会数据实际所在的节点。

并行二分搜索的性能比串行版本差

Parallel Binary Search performs worse than the serial version

c

multithreading

parallel-processing

openmp

hpc