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

Question

我编写了以下代码，该代码在数组中执行一定数量的二进制搜索。我将其与OpenMP并行化，似乎我添加线程的次数越多，完成时间就越多。该程序将在其中应用Bsearch的数组的长度和在第一个数组中要搜索的值初始化的search数组的长度作为参数。并行化在所有三个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

您的程序在没有大量IO的情况下执行计算，因此添加更多线程（超出内核数量）意味着您只是增加了上下文切换的开销，而没有任何其他好处。这就是为什么它不扩展，因为每个线程都占用CPU。

添加更多线程仅在它们正在等待某些东西时才有用，而CPU可以执行其他任务。