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

← →
Dmk © (2003-10-26 14:51) [0]

Кто нибудь занимался subj"ем?
Интересует оптимизация процесса,
особенно умножение с использованием MMX,SSE(2)
инструкций.
Собственно умножение уже реализовано:

asm
mov edx, edi //Save edi

//VecRes[1] := VecRes[1] + XYZRGB[1, 1] * X;
//VecRes[1] := VecRes[1] + XYZRGB[1, 2] * Y;
//VecRes[1] := VecRes[1] + XYZRGB[1, 3] * Z;

pxor xmm0, xmm0

//D65
movq xmm4, X
movq xmm5, Y
movq xmm6, Z

movq xmm7, HiByte

lea edi, XYZRGB
movq xmm1, [edi]
movq xmm2, [edi + 8]
movq xmm3, [edi + 16]

mulpd xmm1, xmm4
mulpd xmm2, xmm5
mulpd xmm3, xmm6

addpd xmm0, xmm1
addpd xmm0, xmm2
addpd xmm0, xmm3

mulpd xmm0, xmm7
movq X, xmm0

//VecRes[2] := VecRes[2] + XYZRGB[2, 1] * X;
//VecRes[2] := VecRes[2] + XYZRGB[2, 2] * Y;
//VecRes[2] := VecRes[2] + XYZRGB[2, 3] * Z;

pxor xmm0, xmm0

lea edi, XYZRGB
movq xmm1, [edi + 24]
movq xmm2, [edi + 32]
movq xmm3, [edi + 40]

mulpd xmm1, xmm4
mulpd xmm2, xmm5
mulpd xmm3, xmm6

addpd xmm0, xmm1
addpd xmm0, xmm2
addpd xmm0, xmm3

mulpd xmm0, xmm7
movq Y, xmm0

//VecRes[3] := VecRes[3] + XYZRGB[3, 1] * X;
//VecRes[3] := VecRes[3] + XYZRGB[3, 2] * Y;
//VecRes[3] := VecRes[3] + XYZRGB[3, 3] * Z;

pxor xmm0, xmm0

lea edi, XYZRGB
movq xmm1, [edi + 48]
movq xmm2, [edi + 56]
movq xmm3, [edi + 64]

mulpd xmm1, xmm4
mulpd xmm2, xmm5
mulpd xmm3, xmm6

addpd xmm0, xmm1
addpd xmm0, xmm2
addpd xmm0, xmm3

mulpd xmm0, xmm7
movq Z, xmm0

emms

mov edi, edx //Restore edi
end;

Такой вариант работает раза в 2 быстрее
эквивалента на FPU. Но если использовать
Integer значения - думаю скорость
повысится еще раза в 2-3. Но проблема состоит
в том, что умножаются числа в диапазоне
0.0 .. 1.0. Например, возведем в куб число
0.5481^3 = 0,164656699641. С целочисленными
значениями получается тоже самое:
5481^3 = 164656699641. Но как можно
определить, а затем очистить кол-во бит,
чтобы получилось целочисленное значение
1646(56699641)(То что в скобках - должно
отсечься). Условие: Заранее неизвестно
будет ли число возведено в куб или в квадрат.

← →
MBo © (2003-10-27 08:15) [1]

общие соображения
- размер матриц подогнать под нужное выравнивание -128 бит для SSE, кажется.
- транспонировать одну из матриц и выполнить построчное векторное произведение с суммированием - примеры кода Vector Dot есть у Интел - при этом проще - не скакать по столбцам, а просто инкрементировать указатели.

- может быть, попробовать работать с фиксированной точкой, если точности хватит - арифметика тогда в целых числах считается

← →
Daniel (2003-10-29 11:01) [2]

Есть другой способ ускорить процесс - применить другой алгоритм.
Есть алгоритм не "поточечного" умножения, а использующий преобразование Фурье, его модификации: быстрое перемножение полиномов и быстрое перемножение больших чисел.
Метод "в лоб" решает за O(N^2) операций, Фурье - за O(N^(1.57)).
см. Кормен, Кнут, I-net, etc

← →
MBo © (2003-10-29 11:05) [3]

>Daniel
подозреваю, что автора интересует (судя по названию форума) в первую очередь перемножение матриц афф.преобразований - 3*3 и 4*4, а для таких маленьких накладные расходы при использовании продвинутых методов неоправданны.

> Dmk

рискни использовать готовую библ-ку Intel Math Kernel Library
сам понимаешь, Intel "заточил" алгоритмы в ней конкретно под свой же процессор и свои же технологии. Ему ли, Intel"у, не знать, как наиболее оптимально и эффективно использовать преимущества MMX и SSE для решения подобных задач.
До некоторых пор пакеты IntelMKL и IntelSPL (последний - Signal Processing Library, реализующий различные Фурье-преобразования, сам использую иной раз) можно было свободно скачать с сайта Интел, на сей момент - не в курсе, но, возможно, ситуация не изменилась.

Умножение матриц Найти похожие ветки