Оптимизация алгоритма умножения матриц в сборке MIPS - PullRequest
Новая
       28

Оптимизация алгоритма умножения матриц в сборке MIPS

0 голосов
/ 31 мая 2019

В настоящее время я нахожусь в процессе оптимизации программы сборки MIPS, которая принимает матрицу nxn и умножает ее на transpose .Я пытаюсь оптимизировать алгоритм вычисления матрицы, чтобы он выполнялся как можно быстрее.Мне дали матрицу A с ее значениями, сохраненными в RAM.Затем я должен вычислить B = A * transpose (A).

Есть несколько предостережений:

  1. Умножение матрицы должно быть точечным произведением i-й строки A иj-й столбец B. Это не означает поэлементное умножение.См. Статью Wikipedia .
  2. Я не хочу делать мой алгоритм более математически эффективным, чем неизмененный пример, который я покажу ниже.Т.е. я не могу использовать симметричную природу, возникающую при умножении матрицы на ее транспонирование.

Вот пример псевдокода, который мне дан: 

// Given array A which is unsigned int A[n*n] (ie word or 32 bit form)
// Reset array B which is unsigned int B[n*n] (ie word or 32 bit form)
for(int i = 0; i < (n * n); i++)
{
    B[i] = 0;
}

// Matrix Multiplicaiton B = A*A'
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++)
        {
            B[i + n * j] = B[i + n * j] + A[i + n * k] * A[j + n * k];
        }
    }
}

Вот моя попыткапри оптимизации приведенного выше примера: 

// Given array A which is unsigned int A[n*n] (ie word or 32-bit form)

// Matrix Multiplicaiton B = A*A'
for(int i = 0; i < n; i++)
{   
    for (int j = 0; j < n; j++)
    {
        temp = 0;
        n_times_i = n * i;

        for (int k = 0; k < (n*n); k+=n)
        {
            temp += A[j + k] * A[i + k];
        }

        B[j + n_times_i] = temp;
    }
}

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

Однако мне было интересно, может ли кто-нибудь увидеть другой способускорения вещей?Т.е. хитро поменять местами порядок петель и т. Д.

Любая помощь будет принята с благодарностью!

...