Online text: ocw.mit.edu/ans7870/textbooks/Strang/Edited/Calculus/5.pdf

Cited passages: Gilbert Strang, Calculus, §5.8, printed p. 223: midpoint rectangles, linear exactness and signed quadratic errors.

The time from a memory reference's request until the requested data become available. Average memory access time averages this delay in the stated serial model; it does not directly measure whole-program runtime.

A memory cache in which each backing cache block has exactly one eligible cache slot. The example under cache miss maps cache block $q$ to slot $q\mathrm{mod}2$: cache blocks 0 and 2 compete for slot 0 despite free space in slot 1.

A memory cache allowing any cache block to occupy any resident slot. When full, its replacement policy chooses a victim from all resident cache lines. The examples in temporal locality and spatial locality use LRU replacement, so no additional placement restriction causes eviction.

The diagram enumerates every read of the fixed memory access trace under memory cache. Keep cache slots fixed: fill the lowest-numbered unused slot first, and subsequently reuse the victim's slot. Separately list recency from least recently used to most recently used. A cache hit refreshes that recency without moving the resident data to another cache slot.

After read 3, cache block 0 is older than cache block 2. Read 4 hits cache block 0, making cache block 2 older; read 5 must therefore evict cache block 2 to load cache block 1. Omitting recency updates on cache hits would choose the wrong victim. Read 6 immediately needs the evicted cache block 2, showing that LRU replacement uses past demand rather than knowledge of future demand.

With capacity four cache slots and the same cache line size, the same memory access trace has just its four compulsory misses and eight cache hits, since all four distinct cache blocks fit. Greater capacity helps this trace, but full associativity alone does not make LRU replacement optimal. Its attraction is freedom from placement restrictions; a hardware implementation must still identify a matching cache tag among eligible entries, and exact recency tracking adds work. ^[ref]

A request whose required data are unavailable in the consulted memory cache. The model in spatial locality fetches the requested cache block and evicts a resident cache line only when capacity is full.

In the fixed memory access trace under memory cache, reads 1, 3, 5 and 8 first request cache blocks 0, 2, 1 and 3: four compulsory misses, also called cold misses. Reads 6, 7 and 11 revisit cache blocks that LRU replacement has evicted: three capacity misses. Read 5 is a compulsory miss even though it also causes an eviction; a full memory cache alone does not determine the classification. The fully associative cache permits every cache block in every cache slot, so this example has no conflict misses.

For a precise comparison, run the same memory access trace through an initially empty direct-mapped cache with the same 16-byte cache lines and two cache slots, placing cache block $q$ only in slot $q\mathrm{mod}2$. Read 3 brings in cache block 2 and displaces cache block 0, leaving the other cache slot unused. Read 4 consequently misses at address 0, whereas the fully associative cache still has cache block 0. That read is a conflict miss: increasing placement freedom at the same capacity removes it. The complete direct-mapped cache trace has eight cache misses: four compulsory misses, three capacity misses and one conflict miss.

The convention here classifies each cache miss by first asking whether its cache block has ever been requested. If so, compare with an initially empty fully associative cache of the same capacity and cache line size using LRU replacement on the same memory access trace: a miss there is a capacity miss, while a hit there identifies a conflict miss in the restricted design. This makes the comparison policy explicit; “capacity” is not a claim that no other replacement choice could save that individual read. The three categories describe this read-only demand model; external invalidations or fetching ahead of requests require additional reasoning. ^[ref]

A request whose required data are already available in the consulted memory cache. In the read-only model of spatial locality, a requested cache block being resident is sufficient for a cache hit.

The memory access trace under memory cache has cache hits at reads 2, 4, 9, 10 and 12. Read 2, at address 4, benefits from the cache line fetched by read 1 at address 0; read 9, at address 52, benefits from read 8 at address 48. These reads use different bytes of the same cache blocks, illustrating spatial locality. Read 4 returns to address 0 while its cache block remains resident, illustrating temporal locality.

A cache hit still takes time to identify the matching cache tag and obtain the requested byte. It is relative to the particular memory cache consulted: a cache miss in one level may be a cache hit in another. The model here has one consulted level and treats a valid matching resident copy as sufficient; it makes no prediction about writes or accesses whose permissions or contents change.

A fixed-sized, aligned block of consecutive bytes transferred and tracked as a unit by a data memory cache. Here cache line and cache block name that unit of data, including its identity in backing computer memory; a resident slot holds a copy. Reading one element can bring neighbouring elements into the same cache line, exploiting spatial locality.

