partr thread support for openblas

[ViralBShah]

Here are some notes from digging into the openblas codebase (with @stevengj) to enable partr threading support.

1. exec_blas is called by all the routines. The code pattern followed is setting up the work queue and calling exec_blas to do all the work through an openmp pragma.
2. The exception is lapack routines, which also use the exec_blas_async functions.
3. The openmp backend doesn’t seem to implement the async and thus I believe that it will not multi-thread the lapack calls.
4. Windows has its own threading backend

The easiest way may be to modify the openmp threading backend, which seems amenable to something like the fftw partr backend. To start with, we should ignore lapack threading. We could probably just implement an exec_blas_async fallback that calls exec_blas (and make exec_blas_async_wait a no-op).

All of this should work on windows too, although the going through the openmp build route may need some work on the makefiles.

The patch to FFTW should be indicative of something similar to be done for the openblas build.

[ChrisRackauckas]

We now have algorithms in DifferentialEquations.jl which utilize simultaneous implicit methods to enhance the parallelizability of small stiff ODEs and DAEs (i.e. <= 20 ODEs). Right now we'll just document that the user should probably set the BLAS threads to 1, but once this PR is in this algorithm can serve as a very good test case / showcase of why PARTR mixed into BLAS is useful.

SciML/OrdinaryDiffEq.jl#872

[ViralBShah]

This is a fairly straightforward project for someone who doesn't mind diving in and seeing how it was done in FFTW. I will certainly try it out if nobody gives it a shot in a few weeks.

[stevengj]

In the long run, it would be good if partr had a documented C API for spawn/wait, which would give us a lot more flexibility in integrating it with external libraries like this.

[nalimilan]

Do you think this something that will require changes to OpenBLAS upstream and/or compiling OpenBLAS with specific options? Just checking from a packager perspective.

[vchuravy]

Do you think this something that will require changes to OpenBLAS upstream and/or compiling OpenBLAS with specific options? Just checking from a packager perspective.

Yes, we probably have to work with OpenBLAS upstream

[stevengj]

I'm also implementing the FFTW strategy of a pluggable threading backend for Blosc (Blosc/c-blosc2#81).

I think we can make a strong argument to upstream developers that their libraries should use this kind of strategy where possible, because it allows easy composability not only with Julia's partr, but also with Intel's TBB and other threading schedulers. It also seems possible to do this with minimal patches in cases where they have already implemented their own threading.

[stevengj]

I think it's attractive to implement this as a runtime option, in addition to existing threading options rather than instead of them, as I did for FFTW and Blosc. That is, we add a single if statement to the existing exec_blas functions:

exec_blas(num, queue) {
    if (threads_callback) {
        // pass work to the callback function
        return;
    }
    // parallelize normally
}

This has three advantages:

• You can install a single library on your system, and it can be used both by programs that need a custom threading backend and programs that don't.
• If OpenBLAS is using things like pthread or win32 mutex locks to make access to shared resources thread-safe, those will continue to work.
• We don't need to add a new configuration option to OpenBLAS … the optional plug-in backend will be used automatically.

[stevengj]

Regarding the exec_blas_async and exec_blas_async_wait, my hope is that the LAPACK code that calls this could be refactored. My understanding is that it looks something like:

exec_blas_async(queue);
// do some other work
exec_blas_async_wait(queue);

I'm not sure why the "other work" can't simply be added to the queue of parallel tasks, and let the runtime worry about load-balancing.

[stevengj]

I posted a very early draft of the requisite changes at OpenMathLib/OpenBLAS#2255

[stevengj]

Actually, I thought of an even easier way to implement exec_blas_async: the Julia callback can just spawn the tasks and return. The parallel tasks can set pthread mutex values to indicate that they are complete, just as they do now, and exec_blas_async_wait can wait on those mutexes as it does not, without modification to it or the LAPACK source code.

[KristofferC]

Removing milestone since this certainly wasn't release blocking for 1.3 and neither will be for 1.4 or 1.x.

[AzamatB]

I'm confused. I thought that now that we switched to a time-based release schedule with 1.x releases, nothing is release-blocking, so should then all the remaining issues be removed from 1.4 milestone as well?

[chriscoey]

friendly bump on this one. new AMD processors have a ton of threads but I can't take much advantage of PARTR until it works nicely with OpenBLAS since my loops all have various LAPACK calls in them (and I also have standalone LAPACK calls outside of loops that ought to still use all threads)

[ViralBShah]

Increasingly, a lot of libraries in Yggdrasil BB are using openmp, and many of them call BLAS. I suspect that we are increasingly going to see multi-threading clashes between julia threads, pthreaded libraries (openblas), and openmp. The fewer of these we can use the better! I also learnt that if MKL enters the picture, it is yet another library - tbb.

[ViralBShah]

cc @kpamnany

[vtjnash]

It was described to me that this thread pool is actually only relevant for a small number of LAPACK functions, so we could probably reimplement them in a julia better and faster than trying to integrate with the existing system in BLAS. @Keno is that accurate?

[ViralBShah]

I have a multi-threaded LU factorization and linear solve here: https://github.com/ViralBShah/HPL.jl/blob/master/src/hpl_shared.jl

It is reasonable on performance, and may be the better way to do multi-threading.

[ChrisRackauckas]

I have a multi-threaded LU factorization and linear solve here: https://github.com/ViralBShah/HPL.jl/blob/master/src/hpl_shared.jl

https://github.com/YingboMa/RecursiveFactorization.jl is multi-threaded and already outperforms BLAS, both OpenBLAS and MKL. SciML has been defaulting to this for over a year with great success. However, achieving that performance relied on using Polyester.jl and thus opting out of the composable multithreading. Adding the non-polyester threads option to that and calling it a day would be a fitting end to the story at least for the LU case.

[jpsamaroo]

Once #42302 is ready to go, we should be able to trivially allow users to swap out which threadpool BLAS operations use for one which is running Polyester threads, so composability wouldn't even need to be lost in the short term (assuming threadpools make it into the same release).

[tkf]

I don't think supporting multiple thread pools improves the composability of throughput-oriented parallel programs. I think #42302 is a good step toward handling latency-oriented sub-programs well. But we need to centralize the pool for throughput-oriented computation for composability; not the other way around.

Adding the non-polyester threads option to that and calling it a day would be a fitting end to the story at least for the LU case.

This sounds like the most promising direction to me.

[stevengj]

OpenMathLib/OpenBLAS#4577 is a new PR to allow pluggable thread backends into OpenBLAS (currently they tried TBB), which hopefully will make it easy to add partr support. Would be good for some Julia folks to take a look.