Я изучаю параллельное программирование и тестирую его на алгоритмах сортировки.
Самый простой способ, который я нашел, это использовать OpenMP, поскольку он предлагает простой способ реализации потоков.
Я провел исследование и обнаружил, что другие люди уже сделали это, а затем я попробовал некоторые коды. Но когда я тестирую его с perf stat -r 10 -d
в Linux, я получаю худшее время, чем сериализованный код (в некоторых случаях это вдвое больше).
Я попытался использовать другое количество элементов в массиве, максимум, который я использовал, составлял 1.000.000 чисел, как будто я использую больше, я получаю сообщение об ошибке.
void merge(int aux[], int left, int middle, int right){
int temp[middle-left+1], temp2[right-middle];
for(int i=0; i<(middle-left+1); i++){
temp[i]=aux[left+i];
}
for(int i=0; i<(right-middle); i++){
temp2[i]=aux[middle+1+i];
}
int i=0, j=0, k=left;
while(i<(middle-left+1) && j<(right-middle))
{
if(temp[i]<temp2[j]){
aux[k++]=temp[i++];
}
else{
aux[k++]=temp2[j++];
}
}
while(i<(middle-left+1)){
aux[k++]=temp[i++];
}
while(j<(right-middle)){
aux[k++]=temp2[j++];
}
}
void mergeSort (int aux[], int left, int right){
if (left < right){
int middle = (left + right)/2;
omp_set_num_threads(2);
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
mergeSort(aux,left,middle); //call 1
#pragma omp section
mergeSort(aux,middle+1,right); //call 2
}
}
merge(aux,left,middle,right);
}
}
int main(){
generate_list(Vet, n);
mergeSort(Vet, 0, n-1);
return(0);
}
Ниже приведены результаты, которые я получаю:
OpenMP код:
Статистика счетчика производительности для ./mergeomp
(10 прогонов):
12,489169 task-clock (msec) # 0,717 CPUs utilized ( +- 3,58% )
8 context-switches # 0,681 K/sec ( +- 6,62% )
0 cpu-migrations # 0,000 K/sec
167 page-faults # 0,013 M/sec ( +- 0,79% )
<not supported> cycles
<not supported> instructions
<not supported> branches
<not supported> branch-misses
<not supported> L1-dcache-loads
<not supported> L1-dcache-load-misses
<not supported> LLC-loads
<not supported> LLC-load-misses
0,01743 +- 0,00211 seconds time elapsed ( +- 12,10% )
Серийный путь (простой код):
Статистика счетчика производительности для ./mergesort
(10 прогонов):
3,757053 task-clock (msec) # 0,449 CPUs utilized ( +- 0,72% )
1 context-switches # 0,293 K/sec ( +- 16,32% )
0 cpu-migrations # 0,000 K/sec
139 page-faults # 0,037 M/sec ( +- 0,34% )
<not supported> cycles
<not supported> instructions
<not supported> branches
<not supported> branch-misses
<not supported> L1-dcache-loads
<not supported> L1-dcache-load-misses
<not supported> LLC-loads
<not supported> LLC-load-misses
0,008375 +- 0,000276 seconds time elapsed ( +- 3,29% )
Я что-то не так делаю? Я компилирую его с флагом -fopenmp
, но не знаю, не подходит ли сортировка слиянием для распараллеливания, или если моя виртуальная машина Linux (я запускаю Ubuntu на машине с виртуальной виртуальной машиной, мой компьютер имеет Процессор Core I7) не очень хорошо настроен.