Accuracy of GEMM

[Sameer Agarwal]

Hi Folks,

I am curious as to how folks who work BLAS like routines, think about measuring and optimizing the accuracy of matrix-matrix multiplication routines.

I am not talking about combinatorial correctness, something that can be easily tested by feeding low order integer matrices to the routine and checking equality. I am more curious about the differences that will arise from different accumulation schemes etc. So floating point accuracy.

Thank you,

Sameer

[Robert van de Geijn]

Hi Sameer,

There is a whole field of study dedicated to answering this question:  numerical linear algebra.  Checking accuracy is nontrivial, because the conditioning of the matrices that are involved play a role. 

So, the best answer to your question is:  it is complicated.

Robert

[Jed Brown]

As a possible starting place, this paper on Strassen (from a performance standpoint) includes citations [11,12] on stability of such algorithms.

https://arxiv.org/abs/1605.01078

This is not about GEMM per se, but the numerical examples have a lovely demo that seems relevant to this conversation.

https://arxiv.org/abs/1201.6035

> --
> You received this message because you are subscribed to the Google Groups "blis-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to blis-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/blis-devel/f55559f8-cf56-49fa-a03d-e73eb4fa1a96n%40googlegroups.com.

[Paolo Bientinesi]

Hi Sameer,

A couple of comments.

1) The accuracy of GEMM and most BLAS (and BLAS-like) routines is typically something that developers do not consider. This is because worst case analyses (bounds) exist, and most implementations trivially satisfy them. (Exceptions exist: TRSM, Strassen-like schemes, ...)

2) As Robert points out, there is a whole field of study concerned with the analysis of algorithms and the development of such bounds: numerical linear algebra. The reference book is Nick Higham's "Accuracy and Stability of Numerical Algorithms". Incidentally, Robert and I also wrote on the subject; ours is maybe a bit more gentle introduction for the uninitiated. [1]

[1]; https://hpac.cs.umu.se/~pauldj/pubs/Stability-74105.pdf

3) Despite the number and the breath of different BLAS routines, most (if not all) analyses build on results for the dot product. This is by far the most important building block for accuracy studies. Surprisingly, "new" results keep coming out, depending on the order of the summands, the precision of the data and of the accumulation, and so on. These days (bit-wise) reproducibility is also a thing; hence more work on the topic.

Cheers,  Paolo

-- 
Prof. Paolo Bientinesi, Ph.D.
Director, HPC2N

[Sameer Agarwal]

Thank you Paolo.

Sameer

--
You received this message because you are subscribed to the Google Groups "blis-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to blis-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/blis-devel/CALsf4tvHo4-et43zxOE1siRwOQqRXBYhBPrTEiPf%2B7PFZGfBJA%40mail.gmail.com.