存储器简介
练习 6.2 计算一个磁盘的容量
磁盘容量 = 2 盘片 * 2面 * 10000个柱面=磁道 * 400个扇区 * 512个字节 = 8192000000, 换算成M 大概是 8192000000/1000/1000 = 8192M 大小, 大概是8GB大小.
练习 6.3 计算扇区的访问时间
平均旋转时间 = 60s/15000RPM/2 = 0.002秒
平均传送时间 = 60s/15000RPM * 1/500平均扇区数 = 0.000008 秒, 寻道时间为8ms, 加起来就是 0.002+0.008+0.000008 = 0.010008秒, 几乎就是10ms
练习 6.4 计算1MB文件的访问时间
这个文件需要的2000个扇区来存储, 正好是1000个扇区的一倍
平均旋转时间 = 60s/10000/2 = 3ms
最好的情况是, 定位到扇区之后, 旋转两圈正好读完, 总时间是 3ms+5ms+ 转两圈的时间 60/10000*2 = 20ms
如果每一个块都不连续, 则读完一个之后还需要读另外一个, 由于读每个块的时间可以忽略不计, 因此总时间是 (3ms+5ms)*2000 = 16秒
练习 6.5 估算SSD的寿命
以470MB/S写, 时间是 128e15/470*1024*1024 = 259724069秒, 换算成年是 8.2 年
以303MB/S的速度写, 时间是 128e15/303/1024/1024/86400/365 = 12.77 年
以20GB每天的速度写: 时间是 128e15/(20*1024*1024*1024*1024)/365 = 15.94 年
局部性
所谓局部性, 有两种局部性, 空间的局部性和时间的局部性.
空间的局部性, 指的就是程序会不断的引用相近的内存空间. 时间的局部性, 指的是不久的将来, 程序还会多次引用一个内存空间.
简单的说, 空间局部性指的是访问一批相近的元素, 时间局部性指的是反复访问同一个元素. 所以标量没有空间局部性.
- 重复引用相同变量的程序具有良好的时间局部性
- 步长为k的程序, 步长越小, 空间局部性越好. 在内存中大步长跳来跳去的程序空间局部性很差
- 对于取指令来说, 循环体越小, 循环次数越多, 局部性越好
练习 6.7 改变循环顺序, 以步长1遍历三维数组
由于三维数组最右边的数字变化最频繁, 所以需要重新排列三个循环变量的位置, 改写如下:
int sumarary3d(int a[N][N][N]) {
int i, j, k, sum = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
sum += a[i][j][k];
}
}
}
return sum;
}
练习 6.8 检查函数的空间局部性
p是一个point类型的数组, 长度1000. point 是一个结构, 包含2个 3个的int数组. 很显然, 在内存中的存放顺序实际上是一个vel, 一个acc这么一直存放下去的.
- 看第一个函数, 其实际上的操作顺序, 是从数组开始然后按照顺序开始一个一个的写成0, 因此空间局部性比较好.
- 第二个函数, 是按照每隔3个元素操作一个结构, 再跳到下一个结构开始间隔三个来操作.
- 第三个函数的跨度就更大了, 是先间隔整个struct长度, 修改三个循环.
所以从空间局部性上来排列的话, 第一个函数空间局部性最好, 第二个次之, 第三个函数空间局部性最差.
高速缓存的结构如下:
如果一共有2的m次方个地址的话, 可以用S长度的一个数组来表示缓存组. 每个组里有E行.
每一行里有1个有效位, m-(b+s)个标记位, 以及B = 2的b次方的字节的高速缓存块.
很显然, 一组E行的高速缓存容量就是E x B, 而全部的缓存大小就是 E x B x S.
如何判断高速缓存中是否存着对应整个机器的某个地址位的元素, 实际上就是把m的地址为翻译成为高速缓存的地址.
简单的说, 就是把地址m(一串二进制位)分成三段, 中间的一段对应数组S的索引, 前边的一段对应标记位, 最后一段对应块的偏移. 这样就可以从高速缓存中取出对应的内容.
练习6.9 高速缓存的参数计算
解释: 主存的存储器地址有32位, 所以一共有2的32次方个地址. 由于C= S*E*B, 可以先计算出来S= 1024/4/1 =
| 高速缓存 | m | C | B | E | S | t | s | b |
|---|---|---|---|---|---|---|---|---|
| 1 | 32 | 1024 | 4 | 1 | 256 | 22 | 8 | 2 |
| 2 | 32 | 1024 | 8 | 4 | 32 | 24 | 5 | 3 |
| 3 | 32 | 1024 | 32 | 32 | 1 | 27 | 0 | 5 |
简单的说, 其实就是将内存通过标记和组索引进行了分块, 然后对应到高速缓存的每个块上, 当然, 高速缓存的块数量是肯定没有内存多的. 可以认为高速缓存中始终存放着一部分内存中的数据.
通过6-30的图, 可以知道内存的多个块, 对应高速缓存中的同一个S组的索引, 这就是高速缓存的原理.
每组只有一行的高速缓存叫做直接映射高速缓存, 其实就是b位的数量的内存块对应1块高速缓存
练习 6.10 填充之后的命中率
在填充之后, 可以看到每次都可以加载的块是4个元素, 因此每次读取的时候, 第一个元素不命中, 其后的三个都会命中, 所以综合命中率是75%.
直接映射高速缓存其实就是将内存按照中间的位数分了组, 低位的位数不断重复对应中间的索引, 可以平均分布高速缓存.
练习6.11 高速缓存问题
用高s位做组索引, 很显然, 内存块的连续片段就是低位的长度, 因为直到改变高位对应的组的时候, 低位不管怎么变, 都对应同一个组. 而这个连续片段长度就是标记t的长度.
组索引长度s=9, 块偏移b=5, m=32, 则 标记长度t = 32-(9+5) = 18位长度, 所以连续块是2的18次方, 足够存放全部的数组块. 但都在同一个块里, 因此不能充分利用高速缓存.
练习6.12 组相联高速缓存
地址宽度为13为位, 8个组的宽度是0-7 即三位, b偏移是0-3 即两位, 所以0和1的位置是CO即块偏移, 然后4-2是组索引, 剩下的部分是高速缓存标记CI.
练习6.13 实际访问的地址与高速缓存的关系
实际的地址二进制是 0 1110 0011 0100, 拆分成对应的高速缓存编号是 01110001 101 00, 可见块偏移是0, 索引是101=5, 标记是71.
- 块偏移CO = 0
- 组索引CI = 5
- 标记CT = 71
- 通过检查表, 可以发现缓存成功命中, 返回的字节是0B.
练习6.14 实际访问的地址与高速缓存的关系
这次的地址是0x0DD5, 即0 1101 1101 0101, 可以知道是 01101110 101 01 , 标记是6E, 索引是5, 块偏移是1.
通过查表可以发现, 索引为5, 标记为6E的有效是0, 所以无法命中.
练习6.15 实际访问的地址与高速缓存的关系
0x1FE4, 即1 1111 1110 0100, 11111111 001 00, 标记是FF, 索引是1, 块偏移是0, 查表很显然, 根本不存在于高速缓存中, 所以也未命中.
练习6.16 列出组3中会命中的地址
先看组三的结构, 组索引是3, 即011, 有效位1 对应的标记是32, 换算成十六进制是 00110010, 则会命中的地址是00110010 011 00-00110010 011 11.
换算成16进制就是0x064C-0x064F.
总的来说, 高速缓存就是将内存地址分组, 然后映射到高速缓存的片上. 总长m-b-s得到的标记位, 就说明把多少字节分成一组.
编写高速缓存友好的代码
让高速缓存得到充分利用的编程方法是:
- 让核心代码反复运行
- 尽量减小每个循环内部的缓存不命中数量
对局部变量的反复引用是好的, 因为可能会被放在寄存器中, 具有时间局部性.
对于步长为1的程序来说, 一旦访问的一个地址不被高速缓存命中, 其后的连续块大小的内存会命中高速缓存. 因为所有层次的缓存在读入内存块的时候, 都是连续读入一部分的.
练习 6.17 按照行还是列模式操作二维数组的差别
问题A, 根据程序的执行流程来看:
- 很显然, 高速缓存L1有S=2, 有两个块, 分别对应8 字节的间隔块
- 对于src[0][0]来说, 由于一开始都不在缓存中, 所以不会命中, 但是会将src[0][0]和src[0][1]的内容都读入到高速缓存的索引0处
- 然后会读取dst[0][0], 由于也不再缓存中, 所以会载入, 但是dst[0][0]对应的块也是索引0, 因此会将src[0][0]和src[0][1]驱逐出块
- 再读src[0][1], 依然未命中, 存入索引0中
- 再读dst[1][0], 这个时候dst[1][0]对应的是索引1的块, 所以未命中, 但是存入索引1处.
- 再读src[1][0], 不存在高速缓存中, 会载入, 然而会驱逐出缓存索引1中存储的dst[1][0]和dst[1][1]
- 再读dst[0][1], 对应的是块0, 依然未命中, 会把索引0驱逐
- 在读src[1][1], 结果会命中一次
- 再度dst[1][1], 又会驱逐, 不会命中.
32字节的高速缓存, 分配了四个组分别对应四块区域, 而且容量也够完全容纳数组, 所以除了一开始的冷不命中之外, 其他的都会命中.
练习 6.18 根据代码判断高速缓存
每个struct的大小是8个字节, 一共有256个8字节的数组, 就是2048个字节, 是按照 struct0 intx, struct0 inty, struct 1 intx, struct 1 inty…..这么排布的.
高速缓存的块大小为16个字节, 整个大小为1024字节, 可见索引一共有64个索引. 整个数组大小2048, 高速缓存1024, 可见是2:1的对应关系, 即一个块对应两个内存中的数据.
这个程序的每一次循环都先读出256个x ,再读出256个y, 所以一共的读取次数是512次.
由于一次可以存储4个地址的空间, 看第一次读x的时候, 由于间隔了一个y的空间, 因此第一次都是未命中, 第二次可以读取到. 所以缓存未命中的比例是50%.
到了读取y的循环, 依然也是跳过了4个,所以未命中的比例也是50%.
综合来看, 整体的命中率是50%, 所以不命中率也是50%.
练习 6.19 根据代码判断高速缓存2
A: 读总数不变, 还是512次
B: 这个要看看读的过程, 都改成了反向, 即限度 grid[0][1], 再读grid[1][1], 实际上相差了16个struct也就是64个位置. 由于高速缓存只有一半大, 很显然 从一半的地方, 即grid[N][0]和grid[N+8][0]的行会互相驱逐. 因此再读完第一遍未命中之后, 会发生抖动, 持续不命中. 不过读y的时候会命中, 因为上一次刚刚加载了对应的区域.
读x的时候不会命中, 读y的时候会命中, 所以总的不命中率就是50%
如果高速缓存有两倍大,足以放下数组的全部, 所以不命中率只会在第一次的时候, 一次能读入4个位置, 每次只有第一个位置冷不命中, 所以不命中率是25%.
练习 6.20 根据代码判断高速缓存2
这个是顺序读, 很显然读写总数依然是512, 但是由于连续读写, 也是只有第一个不命中, 随后3个都会命中, 不命中率就是25%. 如果有两倍大, 也不会再提高命中率, 因为存在冷不命中率.
总结
遇到多个循环的时候, 将注意力集中在最内层循环中, 大部分计算和内存访问都在其中, 合理的编排循环变量.
按照局部性存储的规律, 以步长为1来访问数据, 以此提高空间局部性.
一旦从存储器中获取一个数据对象, 尽可能反复的使用它, 处理完毕之后再切换到下一个, 这样空间局部性最大.
