Optimized matrix multiplication in C

Question

Hello,

I'm trying to compare different methods for matrix multiplication. The first one is normal method:

do
{
                for (j = 0; j < i; j++)
                {
                        for (k = 0; k < i; k++)
                        {
                                suma = 0;
                                for (l = 0; l < i; l++)
                                        suma += MatrixA[j][l]*MatrixB[l][k];

                                MatrixR[j][k] = suma;
                        }
                 }
c++;
}while (c<iteraciones);

The second one consist on transpond the matrix B firstly and then do the multiplication by rows:

int f,co;
for (f=0;f<i;f++){
for (co=0;co<i;co++){
MatrixB[f][co]=MatrixB[co][f];
}
}

c=0;
do
{
                for (j = 0; j < i; j++)
                {
                        for (k = 0; k < i; k++)
                        {
                                suma = 0;
                                for (l = 0; l < i; l++)
                                        suma += MatrixA[j][l]*MatrixB[k][l];

                                MatrixR[j][k] = suma;
                        }
                 }
c++;

The second method supposed to be much faster, because we are accesing contiguos memory slots, but I'm not getting a significant improvement in the performance. Am I doing something wrong?

I can post the complete code, but I think is not needed.

Thanks a lot

Answer 1

If the matrix is not large enough or you don't repeat the operations a high number of times you won't see appreciable differences.

If the matrix is, say, 1,000x1,000 yoy will begin to see improvements, but I would say that if it is below 100x100 you should not worry about it.

Also, any 'improvement' may be of the order of milliseconds, unless yoy are either working with extremely large matrices or repeating the operation thousands of times.

Finally, if you change the computer you are using for a faster one the differences will be even narrower!

Answer 2

If you are working on small numbers, then the improvement you are mentioning is negligible. Also, performance will vary depend on the Hardware on which you are running. But if you are working on numbers in millions, then it will effect. Coming to the program, can you paste the program you have written.

Answer 3

Hi

Can you post some data comparing your 2 approaches for a range of matrix sizes ? It may be that your expectations are unrealistic and that your 2nd version is faster but you haven't done the measurements yet.

Don't forget, when measuring execution time, to include the time to transpose matrixB.

Something else you might want to try is comparing the performance of your code with that of the equivalent operation from your BLAS library. This may not answer your question directly, but it will give you a better idea of what you might expect from your code.

Regards

Mark

Answer 4

How big improvements you get will depend on:

1. The size of the cache
2. The size of a cache line
3. The degree of associativity of the cache

For small matrix sizes and modern processors it's highly probable that the data fron both MatrixA and MatrixB will be kept nearly entirely in the cache after you touch it the first time.

Answer 5

ATTENTION: You have a BUG in your second implementation

for (f = 0; f < i; f++) {
    for (co = 0; co < i; co++) {
        MatrixB[f][co] = MatrixB[co][f];
    }
}

When you do f=0, c=1

        MatrixB[0][1] = MatrixB[1][0];

you overwrite MatrixB[0][1] and lose that value! When the loop gets to f=1, c=0

        MatrixB[1][0] = MatrixB[0][1];

the value copied is the same that was already there.

Answer 6

Here look at this article which shows you how to tune matrix multiplication but also points you to 2 different libraries which are even better tuned.

Answer 7

Just something for you to try (but this would only make a difference for large matrices): seperate out your addition logic from the multiplication logic in the inner loop like so:

for (k = 0; k < i; k++)
{
    int sums[i];//I know this size declaration is illegal in C. consider 
            //this pseudo-code.
    for (l = 0; l < i; l++)
        sums[l] = MatrixA[j][l]*MatrixB[k][l];

    int suma = 0;
    for(int s = 0; s < i; s++)
       suma += sums[s];
}

This is because you end up stalling your pipeline when you write to suma. Granted, much of this is taken care of in register renaming and the like, but with my limited understanding of hardware, if I wanted to squeeze every ounce of performance out of the code, I would do this because now you don't have to stall the pipeline to wait for a write to suma. Since multiplication is more expensive than addition, you want to let the machine paralleliz it as much as possible, so saving your stalls for the addition means you spend less time waiting in the addition loop than you would in the multiplication loop.

This is just my logic. Others with more knowledge in the area may disagree.

Answer 8

For large matrices you'll want to tile the multiplication to keep stuff in the cache. I recall trying this as a test and measured a 12x performance difference, but I specifically picked a matrix size that consumed multiples of my cache.

There's a lot of literature on the subject. A starting point is:

http://en.wikipedia.org/wiki/Loop%5Ftiling

(there was a book by an author at intel that I recall being particularily helpful, but it's been ten years since reading it, and I can't recall that author's name).

Answer 9

What Every Programmer Should Know About Memory (pdf link) by Ulrich Drepper has a lot of good ideas about memory efficiency, but in particular, he uses matrix multiplication as an example of how knowing about memory and using that knowledge can speed this process. Look at appendix A.1 in his paper, and read through section 6.2.1. Table 6.2 in the paper shows that he could get his running time to be 10% from a naive implementation's time for a 1000x1000 matrix.

Granted, his final code is pretty hairy and uses a lot of system-specific stuff and compile-time tuning, but still, if you really need speed, reading that paper and reading his implementation is definitely worth it.