OpenMP Execution and Variable Prediction

1. The OpenMP Execution Model: Fork-Join

OpenMP uses a simple yet powerful model called fork-join parallelism. A program starts as a single process, called the master thread. When it encounters a parallel region, the master thread "forks," creating a team of worker threads. All threads (master included) then execute the code inside the parallel region. At the end of the region, the threads "join" back together. They synchronize, the worker threads are terminated, and only the master thread continues.

Your C++ programs, therefore, become a sequence of serial parts (executed only by the master thread) and parallel regions (executed by all threads).

The primary way to define a parallel region in OpenMP is with the #pragma omp parallel directive. A pragma is a special instruction for the compiler. When you compile with an OpenMP-enabled compiler (e.g., using the -fopenmp flag in GCC/Clang), it interprets these pragmas to generate multi-threaded code.

Let's look at the classic "Hello, World" example:

#include <iostream>
#include <omp.h> // OpenMP header

int main() {
    // This part is serial, executed by the master thread only.
    std::cout << "Starting the program." << std::endl;




    #pragma omp parallel
    {
        // This is the parallel region.
        // Every thread in the team executes this block of code.
        int thread_id = omp_get_thread_num(); // Get my unique ID (0 to N-1)
        int num_threads = omp_get_num_threads(); // Get total number of threads

        std::cout << "Hello from thread " << thread_id 
                  << " of " << num_threads << std::endl;
    } // Implicit barrier: threads wait here until all have finished.

    // This part is serial again.
    std::cout << "Program finished." << std::endl;

    return 0;
}

If you run this program (requesting, say, 4 threads), you might get an output like this:

Starting the program.
Hello from thread 2 of 4
Hello from thread 0 of 4
Hello from thread 3 of 4
Hello from thread 1 of 4
Program finished.

Notice the jumbled order. This directly demonstrates the concept of a race condition we discussed in the last lesson. Multiple threads are racing to access the shared std::cout resource. The operating system schedules them in a non-deterministic order, so the output can be different each time you run it.

Identifying a parallel region is your first step in tracing OpenMP code. Look for the #pragma omp parallel directive. The structured block of code that follows it is what you need to analyze from the perspective of multiple threads.

2. Data Scoping: Shared vs. Private Variables

Correctly predicting the final values of variables hinges on understanding OpenMP's data scoping rules—whether a variable is shared among all threads or private to each thread.

The default rules are straightforward:

• Variables declared outside a parallel region are shared by default. All threads see and can modify the same memory location.
• Variables declared inside a parallel region are private. Each thread gets its own separate copy of the variable.

Now, let's trace a simple example that illustrates the danger of unsynchronized access to a shared variable.

#include <iostream>
#include <vector>
#include <omp.h>

int main() {
    int total_sum = 0; // SHARED variable




    #pragma omp parallel num_threads(4)
    {
        // This is a private variable. Each thread has its own `my_id`.
        int my_id = omp_get_thread_num(); 
        
        // RACE CONDITION on `total_sum`
        total_sum += 10; 

        std::cout << "Thread " << my_id << " sees total_sum as potentially inconsistent." << std::endl;
    }

    // What is the final value of total_sum?
    std::cout << "Final total_sum: " << total_sum << std::endl;
}

You might expect the final total_sum to be 40. However, it is not guaranteed. The operation total_sum += 10 is not atomic; it's a read-modify-write sequence. Two threads could read the same initial value of total_sum, both add 10, and then write their result back, with one write overwriting the other. The final result could be 10, 20, 30, or 40.

Solution 1: Synchronization with critical

To fix this, we can wrap the update in a #pragma omp critical block. This is the OpenMP equivalent of using a mutex to protect a critical section. Only one thread can enter the block at a time.

#pragma omp parallel num_threads(4)
{



    #pragma omp critical
    {
        total_sum += 10; // Correct, but serializes the updates.
    }
}
// Now, the final total_sum is guaranteed to be 40.

Solution 2: The reduction Clause

The pattern of accumulating a value from all threads into a single result is extremely common. OpenMP provides a much more efficient and elegant solution for this: the reduction clause.

The reduction clause tells the compiler to:

