Сравнение производительности методов параллельных вычислений: поэлементные операции над векторами

Введение

Стремительный рост объёмов данных и усложнение вычислительных моделей в физике, инженерии и науках о данных делают проблему повышения производительности программного кода одной из центральных в современных численных исследованиях. Сокращение времени вычислений неизбежно связано с грамотным использованием параллелизма на всех уровнях — от векторных инструкций отдельного процессорного ядра до привлечения множества ядер графического процессора.

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

Импорт библиотек

Присоединим необходимые библиотеки.

BenchmarkTools — эталонный замер времени выполнения и аллокаций (@btime);
Random — генерация исходных случайных данных.

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

CUDA — выполнение вычислений на графическом процессоре;
FLoops — гибкие параллельные циклы с прозрачной многопоточностью;
Folds — параллельные поэлементные операции;
LoopVectorization — автоматическая векторизация циклов;
Polyester — низкоуровневая многопоточность с минимальными накладными расходами;
ThreadsX — параллельная обработка коллекций с автоматической балансировкой нагрузки;
Tullio — тензорная нотация Эйнштейна с автоматическим распараллеливанием и векторизацией.

import Pkg
Pkg.add(["BenchmarkTools", "CUDA", "FLoops", "Folds", "LoopVectorization", "Polyester", "Random", "ThreadsX", "Tullio"])
using BenchmarkTools, CUDA, FLoops, Folds, LoopVectorization, Polyester, Random, ThreadsX, Tullio

Исходные данные

Для тестирования производительности поэлементных операций над векторами, используем данную функцию.

Данная функция выбрана как репрезентативный образец реальных научно-инженерных вычислений: она объединяет лёгкую арифметику (умножение), трансцендентные функции разной сложности ( и ) и сложение трёх разнородных компонентов. Это позволяет в рамках одного теста оценить пропускную способность памяти, качество векторизации, способность к слиянию циклов без создания промежуточных массивов, балансировку многопоточной нагрузки на неравномерных задачах, эффективность планирования инструкций процессором и масштабируемость на GPU — именно такое сочетание факторов позволит объективно оценить производительность каждого из представленных методов.

Создадим случайных значений векторов и .

N = 10^7
a = randn(N)
b = randn(N)

Последовательные и векторизованные вычисления

Последовательные вычисления

# Последовательные
c = similar(a);
@btime begin
    @inbounds for i in eachindex(a)
        c[i] = a[i] * b[i] + sqrt(abs(a[i])) + sin(b[i])
    end
end

  5.218 s (119998978 allocations: 1.94 GiB)

Время выполнения цикла последовательных вычислений составило 5.218 секунд. Используем данный показатель как базовый для сранения с другими методами.

Векторизованные вычисления

# Векторизованные
c = similar(a);
@btime @. c = a * b + sqrt(abs(a)) + sin(b);

  235.731 ms (5 allocations: 128 bytes)

Использование точечной трансляции (@.) позволило делегировать вычисления оптимизированной функции broadcast, избежав проблем глобальной области видимости. Время выполнения — 235.7 мс, что в ~22.1 раза быстрее последовательных вычислений.

Последовательные вычисления внутри функции

# Последовательные внутри функции
c = similar(a);
function serial(c, a, b)
    @inbounds for i in eachindex(a)
        c[i] = a[i] * b[i] + sqrt(abs(a[i])) + sin(b[i])
    end
    return c
end

@btime serial(c, a, b);

  186.282 ms (0 allocations: 0 bytes)

Обёртывание цикла в функцию позволило JIT-компилятору вывести стабильные типы и сгенерировать нативный код. Время — 186.3 мс, ускорение в ~28.0 раз.

Параллельные вычисления

Polyester

# Polyester
c = similar(a);
function polyester!(c, a, b)
    @batch for i in eachindex(a)
        c[i] = a[i] * b[i] + sqrt(abs(a[i])) + sin(b[i])
    end
    return c
end

@btime polyester!($c, $a, $b);

  53.342 ms (0 allocations: 0 bytes)

Макрос @batch с предельно низкими накладными расходами эффективно распределил итерации цикла между потоками CPU. Время выполнения — 53.34 мс, что в ~97.8 раз быстрее последовательных вычислений.

Floops

# Floops
c = similar(a);
function floops!(c, a, b)
    @floop for i in eachindex(a)
        c[i] = a[i] * b[i] + sqrt(abs(a[i])) + sin(b[i])
    end
    return c
