信息安全系统设计基础第七周学习总结

第六章 存储器层次结构

一、知识点总结

（一）存储技术

1. 存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU寄存器保存着最常用的数据。

2. 小而快的高速缓存寄存器靠近CPU，下层存储设备慢而大、便宜。

3. 基本存储技术

• SRAM存储器
• DRAM存储器
• ROM存储器
• 旋转和固态的硬盘

6.1.1 随机访问存贮器

分为静态（SRAM）和动态（DRAM）两类，SRAM更快更贵，用来作为高速缓存存储器。DRAM用来作为主存以及图形系统的帧缓冲区

1. 静态RAM：将每个位存储在一个双稳态的存储器单元里，只要有电就会永远保持它的值

2. 动态RAM：将每个位存储为对一个电容的充电，当电容的电压被干扰后就存储器单元就永远不会恢复了。存储器系统必须周期性地通过读出，然后重写来刷新存储器的每一位。

3. 传统的DRAM：DRAM芯片中的单元（位）被分成d个超单元，每个DRAM芯片被连接到某个称为存储控制器的电路。

4. 存储器模块：DRAM芯片包装在存储器模块，常见包装包括双列直插存储器模块、单列直插存储器模块

5. 增强的DRAM：

• 快页模式DRAM
• 扩展数据输出DRAM
• 同步DRAM
• 双倍数据速率同步DRAM
• Rambus DRAM
• 视频RAM

6. 非易失性存储器：在关电后仍保存着信息。ROM整体上称为只读存储器，ROM以它们能被重编程（写）的次数和重编程所用机制来区分。

• PROM：只能被编写一次
• 可擦写可编程ROM
• 闪存

7. 访问主存：数据流通过称为总线的共享电子电路在处理器和DRAM主存之间来回。读事物 从主存传送数据到CPU，写事物从CPU传送数据到主存。

• 总线是一组并行的导线，能携带地址、数据和控制信号。
• 计算机系统配置：CPU芯片、I/O桥、组成主存的DRAM存储器模块
• 系统总线连接CPU和I/O桥，存储器总线连接I/O桥和主存

6.1.2 磁盘存储

1. 磁盘构造：磁盘由盘片构成，每个盘片有两面或称为表面，盘片中央有一个可旋转的主轴，它使盘片以固定的旋转速率旋转。

2. 磁盘容量：由以下技术因素决定

• 记录密度：磁道一英寸的段中可以放入的位数。
• 磁道密度：从盘片中心出发半径上一英寸的段内可以有的磁道数。
• 面密度：记录密度与磁道密度的乘积。

磁盘容量=字节数/扇区 * 平均扇区数/磁道 * 磁道数/表面 * 表面数/盘片 * 盘片数/磁盘

3.磁盘操作：磁盘用读/写头来存储在磁性表面的位，读写头连接到一个传动臂一端。

磁盘以扇区大小的块来读写数据。对扇区的访问时间有三个主要部分：寻道时间、旋转时间、传送时间

• 寻道时间：为了读取某个目标扇区的内容，传动臂首先将读写头定位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。
• 旋转时间：最大旋转延迟Tmax rotation=1/RPM * 60secs/1min。平均旋转时间Tavg rotation的一半。
• 传送时间：Tavg transfer=1/RPM * 1/(平均扇区数/磁道) * 60secs/1min
• 估计总访问时间=Tavg seek+Tavg rotation+Tavg transfer。因为寻道时间和旋转延迟大致相等，所以将寻道时间乘以2可简单估计磁盘访问时间。

4.逻辑磁盘块

• 控制器上的固件执行一个快速表查找，将一个逻辑块号翻译成一个（盘面、磁道、扇区）的三元组，这个三元组唯一地标识了对应的物理扇区。
• 磁盘控制器维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。

5.连接到I/O设备

有三个不同类型的设备连接到总线

