iOS BLAS - Accelerate framework poor matrix multiplication performance

Question

I'm implementing a tangent distance based OCR solution for the iPhone, which heavily relies on fast multiplication of floating-point matrices of size 253x7. For the proof of concept, I've implemented my own naive matrix routines like this:

Matrix operator*(const Matrix& matrix) const {
    if(cols != matrix.rows) throw "cant multiply!";

    Matrix result(rows, matrix.cols);
    for(int i = 0; i < result.rows; i++){
        for(int j = 0; j < result.cols; j++){
            T tmp = 0;
            for(int k = 0; k < cols; k++){
                tmp += at(i,k) * matrix.at(k,j);
            }
            result.at(i,j) = tmp;
        }
    }

    return result;
}

As you can see, it's pretty basic. After the PoC performed well, I've decided to push the performance limits further, by incorporating the Accelerate Framework's matrix multiplication (which presumably uses SIMD, and other fancy stuff, to do the heavy lifting...):

Matrix operator*(const Matrix& m) const {
    if(cols != m.rows) throw "cant multiply!";

    Matrix result(rows,m.cols);

    cblas_dgemm(CblasRowMajor, CblasNoTrans, CblasNoTrans, rows, m.cols, cols, 1, matrix, cols, m.matrix, m.cols, 1, result.matrix, result.cols);

    return result;
}

Shockingly (at least for me), the above code took double the time to multiply the matrices! I've tried using single precision instead of double, cause I was suspicious that it was something related with the CPU's word-size (32 bit float vs. 64 bit double on a 32 bit ARM), but had no performance gain...

What am I doing wrong? Are my 253x7 matrices too small for noticeable performance boost over the naive implementation?

Look at MGMatrix, it is exactly what you need. It is based on vDSP and proposes and very simple interface. — MohG

Stephen Canon Stephen Canon · Accepted Answer · 2013-04-02T22:02:48

A couple of questions:

253 x 7 multiplied by what size matrix? If you’re doing, say, 253x7 * 7x1, then a general-purpose multiply routine is going to spend most of its time in edging code, and there’s very little that a tuned library can do that will make it faster than a naive implementation.
What hardware are you timing on, and what iOS version? Especially for double precision, older hardware and older iOS versions are more limited performance-wise. On a Cortex-A8, for example, double-precision arithmetic is completely unpipelined, so there’s almost nothing a library can do to beat a naive implementation.

If the other matrix isn’t ridiculously small, and the hardware is recent, please file a bug (unexpectedly low performance is absolutely a bug). Small matrices with high aspect ratio are quite difficult to make fast in a general-purpose matrix-multiply, but it’s still a good bug to file.

If the hardware/iOS version is old, you may want to use Accelerate anyway, as it should perform significantly better on newer hardware/software.

If the other matrix is just tiny, then there may not be much to be done. There is no double-precision SIMD on ARM, the matrices are too small to benefit from cache blocking, and the dimensions of the matrices would also be too small to benefit much from loop unrolling.

If you know a priori that your matrices will be exactly 253x7 * 7x???, you should be able to do much better than both a naive implementation and any general-purpose library by completely unrolling the inner dimension of the matrix multiplication.

iOS BLAS - Accelerate framework poor matrix multiplication performance

2 Answers