Week 6 · MPI IV · Companion to lecture 06a

Describe the Data,
Don't Copy It

Week 5 moved arrays of one type, end to end. Real data is a record, a column, or every p-th element. Today: how to tell MPI where the bytes are, and what each way of shipping them costs.

Concept map

Three questions today, each a mechanism and a cost. Click a node to jump to it. Dashed nodes are Wednesday and R04.

todaylater

A datatype is a description of where the bytes are. Size is what travels. Extent is where the next one starts. The description stays in your program; only the data moves.

Mark this section done

One record, one message?

Rank 0 reads n, a and b. Every rank needs all three. Week 4's thirdMethod used one MPI_Bcast per value.

What three broadcasts cost

Model, not a measurement: a broadcast tree is log₂ p rounds, each one latency α = 2 µs. The bytes are too few for β to matter. At p = 8: 3 rounds, so three Bcasts cost about 3 × 3 × 2 µs = 18 µs and one costs 6 µs.

Be honest about that number. 12 µs saved is nothing. The latency argument alone does not justify derived types for three scalars. The real reasons: (1) a record with twenty fields, or an array of records; (2) data that is not contiguous at all, where the alternative is a copy.

MPI_Bcast takes one pointer, one count, one type. n is an int; a and b are doubles. Can one count and one type describe the record?

Yes: count 3, type MPI_DOUBLE. An int fits inside a double. Yes: count 20, type MPI_BYTE. Bytes are bytes. No. One count and one type means N copies of the same thing, end to end. A record needs a list: which type, at which byte. No, and MPI cannot send mixed types at all; it has to be three calls.

One message needs one description of the whole record. That description is a type you build: a list of (type, byte offset). Before building it you need to know the offsets, and that is the next screen. (Choice b is not wrong as bytes go, but which 20 bytes? The record is not 20 bytes long.)

Mark this section done

Where does b start?

struct { int n; double a; double b; }. Add up the sizes. Write the byte offset of each field. Commit before you look.

How big is the struct, and where do n, a and b start? Hint: a double wants to live at an address divisible by 8.

20 bytes; n at 0, a at 4, b at 12. 24 bytes; n at 0, a at 8, b at 16. 20 bytes; n at 0, a at 8, b at 16. 24 bytes; n at 0, a at 4, b at 12.

A double is 8-byte aligned on x86-64 and ARM, so the compiler inserts 4 bytes after n. sizeof is 24. Offsets are 0, 8, 16.

What the compiler did

What 4 + 8 + 8 assumes

a at 4 and b at 12: both wrong. Bytes 20 to 23 are left out. With offsets 0, 4, 12 the type map describes bytes 0 to 19 of a 24-byte object. Wednesday's input_GuessedOffsets trusts the sum on purpose; you will see what that does to the data then.

Size vs extent, three layouts

struct

Computed from the alignment rule the deck gives (int at a multiple of 4, double at a multiple of 8, the struct padded to a multiple of its widest field). The same rule on every layout; only the order of the fields changed.

Size: the bytes of data. 4 + 8 + 8 = 20. Extent: the span, padding included. 24. Size is what travels. Extent is where the next one starts. Never add up sizes. Ask the compiler: offsetof(TrapInput, b), or subtract MPI_Get_address results.

Mark this section done

MPI_Type_create_struct

A type is a list of (type, byte). The three highlighted lines are the whole lesson from the last screen.

struct TrapInput { int n; double a; double b; };

int          lens[3]  = {1, 1, 1};
MPI_Aint     displ[3] = {offsetof(TrapInput, n),   // 0
                        offsetof(TrapInput, a),   // 8
                        offsetof(TrapInput, b)};  // 16
MPI_Datatype types[3] = {MPI_INT, MPI_DOUBLE, MPI_DOUBLE};

MPI_Datatype T;
MPI_Type_create_struct(3, lens, displ, types, &T);
MPI_Type_commit(&T);

MPI_Bcast(&in, 1, T, 0, MPI_COMM_WORLD);   // one call

MPI_Type_free(&T);

Four steps

Create: describe the layout.
Commit: MPI compiles it. Not free. Commit once, outside the loop; R04's checklist flags a commit inside a send loop.
Use it, as often as you like.
Free it when you are done.

The type map is { (MPI_INT, 0), (MPI_DOUBLE, 8), (MPI_DOUBLE, 16) }. It stays in your program; only the data travels.

Count 1 of type T sends one record. Now MPI_Bcast(recs, 100, T, 0, comm) on an array of 100 TrapInput. Where does MPI look for record k?

At byte k × 20: the size of one record. At byte k × 24: the extent of one record. At byte k × 16: the offset of the last field. It cannot; a struct type has count 1 by definition.

The type describes one record; count says how many. MPI finds record k at k × extent. That only works if the extent is right, which the padding on the last screen set up. Extent is where the next one starts.

