为什么单个进程对列表进行排序的速度比让许多进程对单独大小的单独列表进行排序要快得多？

Question

我在一台机器上有64个内核,运行排序总计1GB的数据.它们每个排序156,250项,不应共享任何数据结构(即总共有64个单独的数组被排序).但是,我运行的核心越多,每个核心在其自己的排序任务中的速度就越慢.

时间测量正在这样做:

void sort_ranges(std::vector<std::vector<std::vector<int> > > & range_partitions, int num_workers, std::string filename, std::string outfile)
{
  #pragma omp parallel default(none) shared(range_partitions, outfile, num_workers)
  {
    int i = omp_get_thread_num();
    std::vector<int> data_vec; //Data copied into separate data structure for each thread
    for(int x = 0; x < num_workers; x ++) {
      data_vec.reserve(data_vec.size() + (range_partitions[x][i]).size());
      data_vec.insert(data_vec.end(), range_partitions[x][i].begin(), range_partitions[x][i].end());
    }
    int n = data_vec.size();
    int * data = &data_vec[0];
    double start = omp_get_wtime();
    std::sort(data, data + n); //Measure sort function call
    double sort_done = omp_get_wtime() - start;
  }
}

当我运行1GB的数据时,每个进程对156,250的数组进行排序,大约需要10秒.显然这是非常缓慢的.如果我运行一个对156,250大小进行排序的进程,则该过程需要<0.1秒进行排序.

我真的很困惑,因为每个进程都在不同的阵列上运行,所以没有理由让更多核心运行相同的任务会减慢所有其他核心的速度.

我认为有一些关于我如何管理内存的问题.任何帮助表示赞赏!

我意识到增加并行性有很多不同的成本,例如进程开销或共享内存,但是我特别关注每个线程的单独数据结构上调用的std :: sort()函数的减速

Answer 1

当您的数据大于缓存(并且1 GB的数据肯定会从缓存中移出)和糟糕的访问模式(并且排序通常非常糟糕,尤其是第一步)时,内存带宽总是有限的成为你的极限.如果你已经用一个核心来限制它,那么并行排序它的N个副本会减慢它的速度N次 - 可能更多,因为你也在颠覆L3缓存(每个核心试图访问不相关的数据).