• 通用串行总线
• 图形卡（或适配器）
• 主机总线适配器
• 其他设备如网络适配器，可以通过将适配器插入到主板上空的扩展槽中，从而连接到I/O总线，这些插槽提供了到总线的直接电路连接。

6.访问磁盘 

CPU使用存储器映射I/O技术来向I/O设备发出指令。

7. 商用磁盘的剖析

6.1.3 固态硬盘

固态硬盘是一种基于闪存的存储技术。一个SDD包由一个或多个闪存芯片和闪存翻译层组成。

6.1.4 存储技术趋势

1. 不同的存储技术有不同的价格和性能折中。
2. 不同存储技术的价格和性能属性以截然不同的速率变化着。
3. DRAM和磁盘的性能滞后于CPU的性能。

（二）局部性

一个编写良好的计算机程序具有良好的局部性，倾向于引用临近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。

局部性两种不同形式：时间局部性、空间局部性

有良好局部性的程序比局部性差的程序运行得更快。

6.2.1 对程序数据引用的局部性

步长为1的引用模式（顺序引用模式）： 顺序访问一个向量每个元素的函数。一个连续向量中，每隔k个元素进行访问被称为步长为k的引用模式。随着步长增加，空间局部性下降。

6.2.2 取指令的局部性

1. 程序指令存放在存储器中，CPU必须取出这些命令，所以我们能评价一个程序关于取指令的局部性。

2. 代码区别于程序数据的一个重要属性是在运行时它不能被修改，程序执行时，CPU只从存储器中读取它的指令，CPU绝不会重写或修改这些指令。

6.2.3 局部性小结

1. 重复引用同一个变量的程序有良好的时间局部性。
2. 对于具有步长为k的引用模式的程序，步长越小空间局部性越好。具有步长为1的引用模式的程序有很好的空间局部性。在存储器中以大步长跳来跳去的程序空间局部性很差。
3. 对于取指令而言，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

（三）存储器层次结构

6.3.1 存储器结构

• 高速缓存是一个小而快速的存储设备，它作为存储在更大也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存。

• 存储器层次结构的中心思想：对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。

• 第k+1层的存储器被划分成连续的数据对象片，称为块。数据总是以块大小为传送单元，在第k层和第k+1层之间来回拷贝。虽然在层次结构中任何一对相邻的层次之间块的大小是固定的，但是其他层次对之间可以有不同的块大小。

1. 缓存命中：当程序需要第k+1层的某个数据对象d时，首先在当前存储于第k层的一个块中查找d，且d刚好缓存在第k层。

2. 缓存不命中：当程序需要第k+1层的某个数据对象d时，首先在当前存储于第k层的一个块中查找d，且第k层没有缓存数据对象d。

覆盖一个现存的块的过程称为替换或驱逐这个块，被驱逐的这个块也称为牺牲块。决定该替换哪个块由缓存的替换策略控制。

3. 缓存不命中的种类：如果第k层的缓存为空，则对任何数据对象的访问都会不命中。

• 冷缓存：空的缓存，此类不命中称为强制性不命中（冷不命中）。通常是短暂的事件，不会在反复访问存储器使得缓存暖身之后的稳定状态出现。
• 只要发生了不命中，第k层的缓存就必须执行某个放置策略，确定把它从第k+1层中取出的块放在哪里。
• 当工作集的大小超过缓存的大小时，缓存会经历容量不命中。

4.缓存管理：存储器层次结构的本质是每一层存储设备都是较低一层的缓存，在每一层上，某种形式的逻辑必须管理缓存。即某个东西要将缓存划分成块，在不同的层之间传送块，判断是命中还是不命中，并处理它们。

6.3.2 存储器层次结构概念小结

1. 利用时间局部性：由于时间局部性，同一数据对象可能会被多次使用。因为缓存比低一层的存储设备更快，对后面的命中服务会比最开始的不命中快很多。

