Exam 1 Study Guide

C, Performance, and MPI · Thursday, October 8

What to prepare

The first exam is on paper on Thursday, October 8. Be ready to explain an MPI program, trace small examples, find communication mistakes, and write or complete short pieces of C/MPI code. A one-page MPI function reference will be supplied with the exam, so focus on understanding what each operation does rather than memorizing argument order. This study guide describes what you should understand, not the exact exam questions.

Review Modules 1–6 and your work on Projects 1 and 2. Compilation, timing, optimization, and locality are part of the exam, along with MPI. Advanced Linux administration and long C library routines are not the focus.

In the second-edition book, concentrate on §3.1 (starting MPI and messages), §3.2 (dividing work), §§3.4.1–3.4.8 (collectives and array distributions), the MPI_Sendrecv discussion in §3.7, and programming assignment 3.2 (the darts model). We have used selected examples from the chapter; this is not an exam on every topic in Chapter 3.

Compile and measure serial C

Review Module 1 as well as the MPI examples. Be able to:

  • Explain source code versus an executable, GCC’s default a.out, and why we type ./program.
  • Use and explain -Wall, -o, -O0, and -O2. -Wall does not enable every warning; -O2 requests optimization, not automatic parallel execution. Exact transformations depend on compiler, target, and source.
  • Interpret shell time: real is elapsed time, user is user-space CPU time, and sys is kernel CPU time. Consumed CPU time is user + sys. real is a separate measurement; it is not generally equal to user + sys. Do not add all three together.
  • Explain why we time the calculation separately from setup, validation, and printing, and why we check correctness before comparing performance.
  • Design a fair repeated comparison: same work, same timed boundaries, comparable machine conditions, multiple trials, and the same summary statistic for both configurations.
  • Explain C’s row-major array storage and why adjacent accesses across a row often reuse cache lines better than jumping down a column. A time difference is evidence about runtime, not a direct measurement of cache misses.
NoteElapsed time and CPU time

Suppose a serial command reports:

real    3.0 seconds
user    2.1 seconds
sys     0.2 seconds

You waited 3.0 seconds. The command used 2.3 seconds of CPU time (2.1 + 0.2). During the remaining elapsed time, it might have waited for input/output or for its turn on a busy CPU. For a CPU-bound serial program these numbers can be close, but they measure different things. When CPU time is accumulated across multiple threads or processes, it can exceed elapsed time. For our performance comparisons, focus on elapsed time for the same work.

Explain the execution model

You should be able to explain these without running a program:

  • MPI is a message-passing interface used from languages such as C, not a separate programming language.
  • Rank is a process’s identifier within a communicator. With MPI_COMM_WORLD, our examples use ranks 0 through size - 1.
  • A process is not a node. Several MPI processes can run on one board; -n 4 alone does not prove four boards were used.
  • Ordinary local arrays and variables belong to each process. Changing rank 0’s copy does not change another rank’s copy.
  • MPI_Init starts MPI use; MPI_Finalize finishes it. Keep both in a correct program.
  • MPI_Comm_rank and MPI_Comm_size tell a process its rank and the communicator’s process count.

Build, launch, and read arguments

Explain each part of:

mpicc -g -Wall -O2 -o count count.c
mpirun -n 4 ./count 120

mpicc is a compiler wrapper that supplies the MPI compilation/linking settings. -g supplies debugging information, -Wall enables useful warnings, -O2 requests compiler optimization, and -o count names the executable. Optimization does not create MPI processes.

The 4 is for the launcher; 120 is input to the C program. In main(int argc, char *argv[]), the executable name is argv[0], the first program argument is argv[1], and it is a string until converted. Our examples let rank 0 interpret the input and broadcast the result. You do not need to reproduce the longer strtoll validation block from Module 6 from memory.

On PicoCluster, our mpirun alias supplies /etc/mpi_hosts. That controls available hosts; actual placement also depends on the launcher configuration. The fallback using -hosts pc0 runs multiple processes on one board.

Match communication to its purpose

Call What it does in our examples
MPI_Send / MPI_Recv Move a message between particular processes; match communicator, source/destination, tag, and compatible data descriptions.
MPI_Bcast Copy root’s data to everyone, including root’s participation.
MPI_Reduce Combine contributions into one result at root; use MPI_SUM for totals or MPI_MAX for the largest value.
MPI_Scatter Send a consecutive block from root’s input to each rank.
MPI_Gather Put each rank’s block into root’s output in rank order.
MPI_Sendrecv Pair a send with a receive so a neighbor exchange does not require hand-arranging send-first/receive-first ranks.
MPI_Barrier Wait until all ranks in the communicator have entered that barrier.
MPI_Wtime Read a local elapsed-time clock, in seconds.

For collectives, every rank in the communicator must participate in a compatible sequence of calls, even if only rank 0 has meaningful full input or final output. Root is a role in that operation, not a process that can call the collective alone. A collective is not automatically a barrier.

Match C data and MPI datatypes: int with MPI_INT, double with MPI_DOUBLE, and long long with MPI_LONG_LONG_INT. A count describes elements, not bytes. For equal-block scatter/gather, the count describes one rank’s block, not the full array length.

Divide and trace the work

For twelve values and three ranks, a block distribution gives four neighboring values per rank. A cyclic loop such as for (i = rank; i < n; i += size) gives ranks alternating indices. Be able to list both distributions on paper.

Distinguish a local index from a global index. For equal blocks, global_i = rank * local_n + i. Each rank has a local element 0, but these are different global elements.

If work is generated from indices, distribute a remainder with n / size plus one extra item for the first n % size ranks. Do not silently drop leftover work. Our fixed scatter examples check divisibility instead; unequal-block scatter/gather is not required on this exam.

