4 ms·

The real money shot is here: https://github.com/flame/blis/blob/master/docs/Performance.md https://github.com/flame/blis/blob/master/docs/Performance.m... It s

by quanto 3y ago

The real money shot is here: https://github.com/flame/blis/blob/master/docs/Performance.md https://github.com/flame/blis/blob/master/docs/Performance.m... It seems that the selling point is that BLIS does multi-core quite well. I am especially impressed that it does as well as the highly optimized Intel MKL on Intel CPUs. I do not see the selling point of BLIS-specific APIs, though. The whole point of having an open BLAS API standard is that numerical libraries should be drop-in replaceable, so when a new library (such as BLIS here) comes along, one could just re-link the library and reap the performance gain immediately. What is interesting is that numerical algebra work, by nature, is mostly embarrassingly parallel, so it should not be too difficult to write multi-core implementations. And yet, BLIS here performs so much better than some other industry-leading implementations on multi-core configurations. So the question is not why BLIS does so well; the question is why some other implementations do so poorly.

celrod 3y ago
I don't think these are realistic. It does far worse than MKL in practice on Intel CPUs in my tests, especially if arrays are not huge.
- mratsim 3y ago
  MKL has a JIT similar to libxsmm for small sizes.
  - gnufx 3y ago
    That's for very small matrices, but I forget the dimensions. It was only because of libxsmm that MKL got it. (You can use libxsmm to dispatch to OpenBLAS or BLIS for non-tiny cases.) BLIS has "small"-dimension support in many cases; I don't remember what they call it, but you can see changelog items about it.
mgaunard 3y ago
It's not that difficult to be faster than MKL when you write the benchmarks. MKL is a general-purpose library, it does compromises to be good for most sizes. If you care about the performance of specific sizes, you can write code to beat it on that very specific benchmark. Interestingly, BLIS does poorly at small sizes, which is the area where it is easiest to beat MKL at.
- mratsim 3y ago
  MKL is very fast, on Intel. Due to how they do CPU detection. It is a specialized library and they JIT their kernel. Usually BLIS is slower.
bee_rider 3y ago
BLIS mixed precision interfaces seem quite interesting and might be a good reason to expand on the BLAS api. If I recall correctly, MKL also has interfaces that allow different array orders (row order or column order).
- quanto 3y ago
  I can't comment on BLIS-specific interfaces as I do not know, but BLAS standards (including MKL API) covers both different precision levels and matrix representations.
  - bee_rider 3y ago
    By mixed precision, I mean something like AB+C where A and B are single and C is double. That way you don’t have to make a double precision copy of A and B.
klysm 3y ago
I think it has different goals than the BLAS API - it seems like they want to be a higher level generator of BLAS-ish APIs.
eigenman 3y ago
Many of the algorithms in BLAS are not easily parallelized. For example, a QR factorization an inherently sequential algorithm. Optimizing BLAS performance comes mainly from rewriting the sequential algorithm into larger blocks so as to efficiently access memory. As Jim Demmel is fond of saying, floating point optimizations are cheap, memory movement is expensive.
- CreRecombinase 3y ago
  QR decomposition isn’t in BLAS, you’re probably thinking of LAPACK.
vatican_banker 3y ago
> numerical algebra work [...] is mostly embarrassingly parallel It's the exact opposite, most numerical linear algebra is _not_ embarrassingly parallel and requires quite an effort to code properly. That is why BLAS/LAPACK is popular and there are few competing implementations.
- quanto 3y ago
  I would love to be corrected: do you have some specific examples or some underlying principles? My professional and academic background is in numerical analysis and scientific computing (including BLAS/LAPACK level implementations), but I admit I haven't done deep numerical implementations in years.
  - hansvm 3y ago
    Using just basic large dense square matrix multiplication on a modern CPU as an example, not caring about numerical stability, embarrassingly parallel implementations have high bandwidth to compute ratios, bottlenecking your results 10x - 1000x. Embarrassingly parallelizing cache friendlier solutions is prone to stragglers and other scheduling issues. If you're operating on asymptotically faster solutions like Strassen's it's at least a little nontrivial to keep the few largest recursive layers from dominating the computation and not really being much faster than other parallel algorithms. As soon as you start mixing numerical stability (data-dependant operation reordering) concerns into linear algebra routines -- arguably one of the main points of LAPACK -- parallelization necessarily gets trickier because you either need a good enough heuristic to ignore those reorderings or you also need data-dependant scheduling without too many pathologies.
  - sfpotter 3y ago
    Anything involving pivoting for stability isn’t trivial to parallelize. Plain old Gaussian elimination on huge sparse matrices doesn’t scale in parallel very well. At the other end of the spectrum, getting a matrix-matrix multiply to run fast isn’t easy either. It’s what necessitated the kind of approach the authors of BLIS adopted. On paper it’s easy, but actually getting it to run fast on a computer isn’t.
