Memory

RAM

random access是指该存储器的所有内容都可以被读取和写入，且与时间和位置无关。

常见问答：

1. DRAM电容量C的权衡：

   • 大电容容量C的优势：提供更长的数据保持时间
   • 大电容容量C的劣势：工艺实现难度加大，密度降低

2. RAS和CAS均为低电平有效，其中CAS可以作为输出使能信号。

cache

原理

存储系统满足局部性原理：

• 时间局部性——最近的将来要用到的信息很可能就是现在正在使用的信息。主要由循环造成。
• 空间局部性——最近的将来要用到的信息很可能与现在正在使用的信息在空间上是邻近的。主要由顺序执行和数据的聚集存放造成。

cache的访问时间

一级cache（$r$为访问时间比，$e$为访问效率）： $$ T_A=T_{A1}+(1-H)T_{A2}\ r=\frac{T_{A2}}{T_{A1}}\ e=\frac{T_{A1}}{T_A} = \frac{1}{1+(1-H)r} $$ 二级cache： $$ T_A=T_{A1}+(1-H_1)[T_{A2}+(1-H_2)T_{A3}] $$

cache的基本结构

需要解决两个问题：

1. 数据是否在cache中？
2. 如果在cache中，如何找到数据？

首先需要指出主存存储和cache存储的格式：

• 主存存储 主存块号+行内地址
• cache存储 （标签）+cache行号+行内地址

每个主存块和每个cache行储存的数据相同，两者的数据传输以块/行为单位。其中每个cache行的组成如下：数据+标签+有效位。

cache地址映像方式

三种地址映像方式：

• 直接映像: 主存块只可能在cache的某个特定行中
• 全相联映像: 主存块可以放在cache的任意行中
• 组相联映像: 主存块可以放在cache中的n个特定行中，n一般在2到8之间，将这n个行称为一个Cache组。

直接映像

主存标号$i$，cache标号$j$满足以下关系： $$ j = i \mod N \ i = j+Nk(k=0,1..) $$

可以直接写成AB、AC，但是只适用于直接映像。

对于32位内存系统，假设cache每行有$x$byte，cache共$y$行，则低$\log_2x$位为块内地址，中间$\log_2y$位为cache行号，剩下$(32-\log_2x-\log_2y)$位为主存标签。

在这种情况下，由于每行cache的数据有$4x$bit，还有1 bit有效位，所以cache的实际总位数为： $$ y[4x+1+(32-\log_2x-\log_2y)] $$ 注意到cache每行至少储存1个word，所以$x$一定是4的倍数，地址的后两位一定是0。载入cache数据时仍然以word为单位进行载入。

全相联映像

对于32位内存系统，假设cache每行有$x$byte，则低$\log_2x$位为块内地址，剩下$(32-\log_2x)$位作为主存标签。

组相联映像

对于32位内存系统，假设cache每行有$x$byte，cache共$y$行，$z$路组相连，则低$\log_2x$位为块内地址，中间$\log_2(\frac{y}{z})$位作为cache组号，剩下$(32-\log_2x-\log_2(\frac{y}{z}))$位作为主存标签。

直接映像为$z=1$，全相联映像为$z=y$。

cache数据替换

每个cache行有一个有效标志位v，表明“这一行的主存数据副本是有效的”。v=1时cache行才能被命中。

• 复位、刚上电或清空cache时，所有行的v=0。
• cache行刚刚被替换时，对应行的v=1。

当访问一个地址发现其不在cache中时，复制主存块到缓存的行中；当主存块对应的cache行均被占用（有效位为1）时，需要选择一个cache行进行替换。

• 直接映像 只有一行可以被替换，不用选
• 组相联/全相联
  • 随机法(Random)：在cache中随机选择一个主存块
  • 先进先出法(FIFO, First-In First-Out)：选择一个集合中最先进入cache中的主存块(即存在时间最长的块)，类似于数据结构中的队列。
  • 最近最少使用法(LRU, Least recently used)：替换cache中最近最少被使用的主存块

cache数据更新

当需要向层次结构存储器写入数据时，需要考虑将数据存入cache还是主存的问题。

write through

指高速缓存和主存都写入。

write back

先将数据写入Cache中，之后在该块要被替换出Cache时才将数据写到主存储器中。

在cache中会添加一个脏位（dirty bit）。脏位为1意味着cache里面的数据是更新后的，而主存储器里面的数据是过时的。不一致的数据在被替换时一定要写回主存中。

cache性能评估

• 强迫性缺失：第一次访问主存储器中的某一个数据块，只能先从主存储器将数据加载到cache中。
• 容量缺失：由于cache容纳不了程序所需的所有主存块而引起的缺失。
• 冲突缺失：在组相联或者直接映像中，多个的主存块竞争同一个cache组时引起的缺失，也称碰撞缺失。