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

Question

Я пытаюсь использовать OpenMP для оценки скорости реализованной мной структуры данных. Однако, похоже, я совершаю фундаментальную ошибку: пропускная способность уменьшается вместо увеличения количества потоков независимо от того, какую операцию я пытаюсь протестировать. Ниже вы можете увидеть код, который пытается измерить скорость for-l oop, поэтому я ожидаю, что он будет масштабироваться (несколько) линейно с количеством потоков, но не (скомпилирован на двухъядерном ноутбуке с и без флага -O3 на g ++ с c ++ 11).

#include <omp.h>
#include <atomic>
#include <chrono>
#include <iostream>

thread_local const int OPS = 10000;
thread_local const int TIMES = 200;

double get_tp(int THREADS)
{
    double threadtime[THREADS] = {0};

    //Repeat the test many times
    for(int iteration = 0; iteration < TIMES; iteration++)
    {
        #pragma  omp  parallel num_threads(THREADS)
        {
            double start, stop;
            int loc_ops = OPS/float(THREADS);
            int t = omp_get_thread_num();

            //Force all threads to start at the same time
            #pragma  omp  barrier
            start = omp_get_wtime();


            //Do a certain kind of operations loc_ops times
            for(int i = 0; i < loc_ops; i++)
            {
                //Here I would put the operations to benchmark
                //in this case a boring for loop
                int x = 0;
                for(int j = 0; j < 1000; j++)
                    x++;
            }

        stop = omp_get_wtime();
        threadtime[t] += stop-start;
        }
    }

    double total_time = 0;
    std::cout << "\nThread times: ";
    for(int i = 0; i < THREADS; i++)
    {
        total_time += threadtime[i];
        std::cout << threadtime[i] << ", ";
    }
    std::cout << "\nTotal time: " << total_time << "\n";
    double mopss = float(OPS)*TIMES/total_time;
    return mopss;
}

int main()
{
    std::cout << "\n1  " << get_tp(1) << "ops/s\n";
    std::cout << "\n2  " << get_tp(2) << "ops/s\n";
    std::cout << "\n4  " << get_tp(4) << "ops/s\n";
    std::cout << "\n8  " << get_tp(8) << "ops/s\n";
}

Выводит с -O3 на двухъядерном процессоре, поэтому мы не ожидаем увеличения пропускной способности после 2 потоков, но даже не при переходе от 1 к 2 потокам он уменьшается на 50%:

1 Thread 
Thread times: 7.411e-06, 
Total time: 7.411e-06
2.69869e+11 ops/s

2 Threads 
Thread times: 7.36701e-06, 7.38301e-06, 
Total time: 1.475e-05
1.35593e+11ops/s

4 Threads 
Thread times: 7.44301e-06, 8.31901e-06, 8.34001e-06, 7.498e-06, 
Total time: 3.16e-05
6.32911e+10ops/s

8 Threads 
Thread times: 7.885e-06, 8.18899e-06, 9.001e-06, 7.838e-06, 7.75799e-06, 7.783e-06, 8.349e-06, 8.855e-06, 
Total time: 6.5658e-05
3.04609e+10ops/s

Чтобы убедиться, что компилятор не удаляет l oop, я также попытался вывести «x» после измерения времени и насколько мне известно, проблема не устранена. Я также пробовал код на машине с большим количеством ядер, и он вел себя очень похоже. Без -O3 пропускная способность также не масштабируется. Так что явно что-то не так с тем, как я тестирую. Надеюсь, ты сможешь мне помочь.

Answer 1

Я не уверен, почему вы определяете производительность как общее количество операций на общее время ЦП , а затем удивляетесь уменьшающейся функцией количества потоков. Это будет почти всегда и всегда, за исключением случаев, когда срабатывают эффекты кеширования. Истинный показатель производительности c - это количество операций на время настенных часов .