For a nonnegative integer physical address $a$ and a cache line size $B$ bytes, Euclidean division gives the backing cache block number $q$ and offset $d$:Here the brackets denote the floor function and $\mathrm{mod}$ gives the remainder. Cache line $q$ contains bytes at physical addresses $Bq$ through $Bq+B-1$. With $B=16$, read address 52 selects cache block 3, spanning addresses 48–63, and offset 4. Addresses 48 and 52 therefore request the same cache line; addresses 15 and 16 request different cache lines despite being adjacent.

For a cache line size $B=2^b$, the low $b$ bits give the offset. In a fully associative cache, all remaining bits identify the backing cache block as its cache tag; there are no address bits selecting a particular cache slot. An eight-bit illustration gives $52={00110100}_2$: four bits 0011 for cache block 3 and four bits 0100 for offset 4 in the binary numeral system. The eight-bit width is illustrative; the trace does not assume an actual eight-bit machine. ^[ref]

Distinguish this identity from a cache slot, which can hold different cache blocks over time. After read nine in the memory cache example, cache slot 0 contains cache line 3 and cache slot 1 contains cache line 0. Their cache tags identify 3 and 0; neither cache line number is its slot number. Some texts use “cache line” for the storage entry itself; this article reserves cache slot for that role.

A group of related payload transfers, often to consecutive addresses, arranged under one transfer sequence. A bus burst can amortize setup and bus arbitration overhead; a longer period of exclusive bus ownership can also make another initiator wait longer. The exact overhead and permitted handover boundaries depend on the protocol.^[ref]

An extension while a bus transaction awaits readiness. A bus wait state spends time without completing the next payload transfer. In a blocking design it also postpones another initiator's access; completion and bus ownership changes must follow the protocol.^[ref]

One clock period in a synchronous computer bus. A bus transaction can occupy several bus cycles. An asynchronous computer bus instead coordinates progress through acknowledgments, so a clock-based count requires an additional timing model.^[ref]

Consider a stipulated synchronous shared computer bus, rather than a timing claim about any named hardware protocol. Assume a 32-bit data bus, a 100 MHz clock, and one four-byte payload transfer per bus cycle during the data phase. Both initiators $A$ and $B$ request at time zero. $A$ has one four-transfer write bus burst and $B$ one two-transfer write bus burst, to an immediately ready target in computer memory. Each bus burst pays one bus cycle for bus arbitration and one for its starting address and command; subsequent addresses advance implicitly. The arbiter chooses $A$ first, owners finish their entire bus bursts, and no phases overlap. There are no bus wait states, retries, extra completion cycles, direction changes or intervening requests. Payload is counted when each data phase completes; the observation interval starts at the first bus arbitration cycle and ends at the last payload completion.

A bus cycle lastsThe timeline uses half-open intervals of bus cycles: $A$ has bus arbitration on $[0,1)$, address and command on $[1,2)$, and four payload transfers on $[2,6)$. Then $B$ has bus arbitration on $[6,7)$, address and command on $[7,8)$, and two payload transfers on $[8,10)$. Their final payload completions are at 60 ns and 100 ns respectively. $B$ waits 60 ns before its own selection cycle even though both requests arrived together.

The six payload transfers contain 24 bytes. Ten bus cycles take 100 ns, giving finite-interval bus throughputwhere MB means $10^6$ bytes. The raw data bus rate is $4\mathrm{bytes}\times 100\times 10^6{\mathrm{s}}^{-1}=400MB/s$. Payload occupies $6/10=60\%$ of the interval. If this same pair repeats with no gaps, its long-run bus throughput equals the finite-interval value; isolated observations need not predict a later workload.

Reverse the bus arbitration order, keeping these assumptions. $B$ finishes after four bus cycles, at 40 ns; $A$ finishes at 100 ns. Aggregate bus throughput stays 240 MB/s, but $B$'s request-to-completion time falls from 100 ns to 40 ns and $A$'s rises from 60 ns to 100 ns. Scheduling changes who waits without changing the available payload capacity in this example.

For an independent perturbation, retain $A$ first and add two bus wait states before $B$'s final payload transfer. The interval grows to 120 ns with the same 24 bytes, so bus throughput falls to 200 MB/s. For another workload, one initiator sends all six transfers in a single bus burst: the stipulated overhead is paid once, giving eight bus cycles, 80 ns and 300 MB/s. This latter comparison assumes one combined request is valid; combining different initiators' operations is not automatically permitted.

Here, competition between pending initiators for the same shared computer bus resource. Correct bus arbitration converts this competition into waiting. Simultaneously driving incompatible values on the same electrical lines is a different, erroneous kind of bus contention; multiple pending requests need not cause it.

