What loop size to multithread?

user_14391257 0
Viewed 84

Imagine a simple loop:

constexpr int N; // some big number

#pragma omp parallel for
for(int i=0; i<N; ++i)
{
    // some not very demanding computation like
    // c[i] = a[i] + b[i]
}

How can I determine (approximately), if such loop is suitable for parallelization with respect to size N?

For example, if I have a 20-core CPU, this #pragma changes nothing compared to normal version in terms of speed for N = 400. However it obviously does for something like N = 1e+7.

What should I know about hardware/operation cost/etc to estimate the speed-up(or down) of multithreading?

openmp multithreading c++
1 Answers

There is obviously no rule of thumb for choosing whether parallelization is suitable for a given piece of code, simply because it does depend on too many things:

  • do you really need the extra performance? maybe your code is totally fine running in 147ms instead of 23ms? maybe you also care about code readability? power consumption? if your program runs along many others, maybe it is not a great idea to hog the computer resources?
  • Amdahl's law tells you that even though most of your code may run in parallel a small single-threaded portion of your code is enough to drastically limit your performance scaling
  • the task itself: even if it is a simple task, how is the data access? is it cache friendly? how do you write your data? would you need to synchronize between threads? maybe your algorithm is convoluted and could be made faster? etc
  • the compiler optimization: for example your compiler may automatically vectorize your loop to leverage your processor AVX support. In such case, the actual "work size" may be way lower than your N
  • regarding OpenMP, most implementation will allocate a thread pool at program start. So you only pay a "small" cost at runtime to dispatch tasks. Of course, if it takes less time to actually do the task than to dispatch it, the parallelization is obviously not worth it

Long story short: the only way you can know whether parallelization may be worth it is to try it out and measure the performance. Fortunately, a #pragma omp parallel for is very fast to write and test.

For more information about parallel efficiency and scalability I recommend you this presentation: https://www.nersc.gov/assets/Uploads/Profiling-and-Scaling.pdf

user_51382590
Related