# direct mapping cache question

I have been doing the question below in what I thought was the correct way. After doing some more reading I am now slightly confused and would appreciate some clarification. Previously I was just using a 4 line cache and recording hits/misses based on the binary numbers shown.

After doing some more reading I found that the address (comprised of the tag & line portions together) gives the block number in main memory, meaning there should be 16 slots in memory.

As far as I read using direct mapping the first line of cache should hold the values of the 0,4,8,12 main memory blocks and so on for each line. This makes me preety confused since I thought when the tag was different to the one currently stored it would take that as a miss and go searching. Can anyone explain this to me ?

sorry if this is hard to understand.

Your cache has 4 blocks of 4 bytes per block each ==> cache size is 16 bytes. Each cache block (4 bytes) stores one word (4 bytes). Thus, there are no byte select bits. (In this machine the smallest addressable unit is a word of 4 bytes.)

Two bits of the word address are directly taken to address these 4 blocks, that's it, why this is called a direct mapped cache. It is not clearly stated in the question which two bits out of the four address bits to use, but usually the lowest significant bits (above the non-existing byte select bits) of the word address are used. These bits are also called the index bits. This leaves the upper two bits for the tag.

The memory has $2^4=16$ words and is thus divided into 16 blocks. The cache block 0 could store the memory blocks 0, 4, 8 and 12 because the two least significant bits (= index) is binary "00" in all these memory block addresses. The cache block 1 could store the memory blocks 1, 5, 9 and 13 because the index is binary "01" here. And so on.

The tag memory (table) is addressed with the same index. If the tag stored at the particular index matches that of the word address, then we have a hit. Otherwise, we have a miss and the block is loaded from memory into the cache at the indexed block and the tag line is updated. There is no further search because we have direct-mapped cache. Each memory block is mapped only to one cache block as selected by the index bits.

Analyzing the address trace gets: EDIT bugfix

Address   Index   Tag_Table[Index] Before / After
0111      11      empty / 01  -> Miss
1010      10      empty / 10  -> Miss
0010      10      10    / 00  -> Miss, because another tag
1010      10      00    / 10  -> Miss, because another tag
0111      11      01    / 01  -> Hit
0100      00      empty / 01  -> Miss
0100      00      01    / 01  -> Hit
1010      10      10    / 10  -> Hit
0100      00      01    / 01  -> Hit  (fixed!)
0010      10      10    / 00  -> Miss, because another tag


Thus, the hit rate is 4/10 = 40% in this example.

• Address #9 in the trace is incorrect. It should be a hit. Commented Nov 28, 2015 at 4:25

The word size is 4. so there are 16/4=4 blocks. The blocks are numbered by the most significant addresses, which are also the tag contents. Least two significant addresses select a byte within a block, so they are irrelevant here. The sequence is miss(block 1) miss(2) miss(0) hit(2) hit(1) hit(1) hit(1) hit(2) hit(1) hit(0) Three misses, seven hits, ten accesses. 7/10=70%. Block 3 remains invalid.

• That is wrong. If you choose the two most significant address bits as the index, then the tag is comprised of the remaining two least significant bits! By the way, this order is uncommon. Commented Nov 27, 2015 at 23:25

16 bytes cache size / 4 bytes block size = 4 lines.

Therefore the 4-bit word address is broken into
{2 bits of tag address, 2 bits of line address} for a direct mapped cache

Manually tracing what happens (with least recently used scheme):
01,11 -- miss -- 01,11 cached
10,10 -- miss -- 10,10 cached
00,10 -- miss -- 00,10 cached -- 10,10 flushed
10,10 -- miss -- 10,10 cached -- 00,10 flushed
01,11 -- hit
01,00 -- miss -- 01,00 cached
...

• A direct mapped cache does not have a replacement strategy. Commented Nov 27, 2015 at 23:21
• Practically speaking, I agree. There are other easier/better ways to improve the cache performance than to mess with the replacement scheme of a direct mapped cache. But if you look at this particular example, some form of aging mechanism would actually improve the hit ratio. Commented Nov 28, 2015 at 4:23
• @rioraxe if you add a replacement policy to a direct mapped cache it is no longer directly mapped, but associative. Commented Jan 15, 2016 at 10:53

Firstly, in a direct mapped cache, there is nothing to search for. That is the main reason such a thing would ever be used. When a memory access occurs, the cache maps the address to a block. Then the tag is compared. If it matches, it is a hit. Otherwise it is a miss. That is what direct mapped means: there is no set there for an associative lookup. (Or, if you will, the set size is 1).

The example you are asked to solve is even simpler, because the block size is equal to the word size. The 16 byte cache holds four blocks, and four words. This means that each word is independent: accessing and replacing one word has no effect on any adjacent word.

This is why the question gives you the sequence of addresses being accessed in binary code. It's an exercise in how well you understand binary code, not how well you understand caches.

The main difficulty is in translating to decimal: 7, 10, 2, 10, 7, 4, 4, 10, 4, 2. Once we have that, we can see the access pattern clearly.

Next, we have to reduce each of these addresses modulo 4 to determine which word/block it maps to: 7:3, 10:2, 2:2, 10:2, 7:3, 4:0, 4:0, 10:2, 4:0, 2:2. (Here, it can help to look back toward the binary representation, where we take the least significant two bits.) 7 goes to block/word 3, 10 goes to 2, and so on.

Okay so 7:3 is a miss, because the cache is empty, and causes block [3] to hold 7. 10:2 is a miss, and so on. We can make a chart which traces the state of the cache as the accesses progress:

  ACCESS        0    1    2    3       MISS  NOTES
7         [ -    -    -    7 ]      X
10         [ -    -   10    7 ]      X
2         [ -    -    2    7 ]      X    2 replaces 10 at [2]
10         [ -    -   10    7 ]      X   10 replaces 2 at [2]
7         [ -    -   10    7 ]           7 matched at [3]
4         [ 4    -    2    7 ]      X
4         [ 4    -    2    7 ]           4 matched at [0]
10         [ 4    -   10    7 ]      X   10 fights with 2 again at [2]
4         [ 4    -   10    7 ]           4 matched again
2         [ 4    -    2    7 ]           2 replaces 10 at [2]


That is all direct mapped is, when the word size is the same as the block size: we are just reducing the address modulo 4 to determine the location in the cache. If the address at the location matches the accessed one, it is a hit, otherwise a miss: and the accessed address overwrites the one in the cache. (Of course, the cache doesn't need the entire address; just the tag bits! This is because for instance address 6 cannot map to slot [2]. When slot [3] remembers that it now has address 7, it really just needs the upper 01 bits of 0111, which are the tag. The lower 11 statically matches the[3]. The tag is those bits of the address which are relevant for identifying what area of memory the cache entry pertains to.

What is the hit rate? 4 hits out of 10 accesses: 40%. See, even the denominator is set up for an easy percentage calculation.

If the cache were organized into blocks of several words (say two words), it would be slightly more complicated. Accessing 10, which maps to [2] would not only bring in the data at 10 into [2], but also bring the data from 11 into [3]. Then the [2..3] block would be tagged to indicate that it holds 10..11.