Exam 1 Study Guide

C, Performance, and MPI · Thursday, October 8

What the exam covers

Exam 1 is on paper Thursday, October 8. It begins with multiple-choice questions and continues with short answers, tracing, bug matching, and placing pieces of MPI code in order. A one-page MPI function reference will be supplied. Focus on what each operation does, which ranks participate, and where the data goes. This guide is a close map of the assessed material, but its practice numbers and examples are different from the exam’s.

Review Modules 1–7, especially the work we did together with compilation and performance, array distributions, collectives, and darts. You can use the exercises below as your main checklist.

C compilation, timing, and locality

  • Know the difference between source code and an executable. Without -o, GCC normally calls the executable a.out; use ./program to run a file in the current directory.
  • Be able to write a compile command such as gcc -Wall -O2 -o work_fast work.c. -Wall enables useful warnings; -o names the executable; -O2 asks for compiler optimization. It does not create parallel processes or guarantee a particular speedup. -O0 asks for no optimization.
  • For a fair timing comparison, use the same work and input, time the same region, check that the answers agree, and repeat the runs. Put timer readings immediately before and after the computation if that is the part you want to compare; leave setup and printing outside. A single fast run does not settle the question.
  • In C, elements across a row of a two-dimensional array are adjacent in memory. An inner loop that advances across a row generally has better spatial locality than one that jumps down columns. A timing result does not tell you the exact number of cache misses.

Shell time reports three different quantities. real is elapsed time: how long you waited. user + sys is CPU time: CPU work in the program plus the kernel. For example, real = 3.0 s, user = 2.1 s, and sys = 0.2 s means 3.0 seconds elapsed and 2.3 seconds of CPU time. They need not be equal; a program may wait for input/output or for CPU access. Do not add real to the CPU times.

MPI processes and operations

mpicc compiles and links an MPI C program; mpirun -n 4 ./program launches four processes, not necessarily four boards. A rank identifies one process in a communicator. Each rank has its own ordinary variables: changing rank 0’s variable does not change rank 1’s copy without communication. MPI_Comm_rank and MPI_Comm_size give a process its rank and the process count.

Operation What to remember
MPI_Send / MPI_Recv A message needs compatible source, destination, tag, datatype, count, and communicator.
MPI_Bcast Every rank participates; root shares a value with all ranks. A count of zero shares nothing.
MPI_Reduce Every rank contributes; only the root gets the combined result. Use MPI_SUM for a total or MPI_MAX for a largest value.
MPI_Scatter Gives each rank a consecutive block of root’s input. The send and receive counts describe one rank’s block, not the whole array.
MPI_Gather Places the ranks’ blocks at root in rank order, regardless of who finished first.
MPI_Sendrecv Pairs a send and receive for a neighbor exchange; messages still must match. It does not guarantee simultaneous transfers.
MPI_Barrier Every rank reaches the barrier before any rank returns from it; it does not copy data or make execution simultaneous.
MPI_Wtime Subtract two readings from the same rank to measure an elapsed interval.

All ranks in a communicator must participate in compatible collective calls such as broadcast, scatter, gather, and reduction. Do not put a collective inside a root-only if when the other ranks also need to call it. For a broadcast of one integer, every rank should use count 1; a count that changes with rank is a bug. A count gives the number of elements, not bytes. Match int with MPI_INT and double with MPI_DOUBLE.

Divide work and combine answers

With values 1 through 8 on four ranks, a block distribution gives [1,2], [3,4], [5,6], [7,8]. A cyclic distribution gives [1,5], [2,6], [3,7], [4,8]. For generated work, a rank can loop over rank, rank + size, rank + 2*size, ... using zero-based indices. Ordinary equal-block MPI_Scatter does not create the cyclic assignment unless root first rearranges its input; the packing code in Module 7 is not something you need to write on the exam.

To compute a dot product when rank 0 owns two arrays: check that the process count divides the array size, scatter a matching block of each array, multiply and add paired local values, reduce the partial sums with MPI_SUM, and print the answer on root. A gather of all individual products is unnecessary. Be ready to put these steps in a workable order, using the supplied MPI reference sheet for call signatures.

