1

There are a number of ways to improve the performance of a matrix-matrix multiplication (e.g. using the transpose of the second matrix to exploit locality of reference, using algorithmic approaches like Strassen etc.)

But is there a way to improve the performance of vector-matrix multiplication? (Even a google search for this would redirect to matrix-matrix multiplication improvement methods.) I know that we can use loop unrolling to get some amount of performance improvement, but are there any other methods?

3 Answers 3

2

By definition, matrix-vector multiplication is a sequence of unrelated dot products. Since they are unrelated, they can be performed in parallel.

GPU matrix-vector product (gemv) gives a very nice & detailed comparison of different GPU parallelizations for gem? operations.

As with anything GPU related, the problem would need to be substantial enough to warrant the setup overhead of a GPU call to begin with. Presumably, if the column dimension of the matrix would be long enough, even CPU thread parallelization could speed things up.


A different direction relates to what you wrote about loop unrolling. Loop unrolling simply exploits some knowledge of computer architecture, namely that a cache miss can safely perform here out-of-order execution

// Code fragment for calculating the ith product entry.
for(size_t j = 0; j < n, j += 4)
{
    sum0 += m[i][j] * v[j];
    sum1 += m[i + 1][j] * v[j];
    sum2 += m[i + 2][j] * v[j];
    sum3 += m[i + 3][j] * v[j];
}

BLAS libraries, e.g., OpenBLAS perform many more such micro optimizations, some of which rely on very architecture-specific features.

2
  • I was looking for something that doesn't use parallelism (hence didn't try GPUs). Thanks anyway! Feb 29, 2016 at 7:07
  • No problem. Good luck.
    – Ami Tavory
    Feb 29, 2016 at 7:08
1

In the past I've used 1-dimensional matrices which are much faster to access than 2-dimensional matrices. They are also not that much harder to use, you can access each element using something like:

int i, j;
for (i = 0; i < COLUMN_LENGTH; i++)
{
    for (j = 0; j < ROW_LENGTH; j++)
    {
        printf("%f\n", A[i * ROW_LENGTH + j]);
    }
}

This is for a row-major ordered matrix.

The math library LAPACK is something that you could use instead in your application, the matrix functions have been highly tuned for various architectures. Otherwise you could read the source code which might give you some ideas for your own optimizations.

1
  • Without using a library, I was trying to do the improvement myself. I'll try the 1-D array thing and see how it would perform. Feb 29, 2016 at 7:08
0

I think that the universal solution doesn't exist. But we can accelerate calculations with attention to specific features of calculating means of throuh using fast memory for vector, the cache memory properties and other.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.