SpeedUp Matrix Multiplication

1
votes

I have to do a matrix boolean multiplication of a matrix with itself in a C++ program and I want to optimize it. The matrix is symmetric so I think to do a row by row multiplication to reduce cache misses. I allocated space for matrix in this way:

matrix=new bool*[dimension];
for (i=0; i<dimension; i++) {
    matrix[i]=new bool[dimension];
}

And the multiplication is the following:

for (m=0; m<dimension; m++) {
    for (n=0; n<dimension; n++) {
         for (k=0; k<dimension; k++) {
                temp=mat[m][k] && mat[n][k];
                B[m][n]= B[m][n] || temp;
...

I did some test of computation time with this version and with another version whit a row by column multiplication like this

for (m=0; m<dimension; m++) {
    for (n=0; n<dimension; n++) {
         for (k=0; k<dimension; k++) {
                temp=mat[m][k] && mat[k][n];
                B[m][n]= B[m][n] || temp;
...

I did tests on a 1000x1000 matrix The result showed that the second version ( row by column ) is faster the previous one. Could you show me why? Shouldn't The misses in the first algorithm be less ?

2
c++performancecachingmatrixmultiplication
You could potentially optimize it for space, and use a data type that uses the bits. - aaragon
Speeding suggestion. In the inner loop: <code> Bmn = false for (k=0; k<dimension && !Bmn; k++) { Bmn = mat[m][k] && mat[k][n]; } B[m][n]= Bmn</code> - Yotam
if you want a even better method for speeding the code up, look up Loop Tiling - programmerjake

2 Answers

1
votes

In the first multiplication approach the rows of the boolean matrices are stored consecutively in memory and also accessed consecutively so that prefetching works flawlessly. In the second approach the cacheline fetched when accessing the element (n,0) can already be evicted when accessing (n+1,0). Whether this actually happens depends on the architecture and its cache hierarchy properties you run your code on. On my machine the first approach is indeed faster for large enough matrices.

As for speeding up the computations: Do not use logical operators since they are evaluated lazy and thus branch misprediction can occur. The inner loop can be exited early as soon as B[m][n] becomes true. Instead of using booleans you might want to consider using the bits of say integers. That way you can combine 32 or 64 elements in your inner loop at once and possibly use vectorization. If your matrices are rather sparse then you might want to consider switching to sparse matrix data structures. Also changing the order of the loops can help as well as introducing blocking. However, any performance optimization is specific to an architecture and class of input matrices.

1
votes

Speeding suggestion. In the inner loop: 

Bmn = false;
for (k=0; k<dimension; k++) {
   if ((Bmn = mat[m][k] && mat[k][n])) {
       k = dimension; // exit for-k loop
   }
} 
B[m][n]= Bmn