Потеря производительности параллельно для

Question

У меня есть программа, которая более или менее выполняет некоторые векторные операции несколько раз. Когда я пытался использовать parallel_for для параллельного выполнения одних и тех же задач, я наблюдал значительное увеличение времени на одну задачу. Каждая задача читает из одних и тех же данных, и синхронизация не происходит. Вот пример кода (для этого требуется библиотека Taskflow (https://github.com/cpp-taskflow/cpp-taskflow):

#include <array>
#include <numeric>
#include <x86intrin.h>
#include "taskflow.hpp"

//#define USE_AVX_512 1
constexpr size_t Size = 5000;
struct alignas(64) Vec : public std::array<double, Size> {};

struct SimulationData
{
    Vec a_;
    Vec b_;
    Vec c_;

    SimulationData()
    {
        std::iota(a_.begin(), a_.end(), 10);
        std::iota(b_.begin(), b_.end(), 5);
        std::iota(c_.begin(), c_.end(), 0);
    }
};
struct SimulationTask
{
    const SimulationData& data_;
    double res_;
    double time_;
    explicit SimulationTask(const SimulationData& data)
    : data_(data), res_(0.0), time_(0.0)
    {}

    constexpr static int blockSize = 20000;
    void sample()
    {
        auto tbeg = std::chrono::steady_clock::now();
        Vec result;
        for(auto i=0; i < blockSize; ++i)
        {
            add(result.data(), data_.a_.data(), data_.b_.data(), Size);
            mul(result.data(), result.data(), data_.c_.data(), Size);
            res_ += *std::max_element(result.begin(), result.end());
        }
        auto tend = std::chrono::steady_clock::now();
        time_ = std::chrono::duration_cast<std::chrono::milliseconds>(tend-tbeg).count();
    }
    inline double getResults() const
    {
        return res_;
    }
    inline double getTime() const
    {
        return time_;
    }
    static void add( double* result, const double* a, const double* b, size_t size)
    {
        size_t i = 0;
        // AVX-512 loop
        #ifdef USE_AVX_512
        for( ; i < (size & ~0x7); i += 8)
        {
            const __m512d kA8   = _mm512_load_pd( &a[i] );
            const __m512d kB8   = _mm512_load_pd( &b[i] );

            const __m512d kRes = _mm512_add_pd( kA8, kB8 );
            _mm512_stream_pd( &result[i], kRes );
        }
        #endif
        // AVX loop
        for ( ; i < (size & ~0x3); i += 4 )
        {
            const __m256d kA4   = _mm256_load_pd( &a[i] );
            const __m256d kB4   = _mm256_load_pd( &b[i] );

            const __m256d kRes = _mm256_add_pd( kA4, kB4 );
            _mm256_stream_pd( &result[i], kRes );
        }

        // SSE2 loop
        for ( ; i < (size & ~0x1); i += 2 )
        {
            const __m128d kA2   = _mm_load_pd( &a[i] );
            const __m128d kB2   = _mm_load_pd( &b[i] );

            const __m128d kRes = _mm_add_pd( kA2, kB2 );
            _mm_stream_pd( &result[i], kRes );
        }

        // Serial loop
        for( ; i < size; i++ )
        {
            result[i] = a[i] + b[i];
        }
    }
    static void mul( double* result, const double* a, const double* b, size_t size)
    {
        size_t i = 0;
        // AVX-512 loop
        #ifdef USE_AVX_512
        for( ; i < (size & ~0x7); i += 8)
        {
            const __m512d kA8   = _mm512_load_pd( &a[i] );
            const __m512d kB8   = _mm512_load_pd( &b[i] );

            const __m512d kRes = _mm512_mul_pd( kA8, kB8 );
            _mm512_stream_pd( &result[i], kRes );
        }
        #endif
        // AVX loop
        for ( ; i < (size & ~0x3); i += 4 )
        {
            const __m256d kA4   = _mm256_load_pd( &a[i] );
            const __m256d kB4   = _mm256_load_pd( &b[i] );

            const __m256d kRes = _mm256_mul_pd( kA4, kB4 );
            _mm256_stream_pd( &result[i], kRes );
        }

        // SSE2 loop
        for ( ; i < (size & ~0x1); i += 2 )
        {
            const __m128d kA2   = _mm_load_pd( &a[i] );
            const __m128d kB2   = _mm_load_pd( &b[i] );

            const __m128d kRes = _mm_mul_pd( kA2, kB2 );
            _mm_stream_pd( &result[i], kRes );
        }

        // Serial loop
        for( ; i < size; i++ )
        {
            result[i] = a[i] * b[i];
        }
    }
};

int main(int argc, const char* argv[])
{
    int numOfThreads = 1;
    if ( argc > 1 )
        numOfThreads = atoi( argv[1] );

    try
    {
        SimulationData data;
        std::vector<SimulationTask> tasks;
        for (int i = 0; i < numOfThreads; ++i)
            tasks.emplace_back(data);

        tf::Taskflow tf;
        tf.parallel_for(tasks, [](auto &task) { task.sample(); });
        tf.wait_for_all();
        for (const auto &task : tasks)
        {
            std::cout << "Result: " << task.getResults() << ", Time: " << task.getTime() << std::endl;
        }
    }
    catch (const std::exception& ex)
    {
        std::cerr << ex.what() << std::endl;
    }
    return 0;
}

Я скомпилировал этот код с g++-8.2 -std=c++17 -mavx -o timing -O3 timing.cpp -lpthread на двойной E5-2697 v2 (каждый ЦП имеет 12 физических ядер с гиперпоточностью, поэтому доступно 48 аппаратных потоков). Когда я увеличиваю количество параллельных задач, время для каждой задачи значительно увеличивается:

# ./timing 1
Result: 1.0011e+12, Time: 618

Использование 12 заданий:

# ./timing 12
Result: 1.0011e+12, Time: 788
Result: 1.0011e+12, Time: 609
Result: 1.0011e+12, Time: 812
Result: 1.0011e+12, Time: 605
Result: 1.0011e+12, Time: 808
Result: 1.0011e+12, Time: 1050
Result: 1.0011e+12, Time: 817
Result: 1.0011e+12, Time: 830
Result: 1.0011e+12, Time: 597
Result: 1.0011e+12, Time: 573
Result: 1.0011e+12, Time: 586
Result: 1.0011e+12, Time: 583

Использование 24 заданий:

# ./timing 24
Result: 1.0011e+12, Time: 762
Result: 1.0011e+12, Time: 1033
Result: 1.0011e+12, Time: 735
Result: 1.0011e+12, Time: 1051
Result: 1.0011e+12, Time: 1060
Result: 1.0011e+12, Time: 757
Result: 1.0011e+12, Time: 1075
Result: 1.0011e+12, Time: 758
Result: 1.0011e+12, Time: 745
Result: 1.0011e+12, Time: 1165
Result: 1.0011e+12, Time: 1032
Result: 1.0011e+12, Time: 1160
Result: 1.0011e+12, Time: 757
Result: 1.0011e+12, Time: 743
Result: 1.0011e+12, Time: 736
Result: 1.0011e+12, Time: 1028
Result: 1.0011e+12, Time: 1109
Result: 1.0011e+12, Time: 1018
Result: 1.0011e+12, Time: 1338
Result: 1.0011e+12, Time: 743
Result: 1.0011e+12, Time: 1061
Result: 1.0011e+12, Time: 1046
Result: 1.0011e+12, Time: 1341
Result: 1.0011e+12, Time: 761

Использование 48 заданий:

# ./timing 48
Result: 1.0011e+12, Time: 1591
Result: 1.0011e+12, Time: 1776
Result: 1.0011e+12, Time: 1923
Result: 1.0011e+12, Time: 1876
Result: 1.0011e+12, Time: 2002
Result: 1.0011e+12, Time: 1649
Result: 1.0011e+12, Time: 1955
Result: 1.0011e+12, Time: 1728
Result: 1.0011e+12, Time: 1632
Result: 1.0011e+12, Time: 1418
Result: 1.0011e+12, Time: 1904
Result: 1.0011e+12, Time: 1847
Result: 1.0011e+12, Time: 1595
Result: 1.0011e+12, Time: 1910
Result: 1.0011e+12, Time: 1530
Result: 1.0011e+12, Time: 1824
Result: 1.0011e+12, Time: 1588
Result: 1.0011e+12, Time: 1656
Result: 1.0011e+12, Time: 1876
Result: 1.0011e+12, Time: 1683
Result: 1.0011e+12, Time: 1403
Result: 1.0011e+12, Time: 1730
Result: 1.0011e+12, Time: 1476
Result: 1.0011e+12, Time: 1938
Result: 1.0011e+12, Time: 1429
Result: 1.0011e+12, Time: 1888
Result: 1.0011e+12, Time: 1530
Result: 1.0011e+12, Time: 1754
Result: 1.0011e+12, Time: 1794
Result: 1.0011e+12, Time: 1935
Result: 1.0011e+12, Time: 1757
Result: 1.0011e+12, Time: 1572
Result: 1.0011e+12, Time: 1474
Result: 1.0011e+12, Time: 1609
Result: 1.0011e+12, Time: 1394
Result: 1.0011e+12, Time: 1655
Result: 1.0011e+12, Time: 1480
Result: 1.0011e+12, Time: 2061
Result: 1.0011e+12, Time: 2056
Result: 1.0011e+12, Time: 1598
Result: 1.0011e+12, Time: 1630
Result: 1.0011e+12, Time: 1623
Result: 1.0011e+12, Time: 2073
Result: 1.0011e+12, Time: 1395
Result: 1.0011e+12, Time: 1487
Result: 1.0011e+12, Time: 1854
Result: 1.0011e+12, Time: 1569
Result: 1.0011e+12, Time: 1530

Что-то не так с этим кодом? Проблема векторизации с parallel_for? Могу ли я получить лучшее понимание, используя перф или аналогичный инструмент?

Answer 1

Вам, вероятно, понадобится Intel VTune , чтобы доказать это, но я предполагаю, что поскольку рабочие потоки не выполняют большую вычислительную работу между нагрузками и хранилищами, они вместо этого ограничены скоростью при котором процессор может загружать данные из оперативной памяти. Следовательно, чем больше у вас потоков, тем больше они конкурируют и лишают друг друга ограниченной пропускной способности памяти. В качестве документа Определение насыщения пропускной способности памяти в многопоточных приложениях от Intel гласит:

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

Профилирование с помощью такого инструмента, как VTune, - единственный способ убедиться в узком месте. Особенность VTune заключается в том, что он может анализировать производительность на аппаратном уровне ЦП, и, будучи инструментом Intel, он имеет доступ к счетчикам производительности и сведениям, которых нет у других инструментов, и поэтому выявляет узкие места с точки зрения процессора. Для процессоров AMD аналогичным инструментом является CodeXL . Дополнительные инструменты, которые могут быть использованы, включают Монитор производительности счетчика (от https://stackoverflow.com/a/4015983) и, если работает под управлением Windows, Профилировщик ЦП Visual Studio (от https://stackoverflow.com/a/3489965).

Для анализа узких мест производительности на уровне команд может быть полезен Intel Architecture Code Analyzer . Это статический анализатор, который выполняет теоретический анализ пропускной способности, задержки и зависимости данных для конкретной архитектуры Intel. Однако оценки исключают эффекты из памяти, кэша и т. Д. Для получения дополнительной информации см. Что такое IACA и как его использовать? .

Answer 2

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

С 1 потоком или 12 потоками вы действительно не столкнетесь с этим утверждением. С 24 потоками вы избежите этой проблемы, только если каждый поток запланирован на свое собственное физическое ядро, что, вероятно, не произойдет (поэтому вы начнете видеть худшее время). С 48 ядрами вы определенно получите вышеуказанную проблему.

Как упомянуто harold , вы также можете быть привязаны к магазину (еще один ресурс, за который конкурируют пары гиперпоточности).