Exam 2 Study Guide – Beau Christ

What the exam covers

Exam 2 is on paper Thursday, November 19. Expect a format like Exam 1’s: multiple-choice questions, then short answers, tracing, and finding the problems in short pieces of code. A one-page Pthreads and OpenMP reference will be supplied, so you do not need to memorize argument lists. Focus on what each construct does, which threads take part, and which data is shared. This guide is a close map of the assessed material, but its practice examples are different from the exam’s.

Review Modules 8–15, along with Projects 3 and 4. You can use the sections below as your main checklist.

Threads and shared memory

An MPI program runs several processes, each with its own memory. A threaded program runs several threads inside one process, on one node. Threads can read and write the same global variables and arrays. Each thread has its own function calls and local variables.
Compile Pthreads programs with -pthread and OpenMP programs with -fopenmp. Run either one directly, as ./program. There is no mpirun.
Output from several threads can appear in any order. Do not assume threads run in the order they were created.

Pthreads

Function	What to remember
`pthread_create`	Starts a thread in a function of the form `void f(void argument)`, passing it one pointer.
`pthread_join`	Waits for that thread to finish. Join before reading a worker’s results.
`pthread_mutex_lock` / `unlock`	Only one thread at a time holds the mutex. Every thread that updates the shared data must use the same mutex.
`pthread_cond_wait`	Called while holding the mutex. It releases the mutex while waiting and reacquires it before returning.
`pthread_cond_signal` / `broadcast`	Wakes one waiter, or all current waiters. It does not copy data.
`pthread_barrier_wait`	No participant continues until all of them have arrived. The count given to `pthread_barrier_init` is the number of threads that will call it.

Pass each thread a stable ID, using an array such as ids[t]. Passing &t, the address of the changing loop variable, is a bug.
A race condition happens when threads update shared data without coordination and the result depends on timing. total++ is a read, an add, and a write, so two threads can read the same old value, and one update is lost. Joining afterward does not fix that.
A critical section is code that only one thread at a time should run. Keep it short. Do most of the work in local variables, then merge once under the lock, as in Project 3.
Wait for a condition in a while loop: while (!ready) pthread_cond_wait(&cond, &lock);. When a thread wakes up, the condition might not hold, so it must check again. The shared variable, not the signal, remembers that something is ready.
In the bounded buffer, the producer waits while the buffer is full, and the consumer waits while it is empty. Both use the same mutex.
Use a barrier when every thread must finish one phase before any thread starts the next. Without the barrier, a fast thread can read data that another thread is still writing.

OpenMP basics

# pragma omp parallel runs the next block on a team of threads. The thread that reaches the directive becomes thread 0 of the team. num_threads(t) requests a team size. At the end of the block there is an implicit barrier, and then only the original thread continues.
omp_get_thread_num() gives a thread’s number, and omp_get_num_threads() gives the team size. omp_get_wtime() returns elapsed time in seconds, like MPI_Wtime().
A variable declared before a parallel block is shared. A variable declared inside it is private. The loop variable of a parallel for is private automatically.
private(x) gives each thread its own uninitialized copy of x. The value from before the block is not copied in or back out.
default(none) makes the compiler require a scope for every outside variable the block uses.
reduction(+: sum) gives each thread a private copy starting at 0, then combines the copies and the original value at the end. Other operators include *, max, and min.

Parallel loops and dependences

# pragma omp parallel for starts a team and divides the loop’s iterations among it. The loop must be in canonical form, so OpenMP can count the iterations before the loop starts. A loop that can break or return early cannot use it.
A loop-carried dependence means one iteration uses a value that a different iteration writes, as in fibo[i] = fibo[i-1] + fibo[i-2]. The compiler does not check for these. A dependence inside a single iteration is fine.
To check a loop, look at each variable the body writes. Is it read or written in a different iteration? If it is a total, a reduction may fix it. If it is a temporary, making it private may fix it.
In the π series, factor = -factor was a loop-carried dependence. Computing the sign from k removed it, and the shared factor also had to become private.

