Почему ускорение, которое я получаю за счет распараллеливания с OpenMP, уменьшается после определенного размера рабочей нагрузки?

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

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
#include <random>

void SingleThreaded(std::vector<float> &weights, int size)
{
    auto totalWeight = 0.0f;

    for (int index = 0; index < size; index++)
    {
        totalWeight += weights[index];
    }

    for (int index = 0; index < size; index++)
    {
        weights[index] /= totalWeight;
    }
}

void MultiThreaded(std::vector<float> &weights, int size)
{
    auto totalWeight = 0.0f;

#pragma omp parallel shared(weights, size, totalWeight) default(none)
    {
        // clang-format off
#pragma omp for reduction(+ : totalWeight)
        // clang-format on
        for (int index = 0; index < size; index++)
        {
            totalWeight += weights[index];
        }

#pragma omp for
        for (int index = 0; index < size; index++)
        {
            weights[index] /= totalWeight;
        }
    }
}

float TimeIt(std::function<void(void)> function)
{
    auto startTime = std::chrono::high_resolution_clock::now().time_since_epoch();
    function();
    auto endTime = std::chrono::high_resolution_clock::now().time_since_epoch();
    std::chrono::duration<float> duration = endTime - startTime;

    return duration.count();
}

int main(int argc, char *argv[])
{
    std::vector<float> weights(1 << 24);
    std::srand(std::random_device{}());
    std::generate(weights.begin(), weights.end(), []()
                  { return std::rand() / static_cast<float>(RAND_MAX); });

    for (int size = 1; size <= weights.size(); size <<= 1)
    {
        auto singleThreadedDuration = TimeIt(std::bind(SingleThreaded, std::ref(weights), size));
        auto multiThreadedDuration = TimeIt(std::bind(MultiThreaded, std::ref(weights), size));

        std::cout << "Size: " << size << std::endl;
        std::cout << "Speed up: " << singleThreadedDuration / multiThreadedDuration << std::endl;
    }
}

Я скомпилировал и запустил приведенный выше код с MinGW g++ на Win10 следующим образом:

g++ -O3 -static -fopenmp OpenMP.cpp; ./a.exe

Выходные данные (см. ниже) показывают максимальное ускорение примерно в 4,2 раза при размере вектора 524288. Это означает, что многопоточный код работал в 4,2 раза быстрее, чем однопоточный код при размере вектора 524288.

Size: 1
Speedup: 0.00614035
Size: 2
Speedup: 0.00138696
Size: 4
Speedup: 0.00264201
Size: 8
Speedup: 0.00324149
Size: 16
Speedup: 0.00316957
Size: 32
Speedup: 0.00315457
Size: 64
Speedup: 0.00297177
Size: 128
Speedup: 0.00569801
Size: 256
Speedup: 0.00596125
Size: 512
Speedup: 0.00979021
Size: 1024
Speedup: 0.019943
Size: 2048
Speedup: 0.0317662
Size: 4096
Speedup: 0.181818
Size: 8192
Speedup: 0.133713
Size: 16384
Speedup: 0.216568
Size: 32768
Speedup: 0.566396
Size: 65536
Speedup: 1.10169
Size: 131072
Speedup: 1.99395
Size: 262144
Speedup: 3.4772
Size: 524288
Speedup: 4.20111
Size: 1048576
Speedup: 2.82819
Size: 2097152
Speedup: 3.98878
Size: 4194304
Speedup: 4.00481
Size: 8388608
Speedup: 2.91028
Size: 16777216
Speedup: 3.85507

Итак, мои вопросы:

  1. Почему многопоточный код работает медленнее при меньшем размере вектора? Это чисто из-за накладных расходов на создание потоков и распределение работы, или я делаю что-то не так?
  2. Почему ускорение, которое я получаю, уменьшается после определенного размера?
  3. Какое наилучшее ускорение теоретически я мог бы достичь на используемом мной процессоре (i7 7700k)?
  4. Имеет ли значение различие между физическими ядрами ЦП и логическими ядрами ЦП с точки зрения ускорения?
  5. Допустил ли я какие-либо вопиющие ошибки в своем коде? Могу ли я что-то улучшить?

🤔 А знаете ли вы, что...
C++ используется для создания компиляторов, интерпретаторов и других инструментов разработки.


32
1

Ответ:

Решено
  1. Я согласен с вашей теорией; это, вероятно, накладные расходы на настройку.
  2. Хотя ядра ЦП вашего процессора имеют свои собственные кэши L1 и L2, все они совместно используют кэш L3 объемом 8 МБ, и как только вектор становится слишком большим, чтобы поместиться в этот кэш L3, возникает риск того, что потоки взаимно вытеснят страницы друг друга из кеш.
  3. Я предполагаю, что под «логическим ядром» вы подразумеваете гиперпоток? Они не могут фактически выполнять параллельные вычисления, они могут просто «заполнять», в то время как другой поток, например. заблокирован в ожидании памяти. Эффективный кеш, вычислительный связанный код, который может значительно ограничить их потенциал для параллелизма.
  4. Я не знаю, в какой степени ваш компилятор векторизует код, который он компилирует; Я бы сравнил две имеющиеся у вас функции с полностью векторизованной реализацией (например, с использованием cblas_sasum и cblas_sscal из хорошей реализации BLAS). Вполне возможно, что в данный момент вы оставляете без внимания производительность одного потока.