eyegor 3y ago
Holy cow, my main takeaway is that mkl is complete garbage on amd parts and that isn't on accident. This makes me think I need to go back and relink some programs against blis or openblas for amd systems... Even though we primarily switched cluster hardware to amd it never occurred to us that mkl would run at half the throughput of open implementations.
- microtonal 3y ago
  You can override the detection function and get the faster Intel AVX kernels: https://danieldk.eu/Posts/2020-08-31-MKL-Zen https://danieldk.eu/Posts/2020-08-31-MKL-Zen Some back history: they used to use (slow) SSE kernels when a non-Intel CPU is detected. Over time, they started adding kernels for Zen, but last time I tested the Zen kernels were still slower than the AVX kernels. So it still pays off override the Intel CPU detection. It looks like these benchmarks use MKL 2020 update 3. If I recall correctly, this version did not have the Zen sgemm kernels yet. A newer MKL version would perform much better and if you disable Intel detection, MKL would be competitive on Zen.
  - gnufx 3y ago
    That sort of support has come and gone in different versions, though I couldn't tell you which. But, really, why bother? There is too much mythology around Intel stuff.
- gnufx 3y ago
  I don't understand why people use MKL on AMD hardware rather than AMD's (current) library, which is basically upstream BLIS for those architectures; their old one from the Operton era wasn't good. OpenBLAS has been largely competitive with MKL even on Intel anyway over many years, and the MKL licence used not to allow the sort of use people made of it. MKL is infinitely slower than OpenBLAS/BLIS averaged over the hardware relevant to HPC, like the POWER system I support.
  - eyegor 3y ago
    Numerics code is annoying to maintain, and most of us have code bases that already use mkl. Intels compilers make it easy and quick to use, whereas openblas was always a headache in my experience. Plus amd hardware only became competitive in the past few years, so it hasn't mattered.
mratsim 3y ago
The batch match-mul API would be very useful for convolutions. It's also used on Nvidia GPUs. Often you get tensors that are sliced views on one or more dimensions, with BLAS-api you need to allocate them in a contiguous buffer. BLIS does not need that, there is a repacking algorithm to overcome memory bandwidth bounds in matrix multiplication (search the "roofline model"), the slicing/realloc can be fused with repacking with BLIS API.
cbarrick 3y ago
> I do not see the selling point of BLIS-specific APIs BLAS/CBLAS assumes your matrices are column-major/row-major. BLIS uses general stride instead (both columns and rows are parameterized by stride) which makes it more flexible on matrix storage and makes it easier to implement tensor contractions in higher dimensions. This necessitates a different API.

by quanto 3y ago

celrod 3y ago

I don't think these are realistic. It does far worse than MKL in practice on Intel CPUs in my tests, especially if arrays are not huge.

mratsim 3y ago
MKL has a JIT similar to libxsmm for small sizes.
- gnufx 3y ago
  That's for very small matrices, but I forget the dimensions. It was only because of libxsmm that MKL got it. (You can use libxsmm to dispatch to OpenBLAS or BLIS for non-tiny cases.) BLIS has "small"-dimension support in many cases; I don't remember what they call it, but you can see changelog items about it.

mgaunard 3y ago

It's not that difficult to be faster than MKL when you write the benchmarks. MKL is a general-purpose library, it does compromises to be good for most sizes. If you care about the performance of specific sizes, you can write code to beat it on that very specific benchmark. Interestingly, BLIS does poorly at small sizes, which is the area where it is easiest to beat MKL at.

mratsim 3y ago
MKL is very fast, on Intel. Due to how they do CPU detection. It is a specialized library and they JIT their kernel. Usually BLIS is slower.

bee_rider 3y ago

BLIS mixed precision interfaces seem quite interesting and might be a good reason to expand on the BLAS api. If I recall correctly, MKL also has interfaces that allow different array orders (row order or column order).

quanto 3y ago
I can't comment on BLIS-specific interfaces as I do not know, but BLAS standards (including MKL API) covers both different precision levels and matrix representations.
- bee_rider 3y ago
  By mixed precision, I mean something like AB+C where A and B are single and C is double. That way you don’t have to make a double precision copy of A and B.

klysm 3y ago

I think it has different goals than the BLAS API - it seems like they want to be a higher level generator of BLAS-ish APIs.

eigenman 3y ago