Reusing threads and scheduling loops

# pragma omp for divides a loop among an existing team. It starts no threads. Inside a parallel block, every thread runs the code outside the for, such as the outer phase loop of odd-even sort.
parallel for and for both end with an implicit barrier. nowait removes it. That is safe only if nothing after the loop depends on other threads’ iterations. In odd-even sort, nowait lets phases overlap and breaks the sort.
schedule(static, c) deals out chunks of c iterations in turn before the loop starts. Without c, each thread gets about one equal block.
schedule(dynamic, c) hands out chunks while the loop runs, to whichever thread asks next. The default chunk size is 1. guided is similar, but the chunks shrink.
schedule(runtime) reads the schedule from OMP_SCHEDULE, as in OMP_SCHEDULE="static,1" ./program 4.
Equal numbers of iterations are not equal work when iterations cost different amounts. The load imbalance is the largest thread’s work divided by the average. With \(t\) threads and imbalance \(I\), the best possible speedup is about \(t/I\).
Dynamic schedules cost more to run. Use them when iteration costs are uneven or unpredictable, not when every iteration is cheap and equal.

OpenMP synchronization

Tool	Use it when
`reduction`	Each thread can work privately and combine once at the end. This is usually fastest.
`# pragma omp atomic`	You need to protect a single update of one variable, such as `x++` or `x += expression`, where the expression does not use `x`. Only the update of `x` is protected.
`# pragma omp critical`	You need to protect a block of code. All unnamed critical sections share one lock. Use `critical(name)` to keep unrelated sections apart.
`omp_lock_t` locks	You need to protect pieces of data chosen while the program runs, such as one bucket per lock.
`# pragma omp barrier`	Every thread in the team must arrive before any continues. Every thread must reach the same barriers.

The OpenMP lock functions correspond to Pthreads mutex functions: omp_init_lock, omp_set_lock, omp_unset_lock, and omp_destroy_lock.
Deadlock: a thread waits forever for a lock that it, or another waiting thread, holds. Two common causes are entering an unnamed critical section from inside another one, and two threads taking the same two locks in opposite orders.
A correct-looking answer does not prove a program is correct. A race can give the right answer on some runs, or at some optimization levels.

Measuring performance

Speedup is the 1-thread time divided by the parallel time, for the same work, as in Exam 1.
Time optimized code (-O2), and repeat runs. Keep the input, the timed region, and the node the same, and check that the answers agree.
Other programs on the same node can slow yours down. uptime shows how busy a node is.

Practice on paper

Try these before opening the answers.

Write commands to compile sum.c as a Pthreads program and as an OpenMP program, with warnings and -O2. How do you run each with four threads?
Two threads each run total++ once, starting from total = 5. Give one order of reads and writes that ends with total = 6. What is the correct result, and what one change to the threads’ code makes it reliable?

Find two problems in this program. It compiles. Then fix them.

int tid;
double total = 0.0;
#   pragma omp parallel num_threads(4)
{
    tid = omp_get_thread_num();
#   pragma omp for
    for (int i = 0; i < 1000; i++) {
        total = total + i;
    }
    printf("Thread %d is done\n", tid);
}
printf("Total: %f\n", total);

A consumer waits with if (!ready) pthread_cond_wait(&cond, &lock);. Why should the if be a while? Why must the consumer hold lock before it calls wait?
A barrier is initialized for 4 participants, but only 3 workers ever call pthread_barrier_wait. What happens?

Give the scope of n, x, sum, i, and y, and the final value of sum:

int n = 100;
double x = 2.0, sum = 0.0;
#   pragma omp parallel for num_threads(4) reduction(+: sum)
for (int i = 0; i < n; i++) {
    double y = x * i;
    sum += y;
}

