The Hardware Software Interface Section 7 Memory and Caches
课程主页：https://courses.cs.washington.edu/courses/cse351/16sp/
课程资料：
实验部分：https://github.com/vuquangtrong/HW-SW_Interface_Course
实验说明：https://courses.cs.washington.edu/courses/cse351/13sp/lab-0.html
课件：http://academictorrents.com/details/b63a566df824b39740eb9754e4fe4c0140306f4b
课程视频：https://www.bilibili.com/video/BV1Zt411s7Gg?from=search&seid=8781593976070799647
这次回顾第七部分，这部分介绍了内存和缓存。
第7节：内存和缓存
缓存基础知识
执行时间和SIZE的关系
int array[SIZE];
int A = 0;
for (int i = 0 ; i < 200000 ; ++ i) {
for (int j = 0 ; j < SIZE ; ++ j) {
A += array[j];
}
}
之所以产生上述现象是由于缓存的原因，后续会详细介绍。
问题：处理器-内存瓶颈
处理器等待内存的时间过久：
解决方法是增加缓存：
缓存
- 英文定义：存放粮食、武器和/或财宝的隐藏空间。
- CSE定义：访问时间很短的计算机内存，用于存储频繁或最近使用的指令或数据（i-cache、d-cache）
- 更普遍地， 用于优化具有不同特性（网络接口缓存、I/O缓存等）的系统元素之间的数据传输。
一般缓存机制
Hit
请求的数据在缓存中：
Miss
请求的数据不在缓存中，所以要将内存中的数据替换缓存中的数据：
总结
局部原则
为什么缓存会起作用
- 局部性原则：程序倾向于引用邻近于其他最近引用过的数据项和指令。
- 时间局部性：
- 最近引用的项可能会在不久的将来再次引用
- 空间局部性：
- 地址接近的项往往会在比较接近的时间内被引用
局部性例子
sum = 0;
for (i = 0; i < n; i++)
sum += a[i];
return sum;- 数组$a$有很好的空间局部性，$\text{sum}$有很好的时间局部性
内存层次结构
缓存不命中的代价
比较99%命中率和97%命中率的平均读取时间：
- 97%：$1+0.03\times 100=4$
- 99%：$1+0.01\times 100=2$
这说明99%的命中率比97%命中率好两倍，所以我们关注不命中率。
缓存性能度量
- 不命中率
- 在缓存中找不到的内存引用的比例（丢失/访问）$\text{= 1 – hit rate}$
- 典型数字（百分比）：
- L1为3-10％
- 对于L2来说可能很小（例如<1％），具体取决于大小等。
- 命中时间
- 从高速缓存传送一个字到CPU所需时间
- 包括确定行是否在缓存中的时间
- 典型数字：
- L1需要4个时钟周期
- L2需要10个时钟周期
- 从高速缓存传送一个字到CPU所需时间
- 不命中处罚
- 因为错过而需要额外的时间
- 主存通常需要50-200个周期（趋势：正在增加！）
内存层次结构
- 硬件和软件系统的一些基本和持久特性：
- 更快的存储技术几乎总是每字节成本更高，容量更低
- 内存技术速度之间的差距正在扩大
- 适用于：寄存器$\leftrightarrow$高速缓存、高速缓存$\leftrightarrow$DRAM，DRAM$\leftrightarrow$磁盘等。
- 写得好的程序往往显示出良好的局部性
- 这些特性彼此完美互补
- 提出了一种组织内存和存储系统的方法，称为内存层次结构
- 内存层次结构的基本思想：
- 每个级别$k$用作以下较大、较慢的级别$k+1$的高速缓存。
- 为什么内存层次结构工作？
- 由于局部性，程序访问级别$k$的数据的频率比访问级别$k+1$的数据的频率高。
- 因此，级别$k+1$的存储更慢，从而更大且每比特便宜。
- 想法：内存层次结构创建了一个庞大的存储池，其成本与最底层的廉价存储相同，但以最上层的快速存储速度向程序提供数据。
例子
英特尔i7内存层次结构
缓存组织
高速缓存$(S,E,B)$的通用组织
高速缓存读取
利用上图的结构进行高速缓存读取，索引组判断属于哪个组，块偏移确定了$B$个字节的数据块中的字偏移，标记位确定标记。
例子
考虑$E=2$的情形：
首先通过$0…01$确定是第二个缓存，然后比较tag：
最后$100$确定偏移：
再来看一个具体例子：
如果读取的缓存中没有内容或者有效位为0，则记为miss，否则为hit。
常规缓存概念：缓存未命中的类型
- 冷未命中
- 由于缓存为空而发生。
- 冲突未命中
- 大多数高速缓存将级别$k + 1$的块限制为级别$k$的块位置的一小部分子集。
- 例如。 第$k + 1$级的块$i$必须放置在第$k$级的块（$i \mod 4$）中。
- 当级别$k$高速缓存足够大，但是多个数据对象都映射到同一级别$k$块时，就会发生冲突未命中。
- 例如。 每次引用块0、8、0、8、0、8，…都会未命中。
- 大多数高速缓存将级别$k + 1$的块限制为级别$k$的块位置的一小部分子集。
- 容量未命中
- 当活动高速缓存块的集合（工作集）大于高速缓存时发生。
写
- 存在多个数据副本：
- L1，L2，L3，主存，磁盘
- write-hit怎么办？
- Write-through（立即写入内存）
- Write-back（将写操作推迟到内存中，直到替换行为止）
- 需要一个dirty bit（行是否与内存不同）
- 发生写缺失该怎么办？
- write-miss（加载到缓存中，更新行在缓存中）
- 如果有更多写入该位置的信息，则很好
- No-write-allocate（直接写入内存，不加载到缓存中）
- write-miss（加载到缓存中，更新行在缓存中）
- 典型
- Write-through + No-write-allocate
- Write-back + Write-allocate
考虑缓存的程序优化
内存层次结构优化
- 编写具有局部性的代码
- 空间局部性：连续访问数据
- 时间局部性：确保访问同一数据的时间不相隔太远
- 如何实现？
- 算法选择合理
- 循环变换
矩阵乘法
/* ijk */
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
sum = 0.0;
for (k=0; k<n; k++)
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
} 注意按这个方法写效率较低，从内存布局即可看出：
更换循环次序，一共可以得到6种循环，效率如下：
这里解释下为什么kij的效率较高，首先看代码：
/* kij */
for (k=0; k<n; k++) {
for (i=0; i<n; i++) {
r = a[i][k];
for (j=0; j<n; j++)
c[i][j] += r * b[k][j];
}
}接着看示意图：
说明该代码的空间局部性较好。
高速缓存未命中的分析
- 假设：
- 矩阵元素是双精度
- 高速缓存块 = 8 doubles
- 缓存大小$C << n$（比$n$小得多）
- 第一次迭代：
- $n / 8 + n = 9n / 8$次未命中
- 总未命中次数：
- $9n / 8 n^2 =(9/8) n^3$
分块矩阵乘法
c = (double *) calloc(sizeof(double), n*n);
/* Multiply n x n matrices a and b */
void mmm(double *a, double *b, double *c, int n) {
int i, j, k;
for (i = 0; i < n; i+=B)
for (j = 0; j < n; j+=B)
for (k = 0; k < n; k+=B)
/* B x B mini matrix multiplications */
for (i1 = i; i1 < i+B; i++)
for (j1 = j; j1 < j+B; j++)
for (k1 = k; k1 < k+B; k++)
c[i1*n+j1] += a[i1*n + k1]*b[k1*n + j1];
}图示如下：
未命中的分析
- 假设：
- 高速缓存块 = 8 doubles
- 缓存大小$C << n$（比$n$小得多）
- 三个分块可以放入缓存，$3B^2<C$
- 第一次（块）迭代：
- 每个方块$B\times B/ 8=B^2/8$次未命中
- 总共：$2n / B * B^2 / 8$ = $nB/4$（忽略矩阵c）
- 总共未命中：
- $nB/4 * (n/B)^2 = n^3/(4B)$
在缓存中的示意图：
分块总结
- 无分块：$(9 / 8)^{*} n^{3}$
- 分块：$1 /(4 B)^{*} n^{3}$
- 建议选择最大的$B$，使得$3B^2<C$
- 产生巨大差异的原因：
- 矩阵乘法具有固有的时间局部性：
- 输入数据：$3n^2$，计算$2n^3$
- 每个数组元素使用$O(n)$次！
- 但是程序必须正确编写
- 矩阵乘法具有固有的时间局部性：