Это легко показать с помощью простых математических рассуждений. Учитывая общую работу W и вычислительную мощность каждого ядра P, время на одном ядре составляет T_1 = W / P. Равномерное разделение работы между n ядрами означает, что каждое из них работает для T_1,n = (W / n + H) / P, где H - накладные расходы на поток, вызванные самим распараллеливанием. Их сумма составляет T_n = n * T_1,n = W / P + n (H / P) = T_1 + n (H / P). Накладные расходы всегда имеют положительное значение, даже в тривиальном случае так называемого смущающего параллелизма , когда два потока не нуждаются в взаимодействии или синхронизации. Например, запуск потоков OpenMP требует времени. Вы не можете избавиться от накладных расходов, вы можете только амортизировать их в течение срока службы потоков, убедившись, что каждый из них получает много работы. Следовательно, T_n> T_1 и при фиксированном количестве операций в обоих случаях производительность на n ядрах всегда будет ниже, чем на одном ядре. Единственным исключением из этого правила является случай, когда данные для работы размером W не помещаются в кеши нижнего уровня, а данные для работы размера W / n подходят. Это приводит к значительному ускорению, превышающему количество ядер, известному как сверхлинейное ускорение . Вы измеряете внутри функции потока, поэтому вы игнорируете значение H, а T_n должно более или менее быть равным T_1 в пределах точности таймера, но ...

При выполнении нескольких потоков несколько ядер ЦП, все они конкурируют за ограниченные общие ресурсы ЦП, а именно за кеш последнего уровня (если есть), пропускную способность памяти и тепловой пакет.

Пропускная способность памяти не является проблемой, когда вы просто увеличиваете скаляр переменная, но становится узким местом, когда код начинает фактически перемещать данные в ЦП и из него. Каноническим примером численных вычислений является умножение разреженной матрицы на вектор (spMVM) - правильно оптимизированная процедура spMVM, работающая с double ненулевыми значениями и long индексами, потребляющая так много полосы пропускания памяти, что можно полностью заполнить память шина всего с двумя потоками на сокет процессора, что делает дорогой 64-ядерный процессор очень плохим выбором в этом случае. Это верно для всех алгоритмов с низкой арифметикой c интенсивностью (операций на единицу объема данных).

Когда дело доходит до тепловой оболочки, большинство современных процессоров используют динамику c управление питанием и будет разгонять или уменьшать частоту ядер в зависимости от того, сколько из них активно. Следовательно, в то время как n ядер с пониженной тактовой частотой выполняют больше работы за единицу времени , чем одно ядро, одно ядро ​​превосходит n ядер с точки зрения работы на общее время ЦП , который является метрикой c, которую вы используете.

Имея в виду все это, нужно учитывать еще одну (но не менее важную) вещь - разрешение таймера и шум измерения. Ваше время работы выражается в парах микросекунд. Если ваш код не работает на каком-то специализированном оборудовании, которое ничего не делает, кроме запуска вашего кода (то есть без разделения времени с демонами, потоками ядра и другими процессами и без обработки прерываний), вам нужны тесты, которые работают на несколько порядков дольше, желательно хотя бы на пару секунд.

Answer 2

l oop почти наверняка все еще оптимизируется, даже если вы выведите значение x после внешнего l oop. Компилятор может тривиально заменить весь l oop одной инструкцией, поскольку границы l oop постоянны во время компиляции. Действительно, в в этом примере :

#include <iostream>

int main()
{
    int x = 0;
    for (int i = 0; i < 10000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            ++x;
        }
    }

    std::cout << x << '\n';
    return 0;
}

l oop заменяется единственной инструкцией по сборке mov esi, 10000000.

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

Подумайте о том, чтобы самый внутренний l oop делал что-то, что нельзя оптимизировать. Генерация случайных чисел является хорошим кандидатом, потому что она должна выполняться в постоянное время, и она имеет побочный эффект перестановки состояния PRNG (что делает невозможным полное удаление, если семя не известно заранее и компилятор может распутать все мутации в ГПСЧ).

Например, :

#include <iostream>
#include <random>

int main()
{
    std::mt19937 r;
    std::uniform_real_distribution<double> dist{0, 1};

    for (int i = 0; i < 10000; ++i) {
        for (int j = 0; j < 1000; ++j) {
            dist(r);
        }
    }

    return 0;
}

И циклы, и вызов ГПСЧ здесь остаются нетронутыми.