一、按字节（字）编址、寻址

首先应该弄懂一个概念叫：按字节编址或寻址。
指的是存储空间的最小编址单位是字节(byte)，也就是说一个地址对应1 byte的内存空间。同理，按字编址，是指存储空间的最小编址单位是字(word)。

二、Memory Size、Block Size、Cache Size

以下举例均为(Direct Mapped Cache)。
Memory Size：就是内存的大小，最小单位根据（一）中所描述的最小编址(寻址)单位而定。
Cache Size：就是cache的大小，最小单位也是根据（一）中所描述的最下编址(寻址)单位而定。
Block Size: Block可以理解为一种组织内存的方式，将内存一段一段地划分开来形成许多Blocks。假如一个Block大小为4 words，那么一个Block就能存4 words=16 bytes的数据。

二、offset、index、tag

如图，CPU根据地址在内存中寻找数据时，需要根据一个32位的cache地址（这里的cache地址非内存中的地址，其中的Tag来搜索。假定cache_size为1 KiByte，block_size为4 words，内存最小寻址单元是1 byte，则有如下地址划分：

下面我们来讨论每一个数据是如何得到的：

1、Offset的确定

要确定offset的位数，需要知道一个block的size大小。上述一个block的size为16 bytes，说明一个block能存16 bytes 的数据，每一个byte对应一个地址。因为$16=2^4$，所以要表示16个byte的地址只需要4个比特，第一个block能储存的地址从0000到1111。当第1个block被存满时，下一个字节的存储地址又重新从0000开始，第二个block储存的地址范围从原来的00000-01111变成了10000-11111。

2、Index的确定

首先我们知道，index指的是cache中block的序号，所以Index数就等于block的个数。承接上面的Offset，根据block的size我们知道了Offset占地址的低4比特(address[3:0])。当每一个block被存满时，都会向第5位进1，即block的Index+1——结合下图理解更加直观。而我们知道，cache_size=1 KiByte，而block_size=16 bytes，所以将两者相除就能得到cache中的block数：$1024bytes/16bytes=64$个，因为$64=2^6$，所以要表示64个block只需要6位比特即可。所以Index需要6位，即地址的4到9位(address[4:9])。

3、Tag的含义

因为一个block中能存储16 bytes的数据，所以不同的两个数据有可能存在同一个block中，那么怎么知道我所寻址的数据就是我想要的数据呢，这时候就要用到tag来作为区分标记。因为每一个地址都是独一无二的，所以在32位地址中，后10位分别用作index和offset后，前22位就可以拿来当作确定数据唯一性的标签。

三、例题

下面分享几道例题帮助大家理解。

【例1】常规offet、index、tag、block计算

For a direct-mapped cache of 2048 bytes, assume that the block size is 256 bytes, the main memory address is 32-bit long, which is in unit of byte. We can know that offset is from bit_____(left) to______bit (right), index is from bit____(left) to bit______(right), tag is from bit_____(left) to bit______(right), assuming that the least significant bit is bit 0. For address 0x12345678, it should be in which block?______.

solution:
我们要得到index是从几位到几位，首先要知道offset占几位。由题意得，block_size是256 bytes，即$2^8$，所以offset占地址的0-7比特位。
因为cache_size=2048 bytes，所以cache中包含$2048/256=2^3$个blocks。所以index总共占地址的8-10比特位。
剩下的9-31位均为tag。
最后一个空有两种做法：
方法一： 直接将地址转换成二进制形式：0001_0010_0011_0100_0101_0110_0111_1000.找到其中的8-10位:$110_{(2)}=6$. 所以地址0x12345678在第6个block。
方法二： 如果地址是以十进制形式给出：305,419,896，先用地址除以block_size，得到在main memory中block的index：$305,419,896/256=1,193,046$，再用得到的商模上cache中block数的比特数8：$1,193,046\equiv 6(mod8)$.所以地址0x12345678在cache中第6个block。
综上：答案为：7, 0, 10, 8, 31, 11, 6.

【例2】提高题

For a direct-mapped cache design with a 32-bit address, the following bits of the address are used to access the cache.

(1)What is the cache block size (in words)?
(2)How many entries does the cache have?
(3)Starting from power on, the following byte-addressed cache references are recorded.

Fill in blanks (show index and tag in decimal, and indicate replace using Y/N).

(4) What is the hit ratio?
(5) List the final state of the cache, with each valid entry represented as a record of <index, tag, data>.

Solution:
(1) 8
Since the unit of the block-size is in words, the Byte Offset is 2 bits. Therefore, the size of cache block is $2^{5-2}=2^3=8$ words.
(2) 32
Since there 5 bits for Index, there are $2^5=32$ entries in cache.
(3)

(4) 33.33%
There are 4 hits in 12 references, so hit ratio = 4/12= 33.33%
(5)