Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Умножение матриц

Умножение матриц

IBetsПользовательwww9 июня 20183:10#0
Имеет ли смысл транспонировать rhs матрицу, а потом начать умножать. Интуитивно видно что таким способом у нас будет меньше кэш промахов, так как матрицы расположены по строкам и таким образом индекс k попадает локально. Когда-то читал что можно просто изменить циклы. Но чет не могу в голове так быстро сообразить,
в каком порядке расставить для скорости
  template<typename T, U32 M, U32 N, U32 P>
    ILINE constexpr auto operator*(Matrix<T, M, N> const & lhs, Matrix<T, N, P> const & rhs) noexcept -> Matrix<T, M, P> {
      auto res = Matrix<T, M, P>{};
      auto tr  = Transpose(rhs);
      for (auto i = 0; i < M; i++)
        for (auto j = 0; j < P; j++)
          for (int k = 0; k < N; k++)
            res(i, j) += lhs(i, k) * tr(j, k);
      return res;
    }

SuslikМодераторwww9 июня 20184:54#1
тебя компилятор забанил, что не даёт проверить что ли? насколько я помню, для самого простого случая перемножения [cht]O(n^3)[/cht] у тебя порядок циклов не оптимальный. оптимальный не помню. но большие матрицы за кубическую сложность никто не умножает, делают хотя бы так https://en.wikipedia.org/wiki/Strassen_algorithm , а особо продвинутые — так https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm . оптимальный алгоритм всё ещё не изобретён.

Правка: 9 июня 2018 4:54

IBetsПользовательwww9 июня 20185:03#2
Suslik
Я Если циклы менять кэш промахов станет больше. Потому что я протранспонировал
FordPerfectПостоялецwww9 июня 201811:13#3
В тензорной записи видимо понагляднее: [cht]C=A \cdot B[/cht] раскрывается в [cht]C_{ij}=A_{ik} B_{kj}[/cht], и порядок циклов произволен.
Дальше можно разбивать на блоки (пачки строчек или квадратики) и работать с ними, но от порядка циклов отдача большая, а от дальнейших вещей - куда меньше. Ну и от низкоуровневых вещей есть отдача. SIMD, порядок инструкций.
От транспонирования тоже может быть польза по сравнению со влобным. Но в случае с изменённым  порядком кеш-промахов почти на уровне транспонированного, и больше влияют низкоуровневые вещи не связанные с памятью.
Вот совсем влобный тест на rextester.com, но он не показательный, эффекты кеша начинаются с ~4000:
http://rextester.com/ZMEFL11030

Suslik
> а особо продвинутые
Так вроде ж правда, что

However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.

Кстати, няшная статья:
http://www.netlib.org/lapack/lawnspdf/lawn189.pdf
Можешь выделить пару часов и прочитать, за чашкой чая: чисто посмотреть, что люди делают из любви к искусству.
И сравнить с тем, что обычно что называют "убер-оптимизациями".

IBetsПользовательwww9 июня 201812:30#4
FordPerfect
Благодарю
SuslikМодераторwww9 июня 201815:09#5
FordPerfect
> However, unlike the Strassen algorithm, it is not used in practice because it
> only provides an advantage for matrices so large that they cannot be processed
> by modern hardware.
я был на докладе чувака, который занимается расчтётом шахматных стратегий. так вот там у них плотные(не разреженные) матрицы перемножались распределённо по очень хитрым алгоритмам.
FordPerfectПостоялецwww9 июня 201822:20#6
IBets
Ну и SIMD, к примеру:
http://rextester.com/PLVO76569
FordPerfectПостоялецwww10 июня 20181:29#7
Suslik
> я был на докладе чувака, который занимается расчтётом шахматных стратегий. так вот там у них плотные(не разреженные) матрицы перемножались распределённо по очень хитрым алгоритмам.
Занятно. В сети где-то этот доклад есть?
SlightlyПользовательwww10 июня 20183:08#8
после такой писанины становится нифига непонятно что имел ввиду автор
и если он вдру случайно подохнет, и на его место возьмут другого, то будет сложно разобраться что это за идиотский шаблон с кучей параметров
и вообще, этот человек работал, или занимался тем, что сочинял наиболее изощренные варианты шаблонов для какой-то фигни
и еще один вопрос появится: если это компания появилась давно, то почему сотрудники до сих пор занимаются алгоритмами умножения матриц, это должно быть пройдено ешё в 70х годах прошлого века
SuslikМодераторwww10 июня 20184:18#9
Slightly
совершенно стандартная реализация шаблонной матрицы, что там разбираться?
IBetsПользовательwww10 июня 20188:46#10
Slightly
Вероятно ваши интеллектуальные способности не способны на такие простейшие вещи. А перемножением матриц человечество будет заниматься всегда
RikkПостоялецwww10 июня 201812:11#11
IBets
> Имеет ли смысл транспонировать rhs матрицу, а потом начать умножать.
Транспонирование —- процедура когда матрицу меняют строки становятся столбцами а столбцы становятся строками в той же самой матрице.


Если была матрица (5строк 4столбца)-—->>стрелка сюда -———>>транспонирование ——>> та же самая матрица становится как (4строки 5столбцов)

Правило умножение матриц ( m x n) *(n x k)= матрица (m x k)

Пример по существу вопроса :

(5строк 4столбца)*(4строки 3столбца)=матрица (5строк 3столбца)

Транспонируем первую матрицу и потом умножаем на вторую матрицу
(4строки 5столбцов)транспонированная первая матрица  * (4строки 3столбца)= невозможная процедура .такие матрицы в принципе перемножать нельзя никак.

Ответ на вопрос :
  не имеет смысла. даже хуже —так делать нельзя вообще. надо просто перемножать матрицы по условиям задачи .

Вопрос оффтопом :
  сколько вы готовы заплатить кувейтских динаров(они дороже доллара , евро, британского фунта-стерлинга) за эту актуальную информацию по существу вопроса ?

Правка: 10 июня 2018 13:03

innuendoПостоялецwww10 июня 201812:18#12
FordPerfect
> Можешь выделить пару часов и прочитать, за чашкой чая: чисто посмотреть, что
> люди делают из любви к искусству.

может это была сильная любовь к PPC ?

DelfigamerПостоялецwww10 июня 201813:43#13
Rikk
Пояснение для особо одарённых - речь шла о реализации

    Изображение

через

    Изображение

    Изображение

с намерением сделать операцию лучше по отношению к кэшу, конвееру и векторным инструкциям.

Правка: 10 июня 2018 13:45

IBetsПользовательwww11 июня 20182:12#14
Rikk
Аххаха.

/ Форум / Программирование игр / Графика

2001—2018 © GameDev.ru — Разработка игр