OpenMP: What is the benefit of nesting parallelizations?

by

(1) Nested parallelism in OpenMP:
http://docs.oracle.com/cd/E19205-01/819-5270/aewbc/index.html

You need to turn on nested parallelism by setting OMP_NESTED or omp_set_nested because many implementations turn off this feature by default, even some implementations didn’t support nested parallelism fully. If turned on, whenever you meet parallel for, OpenMP will create the number of threads as defined in OMP_NUM_THREADS. So, if 2-level parallelism, the total number of threads would be N^2, where N = OMP_NUM_THREADS.

Such nested parallelism will cause oversubscription, (i.e., the number of busy threads is greater than the cores), which may degrade the speedup. In an extreme case, where nested parallelism is called recursively, threads could be bloated (e.g., creating 1000s threads), and computer just wastes time for context switching. In such case, you may control the number of threads dynamically by setting omp_set_dynamic.

(2) An example of matrix-vector multiplication: the code would look like:

// Input:  A(N by M), B(M by 1)
// Output: C(N by 1)
for (int i = 0; i < N; ++i)
  for (int j = 0; j < M; ++j)
     C[i] += A[i][j] * B[j];

In general, parallelizing inner loops while outer loops are possible is bad because of forking/joining overhead of threads. (though many OpenMP implementations pre-create threads, it still requires some to dispatch tasks to threads and to call implicit barrier at the end of parallel-for)

Your concern is the case of where N < # of CPU. Yes, right, in this case, the speedup would be limited by N, and letting nested parallelism will definitely have benefits.

However, then the code would cause oversubscription if N is sufficiently large. I’m just thinking the following solutions:

  • Changing the loop structure so that only 1-level loop exists. (It looks doable)
  • Specializing the code: if N is small, then do nested parallelism, otherwise don’t do that.
  • Nested parallelism with omp_set_dynamic. But, please make it sure how omp_set_dynamic controls the number of threads and the activity of threads. Implementations may vary.

More Related Contents:

  1. Reducing on array in OpenMP
  2. Why is the != operator not allowed with OpenMP?
  3. Concurrency: Atomic and volatile in C++11 memory model
  4. How does the omp ordered clause work?
  5. What’s the difference between “static” and “dynamic” schedule in OpenMP?
  6. Mixing C++11 atomics and OpenMP
  7. Measure execution time in C++ OpenMP code
  8. OpenMP set_num_threads() is not working
  9. How does OpenMP handle nested loops?
  10. openMP nested parallel for loops vs inner parallel for
  11. Example for boost shared_mutex (multiple reads/one write)?
  12. Why is the destructor of a future returned from `std::async` blocking?
  13. understanding of pthread_cond_wait() and pthread_cond_signal()
  14. How to implement multithread safe singleton in C++11 without using
  15. Difference between pointer and reference as thread parameter
  16. How to use SQLite in a multi-threaded application?
  17. Capture Output of Spawned Process to string
  18. boost.python not supporting parallelism?
  19. Is it smart to replace boost::thread and boost::mutex with c++11 equivalents?
  20. C++11 STL containers and thread safety
  21. Reductions in parallel in logarithmic time
  22. Do I need to protect read access to an STL container in a multithreading environment?
  23. How are user-level threads scheduled/created, and how are kernel level threads created?
  24. Is MAXIMUM_WAIT_OBJECTS really 64?
  25. How to implement a unmanaged thread-safe collection when I get this error: is not supported when compiling with /clr
  26. Portable Compare And Swap (atomic operations) C/C++ library?
  27. Is it possible to use threads to speed up file reading?
  28. signal handler function in multithreaded environment
  29. Different execution policies at runtime
  30. Loading a dll from a dll?

Leave a Comment