Memory bought with messages

Every trade this site’s cost field has measured so far spends one countable thing to buy another.

Blocking spends nothing: the blocked and unblocked eliminations perform 72,568 operations each, return a bit-identical factorisation, and move 19,476 words against 41,332. The reduction tree spends arithmetic — 22% more flops — to buy synchronisations, a factor of n of them.

This one spends memory, and the exchange rate is supposed to be a square root.

The construction #

A matrix multiplication C = AB on p processors. The two-dimensional layout puts them on a √p × √p grid: each holds one block of A, one of B and one of C, and the algorithm sweeps. At step k every processor in block-column k broadcasts its A block along its row and every processor in block-row k broadcasts its B block down its column, and each accumulates one block product.

The 2.5D layout uses the same p processors as c layers of a √(p/c) × √(p/c) grid. Each layer takes a distinct 1/c of the summation index, runs the same sweep over its own share, and the layers are added at the end. The grid is smaller by √c, so there are fewer steps and the blocks are larger, and the standard analysis says the words moved fall like 1/√c.

Three phases, then, and the counting has to include all three: replicating A and B to the other layers, the sweep inside each layer, and the reduction that adds the layers.

Counted rather than modelled #

Every broadcast and every reduction here goes through the same Network the communication field already uses, and the algorithm actually multiplies the matrices — so the product is available to be checked against a direct one, and it is, at every layer count and every machine size, to 4·10⁻¹⁶.

That check is not a formality. A communication model that does not compute the answer can count whatever it likes, and the way these analyses are usually presented — a table of asymptotic volumes — has no way to be wrong about an algorithm nobody ran.

What four layers are worth #

A 96×96 multiplication, whole-machine word counts.

At 64 processors replication costs 14% more traffic than not replicating. The crossing is between 64 and 144. At 576 the saving is 1.44, which is 72% of the √4 = 2 the law promises — and the trend is still rising, so the law is the limit of this column and not a value in it.

Why the law is optimistic, in one line each #

The three phases scale differently, and only one of them is what the law counts.

The sweep moves about 2n²√(p/c) words: the grid has √(p/c) steps, each broadcasting to √(p/c) − 1 destinations, each block being n²c/p words. That falls like 1/√c — and by slightly more than the law says, because the number of steps falls like c while the block size grows like √c.

The replication moves 2n²(c − 1) words, and that does not depend on p at all. It is filling c − 1 extra copies of two matrices, and the machine’s size does not enter.

The reduction moves about n²c words, and neither does that.

So the saving is 2n²√p(1 − 1/√c) and the cost is about n²(3c − 2), and the first grows with the machine while the second does not. Below a crossing the fixed costs win. The crossing is at about a hundred processors on this problem, and it moves with n only through the ratio n²/n² — which is to say it does not move with n at all. The last section is about what happened when the figure tried to put a slider on that.

The rounds, which move the other way #

The word count is one of the two currencies this field insists on, and the other one does not favour the layered layout either.

At 256 processors the flat sweep takes 16 rounds — one per step of a 16×16 grid — and the layered one takes 17: eight sweep steps, one replication round, and eight rounds of the final reduction over 256 processors. The layered algorithm has fewer sweep steps and more rounds in total, because the two collective phases it adds are themselves logarithmic in the machine.

That is a small number and it is the wrong direction, and it is worth printing because the whole argument for these layouts is usually made in one currency. A machine whose cost is dominated by latency rather than bandwidth reads this table and finds nothing to buy; a machine dominated by bandwidth reads the previous table and finds 1.44× at 576 processors for four times the memory.

Neither reading is the correct one, which is the position the message and the word already established for three factorisations and is being confirmed here for two layouts of one multiplication.

And the memory is not asymptotic #

The other side of the trade is exact.

c layers hold c copies of A and B, so the machine holds four times the data — measured as blocks held rather than modelled, because it is a count of what the algorithm allocates. There is no regime in which that is 3.8 or 4.2; it is four.

