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

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

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

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

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

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

Ответ 1

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

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

поэтому вы должны попробовать.

Ответ 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, поэтому мы должны перенести его до xxxxyyyyzzzzwwwwtttttt. Это можно сделать с помощью тасов/смесей в SSE. Как только мы получим этот формат, матричный продукт очень эффективен.

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

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

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

Классический метод оптимизации для торговли памятью для циклов...

Ответ 7

Я бы рекомендовал взглянуть на оптимизированную библиотеку 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. Если бы это был я, я бы попытался пойти по этому пути...

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

Ответ 8

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

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

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