Spot communication mistakes

Practice finding these problems and explaining a repair:

  • A send uses one tag while its intended receive expects another.
  • A message goes to the wrong rank, or a receive expects the wrong source.
  • Only root calls a collective, or ranks call different collectives in conflicting order.
  • A broadcast count is zero, so no elements are shared.
  • A scatter count is the entire input length rather than one block’s length.
  • A rank assumes another rank’s local variable changed without communication.
  • Every rank starts with a blocking receive and no one has sent a message.

MPI_Sendrecv still needs matching messages. It does not promise simultaneous events, and it does not fix the separate intermittent PicoCluster finalization problem.

Neighbor values and timing

In a line of blocks, a rank needs copied edge values from its neighbors to update its block boundaries. MPI_PROC_NULL handles a missing neighbor without wrapping the two ends together. Read the old array and write the new array separately so updates do not depend on loop order. Exchange fresh edge values before each step.

For timing, subtract two readings on the same rank. Do not subtract a start on one node from a finish on another. For the measured parallel region, report the maximum of the per-rank elapsed durations rather than their sum. A barrier before the timer reduces start-point skew but does not make clocks identical. State what the timed region includes, repeat measurements, and do not assume more processes must be faster.

Darts, accuracy, and parallel work

Know why the dart model uses \(4\times\text{hits}/\text{tosses}\) and why x*x + y*y <= 1.0 tests the circle. Each rank generates its own samples, then contributes one hit count to a sum reduction. Different seeds avoid simply repeating one identical sequence on every rank, but do not prove statistical independence.

The prime project has an exact answer that should agree across process counts. Monte Carlo estimates may differ because the samples differ. More total samples generally improve statistical accuracy; adding processes at the same total sample count does not automatically improve it. With our fixed seeds, repeated identical configurations test timing variation rather than new random samples.

Practice on paper

Try these before opening the answers:

  1. With three ranks, scatter [2, 4, 6, 8, 10, 12] in equal blocks. List each rank’s input. Each rank adds 1 to each element: what does a gather print? What does a sum reduction of the three local input sums produce?
  2. Rank 0 sets n = 60, while the other ranks have n = 0. After MPI_Bcast(&n, 0, MPI_INT, 0, MPI_COMM_WORLD), what does each rank have? Repair the call.
  3. Write the MPI steps to compute a dot product from two arrays initially on rank 0. What do you scatter, compute locally, and reduce? Is a gather needed for one final dot product?
  4. Distribute eleven tosses among four ranks without dropping any. If the four local hit counts are 2, 2, 1, and 2, calculate the pi estimate.
  5. A ring rank sends right and receives left using MPI_Sendrecv. With five ranks, which rank sends to rank 0? Why is this different from the fixed endpoints of the heat example?
  6. Per-rank durations are 0.41, 0.55, 0.48, and 0.46 seconds. Which statistic describes the slowest rank’s duration? If the one-process time was 1.10 seconds, what is the observed speedup relative to that one-process MPI run?
  7. Compile sample.c with warnings and -O2, naming the executable sample_fast. What does GCC name it if you omit -o?
  8. A serial command reports real = 3.0, user = 2.1, and sys = 0.2 seconds. What is its elapsed time and its consumed CPU time?
  9. Explain why the inner loop over columns of a C matrix usually has better spatial locality than the inner loop over rows. Does that guarantee a fixed speedup?
  10. One rank records start = 12.9 and finish = 13.1 using MPI_Wtime. What is its elapsed time? Why should it subtract its own readings rather than a start time from another rank?
  1. Rank 0 gets [2,4], rank 1 [6,8], rank 2 [10,12]. Gathered outputs: [3,5,7,9,11,13]. Local input sums are 6, 14, 22; their sum reduction is 42.
  2. Rank 0 stays at 60; the other ranks stay at 0 because the count is zero. Use count 1, with every rank calling it.
  3. Scatter a block of each input, compute the sum of matching local products, and sum-reduce those partial dot products to root. No gather is needed for one final scalar.
  4. Toss counts: 3, 3, 3, 2. Total hits: 7. Estimate: \(28/11\approx2.54545\).
  5. Rank 4 sends to rank 0. A ring wraps; a line has missing neighbors at the two ends.
  6. Maximum: 0.55 seconds. Speedup: \(1.10/0.55=2\). This is relative to the measured one-process MPI version, not necessarily a tuned serial program.
  7. gcc -Wall -O2 -o sample_fast sample.c; default executable name a.out.
  8. Elapsed: 3.0 seconds. CPU: \(2.1+0.2=2.3\) seconds.
  9. With a fixed row index, advancing the column visits adjacent elements. Advancing the row instead jumps a row at a time. Cache reuse can help, but machine and compiler effects prevent a universal time ratio.
  10. \(13.1-12.9=0.2\) seconds. Each rank should subtract its own clock readings; clocks on different nodes need not be synchronized.

What is outside this exam’s scope?

The serial clock_gettime/CLOCK_MONOTONIC API, struct timespec, and nanosecond conversion details are not assessed. Know timing concepts and how to use differences of MPI_Wtime readings. The -g flag is also not assessed.

Nonblocking communication (MPI_Isend/MPI_Irecv), derived datatypes, MPI communicators beyond our use of MPI_COMM_WORLD, parallel sorting, MPI_Scatterv/MPI_Gatherv, and advanced random-number theory are not required. MPI_Allgather and MPI_Allreduce were optional reading; the assessed collective operations are the ones in the table above. Pthreads and OpenMP come later.

Back to top