为什么让单个进程对列表进行排序比让多个进程对大小相同的单独列表进行排序要快得多？
Why is having a single process sort a list so much faster than having many processes sort separate lists of equal size?
我单机64核运行正在对总共1GB的数据进行排序。他们每个排序 156,250 个项目，并且不应该共享任何数据结构（即总共有 64 个单独的数组被排序）。然而，我拥有 运行ning 的内核越多，每个内核在执行自己的排序任务时就越慢。
时间测量是这样进行的：
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() 函数在每个线程的单独数据结构上调用的速度减慢
对于并行编程，必须考虑许多因素。
首先，创建单独的 threads/setting 多个进程的启动成本（开销）不可忽略。出于这个原因，添加并行性通常会使事情 运行 更少 高效，除非你有足够的数据 运行 多个线程实际上会提高整体 运行时间.
其次，这些任务必须安排在您可用的内核数量上。如果您有 4 个核心和 64 个任务，则需要将这 64 个任务安排到核心上 - 如果每个任务需要不同的时间来完成，这将是一项重要的任务。
第三，如果线程之间存在任何干扰，则会减慢速度，尤其是在线程数量众多的情况下。
此外，还有倾斜方面，其中最慢的任务是瓶颈 - 在最慢的任务完成之前，整个进程集不会被视为完成。
这些只是一些应该考虑的因素。
总内存带宽是有限的，当你的数据大于你的缓存（1 GB 的数据肯定会从你的缓存中消失）和一个糟糕的访问模式（并且排序通常很糟糕，尤其是第一步) 内存速度将成为你的极限。如果您已经用一个核心限制了它，那么并行排序它的 N 个副本将使它的速度减慢 N 倍 - 可能更多，因为您也在颠簸 L3 缓存（每个核心都试图访问不相关的数据）。
你的问题没有包含 minimum working example，所以我无法重现你的问题。
我同意其他人的看法，您可能看到的是使用太多内核进行排序会导致 cache thrashing，尽管我无法根据自己的测试证明这一点.
当CPU从内存中读取数据时，它不只是读取一个字节。它读取 许多 字节。这些存储在缓存中以便快速访问。缓存是分层的，并在处理器之间或多或少地共享，如下所示：
如您所见，所有内核共享三级缓存。如果内核运行的内存地址彼此相距较远，则内核将有有限的缓存重叠并竞争使用缓存。
验证这是否发生在您的代码中很容易（至少，如果您有 Linux）。您可以使用 perf command 来收集有关程序正在执行的操作的数据。
在这个问题的底部，我包含了一个 MWE，我认为你在问什么。然后，我使用以下 perf 命令收集有关 MWE 行为的统计信息。
perf stat -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads,L1-dcache-stores,l2_rqsts.miss,LLC-load-misses,LLC-loads,LLC-prefetch-misses,LLC-store-misses,LLC-stores ./a.out m
单线程操作的结果如下：
18,676,838 cache-misses # 69.492 % of all cache refs (27.28%)
26,876,349 cache-references (36.38%)
143,224,257 L1-dcache-load-misses # 1.65% of all L1-dcache hits (36.39%)
8,682,532,168 L1-dcache-loads (36.40%)
4,130,005,905 L1-dcache-stores (36.40%)
92,709,572 l2_rqsts.miss (36.40%)
2,409,977 LLC-load-misses # 34.83% of all LL-cache hits (36.39%)
6,919,668 LLC-loads (36.37%)
23,562,449 LLC-prefetch-misses (18.16%)
16,038,395 LLC-store-misses (18.19%)
79,580,399 LLC-stores (18.18%)
24.578381342 seconds time elapsed
对于 运行 四个线程：
21,357,447 cache-misses # 74.720 % of all cache refs (23.99%)
28,583,269 cache-references (33.10%)
160,265,596 L1-dcache-load-misses # 1.85% of all L1-dcache hits (35.91%)
8,670,516,235 L1-dcache-loads (36.52%)
4,131,943,678 L1-dcache-stores (36.50%)
102,495,289 l2_rqsts.miss (36.50%)
2,768,956 LLC-load-misses # 38.05% of all LL-cache hits (32.91%)
7,277,568 LLC-loads (31.23%)
29,220,858 LLC-prefetch-misses (15.36%)
18,920,533 LLC-store-misses (15.26%)
104,834,221 LLC-stores (14.85%)
10.334248457 seconds time elapsed
如您所见，运行 四个线程确实导致更多缓存未命中
我。这可能不是统计上显着的增长；我没有 运行 多个
次检查。但是，与您不同的是，我看到更多的性能得到改善
线程。
为了模拟缓存争用，我可以通过使用比核心更多的线程来超额订阅我的 CPU。为此，我设置了 OMP_NUM_THREADS 环境变量：
export OMP_NUM_THREADS=32
有 32 个线程，我看到：
“./a.out m”的性能计数器统计信息：
24,222,105 cache-misses # 77.175 % of all cache refs (23.39%)
31,385,891 cache-references (32.47%)
161,353,805 L1-dcache-load-misses # 1.87% of all L1-dcache hits (35.27%)
8,618,074,931 L1-dcache-loads (36.70%)
4,131,633,620 L1-dcache-stores (36.28%)
107,094,632 l2_rqsts.miss (36.21%)
5,299,670 LLC-load-misses # 56.36% of all LL-cache hits (31.93%)
9,403,090 LLC-loads (29.02%)
46,500,188 LLC-prefetch-misses (15.09%)
20,131,861 LLC-store-misses (14.26%)
105,310,438 LLC-stores (14.15%)
10.379022550 seconds time elapsed
注意我们的 LLC-load-misses（末级缓存）已经从 34% 到 38% 到
随着线程数量的增加，增加了 56%。然而，速度并没有太大影响。
这可能是因为数据一开始就没有良好的缓存位置。
无论如何，这是研究您的问题的一种方法。如果你想要更好的帮助
这个，你必须自己制作一个 MWE。
您可以通过减少正在使用的线程数并指定它们的关联性来缓解一些缓存争用，这样线程就不会共享相同的 L2/L3 缓存（取决于您的处理器）。更多信息是 here.
最小工作示例
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
typedef std::vector< std::vector<int> > data_t;
data_t GenData(std::mt19937 &mt_rand, int vec_num, int vec_len){
data_t data;
data.reserve(vec_num);
for(unsigned int i=0;i<vec_num;i++){
data.emplace_back();
data.back().reserve(vec_len);
for(unsigned int i=0;i<vec_len;i++)
data.back().emplace_back(mt_rand());
}
return data;
}
void SortSingle(data_t &data){
for(auto &v: data)
std::sort(v.begin(),v.end());
}
void SortMulti(data_t &data){
#pragma omp parallel for default(none) shared(data)
for(unsigned int i=0;i<data.size();i++)
std::sort(data[i].begin(), data[i].end());
}
int main(int argc, char **argv){
std::mt19937 mt_rand;
typedef std::chrono::high_resolution_clock clock;
std::cout<<"Generating data..."<<std::endl;
auto data = GenData(mt_rand,1600,156250);
std::cout<<"Sorting data..."<<std::endl;
const auto start_time = clock::now();
if(argv[1][0]=='s')
SortSingle(data);
else if (argv[1][0]=='m')
SortMulti(data);
else
std::cout<<"Unknown sort type!"<<std::endl;
const auto end_time = clock::now();
const auto time_diff = std::chrono::duration_cast<std::chrono::duration<double>>(end_time - start_time).count();
std::cout<<"Time = "<<time_diff<<"s"<<std::endl;
return 0;
}
您的代码遗漏了最后一个关键的大括号。
我认为您要编写的代码如下所示。
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)
{
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;
}
}
我认为您的代码没有达到您的预期。
#pragma omp parallel 表示 每个 线程都应该执行您的块的内容。
变量 i 没有出现在您的代码摘录中，因此无法知道它的作用。
但是，每个线程似乎都在将多个范围复制到 data_vec，之后每个线程都对相同的数据进行排序。
您可能想试试这个：
void sort_ranges(std::vector<std::vector<std::vector<int> > > & range_partitions, int num_workers, std::string filename, std::string outfile) {
#pragma omp parallel for default(none) shared(range_partitions, outfile)
for(int x=0;x<num_workers;x++){
std::vector<int> data_vec(range_partitions[x][i].begin(), range_partitions[x][i].end()); //Data copied into separate data structure for each thread
double start = omp_get_wtime();
std::sort(data_vec.begin(), data_vec.end()); //Measure sort function call
double sort_done = omp_get_wtime() - start;
}
}
我单机64核运行正在对总共1GB的数据进行排序。他们每个排序 156,250 个项目，并且不应该共享任何数据结构（即总共有 64 个单独的数组被排序）。然而，我拥有 运行ning 的内核越多，每个内核在执行自己的排序任务时就越慢。
时间测量是这样进行的：
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() 函数在每个线程的单独数据结构上调用的速度减慢
对于并行编程，必须考虑许多因素。
首先，创建单独的 threads/setting 多个进程的启动成本（开销）不可忽略。出于这个原因，添加并行性通常会使事情 运行 更少 高效，除非你有足够的数据 运行 多个线程实际上会提高整体 运行时间.
其次，这些任务必须安排在您可用的内核数量上。如果您有 4 个核心和 64 个任务，则需要将这 64 个任务安排到核心上 - 如果每个任务需要不同的时间来完成，这将是一项重要的任务。
第三，如果线程之间存在任何干扰，则会减慢速度，尤其是在线程数量众多的情况下。
此外，还有倾斜方面，其中最慢的任务是瓶颈 - 在最慢的任务完成之前，整个进程集不会被视为完成。
这些只是一些应该考虑的因素。
总内存带宽是有限的，当你的数据大于你的缓存（1 GB 的数据肯定会从你的缓存中消失）和一个糟糕的访问模式（并且排序通常很糟糕，尤其是第一步) 内存速度将成为你的极限。如果您已经用一个核心限制了它，那么并行排序它的 N 个副本将使它的速度减慢 N 倍 - 可能更多，因为您也在颠簸 L3 缓存（每个核心都试图访问不相关的数据）。
你的问题没有包含 minimum working example，所以我无法重现你的问题。
我同意其他人的看法，您可能看到的是使用太多内核进行排序会导致 cache thrashing，尽管我无法根据自己的测试证明这一点.
当CPU从内存中读取数据时，它不只是读取一个字节。它读取 许多 字节。这些存储在缓存中以便快速访问。缓存是分层的，并在处理器之间或多或少地共享，如下所示：
如您所见，所有内核共享三级缓存。如果内核运行的内存地址彼此相距较远，则内核将有有限的缓存重叠并竞争使用缓存。
验证这是否发生在您的代码中很容易（至少，如果您有 Linux）。您可以使用 perf command 来收集有关程序正在执行的操作的数据。
在这个问题的底部，我包含了一个 MWE，我认为你在问什么。然后，我使用以下 perf 命令收集有关 MWE 行为的统计信息。
perf stat -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-loads,L1-dcache-stores,l2_rqsts.miss,LLC-load-misses,LLC-loads,LLC-prefetch-misses,LLC-store-misses,LLC-stores ./a.out m
单线程操作的结果如下：
18,676,838 cache-misses # 69.492 % of all cache refs (27.28%)
26,876,349 cache-references (36.38%)
143,224,257 L1-dcache-load-misses # 1.65% of all L1-dcache hits (36.39%)
8,682,532,168 L1-dcache-loads (36.40%)
4,130,005,905 L1-dcache-stores (36.40%)
92,709,572 l2_rqsts.miss (36.40%)
2,409,977 LLC-load-misses # 34.83% of all LL-cache hits (36.39%)
6,919,668 LLC-loads (36.37%)
23,562,449 LLC-prefetch-misses (18.16%)
16,038,395 LLC-store-misses (18.19%)
79,580,399 LLC-stores (18.18%)
24.578381342 seconds time elapsed
对于 运行 四个线程：
21,357,447 cache-misses # 74.720 % of all cache refs (23.99%)
28,583,269 cache-references (33.10%)
160,265,596 L1-dcache-load-misses # 1.85% of all L1-dcache hits (35.91%)
8,670,516,235 L1-dcache-loads (36.52%)
4,131,943,678 L1-dcache-stores (36.50%)
102,495,289 l2_rqsts.miss (36.50%)
2,768,956 LLC-load-misses # 38.05% of all LL-cache hits (32.91%)
7,277,568 LLC-loads (31.23%)
29,220,858 LLC-prefetch-misses (15.36%)
18,920,533 LLC-store-misses (15.26%)
104,834,221 LLC-stores (14.85%)
10.334248457 seconds time elapsed
如您所见，运行 四个线程确实导致更多缓存未命中 我。这可能不是统计上显着的增长；我没有 运行 多个 次检查。但是，与您不同的是，我看到更多的性能得到改善 线程。
为了模拟缓存争用，我可以通过使用比核心更多的线程来超额订阅我的 CPU。为此，我设置了 OMP_NUM_THREADS 环境变量：
export OMP_NUM_THREADS=32
有 32 个线程，我看到：
“./a.out m”的性能计数器统计信息：
24,222,105 cache-misses # 77.175 % of all cache refs (23.39%)
31,385,891 cache-references (32.47%)
161,353,805 L1-dcache-load-misses # 1.87% of all L1-dcache hits (35.27%)
8,618,074,931 L1-dcache-loads (36.70%)
4,131,633,620 L1-dcache-stores (36.28%)
107,094,632 l2_rqsts.miss (36.21%)
5,299,670 LLC-load-misses # 56.36% of all LL-cache hits (31.93%)
9,403,090 LLC-loads (29.02%)
46,500,188 LLC-prefetch-misses (15.09%)
20,131,861 LLC-store-misses (14.26%)
105,310,438 LLC-stores (14.15%)
10.379022550 seconds time elapsed
注意我们的 LLC-load-misses（末级缓存）已经从 34% 到 38% 到 随着线程数量的增加，增加了 56%。然而，速度并没有太大影响。 这可能是因为数据一开始就没有良好的缓存位置。
无论如何，这是研究您的问题的一种方法。如果你想要更好的帮助 这个，你必须自己制作一个 MWE。
您可以通过减少正在使用的线程数并指定它们的关联性来缓解一些缓存争用，这样线程就不会共享相同的 L2/L3 缓存（取决于您的处理器）。更多信息是 here.
最小工作示例
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
typedef std::vector< std::vector<int> > data_t;
data_t GenData(std::mt19937 &mt_rand, int vec_num, int vec_len){
data_t data;
data.reserve(vec_num);
for(unsigned int i=0;i<vec_num;i++){
data.emplace_back();
data.back().reserve(vec_len);
for(unsigned int i=0;i<vec_len;i++)
data.back().emplace_back(mt_rand());
}
return data;
}
void SortSingle(data_t &data){
for(auto &v: data)
std::sort(v.begin(),v.end());
}
void SortMulti(data_t &data){
#pragma omp parallel for default(none) shared(data)
for(unsigned int i=0;i<data.size();i++)
std::sort(data[i].begin(), data[i].end());
}
int main(int argc, char **argv){
std::mt19937 mt_rand;
typedef std::chrono::high_resolution_clock clock;
std::cout<<"Generating data..."<<std::endl;
auto data = GenData(mt_rand,1600,156250);
std::cout<<"Sorting data..."<<std::endl;
const auto start_time = clock::now();
if(argv[1][0]=='s')
SortSingle(data);
else if (argv[1][0]=='m')
SortMulti(data);
else
std::cout<<"Unknown sort type!"<<std::endl;
const auto end_time = clock::now();
const auto time_diff = std::chrono::duration_cast<std::chrono::duration<double>>(end_time - start_time).count();
std::cout<<"Time = "<<time_diff<<"s"<<std::endl;
return 0;
}
您的代码遗漏了最后一个关键的大括号。
我认为您要编写的代码如下所示。
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)
{
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;
}
}
我认为您的代码没有达到您的预期。
#pragma omp parallel 表示 每个 线程都应该执行您的块的内容。
变量 i 没有出现在您的代码摘录中，因此无法知道它的作用。
但是，每个线程似乎都在将多个范围复制到 data_vec，之后每个线程都对相同的数据进行排序。
您可能想试试这个：
void sort_ranges(std::vector<std::vector<std::vector<int> > > & range_partitions, int num_workers, std::string filename, std::string outfile) {
#pragma omp parallel for default(none) shared(range_partitions, outfile)
for(int x=0;x<num_workers;x++){
std::vector<int> data_vec(range_partitions[x][i].begin(), range_partitions[x][i].end()); //Data copied into separate data structure for each thread
double start = omp_get_wtime();
std::sort(data_vec.begin(), data_vec.end()); //Measure sort function call
double sort_done = omp_get_wtime() - start;
}
}