# Mapping an address to a cache block

A cache with 64 blocks(block0 to block63) and each block of size 16 bytes (or 4 words). This is what I think of the address arrangement, if it is byte addressable.

block0 has addresses: 0, 64, 64*2, 64*3, ...., 64*15

block1: 1, 64+1, 64*2 + 1, 64*3 + 1, .... 64*15 + 1

block2:

...

...

...

...

block63: 63, 64*1 + 63, 64*2 + 63, 64*3 + 63, ... 64*15 + 63

But in the problem given in the figure, the addresses are suggested to be present in a serial order (see the last line saying "maps all addresses between 1200 and 1215") like:

block0: 0,1,2,3,4....15

block1: 16,17,... 31

block2:

...

...

...

...

block63: 1008, 1009,...1023

A cache is a copy of a "chunk" of main memory of a given size that is held in a faster ram closer to the CPU.

In the example given each cache block holds a chunk that is 16 bytes in size and there are a total of 64 blocks available. When a CPU accesses an address if it's not already in cache, the data is copied from main memory into the cache in 16 byte chunks. When the cache load selects a cache block, it ignores the lower 4 bits of the address (for a 16 byte block) then it uses the next 6 bits of the address (for 64 locations) to determine which block to use and the remaining bits of the address are used as a TAG to keep track of the addresses currently cached. It fills the block with the 16 bytes starting at the accessed address with the lower 4 bits zeroed.

The math used in the explanation is based on the physical processes... Dividing by 16 ignores the lower 4 bits. Using the modulo of 64 on the result uses the next 6 bits as an index into the cache. The explanation didn't deal with tagging, but that wasn't really part of the question which was "Which cache block is it using?".

So consider the CPU accesses address 1205 (Using an address that doesn't start at the beginning of a cache block for a little more clarity.):

A 16 bit address 1205 in binary is 0000010010110101.

Ignoring the lower 4 bits, the memory's block address is 1001011

Since the cache is 64 blocks it uses the next 6 bits to select which cache block to use. In this case 001011 is used. This is block number 11.

The remaining bits, 000001, are used in a tag to indicate which memory block is in the cache.

The data is then loaded from the cache into the CPU using the lower 4 bits 0101 as an index (or the 6th byte of the block).

If a subsequent access is for address 1210, or binary 0000010010111010, the tag will match and the cache system won't have to access main memory for the data. It's already in cache and can be used quickly, the CPU just has to use the lower 4 bits of the address 1010 to load the 11th byte from the cache block...

If, however a future access is for address 9403, or binary 0010010010111011, this address also selects cache block 11 so the previous data is overwritten with 16 bytes of data from main memory beginning at 9392 (lower 4 bits zeroed), the new tag for the block is 001001, and the CPU loads the byte from 1011 in the cache block.