Cache mapping techniques

Question

Im trying to understand hardware Caches. I have a slight idea, but i would like to ask on here whether my understanding is correct or not.

So i understand that there are 3 types of cache mapping, direct, full associative and set associative.

I would like to know is the type of mapping implemented with logic gates in hardware and specific to say some computer system and in order to change the mapping, one would be required to changed the electrical connections?

My current understanding is that in RAM, there exists a memory address to refer to each block of memory. Within a block contains words, each words contain a number of bytes. We can represent the number of options with number of bits. So for example, 4096 memory locations, each memory location contains 16 bytes. If we were to refer to each byte then 2^12*2^4 = 2^16 16 bit memory address would be required to refer to each byte.

The cache also has a memory address, valid bit, tag, and some data capable of storing a block of main memory of n words and thus m bytes. Where m = n*i (bytes per word)

For an example, direct mapping 1 block of main memory can only be at one particular memory location in cache. When the CPU requests for some data using a 16bit memory location of RAM, it checks for cache first. How does it know that this particular 16bit memory address can only be in a few places?

My thoughts are, there could be some electrical connection between every RAM address to a cache address. The 16bit address could then be split into parts, for example only compare the left 8bits with every cache memory address, then if match compare the byte bits, then tag bits then valid bit

Is my understanding correct? Thank you! Really do appreciate if someone read this long post

Perhaps electronics.stackexchange.com is a better forum for this question since the question is about hardware. — wooooooooosh

Domso Domso · Accepted Answer · 2018-12-05T09:55:15

You may want to read 3.3.1 Associativity in What Every Programmer Should Know About Memory from Ulrich Drepper. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf#subsubsection.3.3.1

The title is a little bit catchy, but it explains everything you ask in detail.

In short: the problem of caches is the number of comparisons. If your cache holds 100 blocks, you need to perform 100 comparisons in one cycle. You can reduce this number with the introduction of sets. if A specific memory-region can only be placed in slot 1-10, you reduce the number of comparisons to 10. The sets are addressed by an additional bit-field inside the memory-address called index. So for instance your 16 Bit (from your example) could be splitted into:

[15:6] block-address; stored in the `cache` as the `tag` to identify the block
[5:4] index-bits; 2Bit-->4 sets
[3:0] block-offset; byte position inside the block

so the choice of the method depends on the availability of hardware-resources and the access-time you want to archive. Its pretty much hardwired, since you want to reduce the comparison-logic.

Cache mapping techniques

2 Answers