Darts, parallel timing, and speedup

In the dart example, each rank counts its hits, then a sum reduction gives the total. The estimate is

\[ \pi \approx 4\,\frac{\text{total hits}}{\text{total tosses}}. \]

More ranks with the same total number of tosses do not guarantee a more accurate estimate.

For a parallel region, time the same work on each rank with differences of that rank’s MPI_Wtime readings. The slowest rank’s elapsed duration describes when the parallel region can be finished; use MPI_MAX to combine the durations. Do not add the durations together.

Speedup compares times for the same work:

\[ \text{speedup} = \frac{\text{one-process elapsed time}}{\text{parallel elapsed time}}. \]

For example, if a one-process MPI run takes 1.14 s and the slowest rank in a four-process run takes 0.57 s, the measured speedup is \(1.14/0.57=2\). That means roughly twice as fast for the region measured, not a speedup of four just because four processes ran. Repeat timings because measurements vary. The exam will supply the two times; you need to select the parallel time and divide.

Practice on paper

Try these before opening the answers. You do not need to write a complete MPI program.

  1. Compile sample.c with warnings and -O2, naming the executable sample_fast. What filename would GCC use without -o?
  2. Shell time reports real = 4.0, user = 2.8, and sys = 0.2 seconds. What are elapsed and CPU time? Give one short reason they differ.
  3. For values [2,4,6,8,10,12] and three ranks, list the block and cyclic assignments. Under the block distribution, list the local sums, the sum reduction result, and the array root gets if each rank adds 1 to every value and gathers its output.
  4. Rank 0 sets n = 60 and then every rank calls MPI_Bcast(&n, 0, MPI_INT, 0, MPI_COMM_WORLD). What is wrong? What one change repairs it?
  5. Rank 1 sends to rank 0 using tag 4, but rank 0 receives from rank 1 using tag 5. Identify the mistake and a repair. What if rank 1 instead sends to rank 2 while rank 0 still waits for it?
  6. Put these dot-product steps in a valid order: sum-reduce partial results; print at root; check divisibility; compute each local dot product; scatter x; scatter y. May the two scatters exchange places?
  7. Four ranks toss 400 darts total and count 74, 80, 77, and 83 hits. Find the total hits and pi estimate. Must more ranks with the same 400 tosses improve accuracy?
  8. Four ranks measure 0.48, 0.52, 0.57, and 0.51 seconds. Which MPI reduction operation reports the parallel time? If the one-process time was 1.14 seconds, what speedup was observed?
  9. Which loop has better expected locality for a C matrix: visiting adjacent columns of a row, or jumping down a column? Does a timing result by itself reveal an exact cache-miss count?
  1. gcc -Wall -O2 -o sample_fast sample.c; without -o, the executable is a.out.
  2. Elapsed: 4.0 s. CPU: 3.0 s (2.8 + 0.2). The program may have waited for I/O or CPU access.
  3. Blocks: [2,4], [6,8], [10,12]. Cyclic: [2,8], [4,10], [6,12]. Block local sums: 6, 14, 22; root receives 42 from the reduction. Gathered output: [3,5,7,9,11,13] in rank order.
  4. Count zero transfers nothing. Use count 1, and keep all ranks in the broadcast.
  5. Tags 4 and 5 do not match; make them equal. In the second case the destination is wrong; send to rank 0.
  6. Check divisibility; scatter x and y in either order (all ranks use the same order); compute local products and sums; sum-reduce; print at root.
  7. Total hits: 314; estimate: \(4(314)/400=3.14\). No guarantee of better accuracy from more ranks at the same total toss count.
  8. MPI_MAX gives 0.57 s. Speedup: \(1.14/0.57=2\).
  9. Adjacent columns across a row ordinarily have better locality. Timing alone does not count cache misses.

Outside the exam

You do not need clock_gettime/CLOCK_MONOTONIC, nanosecond arithmetic, the -g flag, input-parsing details, MPI_Allreduce, MPI_Allgather, derived datatypes, or parallel sorting. The cyclic array-packing code in Module 7 is an illustration, not a new programming task for this exam. Pthreads and OpenMP come later.

Back to top