【存储】存储器结构|缓存
直接映射
直接映射
组索引位数(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的哪个格子存或取数据
上面标红的三个值,就是将内存地址划分
成的三个变量
数据块(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 | int arr[4096]; |
分析这些内存地址如何在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的某个组内
- 如果是
题目
按字节、字、双字、半字寻址
-
机器
字长32位
,容量为16MB
的DRAM存储器,如果cpu按半字
寻址,则请问可以寻址的单元数是?- 这题目可以对照着上图,让每个超单元大小为
半字
,也就是2B=16bit
,所以16MB
的DRAM存储器需要8M*2B
,先不管8M中是否分成8片,但超单元总量
是8M
- 所以:答案为8M=2^23
- 这题目可以对照着上图,让每个超单元大小为
-
机器
字长64位
,容量为128MB
的DRAM存储器,如果cpu按字
寻址,则请问可以寻址的单元数是?- 和上面一样,每个超单元大小为
一个字,
也就是8B=64bit
,所以128MB
的DRAM存储器需要16M*8B
,所以超单元总量
是16M
- 所以:答案为16M=2^24
- 和上面一样,每个超单元大小为
通俗的解释:
字长32位
,那就是32bit,就是4B
。上面说的按字
编址,半字
编址,双字
编址里面的“字”指的就是这个字长
。
(现在假设内存容量为64MB
)
-
假如按
字节
编址,那么,一个内存超单元大小为一个字节
,就是1B=8bit
;那么64MB
的内存空间需要由64M*1B
构成- 所以
超单元总量
为64M
=2^26 - 寻址范围是0~64M-1(此处注意,不是64-1M而是64M减去1),寻址范围的大小是64M;
- 所以
-
假如按
字
编址,那么一个内存超单元大小为一个字
,就是4B=32bit
;那么64MB
的内存空间需要由16M*4B
构成- 所以
超单元总量
为16M
=2^24 - 其寻址范围是0~16M-1;寻址范围大小是16M;
- 所以
-
假如按
半字
编址那就是半个机器字长,就是2B=16bit
; -
假如按
双字
编址,那就是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时间内完成一行的刷新即可
目前常用**“异步刷新”**,因为每行刷新时间有限,所以,刷新操作刻不容缓
因此:“刷新”操作比“读写”操作有更高优先权,因为刷新操作是周期性,强制性完成的;而读写操作才是偶然发生的,读写操作只能在某行“非刷新”期间完成