Bytes 16 to 39 of the array: the end of record 0, then record 1 beginning at byte 24 = 1 × extent. A type with offsets 0, 4, 12 would have extent 20 and look for record 1 at byte 20, inside record 0's padding.

Mark this section done

A column, in place

Column 3 of an 8 × 8 matrix stored by rows. Row-major: A[i][j] is element i·8 + j. Week 5 would copy the column into a buffer first.

Count, block length, stride

count blocklen

stride start at element

Orange: elements the type covers. Green outline: the address you pass. Stride is in units of the old type's extent, so in doubles here.

Rank 0 sends &A[0][3], count 1, type col. Rank 1 posts MPI_Recv(buf, 8, MPI_DOUBLE, 0, tag, comm, &st): eight plain, contiguous doubles. What happens?

An error: the receive type must be col too. It works: MPI matches the type signature (eight doubles), not the layout. buf holds the column, contiguous. It works, but buf holds 64 doubles: the type sends the whole matrix. It works, but buf gets elements 0 to 7: the first row, because the send started at A.

Two things. The address. The type describes where the elements are relative to the buffer you pass. Pass &A[0][3], the first element of the column, not A. The receiver. It receives 8 contiguous MPI_DOUBLE. That is legal: MPI matches the sequence of basic types, not the layout. Week 5's note said the sender and receiver may describe the same bytes differently. This is that.

Precision if you want it: for point-to-point the sender's signature may be a prefix of the receiver's (a receive may be longer than the message; MPI_Get_count tells you what arrived). Collectives need an exact match.

Same shape as Week 5's cyclic deal: every p-th element. _Cyclic packed every p-th element into a buffer before every send. Same pattern, stride p instead of 8.

Mark this section done

The five constructors

Almost any layout. You have seen two rows. The last row is the subtle one.

Constructor	Describes	For example
`MPI_Type_contiguous`	count copies, end to end	a 3-D point as one unit
`MPI_Type_vector`	equal blocks, equal spacing	a column; every p-th element
`MPI_Type_indexed`	blocks at listed offsets	a triangle; a sparse row
`MPI_Type_create_struct`	mixed types at byte offsets	a C struct
`MPI_Type_create_resized`	same data, new extent	where the next one starts

The rules

vector, indexed: in units of the old type's extent.
struct (and the h-variants, hvector, hindexed): offsets in bytes.
Types nest: a vector of structs is legal.
Commit before use. Free when done.

Which constructor?

Pick one for each layout. Check when you have all four.

MPI_Type_vector(4, 1, 2, T, &everyOther) where T is the TrapInput struct type (size 20, extent 24). How many bytes apart do the four blocks start?

2 bytes: the stride is 2. 40 bytes: 2 × the size, 20. 48 bytes: 2 × the extent, 24. 16 bytes: 2 × 8, the size of a double.

Units trip people. vector and indexed count strides and offsets in units of the old type's extent: a vector of TrapInput steps 24 bytes, not 20. Only struct and the h-variants use bytes.

Mark this section done

The Scatter trap

One Scatter, every p-th element. x has 24 doubles, p = 3. The type: MPI_Type_vector(8, 1, 3, MPI_DOUBLE). Rank 0's share is x[0], x[3], … x[21].

MPI_Scatter sends one of these to each rank. Rank r's piece starts at sendbuf + r × extent. The extent runs from the first element to the end of the last.

How many bytes is the extent, and so where does rank 1's piece start? Commit an index. Then ask whether it is inside x.

64 B (8 doubles of data): rank 1 starts at x[8]. 8 B (one double): rank 1 starts at x[1]. 176 B (22 doubles): rank 1 starts at x[22]. 192 B (24 doubles): rank 1 starts at x[24], just past the end.

(8 − 1) × 3 + 1 = 22 doubles. 22 × 8 B = 176 B of extent; 64 B of it is data. Rank 1's piece would start at x[22] and read x[22], x[25], x[28] … x[43]. Seven of its eight elements are past the end of the array.

unresized   rank 0: x[0] x[3] x[6] x[9] x[12] x[15] x[18] x[21]
            rank 1: x[22] x[25] x[28] x[31] x[34] x[37] x[40] x[43]   7 of 8 past the end
            rank 2: x[44] x[47] x[50] x[53] x[56] x[59] x[62] x[65]   8 of 8 past the end

Nothing in MPI stops this. It is an out-of-bounds read: garbage if lucky, a crash if not. Wednesday's file prints the extent rather than running it for that reason.

MPI_Type_create_resized

MPI_Type_vector(8, 1, 3, MPI_DOUBLE, &vec);
MPI_Type_create_resized(vec, 0, sizeof(double), &cyc);
MPI_Type_commit(&cyc);

MPI_Scatter(x, 1, cyc, myX, 8, MPI_DOUBLE, 0, comm);