1. Create a private copy of the reduction variable for each thread (e.g., sum).
2. Initialize this private copy based on the operator (e.g., to 0 for +).
3. Let each thread work on its private copy.
4. At the end of the region, combine (or "reduce") all the private copies into the original shared variable using the specified operator.

This avoids the race condition without the overhead of a critical section on every single update.

3. Tracing a Parallel Loop

Now, let's combine these concepts to trace a complete example. The most common use of OpenMP is to parallelize loops using the #pragma omp for directive. This directive automatically divides the loop iterations among the threads in the team.

Consider the following program, which calculates the sum of the first 8 integers using two threads.

#include <iostream>
#include <omp.h>

int main() {
    long long sum = 0;
    int num_steps = 8;
    
    omp_set_num_threads(2); // Request 2 threads for the next parallel region

    // This is a combined parallel-for construct.
    // It creates a parallel region AND distributes the loop iterations.



    #pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < num_steps; i++) {
        // Each iteration adds its index+1 to a private copy of sum
        sum += (i + 1);
        
        // Let's add a print to see what's happening
        int thread_id = omp_get_thread_num();
        std::cout << "Thread " << thread_id << " computed iteration " << i << std::endl;
    }

    std::cout << "Final sum: " << sum << std::endl;
    return 0;
}

Let's trace this code to predict the final value of sum.

1. Identify the Parallel Region and Data Scoping:

• The for loop is the parallel region, defined by #pragma omp parallel for.
• sum is a reduction variable. It starts as a shared variable with value 0. Inside the loop, each thread gets a private copy, also initialized to 0.
• i (the loop counter) is automatically made private to each thread.
• num_steps is shared.

2. Determine Work Distribution:

• By default, OpenMP uses a static schedule. It divides the num_steps (8) iterations as evenly as possible among the num_threads (2).
• Thread 0 will likely execute iterations i = 0, 1, 2, 3.
• Thread 1 will likely execute iterations i = 4, 5, 6, 7.

3. Trace the Execution in Each Thread:

• Thread 0:

  • Its private sum starts at 0.
  • i=0: sum = 0 + (0+1) = 1
  • i=1: sum = 1 + (1+1) = 3
  • i=2: sum = 3 + (2+1) = 6
  • i=3: sum = 6 + (3+1) = 10
  • At the end of its work, Thread 0 has a final private sum of 10.

• Thread 1:

  • Its private sum starts at 0.
  • i=4: sum = 0 + (4+1) = 5
  • i=5: sum = 5 + (5+1) = 11
  • i=6: sum = 11 + (6+1) = 18
  • i=7: sum = 18 + (7+1) = 26
  • At the end of its work, Thread 1 has a final private sum of 26.

4. Predict the Final Value:

• At the implicit barrier at the end of the loop, the reduction operation takes place.
• The final value of the shared sum is calculated by combining the initial shared value with all the private values:
  $\text{final\_sum}=\text{initial\_shared\_sum}+\text{private\_sum\_thread0}+\text{private\_sum\_thread1}$
  $\text{final\_sum}=0+10+26=36$

The correct sum of integers from 1 to 8 is indeed 8 * (8 + 1) / 2 = 36. Our trace correctly predicts the program's output.

Conclusion

In this lesson, we transitioned from the theory of parallel execution to the practice of tracing OpenMP code. By understanding the fork-join model, data scoping rules, and work-sharing constructs, you can now analyze a piece of parallel code and reason about its behavior.

Key Takeaways:

• Parallel Regions: Code blocks following #pragma omp parallel are executed by a team of threads, following a fork-join model.
• Data Scoping: Variables are either shared (one copy for all threads) or private (one copy per thread). This is the most critical factor in predicting variable values.
• Synchronization: Unsynchronized updates to shared variables create race conditions. OpenMP provides critical and atomic pragmas for protection.
• Reduction: The reduction clause is a powerful and efficient construct for safely performing aggregation operations (like sum, product, max, min) across threads.
• Work-sharing: Directives like #pragma omp for automatically divide work (e.g., loop iterations) among threads, simplifying parallelization.

In the next lesson, we will move from shared-memory systems to distributed-memory systems and learn to trace the execution of MPI code involving point-to-point and collective communication. This will introduce a new paradigm where processes communicate by explicitly sending messages instead of sharing variables.