Study guides · Intermediate

Trace cache placement from addresses

Decompose byte addresses in a four-set model, trace replacement, and distinguish mapping predictions from measurements of real hardware.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Choose a cache small enough to trace
  2. Split the address into three roles
  3. Read a concrete mapping table
  4. Trace a replacement policy explicitly
  5. Connect mapping to array layout
  6. Keep the machine boundary visible
  7. Change sets and ways independently
  8. Solve a changed configuration
  9. Ask Logeia about this articleCheck your understanding

Choose a cache small enough to trace

Total capacity alone does not explain every cache miss. A cache can have room in one part while repeatedly evicting data from another part because the requested addresses compete for the same locations. This guide develops a paper model for locating a byte within a line and locating that line within a set. Read the binary representation and memory hierarchy textbooks first. You need powers of two and the distinction between an individual byte and the larger block transferred by a cache.

Our model has 64 bytes per line, four sets, and two ways per set. Its data capacity is therefore 512 bytes. Tags, valid bits and replacement metadata are additional storage and are excluded from that figure. Addresses identify bytes, and each example access stays inside one line. These choices define a teaching model, rather than a claim that a particular processor uses this exact indexing arrangement. Keep the assumptions visible when predicting an outcome. Later sections explain which conclusions survive and which require a real machine's documentation.

Split the address into three roles

For a byte address a, the offset is a modulo 64. Integer division by 64 gives the memory line number. That number modulo four selects the set, while integer division of the line number by four gives the tag. Equivalently, tag is floor(a/256). A tag identifies which memory line occupies a way; it is not the byte value stored at that address. Distinguishing these roles prevents confusing a different position in one line with a different line competing for a place.

Because 64 is two to the sixth power, six low bits encode the byte offset. The next two bits encode one of four sets. Higher bits form the tag in this model. Address 320 decomposes into 1×256 + 1×64 + 0, so its tag is one, set is one and offset is zero. Addresses with equal set and tag refer to the same line even if their offsets differ. Equal sets with different tags refer to competing lines. Neither statement depends on the values stored in memory.

Read a concrete mapping table

Addresses zero and eight have the same set and tag. Starting from an empty cache, reading address zero fetches the model line covering bytes zero through 63. A subsequent read at eight hits if that line remains present. An eight-byte load consequently does not imply an eight-byte transfer from the next level. This is the useful distinction behind spatial locality. Reading address 64 instead selects set one, so it does not directly compete for a way in set zero.

Addresses 256 and 512 return to set zero with tags one and two. A displacement of 256 bytes advances through all four sets and wraps back to the original set. The three lines beginning at zero, 256 and 512 contain only 192 bytes altogether, less than total capacity. Nevertheless, they cannot all reside simultaneously in a two-way set zero. Other empty sets cannot lend a way under the mapping rules we chose. Read the table by comparing both set and tag, rather than comparing only how far apart two addresses appear.

Address (B)OffsetSetTag
0000
8800
64010
256001
320011
512002

Trace a replacement policy explicitly

Assume exact least recently used replacement within each set. Starting empty, access zero, 256, zero, 512 and 256. The first two accesses miss and fill the two ways of set zero. The third access hits tag zero and makes it most recently used. Accessing 512 misses on tag two, evicts the older tag one and keeps tags zero and two. The final access to 256 then misses because tag one has just been removed. The complete trace contains one hit and four misses.

Replacement is part of the model, not something obtained from the address bits. Changing the policy can change later occupants even when all mappings remain identical. A rigorous miss taxonomy also specifies a comparison cache, such as a fully associative cache of equal capacity, before assigning conflict and capacity labels. For this exercise, first identify exactly where the claim that a repeated access must hit breaks down. Do not assume a processor implements exact LRU merely because a paper exercise uses it; real replacement mechanisms can approximate recency and include additional behavior.

Connect mapping to array layout

Consider a row-major matrix with a 256-byte row length. Walking down one column advances by 256 bytes and therefore repeatedly selects the same set in our model. Changing the row length changes that pattern. It does not establish that adding one padding element always improves an application. Calculate addresses using element size, the actual row start, the visited range and the relationship between multiple arrays. If a layout change requires copying data into a new representation, include that cost when deciding whether the change is worthwhile.

The related experiments deliberately separate row versus column order, stride and starting alignment. They ask different questions: in what order are bytes used, which bytes are used at all, and does a particular access cross a line? Changing all three together makes an elapsed-time result difficult to interpret. Predict a mapping first, then preserve input and output checks while measuring the native implementation. A result that differs from the prediction is useful evidence to investigate compiler transformations or a mismatch between the teaching cache and the real hierarchy. It is not a reason to silently revise the model.

Keep the machine boundary visible

A real hierarchy contains multiple cache levels. Missing one level does not necessarily mean going to main memory. Virtual to physical translation, page size, shared-cache indexing, prefetching and interference from other work can all affect the result. Splitting a virtual address into a few low bits does not prove placement at every level. When a decision depends on a particular processor, consult that model's official documentation and the configuration exposed by the running environment, rather than transferring this four-set model unchanged.

Record compiler version, optimization flags, CPU and instruction set, allocation size, accesses, repetitions and how computed results are consumed. If you only measured time, leave cache-miss counts unmeasured. Instruction changes, address translation, prefetching, frequency changes and scheduling can contribute to the same elapsed interval. In a virtual machine, the exposed processor name also does not describe every host placement decision. Keep the prediction, executed source, measured durations and available counters in separate fields. That organization lets another reader assess the practical reach of the explanation without turning missing observations into invented measurements.

Change sets and ways independently

Increasing only associativity to four ways leaves the set-index calculation unchanged but permits four tags in set zero. Increasing set count to eight changes index bits and moves address 256 to another set. Both changes increase data capacity, yet affect the same trace differently. A single capacity number cannot determine set count and associativity uniquely. Read capacity, line size and ways together when interpreting a documented configuration.

Solve a changed configuration

Change the model to eight sets while keeping 64-byte lines and two ways. Do zero, 256 and 512 still compete for one set? Six offset bits remain, but three bits now select the set, and the tag is floor(a/512). Zero maps to set zero with tag zero, 256 to set four with tag zero, and 512 to set zero with tag one. Only two of the three lines compete in set zero, so two ways can hold them together. Starting empty, the three initial reads require no eviction.

For a second exercise return to four sets and compare zero, 64, 128, 192 with zero, 256, 512, 768. The first sequence spreads four lines over four sets. The second puts four distinct tags into one two-way set and cannot retain them simultaneously. Both touch four lines, so line count alone misses the difference. Explain the answer using mappings before opening a benchmark. The row-order and stride experiments then compare that prediction with actual compiled code and measured time, without claiming that this model alone predicts a speed ratio.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 8

Prepare for AI systems · STEP 5

Choose a learning path