The permission to use a particular computer bus resource during a specified phase. A pending grant need not authorize immediate use. Arm's AMBA Specification, revision 2.0 (section 3.11.3, figures 3-15–3-17) makes address-path handover depend on completion, and delays data bus ownership relative to address bus ownership. Consequently, a single whole-bus transaction owner is a useful simple model, but does not describe every overlapping implementation.

Buffer capacity measures resistance to a change in pH: how much additional chemical acid or chemical base a chemical solution accommodates per small change in pH. Its differential form is a local derivative, rather than the total inventory available before a buffer solution is exhausted. Two buffer solutions can have identical pH and very different buffer capacities.

Choose a constant volume $V$ and fixed temperature. Let $n_B$ count added moles of fully dissociated, monovalent chemical base supplying hydroxide, and $n_A$ added moles of fully dissociated, monovalent strong acid supplying hydrogen ions. Neither addition supplies the weak acid component itself. The signed addition is $b=(n_B-n_A)/V$, with units $\mathrm{mol}{\mathrm{L}}^{-1}$, andThe last two forms describe separate base-only and acid-only additions. The buffer capacity is positive for the stable chemical equilibrium model below and is reported in $\mathrm{mol}{\mathrm{L}}^{-1}$ per unit of pH. Since pH is dimensionless, the dimensional unit is just $\mathrm{mol}{\mathrm{L}}^{-1}$; stating “per pH” makes the measurement convention clear. Here constant volume is an idealization, realized approximately by small additions of concentrated reagent.

For a sufficiently small addition, $\Delta \mathrm{pH}\approx \Delta b/\beta$. A large buffer capacity means a small local change of pH for a given addition. Over a finite interval, use the changing buffer capacity instead:This integral gives a finite dose in $\mathrm{mol}{\mathrm{L}}^{-1}$; it need not equal the initial buffer capacity times the eventual change in pH.

The Henderson-Hasselbalch equation estimates buffer solution pH using a weak acid's acid dissociation constant and the conjugate base to weak acid concentration ratio.

Its activity form is an exact rearrangement of the chosen chemical equilibrium relation. Write the acid dissociation step as $\mathrm{HA}\rightleftharpoons {\mathrm{H}}^{+}+{\mathrm{A}}^{-}$, with hydrated hydrogen ions understood in water and the solvent convention incorporated into the acid dissociation constant. For consistent standard states,Here each $a_i$ is a dimensionless thermodynamic activity at chemical equilibrium. Exactness refers to this specified acid dissociation constant relation and the chosen single-ion thermodynamic activity convention, not to identifying the ratio with quantities initially mixed. If water is instead written explicitly as a reactant, its thermodynamic activity must be treated consistently. See Hippler and Metcalfe, Using activities to correct the Henderson-Hasselbalch equation (2020), equations 3–4.

For a toy weak acid with stipulated pKa $5$, use the ideal dilute concentration approximation and put $r=[{\mathrm{A}}^{-}]/[\mathrm{HA}]$. The Henderson-Hasselbalch equation becomes $\mathrm{pH}\approx 5+{\log }_{10}r$:More conjugate base relative to weak acid means higher pH. Each tenfold increase in the ratio contributes exactly one to the calculated pH. The stipulated pKa is not a tabulated value for an identified substance.

The distinction between thermodynamic activity and concentration is explicit when $a_i={\gamma }_i[i]/c^{\circ }$, where ${\gamma }_i$ is an activity coefficient and $c^{\circ }$ is the reference concentration:Neglecting the final term gives the usual approximate Henderson-Hasselbalch equation. It is justified when the ratio of activity coefficients is sufficiently close to one, as in a suitable dilute ideal approximation. Ionic strength, including contributions from other dissolved ions, affects activity coefficients; a nominally dilute weak acid alone does not establish that all corrections are small. The ratio must use chemical equilibrium concentrations. Replacing these by prepared amounts or post-neutralization inventories is a further approximation, suitable only when subsequent redistribution is small. See Hippler and Metcalfe, concentration, activity, and analytical-concentration approximations.

The short derivation is to solve the acid dissociation constant relation for $a_{{\mathrm{H}}^{+}}$, take a negative base-ten logarithm, and use the definitions of pH and pKa. Its useful beauty is that a chemical equilibrium becomes a simple rule about a ratio: select a weak acid with pKa near the desired pH, then adjust the partner ratio. Scaling both partner concentrations equally leaves the ideal pH prediction unchanged, while changing buffer capacity. In practical buffer solutions, temperature, ionic strength, and the available inventories still matter.