Multiplying a Matrix with its Transpose Currently, I am in the process of optimizing a MIPS assembly program that takes a n x n matrix and multiplies it with its transpose. I am trying to optimize my matrix calculation algorithm so that it completes in as few clock cycles as possible. I have been given the A matrix, with its values stored in RAM. I must then calculate B=A*transpose(A).

There are a few caveats:


The matrix multiplication must be the dot product of the ith row of A and the jth column of B. It is not meant to be the element-wise multiplication. See the Wikipedia article.
I am not to make my algorithm more mathematically efficient then the un-modified example I will show below. I.e. I cannot exploit the symmetric nature resulting when you multiply a matrix with its transpose.


Here is the pseudo code example I have been given:

// 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 &lt; (n * n); i++)
{
    B[i] = 0;
}

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


Here is my attempt at optimizing the above example:

// 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 &lt; n; i++)
{   
    for (int j = 0; j &lt; n; j++)
    {
        temp = 0;
        n_times_i = n * i;

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

        B[j + n_times_i] = temp;
    }
}


As you can see, I have swapped things around to avoid unnecessary calculations where possible.

However, I was wondering whether anyone can see any other way of speeding things up? I.e. Cleverly swapping the order of the loops, etc.

Any help would be greatly appreciated!
Barring any compiler heroics, you are computing n*n a total of \$n^3\$ times.  You might want to cache that result.

const int nn = n*n;




B[j + n_times_i] is a linearly increasing address location, given that j increases by 1 for each middle loop, and and i increases once for each outer loop, which is n increases of j.  Taking advantage of that, you can skip the j + n*i calculation, and B[ ] indexing.

int *pB  = &amp;B;
// ... loops &amp; calculation of temp omitted for brevity.
      *pB++ = temp;




Result:

const int nn = n*n;
int *pB = B;

for (int i = 0; i &lt; n; i++) {
    for (int j = 0; j &lt; n; j++) {
        temp = 0;
        for (int k = 0; k &lt; nn; k += n) {
            temp += A[i+k] * A[j+k];
        }
        *pB++ = temp;
    }
}




You may find that you can get additional speed by using pointer arithmetic for A[i+k] and A[j+k].

int *pAi = A + i;
int *pAj = A + j;
for (k=0; k&lt;n; k++) {   // Note: n.  The nn variable is no longer needed.
    temp += *pAi * *pAj;
    pAi += n;
    pAj += n;
}


But, you’ll need to profile to find out.  It depends on the number of free registers you have ... and the compiler/optimizers these days are pretty darn good.