OpenMP несколько потоков обновляют один и тот же массив

Question

У меня есть следующий код в моей программе, и я хочу ускорить его с помощью OpenMP.

...
for(i=curr_index; i < curr_index + rx_size; i+=2){ 
    int64_t tgt = rcvq[i];
    int64_t src = rcvq[i+1];
    if (!TEST(tgt)) {
        pred[tgt] = src;
        newq[newq_count++] = tgt;
    }
} 

В настоящее время у меня есть версия следующим образом:

...
chunk = rx_sz / omp_nthreads;

#pragma omp parallel for num_threads(omp_nthreads)
for (ii = 0; ii < omp_nthreads; ii++) { 
    int start = curr_index + ii * chunk;
    for (index = start; index < start + chunk; index +=2) { 
        int64_t tgt = rcvq[index];
        int64_t src = rcvq[index+1];
        if (!TEST(tgt)) {
            pred[tgt] = src;

            #pragma omp critical 
            newq[newq_count++] = tgt;
        }
    }
}

Когда я запускаю версию OpenMP, я вижу значительное снижение производительности по сравнению с оригинальной версией. Я думаю, что проблема может быть из-за "omp критического", который предотвращает параллельную обработку. Я хочу знать, что можно улучшить с помощью моего кода, чтобы повысить производительность по сравнению с последовательной версией. В коде rx_sz всегда кратен omp_nthreads.

Answer 1

Я почти уверен, что критический раздел omp ограничивает вашу производительность на данный момент.

Я бы порекомендовал вам собрать результаты в отдельные буферы / векторы и объединить их после выполнения параллельной обработки (конечно, если порядок не имеет значения для вас)

vector<vector<int64_t>> res;
res.resize(num_threads);
#pragma omp parallel for
for (index = 0; index < rx_sz/2; ++index) { 
        int64_t tgt = rcvq[2*index];
        int64_t src = rcvq[2*index+1];
        if (!TEST(tgt)) {
            pred[tgt] = src;

            res[omp_get_thread_num()].push_back(tgt);
        }
    }

// Merge all res vectors if needed

Answer 2

Да, критический раздел ограничивает вашу производительность. Вы должны собрать результаты локально для каждого потока, а затем объединить их.

size_t newq_offset = 0;
#pragma omp parallel
{
    // Figure out something clever here...
    const size_t max_newq_per_thread = max_newq / omp_get_num_threads();
    int64_t* local_newq = malloc(max_results_per_thread * sizeof(int64_t));
    size_t local_newq_count = 0;

    #pragma omp parallel for
    for (i=curr_index; i < curr_index + rx_size; i+=2)
        int64_t tgt = rcvq[2*index];
        int64_t src = rcvq[2*index+1];
        if (!TEST(tgt)) {
            pred[tgt] = src;
            local_newq_count++;
            assert(local_newq_count < max_newq_per_thread);
            local_newq[local_newq_count] = tgt;
        }
    }
    int local_offset;
    #pragma omp atomic capture
    {
        local_offset = offset;
        offset += local_newq_count;
    }
    for (size_t i = 0; i < counter; i++)
    {   
        res_global[i + local_offset] = res[i];
    }
}

При таком подходе все потоки работают параллельно при слиянии, а на atomic capture, Обратите внимание, что вы также можете сделать простую версию с atomic capture, это более эффективно, чем критический раздел, но все равно быстро станет узким местом:

size_t newq_count_local;
#pragma omp atomic capture
newq_count_local = newq_count++;
newq[newq_count_local] = tgt;

• Там нет гарантии о заказе в течение newq в любой из версий
• Всегда объявляйте переменные как можно более локальными! Особенно при использовании OpenMP. critical-версия, которую вы разместили, неверна, потому что index (определяется во внешней области) неявно разделяется между потоками.
• Все это предполагает отсутствие дубликатов внутриrcvq, В противном случае вы получите условие гонки на pred[tgt] = src;,
• Ваш подход к разрезанию цикла вручную является излишне сложным. Не нужно делать две петли, просто используйте одну pragma omp for петля.

Другой ответ дает правильную идею. Тем не менее, это C++, а не, как помечено, C. Есть также небольшая, но значительная проблема производительности при использовании std::vector<std::vector<>>, Обычно вектор реализуется с тремя указателями, всего 24 байта. на push_back один из указателей увеличивается. Это означает, что: а) указатели локальных векторов из нескольких потоков находятся в одной и той же строке кэша, и б) в каждом успешном TEST, push_back читает и записывает в строку кэша, которая используется другим потоком (ами). Эта строка кэша должна постоянно перемещаться между ядрами, что значительно ограничивает масштабируемость этого подхода. Это называется ложным делением.

Я реализовал небольшой тест, основанный на другом ответе, который дал следующую производительность:

• 0.99 s - одна нить
• 1.58 s - два потока на двух соседних ядрах одного сокета
• 2.13 s - две нитки на двух сердечниках разных розеток
• 0.99 s - два потока, разделяющие одно ядро
• 0.62 s - 24 нитки на двух розетках

Принимая во внимание, что выше версия C масштабируется намного лучше:

• 0.46 s - один поток (не очень сопоставимый C против C++)
• 0.24 s - две темы
• 0.04 s - 24 темы