9. Parallelization

The chapter introduces parallelism in the shared memory domain through OpenMP. OpenMP offers “simple” pragmas to parallelize C/C++ code. For example, we could parallelize a for loop by putting the pragma #pragma omp parallel for in front of the loop. A compiler with OpenMP support will generate code that executes the loop in parallel using multiple threads. You can enable OpenMP support using the flag -fopenmp for both the GNU and the Clang compilers.

With OpenMP the order in which loop iterations are executed is no longer guaranteed. To get correct results, we have to ensure that no dependences between loop iterations exists, i.e., two loop iterations should typically not write and read the same location in memory. Chapter 5.4 (Data-Sharing Attribute Clauses) of the OpenMP Application Binary Interface explains constructs that can be used to share data between threads. For example, we may add a private clause to the pragma to declare a variable thread-local, i.e., each thread gets its own copy of the variable:

float l_a[N];
float l_b[N];
float l_result[N];
float l_sum;

// [...]
// additional code that initializes a and b
// [...]

#pragma omp for private( l_sum )
for( int l_i = 0; l_i < N; l_i++ ) {
  l_sum = l_a[l_i] + b[l_i];
  l_result[l_i] = 2 * l_sum;
}

For parallel applications we are interested in the speedup. The speedup \(S_p\) for \(p\) cores is defined as follows:

(9.1)\[S_p = \frac{T_1}{T_p}\]

\(T_p\) is the observed runtime on \(p\) cores. In the ideal case \(S_p=p\) holds, which means that the application runs \(p\)-times faster on \(p\) cores than on one core. However, largely due to serial parts and communication or synchronization between threads, the achieved speedup is usually smaller: \(S_p < p\).

Tasks

  1. Parallelize your solver using OpenMP!

  2. Compare the run time of your parallelized solver to the serial version on NVIDIA Grace! What speedup do you get for up to 144 threads, i.e., when using all cores of Grace? You can specify the number of OpenMP threads using the environment variable OMP_NUM_THREADS.

  3. For the two-dimensional version of the solver, is it better to parallelize the outer or the inner loops?

  4. Try different scheduling and pinning strategies. What performs best? Study NUMA effects and use OpenMP’s first touch policy to perform NUMA-aware initializations.

  5. (Optional) Benchmark your parallelized solver on the Grace system. Use the following settings and provide statistics like elapsed time and cell updates per seconds:

    • 2011 M 9.1 Tohoku Event with 250m resolution

    • 10000 time steps

    • file I/O every 100 time steps

    Provide a creative team name together with your obtained performance. We will honour the best team.