存储器层次结构

存储技术

随机访问存储器

​ 随机访问存储器分为动态和静态两类，静态RAM(SRAM)比动态RAM(DRAM)要快的多，并且更加昂贵。SRAM一般应用于高速缓冲器，而DRAM一般用于主存,帧缓冲区。

​ 传统的DRAM中的单元(位)被分为$d$个超单元(supercell)，每个超单元由$w$个DRAM单元组成，一个$d×w$的DRAM总共存储了$dw$位的信息。超单元被组成一个$r$行$c$列的长方形阵列，每个超单元有形如$(i,j)$的地址，这里$i$表示行，$j$表示列。

​ 每个DRAM芯片被连接到某个被称为内存控制器(memory controller的电路，这个电路可以一次传送$w$位到每个DRAM芯片或者从每个DRAM芯片传出$w$位。读$(i,j)$中读$i$的请求成为$RAS(Row Access Strobe)$请求，列地址j称为$CAS(Colum Access Strobe)$

磁盘存储

​ 磁盘由盘片$(platter)$组成。每个盘面有两面成为表面$(surface)$。盘片中央有一个可以旋转的主轴$(spindle)$，它使得盘片以固定给的旋转速率旋转，通常是5400~15000转每分钟$(Revolution Per Minute,RPM)$。

​ 如上图所示，磁盘的表面由一组称为磁道(track)的同心圆组成，每个磁道被划分为一组扇区(sector)。扇区之间由一些间隙(gap)，这些间隙不存储数据位，间隙用来表示扇区的格式化位。磁盘控制器维护着逻辑块和实际磁盘扇区之间的映射关系。它会把一个逻辑块号翻译成(盘面，磁道，扇区)的三元组。

​ CPU使用一种称为内存映射I/O的即使来想I/O设备发射命令。，下图

​ 在磁盘控制器收到来自$CPU$的读命令的时候，它将逻辑块号翻译成一个扇区地址，读取该扇区的内容。然后又将这些内容传送到主存(这一部分不需要$CPU$的干预)。

​ 在DMA传送完成之后，磁盘扇区的内容被安全地存储在主存之后，磁盘控制器通过给CPU发送一个中断信息来通知CPU。

固态硬盘

​ 固态硬盘(Solid State Disk,SSD)是一种基于闪存的存储技术，SSD封装插到I/O总线上标准硬盘插槽。一个SSD封装由一个或多个闪存芯片和,闪存翻译层组成，闪存芯片代替传统旋转磁盘中的机械驱动器，而闪存翻译层是一个硬件/固件设备，扮演与磁盘控制器相同的角色，将对逻辑块的请求翻译成对底层物理设备的访问。

​ 数据是以页为单位进行读写的，只有在一页所属的块整个被擦除之后，才能写这一页。不过一旦一个块被擦除了，块中的每一个页都可以不需要再进行擦除就写一次。

局部性

​ 这主要包括对程序数据引用的局部性和取指令的局部性。局部性是指时间局部性和空间局部性。

对程序数据引用的局部性

​ 这一部分直接上代码。

​ 数组是以行优先的模式存储的，对于上述函数。具有步长为1的引用模式，对于a数组具有空间局部性，但是时间局部性很差，因为每个元素只访问一次。对于sum具有很好的时间局部性。

取指令的局部性

​ 因为程序指令是存放在内存中的, CPU必须取出(读出)这些指令,所以我们也能够评价一个程序关于取指令的局部性。例如,图6-18中for循环体里的指令是按照连续的内存顺序执行的,因此循环有良好的空间局部性。因为循环体会被执行多次,所以它也有很好的时间局部性。

局部性小结

• 重复引用相同变量的程序有良好的时间局部性。
• 对于具有步长为k的引用模式的程序,步长越小,空间局部性越好。具有步长为1的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。
• 对于取指令来说,循环有好的时间和空间局部性。循环体越小,循环迭代次数越多,局部性越好。

存储器层次结构

​ 由于局部性原理，并且不同存储技术的访问时间差异，速度较快的技术每字节的成本要比速度较慢的技术高，并且容量很小，CPU和主存之间的速度差距增大，自然而然，这种性质导致了存储器层次结构的诞生。

存储器层次中的缓存

​ 一般而言,高速缓存(cache,读作”cash”)是一个小而快速的存储设备,它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存(caching,读作”cashing”).

​ 一般而言，层次结构较低层的设备的访问时间较长，因此为了补偿这些较长的访问时间，倾向于使用更大的块。

• 缓存命中

  当程序需要第$k+1$层的某个数据对象$d$时，它首先在当前存储在第k层的一个块中查找$d$。如果$d$刚好缓存在第$k$层中，就成为缓存命中

• 缓存不命中

  另一方面，如果第$k$层中没有缓存数据对象$d$，那么就是缓存不命中。当发生缓存不命中的时候，需要从$k+1$层缓存中取出包含$d$的那个块，放到$k$层，如果k层满了的话。那么就会覆盖现存的一个块(过程称为替换($replacing$)或者驱逐$(evicting)$),被驱逐的块称为牺牲块$(victim block)$。决定替换哪个块是由缓存的替换策略决定的。

• 缓存不命中类型

  • 冷不命中：本身就没数据
  • 冲突不命中：限制性的放置策略，比如访问块0，8，0，8
  • 容量不命中：缓存太小了，不能处理某个工作集

存储层次结构概念小结

高速缓存存储器

​ 考虑一个计算机系统，其中每个存储器的地址为$m$位。形成$M=2^m$个不同的地址，如下图所示，这样子的一个机器的高速缓存被组织成$E$个高速缓存行>($cache$ $line$).每个行是由一个$B=2^b$字节的数据块($block$)组成，一个有效位($valid$ $bit$)指明这个行是否包含有意义的信息，有$t=m-(b+s)$个标记位($tag$ $bit$)，它们唯一表示存储在这个高速缓冲行中的块。

​ 一般而言，高速缓存的结构可以用元组$(S,E,B,m)$来描述。高速缓存的大小$C$指的是所有块大小的和。标记位和有效为不包括在内。.因此$C=S×E×B$.

​ 下图对所有的符号进行了一个简单的总结。

直接高速映射缓存

​ 根据每个组的高速缓存行数E，高速缓存被分为不同的类。每个组只有一行$(E=1)$的高速缓存被称为直接映射高速缓存

​ 读取缓存一般分为三步

1. 组选择

1. 行匹配
2. 字抽取

当不命中时，就要进行行替换，在直接高速映射缓存中，替换策略十分简单，用新去除的行替换当前的行。

​ 下面举一个简单的例子，假设$(S,E,B,m)=(4,1,2,4)$换句话说，高速缓存有4个组，每个组一行，每个块两个字节，地址是4位的。那么对应来说组索引位$s$占两位。块偏移位$b$占一位，标记为$t$占1位。那么列举一下这个地址空间：

组相连高速缓存

​ 直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行，这个限制。组相连高速缓存$(set$ $associative$ $cache$)允许每个组都保存有多于一个的高速缓存行。一个$1<E<\frac{C}{B}$。

组相连高速缓存中的行匹配和字选择比较复杂，过程如下

组相连高速缓存中不命中时的行替换，这之后采用一些替换策略

全相连高速缓存(fully associative cache)

​ 这个时候$E=\frac{C}{B}$,S默认为0，因为只有一个组，这样子的话地址默认被划分为标志位和偏移位即可，这里就不赘述了。

• 组匹配

• 行匹配和字匹配

有关写的问题

1. 写命中($write$ $hit$):写一个已经缓存了的字

   $write-through$:直写，立刻将修改了的数据刷新回磁盘。

   $write-back$:写回，只有当替换算法要驱逐这个块的时候，再写回磁盘，这需要一个修改位。

2. 写不命中($write$ $miss$)

   $write-allocate$:被称作写分配，加载相应的第一层中的块到高速缓存中，然后更新这个块。

   $not-write-allocate$：写不分配，避开高速缓存。直接把这个字写到低一层中。

高速缓存的性能影响

• 不命中率：在一个程序执行或程序的一部分执行时间，内存引用不命中的比率。$\frac{不命中数量}{引用数量}$
• 命中率：命中的内存引用比率。它等于($1-$不命中率)
• 命中时间：从高速缓存传送一个字到CPU所需的时间,包括组选择、行确认和字选择的时间
• 不命中处罚：由于不命中而需要的额外时间

编写高速友好代码

• 让最常见的情况运行得快
• 尽量减少每个循环内部的缓存不命中数量
• 读带宽:单位一般是Mbps，指的固定时间内，一个程序从存储系统中读数据的速率(理想情况)
• 吞吐量:单位也是Mbps，指的固定时间内，一个程序从存储系统中读数据的速率(实际情况)

• Previous
  9.顺序容器
• Next
  KMP算法