Derive: The Real Machine

The spacing. Every 32-bit float in the binade $[2^e,2^{e+1})$ has the form $$k\cdot 2^{e-23}\text{with}{2}^{23}\le k<2^{24}.$$ The integer $k$ is the 24-bit significand, and the hidden bit is the leading one. Neighbouring values differ by one unit of $k$, so the gap is $$2^{e-23}.$$ The relative gap is that number divided by the value, and the value lies between $2^e$ and $2^{e+1}$, so $$2^{-24}<\frac{2^{e-23}}{x}\le 2^{-23}.$$ The bound is attained at the bottom of the binade and halves at the top, which is why the unit roundoff is quoted as $2^{-24}$: it is the worst relative error one rounding can cause anywhere in the format.

The two evaluations. At $x=1$ the binade has $e=0$, so the spacing is $2^{-23}=1.19209\times 10^{-7}$. At $x=10^8$ the binade is $[2^{26},2^{27})=[67,108,864,134,217,728)$, so $e=26$ and the spacing is $$2^{26-23}=2^3=8.$$ Eight is the gap between neighbouring numbers near one hundred million, and section 6.2 quotes the same value.

The cancellation bound. Take two operands $a$ and $b$ in the same binade $[2^e,2^{e+1})$, each the result of earlier arithmetic, so each carries an absolute error of at most half a step, $2^{e-24}$. Write $d=a-b$. The subtraction itself is exact, and the errors add, so the difference carries an absolute error of at most $$2\times 2^{e-24}=2^{e-23}.$$ Its relative error is therefore at most $$\frac{2^{e-23}}{d}=2^{-23}\cdot \frac{2^e}{d}\le 2^{-23}\cdot \frac{\max (|a|,|b|)}{d}=2^{-23}\times \text{cancellation ratio}.$$ If the two operands sit in different binades, the larger one's exponent bounds both errors, and the same line holds with its $e$. At $10^8$ a difference of 1 has cancellation ratio about $10^8$, and the bound is $$2^{-23}\times 10^8=1.19\times 10^{-7}\times 10^8\approx \mathrm{11.9.}$$ Using the binade's own base $2^{26}$ instead gives exactly $2^{26-23}=8$, which is the spacing itself. The larger is half again the smaller, and both have the right size. The two sections are one statement: the spacing of section 6.1 is the absolute error, and the ratio of section 6.2 converts it into a relative one. The bound is a worst case for two operands; it does not cover a long sum, where the number of additions enters and the errors can partly cancel.

The spacing. Set $e=24$ in the spacing formula of E2.1. Every float in $[2^{24},2^{25})$ is $k\cdot 2^{24-23}=2k$ with $2^{23}\le k<2^{24}$, so every value in the binade is an even integer and the gap between neighbours is 2. The formula is the same one that gave 8 near $10^8$; only the exponent changed.

The wall. Take a representable $x$ in the binade. The number $x+1$ is odd, and every representable number in the binade is even, so $x+1$ has no representation. It lies strictly between the neighbours $x$ and $x+2$, so rounding returns one of them. The smallest such $x$ is $2^{24}=16,777,216$, and the first integer without a successor is $$n=2^{24}+1=16,777,217.$$ Below $2^{24}$ the spacing is at most 1, so every integer up to $2^{24}$ is representable and has a representable successor.

The two differences. The sum $2^{24}+1$ is exactly halfway between $2^{24}$ and $2^{24}+2$. Rounding to nearest with ties to even picks the neighbour whose last significand bit is 0, which is $2^{24}$. The first subtraction is therefore $$(2^{24}+1)-2^{24}=2^{24}-2^{24}=0,$$ a relative error of one hundred per cent against the true difference 1. The second sum, $2^{24}+2$, is representable, so $$(2^{24}+2)-2^{24}=2.$$ The pair is the edge case that separates two claims. The subtraction is exact in both rows, and the digit was lost in the addition. The failure depends on the parity of the sum rather than on its size. A program can add 1 to one large number and 2 to the next, and the answers differ by more than the inputs did.

The intensity. The layer performs $2n^2$ operations per example, so the batch performs $$2b{n}^2.$$ The bytes are two for each of the $n^2$ weights, two for each of the $bn$ inputs, and two for each of the $bn$ outputs: $$2\left(n^2+bn+bn\right)=2\left(n^2+2bn\right).$$ The intensity is the ratio: $$I(b)=\frac{2b{n}^2}{2\left(n^2+2bn\right)}=\frac{b{n}^2}{n^2+2bn}=\frac{bn}{n+2b}.$$ At $b=1$ this gives $n/(n+2)\approx 1$, which is section 6.4's batch of one. As $b$ grows the intensity rises toward $n/2$, the value at which the weights are read once and reused across the whole batch. The batch cannot push the intensity past $n/2$, because the inputs and outputs keep arriving.

The crossing. Set $I(b)>R$ and clear the denominator, which is positive: $$bn>R\left(n+2b\right)⟺b\left(n-2R\right)>Rn⟺b>\frac{Rn}{n-2R},$$ where the last step divides by $n-2R$ and therefore needs $n>2R$. For $n=4096$ and $R=139$, $$b^{\ast }=\frac{139\times 4096}{4096-278}=\frac{569,344}{3,818}=149.12\dots ,$$ so the smallest whole batch above the crossing is $b=150$. The two checks are $$I(149)=\frac{149\times 4096}{4096+298}=138.89,I(150)=\frac{150\times 4096}{4096+300}=\mathrm{139.76.}$$ The first lies below the ridge and the second above it, so the crossing sits between two consecutive batch sizes.

What the answer means. At $b=150$ the operations are $2\times 150\times 4096^2=5,033,164,800$ and the bytes are $2(4096^2+2\times 150\times 4096)=36,012,032$. The compute time is $5.03\times 10^9/125\times 10^{12}=40.3$ microseconds and the memory time is $3.60\times 10^7/900\times 10^9=40.0$ microseconds, which agree to within one per cent by construction. Below the crossing, adding examples costs almost no extra time, because the weights already dominate the traffic; above it, each example costs its own arithmetic, and the batch stops being free. The derivation assumes that the weights are reused across the batch and that every byte comes from main memory. Section 6.4's cache ridge of 40 moves the crossing to $40\times 4096/(4096-80)=40.8$, so a batch of 41 suffices against the second-level cache. The intensity says where the time goes; it does not say whether the requests exist to reach the rate, which is the count section 6.5 supplies.