Many of the algorithms in BLAS are not easily parallelized. For example, a QR factorization an inherently sequential algorithm. Optimizing BLAS performance comes mainly from rewriting the sequential algorithm into larger blocks so as to efficiently access memory. As Jim Demmel is fond of saying, floating point optimizations are cheap, memory movement is expensive.

CreRecombinase 3y ago
QR decomposition isn’t in BLAS, you’re probably thinking of LAPACK.

vatican_banker 3y ago

> numerical algebra work [...] is mostly embarrassingly parallel It's the exact opposite, most numerical linear algebra is _not_ embarrassingly parallel and requires quite an effort to code properly. That is why BLAS/LAPACK is popular and there are few competing implementations.

quanto 3y ago
I would love to be corrected: do you have some specific examples or some underlying principles? My professional and academic background is in numerical analysis and scientific computing (including BLAS/LAPACK level implementations), but I admit I haven't done deep numerical implementations in years.
- hansvm 3y ago
  Using just basic large dense square matrix multiplication on a modern CPU as an example, not caring about numerical stability, embarrassingly parallel implementations have high bandwidth to compute ratios, bottlenecking your results 10x - 1000x. Embarrassingly parallelizing cache friendlier solutions is prone to stragglers and other scheduling issues. If you're operating on asymptotically faster solutions like Strassen's it's at least a little nontrivial to keep the few largest recursive layers from dominating the computation and not really being much faster than other parallel algorithms. As soon as you start mixing numerical stability (data-dependant operation reordering) concerns into linear algebra routines -- arguably one of the main points of LAPACK -- parallelization necessarily gets trickier because you either need a good enough heuristic to ignore those reorderings or you also need data-dependant scheduling without too many pathologies.
- sfpotter 3y ago
  Anything involving pivoting for stability isn’t trivial to parallelize. Plain old Gaussian elimination on huge sparse matrices doesn’t scale in parallel very well. At the other end of the spectrum, getting a matrix-matrix multiply to run fast isn’t easy either. It’s what necessitated the kind of approach the authors of BLIS adopted. On paper it’s easy, but actually getting it to run fast on a computer isn’t.

eyegor 3y ago

Holy cow, my main takeaway is that mkl is complete garbage on amd parts and that isn't on accident. This makes me think I need to go back and relink some programs against blis or openblas for amd systems... Even though we primarily switched cluster hardware to amd it never occurred to us that mkl would run at half the throughput of open implementations.

microtonal 3y ago
You can override the detection function and get the faster Intel AVX kernels: https://danieldk.eu/Posts/2020-08-31-MKL-Zen https://danieldk.eu/Posts/2020-08-31-MKL-Zen Some back history: they used to use (slow) SSE kernels when a non-Intel CPU is detected. Over time, they started adding kernels for Zen, but last time I tested the Zen kernels were still slower than the AVX kernels. So it still pays off override the Intel CPU detection. It looks like these benchmarks use MKL 2020 update 3. If I recall correctly, this version did not have the Zen sgemm kernels yet. A newer MKL version would perform much better and if you disable Intel detection, MKL would be competitive on Zen.
- gnufx 3y ago
  That sort of support has come and gone in different versions, though I couldn't tell you which. But, really, why bother? There is too much mythology around Intel stuff.
gnufx 3y ago
I don't understand why people use MKL on AMD hardware rather than AMD's (current) library, which is basically upstream BLIS for those architectures; their old one from the Operton era wasn't good. OpenBLAS has been largely competitive with MKL even on Intel anyway over many years, and the MKL licence used not to allow the sort of use people made of it. MKL is infinitely slower than OpenBLAS/BLIS averaged over the hardware relevant to HPC, like the POWER system I support.
- eyegor 3y ago
  Numerics code is annoying to maintain, and most of us have code bases that already use mkl. Intels compilers make it easy and quick to use, whereas openblas was always a headache in my experience. Plus amd hardware only became competitive in the past few years, so it hasn't mattered.

mratsim 3y ago

The batch match-mul API would be very useful for convolutions. It's also used on Nvidia GPUs. Often you get tensors that are sliced views on one or more dimensions, with BLAS-api you need to allocate them in a contiguous buffer. BLIS does not need that, there is a repacking algorithm to overcome memory bandwidth bounds in matrix multiplication (search the "roofline model"), the slicing/realloc can be fused with repacking with BLIS API.

cbarrick 3y ago

> I do not see the selling point of BLIS-specific APIs BLAS/CBLAS assumes your matrices are column-major/row-major. BLIS uses general stride instead (both columns and rows are parameterized by stride) which makes it more flexible on matrix storage and makes it easier to implement tensor contractions in higher dimensions. This necessitates a different API.