2. 利用空间局部性：块通常包含多个数据对象，由于空间局部性，我们会期望后面对该块中其他对象的访问能补偿不命中后拷贝该块的花费。

（四）高速缓存存储器

高速缓存存储器的典型总线结构

6.4.1 通用的高速缓存存储器结构

高速缓存的结构可用元祖（S、E、B、m）来描述，高速缓存的大小（容量）C指的是所有块的大小的和，标记位和有效位不包括在内。C=S * E * B。

6.4.2 直接映射高速缓存

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

高速缓存确定一个请求是否命中，然后抽取被请求的字的过程分为三步：

• 组选择
• 行匹配
• 字抽取

1. 直接映射高速缓存中的组选择

高速缓存从w的地址中间抽取出S个组索引位，这些位被解释成一个对应于一个组号的无符号整数。

2. 直接映射高速缓存中的行匹配

确定是否有字w的一个拷贝存储在组i包含的一个高速缓存行中。当且仅当设置了有效位，而且高速缓存行中的标记与w的地址中的标记相匹配时，这一行中包含w的一个拷贝。如果有效位没有设置，或者标记不匹配，那么得到一个缓存不命中。

3. 直接映射高速缓存中的字选择

确定需要的字在块中从哪里开始。块偏移位提供了需要的字的第一个字节的偏移。

4. 直接映射高速缓存中不命中时的行替换

如果缓存不命中，那么从存储器层次结构中的下一层取出被请求的块，然后将新的块存储在组索引位指示的组中一个高速缓存行中。

5. 综合：运行中的直接映射高速缓存

• 标记位和索引位连起来唯一地标识了存储器中的每个块。
• 因为有8个存储器块，但只有4个高速缓存组，多个块映射到同一个高速缓存组（即它们有相同的组索引）。
• 映射到同一个高速缓存组的块由标记位唯一地标识。

6. 直接映射高速缓存中的冲突不命中

即使程序有良好的空间局部性，而且高速缓存中也有足够的空间来存放块，每次引用还是会导致冲突不命中。这是因为这些块被映射到了同一个高速缓存组。

6.4.3 组相联高速缓存

1. 组相联高速缓存中的组选择

它的组选择与直接映射高速缓存的组选择一样，组索引位标识组。

2. 组相联高速缓存中的行匹配和字选择

它的行匹配比直接映射高速缓存的更复杂，因为它必须检查多个行的标记位和有效位，以确定所请求的字是否在集合中。

重要思想：组中的任何一行都能包含任何映射到这个组的存储器块，所以高速缓存必须搜索组中的每一行，寻找一个有效的行，其标记与地址中的标记相匹配。如果高速缓存找到了这样一行就命中，块偏移从这个块中选择一个字，和前面一样。

3. 组相联高速缓存中不命中时的行替换

缓存不命中则高速缓存必须从存储器中取出包含这个字的块，如果有一个空行则可以被替换，如果没有空行则必须从中选择一个非空的行，希望CPU不会很快引用这个被替换的行。

• 最不常用策略
• 最近最少使用策略

6.4.4 全相联高速缓存

一个全相联高速缓存是由一个包含所有高速缓存行的组（即E=C/B）组成的。

1. 全相联高速缓存中的组选择

只有一个组，地址中没有组索引位，地址只被划分了一个标记和一个块偏移。

2. 全相联高速缓存中的行匹配和字选择

全相联高速缓存中的行匹配和字选择与组相联高速缓存中的一样，主要区别是规模大小的问题。全相联高速缓存只适合做小的高速缓存。

6.4.5 有关写的问题

1. 写命中：

• 直写：高速缓存更新了它的w拷贝后立即将w的高速缓存块写到紧接着的低一层中。缺点是每次写都会引起总线流量。

• 写回：尽可能推迟存储器更新，只有当替换算法要驱逐更新过的块时，才把它写到紧接着的低一层中。能显著地减少总线流量，缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位，表明这个高速缓存块是否被修改过。

