# Formula to see where a memory address can be depicted in cache?

I've been trying to find a formula that helps us identify where an address can be depicted in cache. I remember my professor talking about some kind of division but I can't find it in my textbook nor internet (maybe I am not searching the right words). For example: I have a cache that has $$2^{14}$$ blocks, each 32 bytes, and it is 8-way associative with $$2^{11}$$ sets and each address is 64 bits. So we have 48 bits for the tag, 11 for the index, and 5 for the offset. I would like to answer the following question:

Where can we find in cache, the addresses 300A21 (hex)?

My obvious answer is to convert it into a binary address: 0011 0000 0000 1010 0010 0001, and now, we know that index is 0000 1010 001, so it has to be into the set with this index (it is the 81st), and since 0 0001 is the offset, I guess that since we count from 0, it is the second word on the block (?).

Is there anything else I can say? Something that involves a division or modulo of the address?

Tag Set Offset
0011 0000 0000 1010 001 0 0001

Don't doubt your methods for finding the address location in a set-associative cache. Your approach is absolutely correct, but first, let's clarify some terminology:

From your question you use the term "index." If I am correct you are using this to refer to the "set" in the set-associative cache? I will use the term "set" from this point forward in place of "index" to avoid confusion since it is more explicit with regard to the type of cache in question.

Something that involves a division or modulo of the address?

### The Short Answer Is. . .

. . .yes! However, just not with set-associative cache. Modulo division is used when attempting to find a block to which a memory address may be mapped using a Direct Mapped Cache scheme. Subdividing the cache blocks into sets that map to a main memory location based on a portion of its address removes the necessity to obtain a cache location via modulo division.

### The Long Answer. . .

Direct mapping involves the process where block X of main memory is mapped to block Y of cache memory, mod N, where N is the number of blocks in cache.[1]

### Example:

Provided you are given a cache memory consisting of four blocks and a main memory consisting of eight blocks, the direct mapping scheme will be as follows:

Cache
Blocks
Mapping Main Memory
Blocks
Mapping
Formula
CB 0 MM 0
MM 4
MM 0 MM 0 % 4 = CB 0
CB 1 MM 1
MM 5
MM 1 MM 1 % 4 = CB 1
CB 2 MM 2
MM 6
MM 2 MM 2 % 4 = CB 2
CB 3 MM 3
MM 7
MM 3 MM 3 % 4 = CB 3
MM 4 MM 4 % 4 = CB 0
MM 5 MM 5 % 4 = CB 1
MM 6 MM 6 % 4 = CB 2
MM 7 MM 7 % 4 = CB 3

## The Difference

Direct Mapped Cache does not require any searching and is therefore less expensive. However, main memory is constantly being swapped in and out of cache. In the above example, you can see that either block of cache may only hold one of two blocks of main memory at a time. Imagine the scenario where CB 0 is polled for MM 0 but is currently holding MM 4. The CPU would need to expunge MM 4 and bring in MM 0. If the next read/store cycle required MM 4, the process would occur again leading to cache thrashing.[1]

In an ideal world we would use Fully Associative Cache, wherein each block of main memory has its own location in cache and does not have to share with any other addresses. The best way of implementing this type of cache is to have each memory address assigned to any free location at random. However, this requires additional structures within the CPU that search every cache location in parallel.[1] Not only does this translate into a higher monetary expense for the additional hardware structures, it also comes with a look-up cost by having to search each cache block for a hit.

The answer is to strike a happy medium by using Set-associative Cache that combines advantages of the two other types. Each main memory block may be assigned to a specific set location similar to direct mapping, but the exact block in cache will differ based upon the next free block within the set similar to Fully Associative Cache.

## Links Regarding Different Cache Mapping Schemes

https://www.geeksforgeeks.org/cache-memory-in-computer-organization/

https://en.wikipedia.org/wiki/Cache_placement_policies

[1]Null, L., & Lobur, J. (2015). Ch. 6 Memory: Direct Mapped Cache. In The Essentials of Computer Organization and Architecture (4th ed., pp. 350-365). Burlington, MA: Jones & Bartlett.

• absolutely amazing your enthusiasm! thank you so much.. Mar 6, 2021 at 19:27
• @brucebanner No problem! Happy to help Mar 6, 2021 at 20:55