Can # pragma omp parallel for be placed safely on each loop, as written? If not, can a clause fix it?
1. for (i = 0; i < n; i++) a[i] = a[i] + b[i];
2. for (i = 1; i < n; i++) a[i] = 2 * a[i - 1];
3. for (i = 0; i < n; i++) if (a[i] > big) big = a[i];
4. for (i = 0; i < n; i++) { if (a[i] == key) break; }
A loop has 10 iterations, numbered 0 through 9, and two threads. List each thread’s iterations under schedule(static) and under schedule(static, 3). Under schedule(dynamic), can you predict the assignment?
With a block schedule, four threads do 10, 30, 30, and 10 units of work. Find the load imbalance and the best possible speedup. Name one schedule that might do better.
Which updates can use # pragma omp atomic? (a) hits++; (b) x = x * x; (c) total += f(i);, where f does not use total. In (c), is the call to f protected?
Thread A sets lock 1 and then lock 2. Thread B sets lock 2 and then lock 1. What can go wrong, and how do you prevent it?
In odd-even sort with one team and two for directives, why must the for loops keep their implicit barriers? How many times does each thread run the outer phase loop?
A program takes 12.0 s with 1 thread and 4.0 s with 4 threads. What is the speedup? Name two things to check before trusting the comparison.

Check your practice answers

gcc -Wall -O2 -pthread -o sum sum.c and gcc -Wall -O2 -fopenmp -o sum sum.c. Run each directly as ./sum. The thread count comes from the program or its arguments, such as ./sum 4, not from mpirun.
Both threads read 5, both add 1, and both write 6. The correct result is 7. Protect the increment with one shared mutex, so each read, add, and write happens as a unit.
tid is shared, so threads overwrite each other’s number. Declare it inside the block, or add private(tid). total = total + i is an unprotected update of a shared variable. Add reduction(+: total) to the for directive. (critical or atomic would also be correct, but slower.)
When the consumer wakes, ready might still be false, so it must check again before going on. Wait must be called while holding the mutex, because it releases that mutex while waiting and reacquires it before returning. That lets the producer change ready safely.
The three workers wait forever. The barrier never gets its fourth arrival.
n and x are shared, sum is a reduction variable, and i and y are private. sum \(= 2(0 + 1 + \cdots + 99) = 2(4950) = 9900\).
1. Safe. (b) Not safe: loop-carried dependence through a[i - 1], and no clause fixes it. (c) Not safe as written: big is shared, but reduction(max: big) fixes it. (d) Not allowed: the break means OpenMP cannot count the iterations ahead of time.
static: thread 0 gets 0–4, and thread 1 gets 5–9. static, 3: thread 0 gets 0, 1, 2, 6, 7, 8, and thread 1 gets 3, 4, 5, 9. dynamic: no. It depends on which thread asks first, and it can change between runs.
The average is \(80/4 = 20\), so \(I = 30/20 = 1.5\), and the best speedup is \(4/1.5 \approx 2.67\). static, 1 or dynamic with a small chunk might balance better.
1. Yes. (b) No: the expression uses x, and it is not one of the allowed forms. (c) Yes. Only the update of total is protected. f(i) is computed outside the protection, which is fine, since it does not use total.
Deadlock: A holds lock 1 and waits for lock 2, while B holds lock 2 and waits for lock 1. Take the locks in the same order in every thread.
A later phase compares elements that the previous phase may have swapped, so all threads must finish one phase before any start the next. Every thread runs all n passes of the outer loop. Only the inner loops’ iterations are divided.
A speedup of \(12.0/4.0 = 3.0\). Check that both runs did the same work and produced the same answer, that both were compiled with -O2, and that the runs were repeated on the same, otherwise idle node.

Outside the exam

You do not need the book’s message-passing program with its queues, OpenMP tasks, caches and false sharing (our class on Tuesday, November 17), OMP_WAIT_POLICY, exact guided chunk sizes, or Pthreads read-write locks and semaphores. MPI is not the focus of this exam, though comparisons between processes and threads are fair game.