直接映射

直接映射

直接映射宏观图

  • 组索引位数（set index）表示去cache中的哪个组找
  • 一个组内可以有一行、可以有多行
  • 如果一个组内只有一行，找到了组号，再确定下tag号和有效位valid就能知道：数据是否被缓存在cache中。再根据偏移位数，拿出数据即可【一组一行是直接映射】
  • 如果一组内有多行，找到了组号，还需要顺序逐个对比tag和有效位……逐个对比地址的tag号和某行的tag号是否相同，若相同并且有效，再拿数据【一组有多行是组相联】

组内某行的内部结构

可以看到：

  • 一个组（set）中包含：有效位（valid），标志位数（tag），一个数据块（Cache block）
  • 其中如图的Cache block一共有8个格子【0~7号格子】，每一个格子上，可以放一个字节【先不管为啥直接放一个字节】！！！

所以，一个数据块Cache block一共可以放8个字节

又因为，0~7这8个数，只要3位二进制就能表示

所以在内存地址的后三位叫“Block offset”【叫偏移位数】用来表示用Cache block的哪个格子存或取数据

上面标红的三个值，就是将内存地址划分成的三个变量

image-20220701124454980

数据块（Cache block）里面的单位是字？还是字节？

得看具体要求，有的题目写“每个数据块可以放4字”，其实就等价于“每个数据块可以放16字节”，从而得到B=16，偏移位数b=4

说白了，就是懒……像下面题目，浮点数本身就占用4字节，一个数据块最大装入16字节

大家都提出个共因数4，变成浮点数1字，一个数据块最大装入4字

比如：某个处理器16KiB的cache，包含256个数据块，每个数据块16字。地址宽度32位

可以得到：

  • 组索引位=8【256=2^8】
  • 数据块16字，但有16*4=64字节【64=2^6】，偏移位=6
  • 标志位=32-(8+6)=18

所以内存地址划分为：标志18位（31~14位）----组索引8位（13~6位）-----偏移6位【块内偏移4位（5~2位） 和 字节2位（1~0位）】

如果数据块按字划分，只有16字，那只需4位偏移即可。但实际上需要多出2位表示一字四字节

​

Cache容量计算

公式：总数据块数*（单个数据块容量+标签位+有效位）

【只要有一个数据块，就对应一个对应的有效（valid）位和标签（tag）位】

例如：假设64位存储地址，使用直接映射【暗示一组一个数据块】，如果数据大小为16KB，每个数据块4字大小，问cache容量多大【用bit表示】

解：

  • 求偏移位数b，因为数据块4字【每个字4字节】，所以每个数据块有16Bytes，B=16，偏移位数b=4
  • 数据大小为16KB，则需要16KB/16=1K个数据块，对应S=1K，组索引s=10
  • 。。。。。。。。。。。所以标签位t=64-(10+4)=50位

所以根据公式

  • sum=1K * (16*8 + 50 + 1) =179Kb

地址映射到cache组号

公式：组号 =（数据块地址） mod (cache中组数)

数据块地址 = 字节地址/数据块字节数

例如：cache有64个组，每数据块大小为16字节，问字节地址为1200的映射到哪个组号？

先求数据块地址 = 1200 / 16 =75

再求组号= 75 / 64

抖动与冲突不命中

P431

Suppose that floats are 4 bytes, that x is loaded into the 32 bytes of contiguous memory starting at address 0, and that y starts immediately after at address 32. For simplicity, suppose that a block is 16 bytes

the cache consists of two sets, each set has one line, for a total cache size of 32 bytes. We will assume that the variable sum is actually stored in a CPU register and thus does not require a memory reference. Given these assumptions, each x[i] and y[i] will map to the identical cache set

题目中没说内存地址长度，假设为16位，够长~

其中cache为2组，所以s=1;每个数据块有16字节，所以b=4

若y从地址32开始，这些数组的映射关系如下：

​ 标志Tag 组索引Set 偏移b 标志Tag 组索引Set 偏移b

x0 0 0 0000 y0 1 0 0000
x1 0 0 0100 y1 1 0 0100
x2 0 0 1000 y2 1 0 1000
x3 0 0 1100 y3 1 0 1100

x4 0 1 0000 y4 1 1 0000
x5 0 1 0100 y5 1 1 0100
x6 0 1 1000 y6 1 1 1000
x7 0 1 1100 y7 1 1 1100

很明显，x[0]~x[3]与y[0]~y[3]会对组0进行争抢

x[0]未命中后，会将x[0]~x[3]都缓存到cache中的组0

