CSAPP 第六章 存储器体系

CSAPP 第六章 存储器体系

存储器简介 局部性 高速缓存 编写适合高速缓存的代码 总结 存储器简介 练习 6.2 计算一个磁盘的容量 磁盘容量 = 2 盘片 * 2面 * 10000个柱面=磁道 * 400个扇区 * 512个字节 = 8192000000, 换算成M 大概是 8192000000/1000/1000 = 81

  1. 存储器简介
  2. 局部性
  3. 高速缓存
  4. 编写适合高速缓存的代码
  5. 总结

存储器简介

练习 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 年

局部性

所谓局部性, 有两种局部性, 空间的局部性和时间的局部性. 空间的局部性, 指的就是程序会不断的引用相近的内存空间. 时间的局部性, 指的是不久的将来, 程序还会多次引用一个内存空间. 简单的说, 空间局部性指的是访问一批相近的元素, 时间局部性指的是反复访问同一个元素. 所以标量没有空间局部性.
  1. 重复引用相同变量的程序具有良好的时间局部性
  2. 步长为k的程序, 步长越小, 空间局部性越好. 在内存中大步长跳来跳去的程序空间局部性很差
  3. 对于取指令来说, 循环体越小, 循环次数越多, 局部性越好

练习 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这么一直存放下去的.
  1. 看第一个函数, 其实际上的操作顺序, 是从数组开始然后按照顺序开始一个一个的写成0, 因此空间局部性比较好.
  2. 第二个函数, 是按照每隔3个元素操作一个结构, 再跳到下一个结构开始间隔三个来操作.
  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.
  1. 块偏移CO = 0
  2. 组索引CI = 5
  3. 标记CT = 71
  4. 通过检查表, 可以发现缓存成功命中, 返回的字节是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. 让核心代码反复运行
  2. 尽量减小每个循环内部的缓存不命中数量
对局部变量的反复引用是好的, 因为可能会被放在寄存器中, 具有时间局部性. 对于步长为1的程序来说, 一旦访问的一个地址不被高速缓存命中, 其后的连续块大小的内存会命中高速缓存. 因为所有层次的缓存在读入内存块的时候, 都是连续读入一部分的.

练习 6.17 按照行还是列模式操作二维数组的差别

问题A, 根据程序的执行流程来看:
    很显然, 高速缓存L1有S=2, 有两个块, 分别对应8 字节的间隔块
  1. 对于src[0][0]来说, 由于一开始都不在缓存中, 所以不会命中, 但是会将src[0][0]和src[0][1]的内容都读入到高速缓存的索引0处
  2. 然后会读取dst[0][0], 由于也不再缓存中, 所以会载入, 但是dst[0][0]对应的块也是索引0, 因此会将src[0][0]和src[0][1]驱逐出块
  3. 再读src[0][1], 依然未命中, 存入索引0中
  4. 再读dst[1][0], 这个时候dst[1][0]对应的是索引1的块, 所以未命中, 但是存入索引1处.
  5. 再读src[1][0], 不存在高速缓存中, 会载入, 然而会驱逐出缓存索引1中存储的dst[1][0]和dst[1][1]
  6. 再读dst[0][1], 对应的是块0, 依然未命中, 会把索引0驱逐
  7. 在读src[1][1], 结果会命中一次
  8. 再度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来访问数据, 以此提高空间局部性. 一旦从存储器中获取一个数据对象, 尽可能反复的使用它, 处理完毕之后再切换到下一个, 这样空间局部性最大.
LICENSED UNDER CC BY-NC-SA 4.0
Comment