CS 452 Exam 1 — MPI and Parallel Algorithms Vocabulary

62 cards: vocabulary, MPI argument examples, and high-yield exam practice on choosing collectives, tracing ranks, and tree time/work.

Process rank

A process's unique ID within a communicator, numbered 0 through p-1. Use it to choose that process's work.

Process count p

The number of MPI processes in the communicator. MPI_Comm_size stores it in p.

MPI_COMM_WORLD

The communicator containing all processes launched for the program.

Root process

The designated process for a collective operation; often rank 0. It may own the input or receive the answer.

MPI_Init

Starts the MPI environment. Call it before other MPI operations.

MPI_Finalize

Ends the MPI environment after the parallel work is done.

MPI_Comm_rank

Writes this process's rank into the supplied integer variable.

MPI_Comm_size

Writes the number of processes into the supplied integer variable.

MPI_Send

Sends a specified buffer to one destination rank with a tag.

MPI_Recv

Receives a message from a specified source and tag; it waits for a matching message.

Message tag

An integer label used to distinguish messages. A receive must match the intended send's tag.

Blocking receive

An MPI_Recv call that cannot return until its receive buffer contains a matching message.

Deadlock

Processes wait in a cycle or for messages that will never arrive, so the program cannot progress.

Collective operation

An MPI operation involving every process in a communicator. All participating ranks must call it compatibly.

MPI_Bcast

Broadcasts a value from one root process to every process in the communicator.

MPI_Scatter

Distributes equal-sized consecutive chunks of a root array among all processes.

MPI_Gather

Collects equal-sized chunks from all processes into an array on the root.

MPI_Reduce

Combines one value or array from every process using an operation such as sum, max, or min; the result is at the root.

MPI_Allreduce

Like MPI_Reduce, but every process receives the combined result.

MPI_SUM / MPI_MAX / MPI_MIN

Predefined reduction operations for sum, maximum, and minimum. Choose the one that matches the required answer.

Blocking data allocation

Give each process a consecutive chunk of the input, such as indices 0-3 to rank 0 and 4-7 to rank 1.

Striping

Give rank r indices r, r+p, r+2p, and so on. It can balance uneven work but may hurt data locality.

Load balancing

Distributing work so processes finish at roughly the same time instead of leaving some idle.

Data locality

Keeping a process's data near or contiguous to its other data, reducing costly access and transfer.

Distributed memory

Each process has its own memory; processes exchange data explicitly using messages such as MPI sends and receives.

Shared memory

Processes or threads can access a common memory space; coordination is needed to avoid conflicting access.

Parallel overhead

Extra time spent dividing work, communicating, synchronizing, and combining results.

Speedup

Sequential running time divided by parallel running time. Overhead and serial work limit it.

Work W(n)

The total number of operations performed across all processors and rounds in the work-depth model.

Depth T(n)

The number of sequential parallel rounds on the longest dependency path in the work-depth model.

Parallel reduction

Combine values up a balanced tree to get one answer; for n values, depth O(log n) and work O(n).

Prefix computation / scan

Compute one cumulative answer for every prefix; tree up-sweep and down-sweep give depth O(log n) and work O(n).

Associative operation

An operation where grouping does not change the result, such as sum, min, or max. This lets a tree combine subproblems safely.

MPI_Init and MPI_Finalize: what arguments?

Start with MPI_Init(&argc, &argv); end with MPI_Finalize(); Init gets addresses of main's argument count and argument vector. Finalize takes no arguments.

MPI_Comm_rank: fill the arguments

MPI_Comm_rank(MPI_COMM_WORLD, &rank); The communicator comes first; &rank is where MPI writes this process's ID.

MPI_Comm_size: fill the arguments

MPI_Comm_size(MPI_COMM_WORLD, &p); The communicator comes first; &p is where MPI writes the process count.

MPI_Send: fill the arguments

MPI_Send(&x, 1, MPI_INT, dest, tag, MPI_COMM_WORLD); Send x: address, element count, type, destination rank, message tag, communicator.

MPI_Recv: fill the arguments

MPI_Recv(&x, 1, MPI_INT, source, tag, MPI_COMM_WORLD, &status); Receive into x: address, max count, type, source rank, matching tag, communicator, status output.

MPI_Bcast: fill the arguments

