Параллельное суммирование массива медленнее, чем последовательное в C ++

Question

Я пишу код для параллельного суммирования массива с C ++ std :: thread. Но параллельная сумма занимает 0,6 с, а последовательная - 0,3 с.

Я не думаю, что этот код выполняет какую-либо синхронизацию на arr или ret.

Почему такая ситуация происходит?

Мой процессор - i7-8700, который имеет 6 физических ядер.

#include <stdio.h>
#include <ctime>
#include <thread>

// Constants
#define THREADS 4
#define ARR_SIZE 200000000
int ret[THREADS];

// Function for thread.
void parallel_sum(int *arr, int thread_id) {
    int s = ARR_SIZE / THREADS * thread_id, e = ARR_SIZE / THREADS * (thread_id + 1);
    printf("%d, %d\n", s, e);
    for (int i = s; i < e; i++) ret[thread_id] += arr[i];
}

int main() {

    // Variable definitions
    int *arr = new int[ARR_SIZE]; // 1 billion

    time_t t1, t2; // Variable for time consuming checking
    std::thread *threads = new std::thread[THREADS];

    // Initialization
    for (int i = 0; i < ARR_SIZE; i++) arr[i] = 1;
    for (int i = 0; i < THREADS; i++) ret[i] = 0;
    long long int sum = 0;

    // Parallel sum start
    t1 = clock();
    for (int i = 0; i < THREADS; i++) threads[i] = std::thread(parallel_sum, arr, i);
    for (int i = 0; i < THREADS; i++) threads[i].join();
    t2 = clock();

    for (int i = 0; i < THREADS; i++) sum += ret[i];
    printf("[%lf] Parallel sum %lld \n", (float)(t2 - t1) / (float)CLOCKS_PER_SEC, sum);
    // Parallel sum end


    sum = 0; // Initialization


    // Sequential sum start
    t1 = clock();
    for (int i = 0; i < ARR_SIZE; i++) sum += arr[i];
    t2 = clock();

    printf("[%lf] Sequential sum %lld \n", (float)(t2 - t1) / (float)CLOCKS_PER_SEC, sum);
    // Sequential sum end


    return 0;
}

Answer 1

for (int i = s; i < e; i++) ret[thread_id] += arr[i];

Это вызывает большой конфликт в кэше, поскольку элементы массива ret, вероятно, совместно используют одну и ту же строку кэша. Обычно это называется ложное совместное использование .

Простой обходной путь - использовать вспомогательную (thread-) локальную переменную для обновления цикла и просто, наконец, увеличить общий счетчик, например:

int temp = 0;
for (int i = s; i < e; i++) temp += arr[i];
ret[thread_id] += temp;

Или лучше использовать один глобальный ret типа std::atomic<int> для многопоточной суммы. Затем вы можете просто написать:

int temp = 0;
for (int i = s; i < e; i++) temp += arr[i];
ret += temp;

Или еще эффективнее:

ret.fetch_add(temp, std::memory_order_relaxed);

Answer 2

С включенной оптимизацией компилятора (нет смысла в бенчмаркинге любым другим способом), я получаю следующие результаты:

[0.093481] Параллельная сумма 200000000
[0.073333] Последовательная сумма 200000000

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

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