So the trade at 576 processors is: four times the memory for 1.44 times less traffic. Whether that is worth making is a question about which resource is scarce, and the honest form of the answer is that the memory is spent immediately and in full while the traffic saving arrives slowly and never reaches its own headline.

What one layer is #

The layered algorithm at c = 1 is the flat one — same grid, same sweep, no replication and no reduction — and that is asserted rather than assumed, because it is what makes the comparison a comparison. One routine, one parameter, and the two ends of the parameter are the two algorithms being weighed against each other.

That matters more than it sounds. The usual presentation gives 2D and 2.5D as separate algorithms with separate analyses, and a reader comparing two published word counts is comparing two people’s accounting conventions as much as two algorithms. Here the flat count and the layered count come out of the same instrumented routine on the same matrices with the same block sizes, so the ratio in the table is a ratio of two measurements rather than of two models.

The check that the two really are one routine is short: at c = 1 the grid is √p, the round count is exactly the number of sweep steps, and there is no replication round and no final reduction. All three are asserted.

The fifth instance of one sentence #

The breadth phase’s organising finding was that a statement about a limit is not a statement about a computation, and it collected four instances in areas sharing no mathematics: Szegő’s limit reached to 52% by an 8×8 section, circulant preconditioning taking 109 steps against an unpreconditioned 66, blocking buying a constant rather than an exponent, and the Picard crossing arriving four to eleven indices late.

This is the fifth, and it is the cleanest of them, because the gap between the limit and the measurement is a single number that can be watched moving: 0.88, 1.10, 1.25, 1.44, against a law that says 2 at every row.

What makes the instance worth adding rather than merely counting is where it comes from. The √c is not a bound that happens to be loose — it is exactly right about the phase it describes and silent about two phases that are lower-order in an asymptotic sense and are, at 64 processors, larger than the thing they are lower-order than.

What the simulation actually does #

Worth being concrete about, because “counted rather than modelled” is a claim about code.

The routine holds A and B as ordinary matrices and cuts them into g×g blocks, with g = √(p/c). It then walks the algorithm: for each summation index k assigned to a layer, it charges one round of 2g(g − 1) messages of (n/g)² words to the network, and multiplies the corresponding block of A by the corresponding block of B into the accumulating C — the real arithmetic, in the real order, with the blocks the layout would actually hold.

At the end it charges the replication and the reduction, and returns both the product and the network’s summary.

So the traffic figure and the answer come from the same walk. That is the property that makes the table trustworthy in a way a spreadsheet of asymptotic volumes is not: if the loop bounds were wrong, the product would be wrong, and the product is checked against a direct multiplication at every layer count and every machine size.

It is also the property that bounds what the measurement can say. The simulation charges every broadcast at full price to every destination; it assumes the blocks divide evenly; and it counts a collective as the sum of its point-to-point messages. Those are modelling choices inside a measurement, and each of them is stated where the code makes it.

What is being left out #

Three things, and stating them is what keeps the measurement from claiming more than it is.

The word count is whole-machine rather than per processor. The classic statement is per processor, and dividing by p changes none of the ratios above — the crossing, the trend and the shortfall against the law are the same numbers either way.

Latency is counted separately and is not in the table. The layered layout takes one more round than the flat one at 256 processors, and a reader whose machine is latency-bound rather than bandwidth-bound should read the rounds column of the communication field’s own figures instead.

And the arithmetic is unchanged. Both layouts perform exactly n³ multiply-adds distributed differently, which is worth stating because it is what separates this trade from the reduction tree’s: that one buys synchronisations with 22% more flops, and this one buys traffic with memory and nothing else.

The other half of the deferral #

This essay and doing it twice are the two halves of one line the synthesis phase wrote down — CholeskyQR2 and the 2.5D communication-avoiding factorisations — and they turn out to be about different things.