2. 写不命中

• 写分配：加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。缺点是每次不命中都会导致一个块从低一层传送到高速缓存。
• 非写分配：避开高速缓存，直接把这个字写到低一层中。直写高速缓存通常是非写分配的，写回高速缓存通常是写分配的。

6.4.6 一个真实的高速缓存层次结构的解剖

高速缓存既保存数据也保存指令。只保存指令的高速缓存称为i-cache，只保存程序数据的高速缓存称为d-cache。既保存数据也保存指令的高速缓存称为统一的高速缓存。

6.4.7 高速缓存参数的性能影响

衡量高速缓存性能的指标：

• 不命中率
• 命中率
• 命中时间
• 不命中处罚

1. 高速缓存大小的影响：较大的高速缓存可能会提高命中率，使大存储器运行得更快更难，较大的高速缓存可能会增加命中时间。

2. 块大小的影响：较大的块能利用程序中可能存在的空间局部性，帮助提高命中率。但对于给定的高速缓存大小，块越大代表高速缓存行数越少，会损害时间局部性比空间局部性更好的程序的命中率。较大的块对不命中处罚也有负面影响。

3. 相联度的影响：较高的相联度（E值较大）的优点是降低了高速缓存由于冲突不命中出现抖动的可能性。但较高的相联度成本较高，很难使之速度变快，增加命中时间，增加不命中处罚。

4. 写策略的影响：直写高速缓存容易实现，且能独立于高速缓存的写缓冲区，用来更新存储器。读不命中的开销不大，因为不会触发存储器写。另外，写回高速缓存引起的传送较少。一般高速缓存越往下层越可能使用写回。

五)编写高速缓存友好的代码

1. 基本方法

• 让最常见的情况运行的快
• 在每个循环内部缓存不命中数量最小

2. 重要问题

• 对局部变量的反复引用是好的，因为编译器能够把它们缓存在寄存器文件中。（时间局部性）
• 步长为1的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块。（空间局部性）

（六）综合：高速缓存对程序性能的影响

6.6.1 存储器山

1. 一个程序从存储系统中读数据的速率称为读吞吐量或读带宽。
2. 每台计算机都有表明他存储器系统的能力特色的唯一的存储器山。
3. 目的：使得程序运行在山峰而不是低谷。利用时间局部性，使得频繁使用的字从L1中取出；利用空间局部性，使得尽可能多的字从一个L1高速缓存行中访问到。

6.6.2 重新排列循环以提高空间局部性 

1. 对于大的n值，即使每个版本都执行相同数量的浮点数运算最快的版本比最慢的版本运行得快几乎20倍。
2. 每次迭代存储器引用和不命中数量都相同的一对版本有大致相同的测量性能。
3. 存储器行为最糟糕的两个版本，就每次迭代的访问数量和不命中数量而言，明显比其他四个版本运行得更慢，其他四个版本有较少的访问数量和不命中数量，或兼而有之。
4. 这种情况下，与存储器访问总数相比，不命中率是一个较好的性能指示。
5. 对于较大的n值，最快的一对版本（kij和ikj）的性能保持不变。

6.6.3 在程序中利用局部性

1. 将注意力集中于内循环，大部分计算和存储器访问都在此。
2. 通过按照数据对象存储在存储器中的顺序，以步长为1的来读数据，从而使程序中空间局部性最大。
3. 一旦存储器中读入了一个数据对象，就尽可能多用它，从而使程序中时间局部性最大。

二、参考资料

• 《深入理解计算机系统》
• 《嵌入式Linux应用程序开发标准教程》

三、心得体会

通过对本章存储器结构层次的学习，我初步掌握了存储技术、局部性、存储器层次结构、高速缓存存储器等知识点，尤其是在图像的解释下对于存储器层次结构有了更深层次的理解。通过课后练习进一步巩固了所学知识。

四、附录

第四章家庭作业已传至博客。