end

@btime floops!($c, $a, $b);

  47.111 ms (35 allocations: 2.62 KiB)

Благодаря прозрачной многопоточности и возможности трансляции действий, время выполнения вычислений составило 47.11 мс, что в ~110.7 раз быстрее последовательных вычислений.

Folds

# Folds
c = similar(a)
@btime Folds.map!(i -> $a[i]*$b[i] + sqrt(abs($a[i])) + sin($b[i]), $c, eachindex($a, $b));

  46.395 ms (42 allocations: 3.28 KiB)

Параллельная свёртка в функциональном стиле без создания промежуточных массивов: Folds.map! эффективно распределяет нагрузку. Время — 46.40 мс, ускорение в ~112.5 раз.

ThreadsX

# ThreadsX
c = similar(a)
@btime ThreadsX.map!(i -> $a[i]*$b[i] + sqrt(abs($a[i])) + sin($b[i]), $c, eachindex($a, $b));

  44.999 ms (253 allocations: 18.84 KiB)

Специализированная параллельная обработка коллекций обеспечила наилучший баланс среди чистых многопоточных решений. Время — 45.00 мс, ускорение в ~116.0 раз.

LoopVectorization

# LoopVectorization
c = similar(a);
function turbo!(c, a, b)
    @turbo for i in eachindex(a)
        c[i] = a[i] * b[i] + sqrt(abs(a[i])) + sin(b[i])
    end
    return c
end

@btime turbo!($c, $a, $b);

  32.258 ms (0 allocations: 0 bytes)

Warning: detected a stack overflow; program state may be corrupted, so further execution might be unreliable.

Время выполнения составило 32.26 мс, что в ~161.8 раз быстрее последовательного цикла вычислений.

Tullio

# Tullio
function tullio!(c, a, b)
    @tullio c[i] = a[i] * b[i] + sqrt(abs(a[i])) + sin(b[i])
end
@btime tullio!($c, $a, $b);

  8.288 ms (41 allocations: 1.67 KiB)

Нотация Эйнштейна с автоматическим распараллеливанием и векторизацией, будучи обёрнутой в функцию, показала впечатляющий результат. Время выполнения — 8.288 мс при минимальных аллокациях (1.67 KiB), что в ~629.6 раз быстрее последовательных вычислений.

CUDA

Для использования библиотеки CUDA.jl, необходимо синхронизировать версию среды исполнения и драйвера CUDA. Для может потребоваться выполнение данной команды и перезапуск ядра Julia.

CUDA.set_runtime_version!(CUDA.driver_version())

Выполним вычисления с помощью CUDA.jl.

# CUDA
da = CuArray(a)
db = CuArray(b)
dc = similar(da)

function cuda_broadcast!(dc, da, db)
    @. dc = da * db + sqrt(abs(da)) + sin(db)
    return dc
end

cuda_broadcast!(dc, da, db)
CUDA.synchronize()

@btime begin
    cuda_broadcast!($dc, $da, $db)
    CUDA.synchronize()
end

  198.631 μs (101 allocations: 2.61 KiB)

Массивы были перенесены в память видеокарты, и вычисления выполнены на ядрах GPU. Время — ~0.199 мс (198.6 мкс) , что в ~26 200 раз быстрее последовательных вычислений. Абсолютный рекорд измерений.

Итоговая таблица

Место	Метод	Время	Ускорение
1	CUDA	0.199 мс	~26 200×
2	Tullio	10.04 мс	~520×
3	LoopVectorization	32.26 мс	~162×
4	ThreadsX	45.00 мс	~116×
5	Folds	46.40 мс	~113×
6	FLoops	47.11 мс	~111×
7	Polyester	53.34 мс	~98×
8	Последовательный в функции	186.3 мс	~28×
9	Векторизованный	235.7 мс	~22×
10	Последовательный	5218 мс	1×

Правильный выбор метода даёт 26000-кратный разброс производительности: от 5.2 секунд последовательного цикла до 199 микросекунд на GPU.

Заключение

Проведённые измерения показали, что разные способы выполнения одной и той же задачи могут давать совершенно разное время работы — от нескольких секунд до долей миллисекунды. Даже простое оформление расчётов в виде функции даёт заметное ускорение. Специальные библиотеки для многопоточных вычислений позволяют получить ещё больший выигрыш, а использование видеокарты делает расчёты практически мгновенными.

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