The data description is the same (8 elements, stride 3); only "where the next rank's piece begins" changed. Resize: extent 8 B, so rank r starts at x[r]. That is exactly the cyclic deal from Week 1's card sort.

Explore it

N p 3 resized to sizeof(double)

A vector type has one count. If p does not divide N, the ranks need different counts, and this trick does not do that by itself. Wednesday's file skips p = 5 at N = 24 and says so. Derived types describe layout; they do not fix the remainder.

Mark this section done

Boost.MPI: what vanishes

For five weeks you did it the hard way on purpose. You counted bytes, built counts and displs, committed and freed types. Now the short version, because you can read what it does.

What you wrote	Boost.MPI	What vanished
MPI_Init … MPI_Finalize	bmpi::environment env;	the pair; RAII
MPI_Comm_rank(MPI_COMM_WORLD, &r)	bmpi::communicator world; world.rank() world.size()	the out-parameter
MPI_Send(&x, 1, MPI_DOUBLE, d, t, c)	world.send(d, t, x);	count, datatype
MPI_Recv(&x, 1, MPI_DOUBLE, s, t, c, &st)	world.recv(s, t, x);	count, datatype, status
MPI_Bcast(&in, 1, T, 0, c)	broadcast(world, in, 0);	the type T
MPI_Reduce(&x, &s, 1, MPI_DOUBLE, MPI_SUM, 0, c)	reduce(world, x, s, std::plus<double>(), 0);	count, datatype, MPI_SUM
MPI_Gatherv(.. counts, displs ..)	gather(world, myVec, all, 0);	counts[], displs[]
create_struct + commit + free	serialize(): ar & n & a & b;	the whole type

bmpi is the course alias: namespace bmpi = boost::mpi;. Build: -lboost_mpi -lboost_serialization. On Cardinal: module load boost/1.83.0. The templates pick MPI_DOUBLE for you; get the type wrong and it fails to compile, not at 2 a.m. on Cardinal. You can mix raw MPI and Boost in one program: bmpi::communicator world; just wraps the existing MPI_COMM_WORLD.

Same program, twice

// raw MPI: Weeks 3-6
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);

MPI_Bcast(&in, 1, T, 0, comm);       // T: build, commit, free

double local = trapezoid(in), total;
MPI_Reduce(&local, &total, 1, MPI_DOUBLE, MPI_SUM, 0, comm);

MPI_Finalize();

// Boost.MPI
bmpi::environment  env(argc, argv);
bmpi::communicator world;

bmpi::broadcast(world, in, 0);       // TrapInput::serialize()

double local = trapezoid(in), total;
bmpi::reduce(world, local, total, std::plus<double>(), 0);

TrapInput has a serialize() member and nothing else. Count the MPI calls underneath the Boost half: how many MPI_Bcast and how many MPI_Reduce?

1 Bcast, 1 Reduce: it is the raw program with the names changed. 3 Bcasts (one per field), 1 Reduce. 2 Bcasts (the packed size, then the bytes), 1 Reduce. 2 Bcasts, 2 Reduces: Boost reduces a size first too.

The reduce is identical work: a double with std::plus<double> is MPI_Reduce with MPI_SUM. Zero overhead. The broadcast is not identical. TrapInput has serialize() but no BOOST_IS_MPI_DATATYPE, so Boost packs it into an archive, broadcasts the archive size, then broadcasts the bytes as MPI_BYTE: two MPI_Bcast calls where the struct type needed one, plus a pack on rank 0 and an unpack everywhere else.

PMPI call counter, Boost 1.83 (the OSC module), verified Sep 28
bmpi::broadcast(world, in, 0)   serialize() only          MPI_Bcast   × 2
bmpi::broadcast(world, in, 0)   + BOOST_IS_MPI_DATATYPE   MPI_Bcast   × 1
bmpi::reduce(world, local, total, std::plus<double>(), 0)  MPI_Reduce  × 1   either way
bmpi::gather(world, myVec, all, 0)   4 ranks, lengths 1-4  MPI_Gather × 1 + MPI_Gatherv × 1

Add BOOST_IS_MPI_DATATYPE(TrapInput) after the struct and Boost builds a derived datatype from serialize() and sends one Bcast: it becomes the create_struct screen. And the gather of a std::vector per rank: one MPI_Gather of the sizes, then one MPI_Gatherv of the bytes. That is exactly the Week 5 two-step. Boost wrote your Week 5 code for you.

What a Boost call turns into

the call

double, int, or a BOOST_IS_MPI_DATATYPE struct: the same MPI call. std::vector, std::string, serialize()-only classes: packed. Size, then bytes. Easy for you is not always fast for the machine. The wrapper is a productivity tool, not a performance tool; knowing the raw calls is how you tell which one you are holding.

