Как здесь распараллелили сортировку OpenMP?

Question

[ahame]

Задача: распараллелить сортировку поразрядную сортировку для целых чисел с простым слиянием. Как в данном коде идет распараллеливание?

void signedRadixSortOmp(int* sortVec, int sizeVec) {
    int shift = 0;
    int s = static_cast<int>(sizeof(int));
#pragma omp parallel shared(sortVec, sizeVec)
    {
        int sizePartVec = 0;
        int numberThreads = omp_get_num_threads();
        sizePartVec = sizeVec / numberThreads;
        int remainder = sizeVec % numberThreads;
        int threadId = omp_get_thread_num();

#pragma omp master
        {
            sizePartVec += remainder;
            remainder = 0;
        }

        int* localOutVec = new int[sizePartVec];
        int* localInVec = new int[sizePartVec];
        int j = 0;
        for (int i = threadId * sizePartVec + remainder;
        i < (threadId + 1) * sizePartVec + remainder; i++, j++) {
            localInVec[j] = sortVec[i];
        }

        std::vector<int> counters(sizeof(int) * 256);
        createCounters(localInVec, counters.data(), sizePartVec);
        int* count;
        for (int i = 0; i < s; i++) {
            count = counters.data() + 256 * i;
            signedRadix(i, sizePartVec, localInVec, localOutVec, count);
            std::swap(localInVec, localOutVec);
        }
        delete[] localOutVec;

#pragma omp master
        {
            for (int i = 0; i < sizePartVec; i++)
                sortVec[i] = localInVec[i];
            shift++;
        }
#pragma omp barrier
#pragma omp critical
        if (threadId != 0) {
            mergeOrderVec(sortVec, shift * sizePartVec + remainder,
        localInVec, sizePartVec);
            shift++;
        }
        delete[] localInVec;
    }
}

Answer 1

[Wataru]

Сортируют параллельно куски массива. В конце объединяют отсортированные части операцией слияния (эта часть не параллельна).

Надо сказать, реализация ужасна. Последняя часть - слияние, похоже, вообще выполняется за квадрат. Т.е. этот подход сильно медленнее непараллельной сортировки всегда.

Если уж и параллелить radix sort, то надо параллельно считать сколько в каждом куске каждой цифры, потом высчитать, куда каждая цифра из каждого куска должна попасть, и потом параллельно каждый кусок перетасовать в нужные места.