Ускорение умножения матриц по SSE (C ++)

Question

Мне нужно запустить умножение матрицы на вектор 240000 раз в секунду.Матрица 5x5 и всегда одинакова, тогда как вектор меняется на каждой итерации.Тип данных float.Я думал об использовании некоторых инструкций SSE (или аналогичных).

1) Я обеспокоен тем, что число арифметических операций слишком мало по сравнению с количеством операций с памятью.Как вы думаете, я смогу получить ощутимое (например,> 20%) улучшение?

2) Нужен ли мне компилятор Intel для этого?

3) Можете ли вы указать некоторые ссылки?

Спасибо всем!

Answer 1

Библиотека шаблонов Eigen C ++ для векторов, матриц, ... содержит оба

• оптимизированный код для небольших матриц фиксированного размера (а также динамических размеров)

• оптимизированный код, который использует оптимизацию SSE

так что вам стоит попробовать.

Answer 2

В принципе ускорение может быть в 4 раза с SSE (8 раз с AVX). Позвольте мне объяснить.

Давайте назовем вашу фиксированную матрицу 5x5 M . Определение компонентов 5D вектора как (x, y, z, w, t). Теперь сформируйте матрицу 5x4 U из первых четырех векторов.

U =
xxxx
yyyy
zzzz
wwww
tttt

Далее делаем матричное произведение MU = V . Матрица V содержит произведение M и первые четыре вектора. Единственная проблема заключается в том, что для SSE нам нужно читать в строках U , но в памяти U хранится как xyzwtxyzwtxyzwtxyzwt , поэтому мы должны транспонировать его в xxxxyyyyzzzzwwwwtttt . Это можно сделать с помощью перемешивания / смешивания в SSE. Как только мы получим этот формат, матричный продукт будет очень эффективным.

Вместо операций O (5x5x4) со скалярным кодом, требуется только O (5x5) операций, то есть ускорение в 4 раза. С AVX матрица U будет иметь размер 5x8, поэтому вместо операций O (5x5x8) она облагает налогом только O (5x5), то есть ускорение в 8 раз.

Матрица V , однако, будет иметь формат xxxxyyyyzzzzwwwwtttt , поэтому в зависимости от приложения ее, возможно, придется преобразовать в формат xyzwtxyzwtxyzwtxyzwt .

Повторите это для следующих четырех векторов (8 для AVX) и т. Д., Пока не будет сделано.

Если у вас есть контроль над векторами, например, если ваше приложение генерирует векторы на лету, вы можете генерировать их в формате xxxxyyyyzzzzwwwwtttt и избегать транспонирования массива. В этом случае вы должны получить 4-кратную скорость с SSE и 8-кратную с AVX. Если вы объедините это с многопоточностью, например, OpenMP, ваше ускорение должно быть близко к 16x (при условии четырех физических ядер) с SSE. Я думаю, что это лучшее, что вы можете сделать с SSE.

Редактировать: Из-за параллелизма на уровне команд (ILP) вы можете получить еще один коэффициент ускорения, равный 2, так что ускорение для SSE может увеличиться в 32 раза с четырьмя ядрами (64x AVX) и снова еще раз с 2 с Haswell из-за FMA3.

Answer 3

Если вы используете GCC, обратите внимание, что опция -O3 включит автоматическую векторизацию, которая во многих случаях будет автоматически генерировать инструкции SSE или AVX. В общем, если вы просто напишите это как простой цикл for, GCC будет векторизовать его. См. http://gcc.gnu.org/projects/tree-ssa/vectorization.html для получения дополнительной информации.

Answer 4

Я бы предложил использовать Intel IPP и абстрагироваться от зависимости от методов

Answer 5

Это должно быть легко, особенно когда вы работаете на Core 2 или более поздней версии: вам нужно 5 * _mm_dp_ps, один _mm_mul_ps, два _mm_add_ps, одно обычное умножение, плюс некоторые тасования, загрузки и сохранения (и если матрица исправленаВы можете хранить большую часть этого в sse регистрах, если они вам не нужны ни для чего другого).

Что касается пропускной способности памяти: мы говорим о 2,4 мегабайтах векторов, когда пропускная способность памяти находится воднозначные гигабайты в секунду.

Answer 6

Что известно о векторе? Поскольку матрица фиксирована, И если существует ограниченное количество значений, которые может принимать вектор, то я бы посоветовал вам предварительно рассчитать вычисления и получить к ним доступ с помощью поиска в таблице.

Классическая методика оптимизации обмена памяти на циклы ...

Answer 7

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

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

5x5 - забавный размер, но вы можете сделать как минимум 4 флопа в одной инструкции SSE и попытаться сократить свои арифметические издержки.Вам не нужен компилятор Intel, но, может быть, он и лучше, я слышал легенды о том, насколько лучше с арифметическим кодом.Visual Studio имеет встроенные функции для работы с SSE2, и я думаю, что до SSE4 зависит от того, что вам нужно.Конечно, вам придется свернуть это самостоятельно.Захват библиотеки может быть разумным шагом здесь.

Answer 8

Я бы порекомендовал взглянуть на оптимизированную библиотеку BLAS, такую ​​как Intel MKL или AMD ACML.Исходя из вашего описания, я бы предположил, что вы после процедуры SGEMV уровня 2 матрицы-вектора будете выполнять операции y = A*x стиля.

Если вы действительно хотите что-то реализовать самостоятельно, используя (наборы команд SSE..SSE4 и AVX могут в некоторых случаях значительно повысить производительность, хотя именно это и будет делать хорошая библиотека BLAS.Вам также нужно много думать о шаблонах доступа к данным, дружественным к кешу.

Я не знаю, применимо ли это в вашем случае, но можете ли вы одновременно работать с «кусками» векторов ??Таким образом, вместо многократного выполнения операции в стиле y = A*x вы можете работать с блоками [y1 y2 ... yn] = A * [x1 x2 ... xn].Если это так, это означает, что вы можете использовать оптимизированную матрично-матричную подпрограмму, например SGEMM.Из-за шаблонов доступа к данным это может быть значительно более эффективным, чем повторные вызовы SGEMV.Если бы это был я, я бы попытался пойти по этому пути ...

Надеюсь, это поможет.