MPI_Bcast(&x, 1, MPI_INT, 0, MPI_COMM_WORLD); Every rank calls it with a buffer. Rank 0 supplies x; all ranks receive x. The 0 is the root rank.

MPI_Scatter: fill the arguments

MPI_Scatter(a.data(), n/p, MPI_INT, local.data(), n/p, MPI_INT, 0, MPI_COMM_WORLD); Root sends n/p ints to each rank. Every rank receives n/p ints into local.

MPI_Gather: fill the arguments

MPI_Gather(local.data(), n/p, MPI_INT, result.data(), n/p, MPI_INT, 0, MPI_COMM_WORLD); Each rank sends n/p ints. Root collects all chunks into result of length n.

MPI_Reduce: fill the arguments

MPI_Reduce(&local, &total, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD); Every rank contributes one int; MPI sums them; only root 0 receives total.

MPI_Allreduce: fill the arguments

MPI_Allreduce(&local, &total, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD); Every rank contributes one int and every rank receives total. There is no root argument.

MPI_Allgather: fill the arguments

MPI_Allgather(local.data(), n/p, MPI_INT, result.data(), n/p, MPI_INT, MPI_COMM_WORLD); Every rank sends a chunk; every rank receives all chunks. There is no root.

MPI_Barrier: fill the arguments

MPI_Barrier(MPI_COMM_WORLD); Every rank in the communicator calls it and waits until all have reached the barrier.

What does count mean in MPI_Scatter?

Sendcount and recvcount are elements PER RANK, usually n/p. They are not byte counts and the root sendcount is not the whole array length n.

What does count mean in MPI_Reduce?

Count is how many elements EACH rank contributes. For one local sum, count is 1 even if the original array has n elements.

Scalar buffer versus vector buffer

Use &x for one scalar x; use a.data() for a vector a. MPI needs a memory address, not the scalar's value.

Root argument: what number goes there?

Usually 0 when rank 0 owns the input or should receive the result. Every rank passes the same root value for that collective call.

Datatype argument: what goes there?

Match the C++ element type: int -> MPI_INT; long -> MPI_LONG; double -> MPI_DOUBLE. Send and receive datatypes must match.

Send and receive: what must match?

The send destination must be the receiving rank; receive source must be the sending rank; tags and communicator must match; counts and datatypes must be compatible.

MPI_Scan versus MPI_Exscan arguments

MPI_Scan(&local, &prefix, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD) includes this rank. MPI_Exscan has the same arguments but excludes this rank; rank 0 has no prefix result.

One final sum on rank 0: which MPI call?

MPI_Reduce(&local, &total, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD). Every rank contributes local; only rank 0 receives total.

Same final sum on every rank: which MPI call?

MPI_Allreduce(&local, &total, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD). It has no root argument because every rank gets total.

Root has an array; each rank needs one equal chunk: which call?

MPI_Scatter. For n values and p ranks, each rank receives n/p values when p divides n.

Rank 0 needs all ranks' chunks in order: which call?

MPI_Gather. Each rank sends its local chunk; rank 0 receives the assembled array.

For n=12 and p=4, what are Scatter's counts?

3 elements per rank. Use sendcount=3 and recvcount=3 when each element has the same MPI datatype.

Reduction of 8 values: rounds and total additions?

3 parallel rounds because log2(8)=3; 7 total additions because n-1=7. Time O(log n), work O(n).

Reduction versus prefix scan: what differs?

Reduction gives one final answer. Prefix scan gives an answer for every prefix. A work-efficient balanced-tree scan has O(log n) time and O(n) work.

Nearest 1 strictly to the left: which prefix idea?

At index i store i if A[i]=1, else -1. Use an EXCLUSIVE prefix maximum; the largest earlier 1-index is the nearest 1 on the left.

Rank 2 sends one int x to rank 0 with tag 7: calls?

On rank 2: MPI_Send(&x, 1, MPI_INT, 0, 7, MPI_COMM_WORLD). On rank 0: MPI_Recv(&x, 1, MPI_INT, 2, 7, MPI_COMM_WORLD, &status).

Handwritten MPI program: what order should you draft?

MPI_Init; Comm_rank and Comm_size; root sets input; distribute data; each rank computes local work; combine results; MPI_Finalize. Check every collective is called by all ranks.