[Discussion] More OpenMP support

[Segfault1602]

Hi,

I am wondering if there has been discussion regarding better multithreading/openmp support in ensmallen. It seems to me that certain algorithms (PSO, CNE, and DE come to mind) could benefit greatly from parallel processing. Such a change would potentially break a lot of the callbacks shipped with ensmallen so I'm wondering if it's something people have already thought about and if that is something people are generally interested in.

Thanks,
-Alex

[rcurtin]

I agree that it would be really nice for some algorithms---especially the ones that you specified which are in places embarrassingly parallel. I'd be happy to help an effort to implement that support but I think we'd need to think about the following:

• How could a user disable or control the multithreading so that, e.g., if their Evaluate() implementation is already using parallelism, they could disable the optimizer-level parallelism?

• How could we ensure that callbacks (when they were called) were still thread-safe, or, e.g., only called from the main thread?

• How can we ensure that the code will still compile and run just fine even if the user doesn't have OpenMP enabled?

• Are there places where parallelism would actually affect the results (moreso than just changing floating-point operation ordering)?

Definitely those questions are not impossible to answer, I just think we'd need to keep them in mind as we worked out a solution.

[Segfault1602]

For the build related questions:

I was hoping this part would be relatively easy given that ParallelSGD already uses OpenMP but it appears the build is broken when enabling ENS_USE_OPENMP. It's an easy fix but then the ParallelSGD tests are failing so that would probably need to be fixed first.

I do think that reusing ENS_USE_OPENMP could be a big breaking change so maybe we need to use a new #define flag?

How could we ensure that callbacks (when they were called) were still thread-safe, or, e.g., only called from the main thread?

I think that it would be reasonable to expect the user's code to be thread-safe when parallelization is enabled, I'm not sure I can imagine a scenario where I expect my Evaluate() calls to be called on multiple threads but then need my Callback::Evaluate() call to be sequential and or single threaded. Things like ens::report() can be made thread-safe relatively easily but for more complex callback that changes optimizer state, I don't know if there is a solution that will work for everyone. Taking CNE as an example, it looks like the optimizer state can't be changed in the middle of a generation so that is good. It also looks like it doesn't support early termination in the middle of a generation, so that also make things easier.

// Calculating fitness values of all candidates.
// cne_impl.hpp:122
#pragma omp parallel for
for (size_t i = 0; i < populationSize; i++)
{
    // Select a candidate and insert the parameters in the function.
    iterate = population[i];

    #pragma omp critical
    {
    terminate |= Callback::StepTaken(*this, function, iterate, callbacks...);
    }

    // Find fitness of candidate.
    fitnessValues[i] = function.Evaluate(iterate);

    #pragma omp critical
    {
    terminate |= Callback::Evaluate(*this, function, iterate, fitnessValues[i], callbacks...);
    }
}

On the other hand, changing differentialWeight in de_impl.hpp could lead to unexpected result and I don't think wrapping Callback::*() calls in critical section would help in that regard.

[rcurtin]

I was hoping this part would be relatively easy given that ParallelSGD already uses OpenMP but it appears the build is broken when enabling ENS_USE_OPENMP. It's an easy fix but then the ParallelSGD tests are failing so that would probably need to be fixed first.

Can you tell me more of what you mean? When I compile locally with the CMake option -DUSE_OPENMP=ON (the default), OpenMP is successfully enabled and the ParallelSGD tests run just fine.

I need to think a bit more deeply about the rest of this before giving a thoughtful response; I'm a bit held down with other things today and not in the right headspace to think about ensmallen design. Tomorrow should be better.

[Segfault1602]

USE_OPENMP is enabled by default yes, but nothing is setting ENS_USE_OPENMP which is what enables the openmp codepath in ensmallen. The only tests that is not behind the #ifdef is ParallelSGD_ExponentialBackoffDecayTest, so maybe that what your are seeing? I'm also seeing this in config.hpp:

#if defined(ARMA_USE_OPENMP)
  #undef  ENS_USE_OPENMP
  #define ENS_USE_OPENMP
#endif

I don't have ARMA_USE_OPENMP defined, but maybe you do so that could also explain why it is enabled on your end?

When I define ENS_USE_OPENMP I get "unknown pragma" errors that seems to be due to a missing -fopenmp flag during compilation. Adding the line find_package(OpenMP) in CMakeLists.txt fixes that for me. It sounds like find_package(OpenMP) was broken in older version of cmake so that might not work if your cmake version is older than 3.9.

omp.h is also not included anywhere so places that call omp_get_thread_num() should not compile. I'm guessing omp.h is included somewhere in armadillo, in which case things would compile as long as ARMA_USE_OPENMP is defined.

Once I have everything compiling I can run the tests and get this output:

alex@desktop:~/src/ensmallen$ ./build/Release/ensmallen_tests "[ParallelSGD]"
ensmallen version: 3.11.0 (Sunny Day)
armadillo version: 12.6.7 (Cortisol Retox)
random seed: 0
Filters: [ParallelSGD]

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ensmallen_tests is a Catch v2.13.10 host application.
Run with -? for options