接着轮到y[0]，y[0]未命中后，y[0]~y[3]都缓存到cache中组0，这个操作会覆盖原来的x[0]~x[3]；

接着轮到x[1]，x[1]未命中后，会将x[0]~x[3]都缓存到cache中的组0，又把y[0]~y[3]覆盖了。

如此反复下去，只会不断的覆盖原来的数据，不会发生命中，这就是抖动

解决方法：定义数组x大小不是x[8]而是x[12]，保证让y[i]与x[i]不同时映射到同一组

若y从地址48开始，这些数组的映射关系如下：

​ 标志Tag 组索引Set 偏移b 标志Tag 组索引Set 偏移b

x0 00 0 0000 y0 01 1 0000
x1 00 0 0100 y1 01 1 0100
x2 00 0 1000 y2 01 1 1000
x3 00 0 1100 y3 01 1 1100

x4 00 1 0000 y4 10 0 0000
x5 00 1 0100 y5 10 0 0100
x6 00 1 1000 y6 10 0 1000
x7 00 1 1100 y7 10 0 1100

这样的好处是，将x[0]~x[3]与y[0]~y[3]错开，分别使用不同的组，不会因为争抢同一个组而发布抖动

例题

P433

考虑下面代码，它运行在cache形式为(S,E,B,m)=(512,1,32,32)【512个组set，每组一行，一个数据块装32字节，内存地址32位】

1
2
3
int arr[4096];
for(i=0;i<4096;i++)
	sum+=arr[i];

分析这些内存地址如何在cache中分布

分析：

因为一个块装32字节，一组一行【一行对应一个数据块】，所以一组装32字节

int是4字节，所以一组装32/4=8个int

所以全部的arr需要4096/8=512个组

解：

  • 块内32字节，对应B=32，b=5【5位二进制可以表示32个】
  • 一共512个组，对应S=512，s=9
  • 按公式:t=m-(b+s)，所以t=32-(5+9)=18

按直接映射格式：tag 18位----set 9位----块内偏移 5位

将内存32位地址按格式划分，得到下面表格

tag位 set位 块内偏移 内存地址 组号 arr下标
0000……0【18个0】 0000 0000 0 0 0000 0 0 0
0000……0【18个0】 0000 0000 0 0 0100 4 0 1
0000……0【18个0】 0000 0000 0 0 1000 8 0 2
0000……0【18个0】 0000 0000 0 0 1100 12 0 3
0000……0【18个0】 0000 0000 0 1 0000 16 0 4
0000……0【18个0】 0000 0000 0 1 0100 20 0 5
0000……0【18个0】 0000 0000 0 1 1000 24 0 6
0000……0【18个0】 0000 0000 0 1 1100 28 0 7
0000……0【18个0】 0000 0000 1 0 0000 32 1 8
0000……0【18个0】 0000 0000 1 0 0100 36 1 9
0000……0【18个0】 0000 0000 1 0 1000 40 1 10
………… …………
………… …………
0000……0【18个0】 1111 1111 1 1 1100 16380 511 4095

可以看到：

  • arr[0]~arr[7]属于组0
  • arr[8]~arr[15]属于组1
  • …………
  • arr[4088]~arr[4095]属于组511【4096*4得到字节地址x，x再除以数据块字节数32，得到数据块地址y，y再 mod 组数512，得到组号511】

因为512个组刚好可以装完4096个int，所以tag位始终没变化，如果是arr[65536]呢？

那么从arr[4096]开始tag就要变成1，并且arr[4096]~arr[4103]与arr[0]~arr[7]共用组号0，他们两波，通过tag来区分

tag set 偏移 内存地址 组号 arr下标
0000 0000 0000 0000 01 0000 0000 0 0 0000 16,384 512 4096

块、行、组

  • block，块，是一个固定大小的包，用来上下两层存储器之间传输数据
  • line，行，人为设定的，cache中的一个空串，行存储了：“块”、“有效位”、“标记位”
  • set，组，一行或多行的集合。
    • 直接映射一组只有一行；在直接映射里面，组可以等价于行
    • 组相联或全相联，一组有多行；组和行不能乱用

因为行存储了：“块”、“有效位”、“标记位”。 有时某些场合下，在计算cache容量时，往往忽略了“有效位”和“标记位”，把“行”与“块”就等价了【因为真正存储目标数据的只有“块”】