Why Boost cannot just send one message in general: it cannot know the length. R04's Particle holds std::vector members whose lengths only the sender knows; the doubles live elsewhere on the heap. That is where Boost earns its keep.

Mark this section done

What a copy costs

Week 5's model, one term longer. A copy costs by the byte, too.

t_pack(m) ≈ α + m·β + 2m·γ

Term	Planning number	What it is
α	2 µs	latency, as in Week 5
β	0.05 ns/B	the wire: 20 GB/s, as in Week 5
γ	0.1 ns/B	one memory copy: about 10 GB/s, one core, out of cache. A planning number, not a measurement; in cache it is much faster.

Pack copies every byte into the buffer on the sender and out of it on the receiver: 2m × γ. Serialized Boost (the two-Bcast case) does the same.

Where the time goes, by message size

Model. α + mβ is Week 5's wire cost; the extra 2mγ is the copy in and the copy out. Past about 40 KB the copies cost more than the wire.

Derived: ?

How you send	Pays γ	Total
MPI_Pack, or serialized Boost	twice: once in, once out	α + mβ + 2mγ
a derived type over the same bytes	?	α + mβ + ?·mγ

A derived type: MPI may still copy inside for non-contiguous data. How often is the question. Only a type with no holes can always be sent in place; the struct on screen 4 has a 4-byte hole (size 20, extent 24), and a column is all holes. Whether a derived type pays γ zero times, once or twice, on Cardinal with MVAPICH, is what R04 measures (Fri Oct 16). Its prediction asks for exactly this ratio. This page does not answer it.

Mark this section done

Run it on Cardinal

Today was the concepts. Wednesday walks the code on branch lecture06: five ways to send n, a, b (one wrong on every run, at every p but 1); a column; Week 5's cyclic deal in three calls. Have it built before then. About 10 minutes.

Clone once, check out the lecture branch

ssh <your-username>@cardinal.osc.edu
git clone -o class git@gitlab.com:cs4540-spring-2019/cs-4170-5170-fall-2026/mpi.git mpi
cd mpi
git fetch class
git checkout -b lecture06 class/lecture06

Load the modules, build

Boost joins the module line this week. Modules do not persist between sessions: load them every time, and again inside the allocation.
```
module load mvapich/4.1 boost/1.83.0
cd Default && make OSC && cd ..
```
Get processes of your own

Nothing is timed today, so one node with five slots is enough. The login node is shared; do not run there.
```
salloc --nodes=1 --ntasks-per-node=5 -c 2 --time=00:15:00 -A PCS0313
module load mvapich/4.1 boost/1.83.0
```
Every run: srun -c 2 -n p ./Default/MPI [N]. Default N = 24.

Experiments

A · Ask the compiler, not the sum

srun -c 2 -n 1 ./Default/MPI | head -n 1

What you should see

The first output line prints sizeof(TrapInput) and the three offsets. Compare it with the number you committed on screen 3: 24, and 0 / 8 / 16. If you wrote 20 and 0 / 4 / 12, that is the guess input_GuessedOffsets is built on. Wednesday shows what it does to the data.

B · The column and the cyclic deal, p = 3

srun -c 2 -n 3 ./Default/MPI

What you should see

column_Vector (needs p ≥ 2): rank 1 receives the column as eight plain doubles, 3 13 23 … 73, and rank 0 prints it. cyclic_Extent prints the unresized extent and does not run it: 22 doubles, 176 B at N = 24, p = 3, the index you committed on screen 7. cyclic_Scatter uses the resized type and runs.

C · The remainder, p = 5

srun -c 2 -n 5 ./Default/MPI
exit

What you should see

24 % 5 ≠ 0. cyclic_Scatter skips and says so: a vector type has one count, and the resized trick does not fix the remainder. Then exit to release the allocation.

Before Friday Oct 2 (R03 lab, the full period): repository made, lab03 pulled, the three TODOs read, none written. R03 is Week 5 material (hand-rolled gather vs MPI_Gatherv); its prediction comes first, no machine, with Week 5's α ≈ 2 µs and β ≈ 1/(20 GB/s), crossover about 40 KB. R04 (Oct 16) times derived type against pack: today's model, measured.

Mark this section done

Concept map

One record, one message?

What three broadcasts cost

Where does b start?

Size vs extent, three layouts

MPI_Type_create_struct

Four steps

A column, in place

Count, block length, stride

The five constructors

The rules

Which constructor?

The Scatter trap

MPI_Type_create_resized

Explore it

Boost.MPI: what vanishes

Same program, twice

What a Boost call turns into

What a copy costs

Where the time goes, by message size

Derived: ?

Run it on Cardinal

Clone once, check out the lecture branch

Load the modules, build

Get processes of your own

Experiments

A · Ask the compiler, not the sum

B · The column and the cyclic deal, p = 3

C · The remainder, p = 5

Check yourself