Мой алгоритм mergesort работает медленнее с OpenMP, как я могу сделать это быстрее, чем сериализованная форма? - PullRequest
4 голосов
/ 09 мая 2019

Я изучаю параллельное программирование и тестирую его на алгоритмах сортировки. Самый простой способ, который я нашел, это использовать 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) не очень хорошо настроен.

1 Ответ

0 голосов
/ 12 мая 2019

Спасибо всем, что решил проблему.

Прежде всего, я не установил многоядерные режимы на своей виртуальной машине.

Затем я изменил конструкцию sections для task.

Я также использовал большее количество элементов в моем массиве (2 миллиона).

И, наконец, я добавил фильтр, чтобы прекратить использовать параллелизм, когда массив меньше, чем "n" элементов:

void mergeSortSerial(int aux[], int left, int right){
    if (left < right){
        int middle = (left + right)/2;
        mergeSortSerial(aux,left,middle); //call 1
        mergeSortSerial(aux,middle+1,right); //call 2
        merge(aux,left,middle,right);
    }
}

void mergeSort (int aux[], int left, int right){
    if (left < right){
        if ((right-left) > 1000){
            int middle = (left + right)/2;
           #pragma omp task firstprivate (aux, left, middle)
                mergeSort(aux,left,middle); //call 1
            #pragma omp task firstprivate (aux, middle, right)
                mergeSort(aux,middle+1,right); //call 2
            #pragma omp taskwait
            merge(aux,left,middle,right);
        } else{mergeSortSerial(aux, left, right);}
    }
}

Я обнаружил, что 1.000.000 - это лучшее число для "n", мой алгоритм в 2 раза быстрее, чем последовательный.

...