我正在修补OpenMP，并试图实现quicksort的并行版本
我已经实现了一个版本，它总是将第一个元素作为pivot，它的并行版本，通过选择三个随机元素的中间值来随机化pivot的版本，以及它的并行化版本。
困扰我的是，我在第一次并行化中获得了很好的速度，而第二个(尽管以相同的方式并行化(比顺序对应的慢
在这两种情况下，我都只对函数的第一次调用进行并行化，我知道在三次递归中我可以进行更深入的并行化，但关键是我希望从两次并行化中获得相同的加速。
以下是"幼稚"(无随机化(分区函数的代码片段：
int partition(vector<int>& v, int p, int q){
int x = v[p];
int i = p;
for(int j = p+1; j <= q; j++){
if(v[j] <= x){
i++;
swap(v[i], v[j]);
}
}
swap(v[i], v[p]);
return i;
}
这就是随机划分函数：
int rand_median(const vector<int>& v, int p, int q){
int n1 = (rand() % (p - q)) + p;
int n2 = (rand() % (p - q)) + p;
int n3 = (rand() % (p - q)) + p;
if((v[n1] <= v[n2] && v[n1] >= v[n3]) || (v[n1] <= v[n3] && v[n1] >= v[n2])) return n1;
else if ((v[n2] <= v[n1] && v[n2] >= v[n3]) || (v[n2] <= v[n3] && v[n2] >= v[n1])) return n2;
else return n3;
}
int rand_partition(vector<int>& v, int p, int q){
int pivot = rand_median(v,p,q);
swap(v[p], v[pivot]);
int x = v[p];
int i = p;
for(int j = p+1; j <= q; j++){
if(v[j] <= x){
i++;
swap(v[i], v[j]);
}
}
swap(v[i], v[p]);
return i;
}
天真的快速排序：
void quicksort(vector<int>& v, int s, int e){
if(s >= e) return;
int p = partition(v,s,e);
quicksort(v,s,p-1);
quicksort(v,p+1,e);
}
并行天真快速排序：
void quick_par(vector<int>& v, int s, int e){
if(s >= e) return;
int p = partition(v,s,e);
omp_set_num_threads(2);
#pragma omp parallel sections
{
#pragma omp section
quicksort(v,s,p-1);
#pragma omp section
quicksort(v,p+1,e);
}
}
随机快速排序：
void quick_rand(vector<int>& v, int s, int e){
if(s >= e) return;
int p = rand_partition(v,s,e);
quick_rand(v,s,p-1);
quick_rand(v,p+1,e);
}
并行随机快速排序：
void quick_par_rand(vector<int>& v, int s, int e){
if(s >= e) return;
int p = rand_partition(v,s,e);
omp_set_num_threads(2);
#pragma omp parallel sections
{
#pragma omp section
quick_rand(v,s,p-1);
#pragma omp section
quick_rand(v,p+1,e);
}
}
以下是使用谷歌基准获得的结果：
bench_ser 887282457 ns 887038659 ns 10 //naive quicksort
bench_par 10738723 ns 10734826 ns 70 //parallelized naive
bench_rand 613904 ns 613686 ns 1039 //randomized quicksort
bench_par_rand 3249751 ns 3248460 ns 213 //parallelized randomized
bench_sort 106110 ns 106074 ns 5952 //std::sort
正如您所看到的，并行随机化版本比顺序版本慢。这是我使用过的整个代码的粘贴框。
并行版本bench_par_rand不正确：它使用的rand不是线程安全的。这会导致比赛状态。因此，结果可能不是随机的(快速排序所需的关键点(，代码也会慢得多，因为线程会不断尝试修改rand函数的共享内部状态(迭代种子(。如果可能的话，考虑使用C++11随机数生成器(每个线程一个(。
一个快速的解决方法是将thread_local存储和C++11随机数生成器一起使用，并用safe_rand()重命名所有rand()。这里有一个例子：
thread_local std::uniform_int_distribution<int> distrib(0, RAND_MAX);
thread_local std::mt19937 rdGen;
thread_local auto safe_rand = std::bind(distrib, rdGen);
使用局部变量而不是全局thread_local(以及使用特定的uniform_int_distribution而不是模数(可以提高性能，尽管这样做有点乏味
以下是时间安排：
Base version:
- bench_rand: 582499 ns
- bench_par_rand: 2765300 ns
Fixed version with thread_local:
- bench_rand: 1109800 ns
- bench_par_rand: 737799 ns
Fixed version with local variables:
- bench_rand: 798699 ns
- bench_par_rand: 572300 ns
上一个固定的并行版本要快得多！然而，最后一个固定的顺序版本也比以前慢。我认为这是由于一个较慢的随机生成器。最后，代码中没有截断方法(对于小数组，从快速排序切换到更快的算法(。因此，随机生成器的成本在很大程度上得到了体现。