From Theory to Typing

This is the last session of Unit I.

Three Ways to Split Work

Example: One Job, Split Three Ways

The job: encode a 1-hour video. Serially it takes 60 minutes, made of four stages — decode (10 min), denoise (8 min), encode video (40 min), encode audio (2 min).

Worked Example: Why a Pipeline Feels Faster

A 3-stage line: wash (2 min) → dry (3 min) → fold (1 min). One load takes 6 minutes. You have 4 loads.

min:  0    2    4    6    8   10   12   14   16
      |----|----|----|----|----|----|----|----|
L1    [W ][ D  ][F]
L2         [W ][ D  ][F]
L3              [W ][ D  ][F]              <-- W waits for the dryer
L4                   [W ][ D  ][F]

serial:   4 loads x 6 min           = 24 min
pipeline: 6 + (3 loads x 3 min)     = 15 min      <-- 3 = the SLOWEST stage

The Programming-Models Landscape

Session 02's memory model decides your tool — because it decides how workers communicate.

What OpenMP Actually Is

• Not a new language. Not a big library. Just compiler directives — special comments of the form #pragma omp ... — added to normal C/C++.
• The compiler reads them and generates all the thread code for you: creating, scheduling, cleaning up.
• If the compiler doesn't understand OpenMP, the pragmas are ignored — your code still runs correctly, just serially. A built-in safety net.

Turn it on with one flag

gcc -fopenmp myprogram.c -o myprogram

OMP_NUM_THREADS=4 ./myprogram    # a team of 4
OMP_NUM_THREADS=1 ./myprogram    # serial (team of 1)

The Fork-Join Model

1. Program starts as one thread — the master.
2. At #pragma omp parallel it forks into a team; all threads run the region.
3. At the closing brace they join back into one, and the program continues serially.

FORK-JOIN MODEL

                    #pragma omp parallel
                          |
                          v
                     ____ fork ____
                    /      |       \
   master ●========●   thread 1     \
   (serial)         \   thread 2      >  all run AT ONCE
                     \  thread 3     /   (the parallel region)
                      \____ join ___/
                          |
                          v
                     master ●========●   (serial again)

Worked Example: Fork-Join Is Not Free

Forking a team and joining it back costs roughly 5 microseconds. Sounds like nothing. Let's find out when it isn't.

Same loop, 8 cores, each iteration does 10 ns of work. Only N changes:

for (i = 0; i < 1000000; i++)          // outer
    #pragma omp parallel for          // WRONG: forks a team 1,000,000 times
    for (j = 0; j < 8; j++)            // 8 iterations of nothing
        c[i][j] = a[i][j] + b[i][j];

Today's OpenMP Toolkit

That's the whole toolkit for today. Six things — and you can already write real parallel code.

Your First OpenMP Program

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

int main(void) {
    #pragma omp parallel
    {
        int id = omp_get_thread_num();
        int total = omp_get_num_threads();
        printf("Hello from thread %d of %d\n", id, total);
    }
    return 0;
}

gcc -fopenmp hello.c -o hello
OMP_NUM_THREADS=4 ./hello

The First Lesson: Order Is Not Yours

A likely run prints:

Hello from thread 2 of 4
Hello from thread 0 of 4
Hello from thread 3 of 4
Hello from thread 1 of 4

Worked Example: Who Runs Which Iteration?

12 iterations, a team of 4. What does parallel for actually do?

#pragma omp parallel for
for (int i = 0; i < 12; i++)
    printf("i=%2d  ran on thread %d\n", i, omp_get_thread_num());

i= 6  ran on thread 2
i= 0  ran on thread 0
i= 9  ran on thread 3
i= 3  ran on thread 1
i= 7  ran on thread 2
i= 1  ran on thread 0
i=10  ran on thread 3
   ... and so on

Parallel Sum — the WRONG Way

long sum = 0;
#pragma omp parallel for
for (int i = 0; i < N; i++) {
    sum += a[i];        // RACE: many threads write 'sum' at once
}

Looks fine. It's broken — the answer is too small, and different every run. Why? sum += a[i] is really three steps:

Worked Example: Watch the Race Eat Your Sum

a[] = {10, 20, 30, 40}, two threads. Thread 0 takes 10 and 20; thread 1 takes 30 and 40. The correct answer is 100.

Parallel Sum — the RIGHT Way

long sum = 0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < N; i++) {
    sum += a[i];        // each thread gets a PRIVATE partial sum
}

Heavier alternatives (know they exist)

• #pragma omp critical / atomic — let one thread update at a time. Correct, but they serialize the line and kill your speedup.
• For a sum, reduction is the right tool: correct and parallel.

Worked Example: What reduction Actually Does

a[] = {10, 20, 30, 40, 50, 60, 70, 80}, 4 threads, reduction(+:sum). The true total is 360.

Quick Check: Will This Loop Parallelise?

The one question that decides it: can two different iterations touch the same memory, where at least one is writing?

for (i=0; i<n; i++)
    c[i] = a[i] * b[i];

for (i=1; i<n; i++)
    a[i] = a[i-1] + 1;

for (i=0; i<n; i++)
    if (a[i] > max)
        max = a[i];

for (i=0; i<n; i++)
    total += a[i]*a[i];

for (i=0; i<n; i++)
    printf("%d\n", a[i]);

Example in Code: Shared By Accident

The race you just saw was obvious — sum was clearly shared. Here is the version that catches people out.

double temp;

#pragma omp parallel for
for (i = 0; i < n; i++) {
    temp = a[i] * a[i];
    b[i] = temp + 1;
}

// 1. tell OpenMP explicitly
#pragma omp parallel for private(temp)

// 2. better — declare it inside
#pragma omp parallel for
for (i = 0; i < n; i++) {
    double temp = a[i] * a[i];
    b[i] = temp + 1;
}

Your Turn: Three Bugs, Five Minutes

In pairs. This compiles cleanly, runs without crashing, and is wrong in three separate ways. Find them.

double avg = 0.0, diff;
int    count = 0;

#pragma omp parallel for
for (int i = 1; i < n; i++) {
    diff    = a[i] - a[i-1];
    avg    += diff;
    a[i]    = diff;
    if (diff > 0) count++;
}
avg = avg / (n-1);

Recap, Unit I Wrap-Up & What's Next

Key Takeaways

• Work splits three ways: data, task, pipeline.
• Memory model → tool: shared → OpenMP, distributed → MPI, GPU → CUDA (all three in Unit IV).
• OpenMP = #pragma directives on normal C, compiled with -fopenmp; the fork-join model.
• Parallel output is non-deterministic; a data race is fixed here by reduction(+:sum).