Почему сортировка с параллельным слиянием выполняется быстрее с одним потоком? - PullRequest
Новая
       61

Почему сортировка с параллельным слиянием выполняется быстрее с одним потоком?

0 голосов
/ 27 октября 2019

У меня есть следующий алгоритм сортировки параллельного слияния в openMP. OpenMP создает 8 потоков по умолчанию, но это намного медленнее, чем последовательный. Но когда я указываю omp_set_num_threads (1), т.е. устанавливаю число потоков равным одному, время быстрее, чем последовательное. Любое правдоподобное объяснение этому? 

void para_merge_sort(int para_arr[], int low, int high)
{
    if (low < high)
    {
        int med = low + (high-low)/2;
        #pragma omp task firstprivate(para_arr, low, med)
        para_merge_sort (para_arr, low, med);
        #pragma omp task firstprivate(para_arr, med, high)
        para_merge_sort (para_arr, med+1, high);
        #pragma omp taskwait
        merge (para_arr, low, med, high);
    }
}

void merge_sort()
{
    int seq_arr[MAX], para_arr[MAX];
    omp_set_num_threads(1);

    for (int i=0; i<MAX; ++i)
        seq_arr[i] = para_arr[i] = rand()%100;

    double start_time = omp_get_wtime();
    seq_merge_sort(seq_arr, 0, MAX-1);
    double comp_time = omp_get_wtime() - start_time;
    printf ("Sequential merge sort : %f\n", comp_time);

    start_time = omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single
        para_merge_sort(para_arr, 0, MAX-1);
    }
    comp_time = omp_get_wtime() - start_time;
    printf ("Parallel merge sort : %f\n", comp_time);

    /*for (int i=0; i<MAX; ++i)
        printf ("%d\n", para_arr[i]);*/
}

Последовательная сортировка слиянием: 0,004533

Параллельная сортировка слиянием: 0,007102

когда omp_set_num_threads (1):

Последовательнаясортировка слиянием: 0,005124

параллельная сортировка слиянием: 0,002424

...