The first is about accuracy: a method with the fewest possible communication rounds pays for them with κ², and one extra round buys the square back. Nothing about the machine enters; the trade is arithmetic for arithmetic.

The second is about resources: a method spends memory to move fewer words, and whether that is worth doing depends on a crossing that is a property of the machine. Nothing about accuracy enters; the product is identical to the last bit at every layer count.

Grouping them under one heading is the literature’s doing rather than the subject’s, and the grouping is defensible — both are communication-avoiding in the sense of trading something for traffic. What the measurements show is that the two trades have nothing else in common: one has a threshold in κ and no dependence on p, the other has a crossing in p and no dependence on κ.

Where the crossing would move #

The measurement is one problem shape on one cost model, and three things would move the crossing if they were different.

A cheaper broadcast. The count here charges every broadcast to g − 1 destinations at full price, which is what a naive implementation costs and what a network with hardware multicast does not. Halve the replication’s price and the crossing moves down by roughly the same factor.

A larger c. Four layers is what the grids in this figure divide into; nine or sixteen would move the sweep’s saving up like √c and the fixed costs up like c, so the crossing moves up with c — a bigger replication factor needs a bigger machine to pay for itself, which is the opposite of the way the law reads.

And a rectangular problem. Everything here is n×n by n×n. A tall-skinny product has a different balance between the sweep and the replication, and the communication field’s own tall-skinny factorisations are the case where the reduction tree wins outright — so the shape of the operands is not a detail of this trade, it is one of its parameters.

None of those changes the sentence the essay is about. They move the crossing; they do not make the fixed costs scale with the machine, and that is the whole reason the crossing exists.

What a reader should take from the table #

Three sentences, in the order the numbers support them.

The direction of the trade is right. At every machine size above the crossing, four layers move fewer words than one, and the advantage grows with the machine. Nothing here says the idea is wrong.

The size of it is not what the law says, and the shortfall is not a small correction: 1.44 against 2 at 576 processors, and negative at 64. A capacity plan built on √c is over-optimistic by 39% at the largest size drawn here and by more below it.

And the memory is spent in full, immediately. Four times the data is four times the data whatever the machine’s size, so a trade that is marginal in traffic is unambiguous in memory — which makes the decision easier than the table suggests, in the direction of not making it unless the machine is large.

The figure has no slider, and that is the finding #

Every other figure in this field carries a crank. This one was drafted with one — the size of the matrix, from 48 to 192 — and a note saying that a larger matrix moves every point on the curve up together without moving the crossing.

The build refused it. The figure machinery renders every stop of a declared range and compares the frames, and all four were the same picture; the message was that either the generator ignores the parameter or the range is too narrow to change anything. Neither was true, and the truth was worse for the note: on a ratio axis a larger matrix moves nothing at all, not every point up.

The reason is the one already given above. The sweep moves 2n²(g − 1) words, the replication 2n²(c −

1. and the reduction about n²c, where the grid g depends on p and c and not on n. Every term carries the same n², so the ratio of two layouts is a rational number with n² cancelled out of it — and cancelled exactly, because the model counts whole blocks and a block is (n/g)² words. The four saving factors at n = 48, 96, 144 and 192 are not close to each other. They are the same double: 0.878431, 1.101530, 1.250814, 1.437812, at 64, 144, 256 and 576 processors, to every digit a comparison can see.

So the assertion that replaced the slider states it as an equality rather than a tolerance, and it is paired with a second one that the word counts themselves are not equal — they grow like n² to twelve digits — so what is being reported is cancellation and not a model that quietly ignores its matrix size. The claim fed to the refusal is the drag note’s own: that a larger matrix makes replication pay better at the same processor count.

A reader who has been told that 2.5D algorithms are for large problems has been told the wrong axis. They are for large machines, and the strongest form of that statement is not a curve that shifts under a slider but a number that refuses to move.