-------------------------------------------------------------------------------
ParallelSGDTest_SparseFunction - arma::mat
-------------------------------------------------------------------------------
/home/alex/src/ensmallen/tests/parallel_sgd_test.cpp:36
...............................................................................

/home/alex/src/ensmallen/tests/test_function_tools.hpp:118: FAILED:
  REQUIRE( objective == Approx(expectedObjective).margin(objectiveMargin) )
with expansion:
  inf == Approx( 123.75 )

...
===============================================================================
test cases:   6 |   1 passed | 5 failed
assertions: 125 | 120 passed | 5 failed

[rcurtin]

Thanks for reporting that @Segfault1602 and sorry it took me so long to get back to this. When I dug a little bit deeper I found what I wrote is actually wrong:

When I compile locally with the CMake option -DUSE_OPENMP=ON (the default), OpenMP is successfully enabled

I took "CMake found OpenMP" to be "successfully enabled" but that's not true. As soon as I did that, I realized that the issue in the tests was just that the step sizes were too large (due to some long-time-ago changes that mistakenly overlooked ParallelSGD for exactly this reason!), and they needed to be tuned. I opened #454 to fix that issue.

Also I believe you are right that omp.h is included by Armadillo... but I made it explicit in #454 too.

In any case, bugs aside... back to the original issue...

I do think that reusing ENS_USE_OPENMP could be a big breaking change so maybe we need to use a new #define flag?

I don't know that it would be needed: if the changes that you make are wrapping callbacks in critical sections, then I don't think it will break anyone's code.

ensmallen will indeed behave differently if a non-parallel optimizer suddenly becomes parallel, but, I am less concerned about this: for embarrassingly parallel sections of optimizers (like you are proposing to focus on), the results will be the same (modulo floating-point errors); but most ensmallen users will be optimizing from a random starting position anyway and I would not imagine they expect exact reproducibility with older code.

They will, however, expect reproducibility across different runs of their own code; but, this should be handled at the Armadillo level: when you call arma_rng::set_seed(), it will set a different (but deterministic) random seed for each OpenMP thread.

But even there OpenMP may have a subtle problem for us: if the schedule is not static, then there are no guarantees about which threads work is assigned to, and even if the user sets the random seed, there is not a guarantee that the same threads will receive the same work (and this can result in different overall results). There is some thinking and discernment to be done here: do we work hard to provide a way for users to get the exact same results in a multithreaded setting? Are there environment variables we can tell them to set to disable dynamic scheduling and thus get reproducible results? Or do we tell them that the way to get reproducible results is to run singlethreaded? I could be persuaded that any of those (or perhaps a fourth option) would be the right way to go; what do you think?

On the other hand, changing differentialWeight in de_impl.hpp could lead to unexpected result and I don't think wrapping Callback::*() calls in critical section would help in that regard.

I think the critical section idea works reasonably well, although it may make sense to allow users to configure whether critical sections are used. (Perhaps a boolean "allowParallelCallbacks" option to be added to the affected optimizers?)

For DE, parameters that are used in the inner loop could be collected from the class's value as an atomic operation at the start of the iteration. Or, we could not worry about it: I am not sure it would make a significant difference if a user is modifying internal state of the optimizer and one thread uses a larger differential weight than another because of a race condition; an iterative algorithm like ensmallen's optimizers are already generally robust to noise anyway.

Perhaps it makes sense to start with a single optimizer where the more tricky stuff is not an issue (e.g. CNE) and get a minimum viable example of parallelization?

I know I wrote a lot but I hope it is overall helpful. Sorry again it took me so long to get back to this.

[Segfault1602]

I don't know that it would be needed: if the changes that you make are wrapping callbacks in critical sections, then I don't think it will break anyone's code.

The breaking change I was thinking about is that the Evaluate calls will now need to be thread safe. If ENS_USE_OPENMP is enabled by default that would cause some issue.

The other issue is, maybe Evaluate() is thread-safe but it uses one of the Armadillo function that is OpenMP enabled. I don't think OpenMP support those types of nested parallel scenario well from what I could read. There should probably be a way to have ARMA_USE_OPENMP=ON and ENS_USE_OPEN=OFF at the same time.

I had CNE,PSO and DE working in parallel on my machine, unfortunately my SSD died and I did not think to save those changes. Luckily the change needed were extremely small so I should be able to share something in the coming days.

[rcurtin]

That's true, but I don't think that needs compile-time intervention; I think you can solve that problem by adding a numThreads parameter to the relevant optimizers. This parameter could always default to 0 (representing whatever OMP_NUM_THREADS is set to), and a setting of 1 would allow the program to use OpenMP at the lower Armadillo level instead of the ensmallen level. (I think some checking of the implementation would need to be done to make sure that works right, because OMP_NESTED is I think turned off by default, so we'd need to make sure that when the user is only using one thread, that we haven't inadvertently disallowed the lower level of OpenMP parallelization.)

So I guess my take is: at compile-time the user chooses whether or not parallelization is even going to be available at runtime. Control over the parallelization can then happen at runtime (or, rather, in C++ vs. via macros). What do you think?

[github-actions]

This issue has been automatically marked as stale because it has not had any recent activity. It will be closed in 7 days if no further activity occurs. Thank you for your contributions! 👍