Above average kernel times causing slow performance

[bgeneto]

Hi!

In comparing OpenBLAS performance with Intel MKL I've noticed that (at least in my particular case: real or hermitian eigenvalue problem, e.g. ZHEEV) OpenBLAS is consuming too much more kernel times (red bars in htop) than Intel MKL and maybe this is why it is so slow (three to five times slower, depending on matrix size) compared to MKL. Does anybody know what is causing so much kernel threads/time and how to avoid it? I've already limited OPENBLAS_NUM_THREADS to 4 or 8... TIA.

[martin-frbg]

What CPU, which version of OpenBLAS, what matrix size(s) ? Does limiting OPENBLAS_NUM_THREADS further (even to just 2) improve performance ?
MKL may simply have a more efficient implementation of ZHEEV than the one from the netlib reference implementation of LAPACK that OpenBLAS uses, or may be better at choosing the appropriate number of threads for your problem size in a BLAS call from some part of ZHEEV. (Can you tell where in ZHEEV the time is spent, or can you provide a code sample that shows the problem ? At a quick glance, netlib ZHEEV calls at least ZHETRD, ZSTEQR and either DSETRF or ZUNGTR, and those four will in turn call other routines...)

[bgeneto]

I've tested with various CPU families (mostly Nehalem, but also with AMD ryzen/threadripper). The above mentioned aspect (too much time spent with kernel calls) happens with every tested system. In fact OPENBLAS_NUM_THREADS=1 has better performance than any other number of threads, problem size is 200x200 or 300x300. When running with only one thread CPU time is 100% green, with two or more threads the first thread is 100% green and the other ones are mostly red (kernel times) and results in worse performance. I would like to understand why this is happening and how to avoid it (while using multiple threads). Maybe an openmp build of OpenBLAS has better parallelism in this particular case? I can provide a quick example/fortran source later...

[martin-frbg]

kernel time on the "other" threads is probably spent in sched_yield() - either waiting on a lock, or simply waiting for something to do. Which version of OpenBLAS are you using - 0.2.20 or a snapshot of the develop branch ? (The latter has a changed GEMM multithreading which may help)

[brada4]

Once can experiment with YIELDING macro. No idea why but sched_yield there spins CPU in kernel to 100% while having noop there runs cpus nearly idle at no penalty to overall time.
I dont remember the issue in the past around it

[martin-frbg]

Issue #900, but previous experiments there have been quite inconclusive. I would not exclude the possibilty that processes spending their time in YIELDING (for whatever implementation of that) is just a symptom and not the issue itself.

[brada4]

I suspect sched_yield became CPU hog at some point, but what it hogs otherwise would go unused...

[brada4]

I wonder if it is same observation as #1544

[martin-frbg]

Observation from #1544 is not quite clear yet, and ARMV7 already has nop instead of sched_yield

[bgeneto]

I don't know if the "problem" is related to sched_yield(), I'm afraid I don't have the right tools to check... So instead I provide the example code below so the experts here can profile/debug :-)

zheev-example

[brada4]

Thank you for sample.

1. official doc shortlists BLAS functions that may have wrong multiprocessing thresholds (abovemost diagram, 4-o-clock corner)
2. sched_yield that eats a lot, but experimenting to eliminate it did not give conclusive improvement.

[martin-frbg]

This may in part be a LAPACK issue, recent LAPACK includes an alternative, OpenMP-parallelized version of ZHEEV called ZHEEV_2STAGE that may show better performance (have not gotten around to trying with your example yet, sorry). On the BLAS side, it seems interface/zaxpy.c did not receive the same ("temporary") fix for inefficient multithreading of small problem sizes as interface/axpy.c did (7 years ago, for issue #27). Not sure yet if that is related either...

[martin-frbg]

According to perf, most of the time (on Kaby Lake mobile hardware at least) appears to be spent in zlasr, with zaxpy playing a minor role (but indeed doing needless multithreading for small sizes). zgemm seems to be more prominent, though from #1320 its behaviour should be quite good already.

[brada4]

The problem is that threads doing nothing but spun up are not accounted in perf, they land as yielding instead.
What about adding another thread only when previous sort of utilizes all l3 cache in in+temp+out ?
I know it is shared and repartitioned between cores/clusters/whatever on modern CPUs, but at least to start with good approximation.
I guess at few cores axpy will saturate memory bw anyway.

[martin-frbg]

Preliminary - changing sched_yield to nop does not directly affect running time, but gets rid of busy waiting that would drive cpu temperature (possibly leading to thermal throttling on poorly designed hardware). Dropping zaxpy to single threading is the only change that leads to a small speedup, while changing the thresholds for multithreading in zgemm, zhemv only reduces performance. As noted above, the majority of the time is spent in unoptimized LAPACK zlasr - for which MKL probably uses a better algorithm than the reference implementation. Also most of the lock/unlock cycles spent in the testcase appear to be from libc's random() used to fill the input matrix. (I ran the testcase 1000 times in a loop to get somewhat better data, but still the ratio between times spent in setup and actual calculation is a bit poor - which probably also explains the huge overhead from creating threads that are hardly needed afterwards.) Probably need to rewrite the testcase first when I find time for this again.