Матричная оптимизация доступа и умножения для процессора

Question

Im, создающая некоторую внутреннюю оптимизированную матричную оболочку в java (с помощью JNI). Нужно ли утверждать это, , можете ли вы дать некоторые подсказки по оптимизации матриц? То, что я собираюсь реализовать, это:

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

Matrix signature: 

0 1 2 3 

4 5 6 7 

8 9 1 3 

3 5 2 9 

First(hroizontal) set: 
horSet[0]={0,1,2,3} horSet[1]={4,5,6,7} horSet[2]={8,9,1,3} horSet[3]={3,5,2,9} 

Second(vertical) set: 
verSet[0]={0,4,8,3} verSet[1]={1,5,9,5} verSet[2]={2,6,1,2} verSet[3]={3,7,3,9} 

Third(optional) a diagonal set: 
diagS={0,5,1,9} //just in case some calculation needs this 

Fourth(calcuation list, in a "one calculation one data" fashion) set: 
calc={0,2,1,3,2,5} --->0 means multiply by the next element 
         1 means add the next element 
         2 means divide by the next element 
         so this list means 
         ((a[i]*2)+3)/5 when only a[i] is needed. 
Example for fourth set: 
A.mult(2), A.sum(3), A.div(5), A.mult(B) 
(to list) (to list) (to list) (calculate *+/ just in time when A is needed) 
so only one memory access for four operations. 
loop start 
a[i] = b[i] * ((a[i]*2) +3)/5 only for A.mult(B) 
loop end 

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

Это должно дать некоторые вещи проще и некоторые вещи сложнее:

Easier: 
**Matrix transpozing operation. 
Just swapping the pointers horSet[x] and verSet[x] is enough. 

**Matrix * Matrix multiplication. 
One matrix gives one of its horizontal set and other matrix gives vertical buffer. 
Dot product of these must be highly parallelizable for intrinsics/multithreading. 
If the multiplication order is inverse, then horizontal and verticals are switched. 

**Matrix * vector multiplication. 
Same as above, just a vector can be taken as horizontal or vertical freely. 

Harder: 
** Doubling memory requirement is bad for many cases. 
** Initializing a matrix takes longer. 
** When a matrix is multiplied from left, needs an update vertical-->horizontal 
sets if its going to be multiplied from right after.(same for opposite) 
(if a tranposition is taken between, this does not count) 


Neutral: 
** Same matrix can be multiplied with two other matrices to get two different 
results such as A=A*B(saved in horizontal sets) A=C*A(saved in vertical sets) 
then A=A*A gives A*B*C*A(in horizontal) and C*A*A*B (in vertical) without 
copying A. 

** If a matrix always multiplied from left or always from right, every access 
and multiplication will not need update and be contiguous on ram. 

** Only using horizontals before transpozing, only using verticals after, 
should not break any rules. 

Главной цель состоит в том, имеющая матрицу (кратные 8, кратные 8) размера и применение AVX встроенных функций с несколькими потоками (каждый протекторные произведения на множестве одновременно).

У меня есть только векторный векторный векторный продукт. Я пойду в это, если вы, мастера программирования, дадите направление.

dotproduct, который я написал (с внутренними функциями), на 6 раз быстрее, чем развернутая по циклу версия (которая в два раза быстрее умножается по отдельности), также стекает с пропускной способностью памяти, когда многопоточность включена в оболочке (8x - -> использует почти 20 ГБ/с, что близко к пределу моего ddr3). Пробовал opencl уже, и он медленный для процессора, но отлично подходит для gpu.

спасибо.

Редактировать: Как выполнить буфер «Матрица блоков»? При умножении больших матриц небольшие патчи умножаются особым образом, и кеш, вероятно, используется для уменьшения доступа к основной памяти. Но для этого потребуется еще больше обновлений между матричными умножениями между вертикально-горизонтальной диагональю и этим блоком.

Answer 1

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

The C++ Programming Lanuage также содержит краткую главу о «Плавленых операциях» (29.5.4, 4-е издание).

Это позволяет конкатенацию заявления а-ля:

M = A*B.transp(); // where M, A, B are matrices 

Вы хотите иметь 3-х классов в этом случае:

class Matrix; 

class Transposed 
{ 
public: 
    Transposed(Matrix &matrix) : m_matrix(matrix) {} 
    Matrix & obj (void) { return m_matrix; } 
private: 
    Matrix & m_matrix; 
}; 

class MatrixMatrixMulTransPosed 
{ 
public: 
    MatrixMatrixMulTransPosed(Matrix &matrix, Transposed &trans) 
    : m_matrix(matrix), m_transposed(trans.obj()) {} 
    Matrix & matrix (void) { return m_matrix; } 
    Matrix & transposed (void) { return m_transposed; } 
private: 
    Matrix & m_matrix; 
    Matrix & m_transposed; 
}; 

class Matrix 
{ 
    public: 
    MatrixMatrixMulTransPosed operator* (Transposed &rhs) 
    { 
     return MatrixMatrixMulTransPosed(*this, rhs); 
    } 

    Matrix& operator= (MatrixMatrixMulTransPosed &mmtrans) 
    { 
     // Actual computation goes here and is stored in this. 
     // using mmtrans.matrix() and mmtrans.transposed() 
    } 
}; 

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

Answer 2

Это эффективно эквивалентно кэшированию транспонирования. Похоже, вы намерены делать это с нетерпением; Я просто вычислил транспозицию только тогда, когда это необходимо, и запомните ее, если она понадобится снова. Таким образом, если вам это никогда не понадобится, он никогда не будет вычисляться.