偏移位、有效位、标志位

  • 偏移位，block index，看英文名就很清楚了，它是在block里面用来区分不同数据的下标，因为一“块”可以装入多个字节，就需要用下标来指定，数据被装入到块内哪个部分
  • 有效位，valid ，当刚开机时，所有的valid都设置为0，避免一些脏数据。
  • 标志位，tag，用来确定要找的目标数据是否在cache的其中一个依据
    • 如果是全相联，就只能根据标志位判断数据是否在cache中
    • 如果是直接映射或组相联，先根据组索引号，找到对应组，再判断数据是否在cache的某个组内

题目

按字节、字、双字、半字寻址

回答时会用到

  1. 机器字长32位，容量为16MB的DRAM存储器，如果cpu按半字寻址，则请问可以寻址的单元数是？

    • 这题目可以对照着上图，让每个超单元大小为半字，也就是2B=16bit，所以16MB的DRAM存储器需要8M*2B，先不管8M中是否分成8片，但超单元总量是8M
    • 所以：答案为8M=2^23

  2. 机器字长64位，容量为128MB的DRAM存储器，如果cpu按字寻址，则请问可以寻址的单元数是？

    • 和上面一样，每个超单元大小为一个字，也就是8B=64bit，所以128MB的DRAM存储器需要16M*8B，所以超单元总量是16M
    • 所以：答案为16M=2^24

通俗的解释：

字长32位，那就是32bit，就是4B。上面说的按字编址，半字编址，双字编址里面的“字”指的就是这个字长。

（现在假设内存容量为64MB）

  1. 假如按字节编址，那么，一个内存超单元大小为一个字节，就是1B=8bit;那么64MB的内存空间需要由64M*1B构成

    • 所以超单元总量为64M=2^26
    • 寻址范围是0~64M-1（此处注意，不是64-1M而是64M减去1），寻址范围的大小是64M；

  2. 假如按字编址，那么一个内存超单元大小为一个字，就是4B=32bit;那么64MB的内存空间需要由16M*4B构成

    • 所以超单元总量为16M=2^24
    • 其寻址范围是0~16M-1；寻址范围大小是16M；

  3. 假如按半字编址那就是半个机器字长，就是2B=16bit；

  4. 假如按双字编址，那就是8B=64bit；

数据寄存器、地址寄存器

地址寄存器：用来存放cpu取、存内存单元的地址

数据寄存器：用来存放cpu取、存内存单元的数据

地址寄存器位数：就是超单元总量8M/64M……

数据寄存器位数：超单元自身的大小1B/2B/3B……

举例

机器字长32位，容量为16MB的DRAM存储器，如果cpu按半字寻址，问地址寄存器位数、数据寄存器位数？

  • 这题目可以对照着上图，让每个超单元大小为半字，也就是2B=16bit，所以16MB的DRAM存储器需要8M*2B，先不管8M中是否分成8片，但超单元总量是8M
  • 8M=2^23，23位就是地址寄存器位数
  • 2B=16位，16位就是数据寄存器位数

再举例

机器字长64位，容量为128MB的DRAM存储器，如果cpu按字寻址，问地址寄存器位数、数据寄存器位数？

  • 和上面一样，每个超单元大小为一个字，也就是8B=64bit，所以128MB的DRAM存储器需要16M*8B，所以超单元总量是16M
  • 16M=2^24，24位就是地址寄存器位数
  • 8B=64位，64位就是数据寄存器位数

DRAM

因为DRAM电荷只能维持1~2ms，人为设置2ms为刷新周期，每隔2ms必须刷新一次全部DRAM芯片的全部单元。

所谓刷新，就是将单元内数据读出，再重新写回到单元内

其中，刷新操作有集中刷新、分散刷新、异步刷新

集中刷新：

  • 设置一个固定的时间段，在这一时间段内，对全部的DRAM同步地将每个DRAM每个单元刷新
  • 缺点：此时间段cpu无法访问DRAM

分散刷新：

  • 每次对某行进行存取操作后，再对这行进行刷新
  • 缺点：因为刷新本身就是一次存取操作，所以，cpu每次存取数据时，进行一次存取操作，随后的刷新操作又进行了一遍存取操作。增加了整个访问周期

异步刷新：

  • 因为整个DRAM每次只能维持2ms，将2ms/行数，可以就是留给一行的刷新时间t，只要每一行在自己的t时间内完成一行的刷新即可

目前常用**“异步刷新”**，因为每行刷新时间有限，所以，刷新操作刻不容缓

因此：“刷新”操作比“读写”操作有更高优先权，因为刷新操作是周期性，强制性完成的；而读写操作才是偶然发生的，读写操作只能在某行“非刷新”期间完成

DRAM单元

DRAM单元

DRAM超单元

DRAM超单元

DRAM超单元2

DRAM芯片(chip)

DRAM芯片(chip)

DRAM模块

DRAM模块