Recap: Fork-Join & Parallel Regions

• Your program starts on one master thread, running serially.
• #pragma omp parallel forks a team of threads — the block that follows runs on all of them at once.
• At the end of the block they join back to one thread. You never created or destroyed a thread by hand.

#include <omp.h>
#include <stdio.h>

int main(void) {
    printf("Before: one master thread\n");   // serial

    #pragma omp parallel                      // FORK a team
    {
        int id = omp_get_thread_num();        // 0, 1, 2, ...
        printf("Hello from thread %d\n", id); // runs on every thread
    }                                         // JOIN back to one

    printf("After: serial again\n");          // serial
    return 0;
}

Work-Sharing: Splitting the Job

A parallel region alone makes every thread do the same work. Work-sharing constructs divide the work up:

// The combined shortcut you'll use most: parallel + for in one line
#pragma omp parallel for
for (int i = 0; i < N; i++) {
    a[i] = b[i] + c[i];     // each thread gets a slice of the iterations
}

Task Parallelism with sections

for is the same work over many data. sections is different jobs at once — one cook chops, one boils rice, one fries.

#pragma omp parallel
{
    #pragma omp sections          // the team splits up the sections
    {
        #pragma omp section
        { load_data(); }          // one thread runs this

        #pragma omp section
        { render_report(); }      // another thread runs this

        #pragma omp section
        { send_email(); }         // another thread runs this
    }                             // implicit barrier: wait for all three
}

Scheduling: Who Gets Which Iterations?

schedule(kind [,chunk]) decides how loop iterations map to threads. This ties directly to load balancing (Session 09).

Worked Example: One Loop, Four Schedules

12 iterations, 4 threads. Iteration i costs (i+1) ms — so 1, 2, 3 … 12 ms. Total 78 ms. Who gets what?

Data Scoping — The #1 Bug Source

When threads share a variable they shouldn't, you get a silent, luck-dependent wrong answer. Scoping clauses say who sees what:

Worked Example: Predict the Output

Cover the answers. Write down what you think this prints. Almost everyone gets at least one wrong the first time.

int x = 10, y = 20, z = 30, total = 0;

#pragma omp parallel for num_threads(4) \
        private(x) firstprivate(y) lastprivate(z) reduction(+:total)
for (int i = 0; i < 4; i++) {
    x = x + i;          // what is x here?
    y = y + i;
    z = i * 100;
    total = total + i;
}
printf("x=%d  y=%d  z=%d  total=%d\n", x, y, z, total);

Synchronization: Taking Turns Safely

long sum = 0;
#pragma omp parallel for reduction(+:sum)   // the right way to combine
for (int i = 0; i < N; i++) sum += a[i];   // no race, correct every run

Worked Example: The Barrier You Didn't Write

Every omp for, sections and single ends with an implicit barrier you never typed. Sometimes that's exactly right. Sometimes it costs you 20%.

#pragma omp parallel
{
    #pragma omp for
    for (i=0;i<N;i++)  a[i] = f(i);      // <-- invisible barrier here

    #pragma omp for
    for (i=0;i<N;i++)  b[i] = g(i);      // <-- and here
}

Suppose each loop averages 100 ms per thread, but the slowest thread takes 120 ms. Four such loops:

    #pragma omp for nowait
    for (i=0;i<N;i++)  a[i] = f(i);      // finish early, move straight on

    #pragma omp for
    for (i=0;i<N;i++)  b[i] = g(i);      // barrier at the end of the region anyway

    #pragma omp for nowait
    for (i=0;i<N;i++)  a[i] = f(i);

    #pragma omp for
    for (i=0;i<N;i++)  b[i] = a[i] * 2;   // may read a[i] before it was written

Lab 1: Matrix Multiplication

Multiplying two matrices, C = A × B, is the textbook "embarrassingly parallel" problem: every output cell is an independent dot product. No two cells depend on each other — so they can all be computed at once.

C[i][j] = A[i][0]*B[0][j] + A[i][1]*B[1][j] + ... + A[i][n-1]*B[n-1][j]

        A (rows)              B (cols)            C (independent cells)
     ┌───────────┐        ┌───┬───┬───┐        ┌───┬───┬───┐
row i│ ● ● ● ● ● │   ×    │ │ │ │ │ │ │   =    │ · │ ✦ │ · │  ← each ✦ is
     └───────────┘        │ │ │ │ │ │ │        ├───┼───┼───┤    its own job,
                          │ ▼ │ ▼ │ ▼ │        │ · │ · │ · │    computed by
                          └───┴───┴───┘        └───┴───┴───┘    any thread

Lab 1: The Serial Version

The classic triple loop, running on one thread. This is our baseline — we time it, then race the parallel version against it.

void multiply_serial(const double *A, const double *B, double *C) {
    for (int i = 0; i < N; i++) {          // each row
        for (int j = 0; j < N; j++) {      // each column
            double sum = 0.0;              // dot product accumulator
            for (int k = 0; k < N; k++) {  // walk the row x column
                sum += A[i*N + k] * B[k*N + j];
            }
            C[i*N + j] = sum;              // one output cell
        }
    }
}

double t0 = omp_get_wtime();               // high-resolution timer
multiply_serial(A, B, C);
double serial_time = omp_get_wtime() - t0; // seconds

Lab 1: The Parallel Version — One Line

The maths is identical. We add one pragma on the outer loop — and get the scoping right.

void multiply_parallel(const double *A, const double *B, double *C) {
    #pragma omp parallel for schedule(static) \
            default(none) shared(A, B, C)
    for (int i = 0; i < N; i++) {          // i is private (the omp for index)
        for (int j = 0; j < N; j++) {      // j declared here -> private
            double sum = 0.0;              // sum is local -> private
            for (int k = 0; k < N; k++) {  // k declared here -> private
                sum += A[i*N + k] * B[k*N + j];
            }
            C[i*N + j] = sum;              // threads write disjoint rows: no race
        }
    }
}

Lab 1: Results & Speedup

Same 512×512 multiply, just changing OMP_NUM_THREADS (measured on an 8-core laptop):

Pitfalls & Good Habits

Recap & What's Next

Key Takeaways

• Work-sharing: for splits a loop, sections splits different jobs.
• Scheduling maps iterations to threads — match it to how even the work is.
• Data scoping is the #1 bug source; default(none) saves you.
• Synchronization (reduction, atomic, critical) makes shared updates safe.
• Lab 1: one pragma turned a serial matrix multiply into a 3–5× speedup.

Homework

• Run 03-matrix-multiply.c at 1, 2, 4, 8 threads and tabulate speedup.
• Change schedule(static) to dynamic — does it get faster or slower? Why?
• Bump N to 1024 and watch how the speedup changes.