CSAPP:第6章存储器层次结构

Dear 丶 2022-10-28 10:09 255阅读 0赞

### CSAPP:第6章 存储器层次结构 ###

### 文章目录 ###

*   *   *  CSAPP:第6章 存储器层次结构
         *   *  6.1 存储技术
             *   *  6.1.1 随机访问存储器
                 *  6.1.2 磁盘存储
                 *  6.1.3 固态硬盘
                 *  6.1.4 存储技术趋势
             *  6.2 局部性
             *   *  6.2.1 对程序数据引用的局部性
                 *  6.2.2 取指令的局部性
                 *  6.2.3 局部性小结
             *  6.3 存储器层次结构
             *   *  6.3.1 存储器层次结构中的缓存
                 *  6.3.2 存储器层次结构概念小结
             *  6.4 高速缓存存储器
             *   *  6.4.1 通用的高速缓存存储器组织结构
                 *  6.4.2 直接映射高速缓存
                 *  6.4.3 组相联高速缓存
                 *  6.4.4 全相联高速缓存
                 *  6.4.5 有关写的问题
                 *  6.4.6 一个真实的高速缓存层次的结构解剖
                 *  6.4.7 高速缓存参数的性能影响
             *  6.5 编写高速缓存友好的代码
             *  6.6 综合：高速缓存对程序性能低影响
             *   *  6.6.1 存储器山
                 *  6.6.2 重新排列循环以提高空间局部性
                 *  6.6.3 在程序中的局部性

#### 6.1 存储技术 ####

##### 6.1.1 随机访问存储器 #####

*  RAM（Random-Access Memory）分为两类，静态的和动态的，即SRAM与DRAM。速度SRAM快，也贵。
 *  1、SRAM：
    
     *  SRAM 将每个位存储在一个双稳态的（Instable)存储器单元里。每个单元是用一个六晶体管电路来实现的。
     *  它只有两个稳态，如下所示：分别为左稳态和右稳态
        
         *  ![image-20210204230813579][]
     *  由于 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。即使有干扰（例如电子噪音）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。
 *  2、DRAM：
    
     *  DRAM 将每个位存储为对一个电容的充电。DRAM 存储器可以制造得非常密集—每个单元由一个电容和一个访问晶体管组成。
     *  DRAM 存储器单元对干扰**非常敏感**。当电容的电压被扰乱之后，它就永远不会恢复了。暴露在光线下会导致电容电压改变。
        
         *  数码照相机和摄像机中的传感器本质上就是 DRAM 单元的阵列。
     *  很多原因会导致漏电，使得 DRAM 单元在 10 100 毫秒时间内失去电荷。内存系统必须周期性地通过读出，然后重写来刷新内存每一位。
 *  3、传统DRAM
    
     *  DRAM 芯片中的单元（位）被分成 d 个超单元（supercell)，每个超单元都由 w 个 DRAM单元组成。一个 加的 DRAM 总共存储了如位信息。超单元被组织成一个厂行 列的长单元组成
     *  可以理解成：16x8位=》每个超单元有8位，共16个超单元
 *  4、内存模块
    
     *  DRAM 芯片封装在内存模块（memory module)中，它插到主板的扩展槽上。
     *  示例模块用 8 个 64 Mbit 的 8 MX 8 的 DRAM芯片，总共存储 64MB(兆字节），这 8 个芯片编号为 0～7。
     *  ![image-20210204234002155][]
     *  个人理解：从图中可知是低位交叉存储，相邻两个字节（超单元）存在相邻的存储片中，这样有利于流水线模式。
 *  5、增强的DRAM
    
     *  快页模式 DRAM(Fast Page Mode DRAM, FPM DRAM)。
        
         *  传统的 DRAM 将超单元的一整行复制到它的内部行缓冲区中，使用一个，然后丢弃剩余的。FPM DRAM 允许对同一行连续地访问可以直接从行缓冲区得到服务，从而改进了这一点。(一个RAS（行请求）后面可以跟多个CAS（列请求）)
     *  扩展数据输出 DRAM(Extended Data Out DRAM, EDO DRAM)。
        
         *  FPM DRAM 的一个增强的形式，它允许各个 CAS 信号在时间上靠得更紧密一点。
     *  同步 DRAM(Synchronous DRAM, SDRAM)。
        
         *  它们与内存控制器通信使用一组显式的控制信号来说，常规的、FPM 和 EDO DRAM 都是异步的。SDRAM 用与驱动内存控制器相同的外部时钟信号的上升沿来代替许多这样的控制信号。
         *  SDRAM 能够比那些异步的存储器更快地输出它的超单元的内容。
     *  双倍数据速率同步 DRAM(Double Data-Rate Synchronous DRAM, DDR SDRAM)。
        
         *  DDR SDRAM 是对 SDRAM 的一种增强，它通过使用两个时钟沿作为控制信号，从而使 DRAM 的速度翻倍。
         *  不同类型的 DDR SDRAM 是用提高有效带宽的很小的预取缓冲区的大小来划分的：DDR(2 位）、 DDR2(4 位）和 DDR(8 位）。
     *  视频 RAM( Video RAM, VRAM)。
        
         *  它用在图形系统的帧缓冲区中。
         *  VRAM 的思想与 FPM DRAM 类似。两个主要区别是：
            
             *  1 ) VRAM 的输出是通过依次对内部缓冲区的整个内容进行移位得到的；
             *  1.  VRAM 允许对内存并行地读和写。因此，系统可以在写下一次更新的新值（写）的同时，用帧缓冲区中的像素刷屏幕(读）。
 *  **6. 非易失性存储器**
    
     *  只读存储器（Read-Only Memory, ROM)。
     *  ROM 是以它们能够被重编程（写）的次数和对它们进行重编程所用的机制来区分的。
        
         *  **PROM**(Programmable ROM, 可编程 ROM)只能被编程一次。PROM 的每个存储器单元有一种熔丝（fuse)，只能用高电流熔断一次。
         *  可擦写可编程 ROM(Erasable Programmable ROM, **EPROM**)有一个透明的石英窗口，允许光到达存储单元。紫外线光照射过窗口，EPROM 单元就被清除为 0。对EPROM 编程是通过使用一种把 1 写人 EPROM 的特殊设备来完成的。EPROM 能够被擦除和重编程的次数的数量级可以达到 1000 次。
         *  电子可擦除 PROM(Electrically ErasablePROM, **EEPROM**)类似于 EPROM, 但是它不需要一个物理上独立的编程设备，因此可以直接在印制电路卡上编程。EEPROM 能够被编程的次数的数量级可以达到 10^5 次。
         *  闪存（flash memory)是一类非易失性存储器，基于 EEPROM，它已经成为了一种重要的存储技术。
         *  一种新型的基于闪存的磁盘驱动器，称为固态硬盘（SoHd State Disk, SSD), 它能提供相对于传统旋转磁盘的一种更快速 、 更强健和更低能耗的选择。
 *  7、**访问主存**
    
     *  下面引用课件中原话介绍bus：
        
         *  A bus is a collection of parallel wires that carry address, data, and control signals.
         *  Buses are typical shared by multiple devices
            
             *  ![image-20210205100901612][]
         *  下面展示写过程数据流
            
             *  ![image-20210205101354819][]

##### 6.1.2 磁盘存储 #####

*  **1、磁盘构造**
    
     *  看张图就行了：
        
         *  ![image-20210205101510746][]
 *  **2、磁盘容量**
    
     *  一个磁盘上可以记录的最大位数称为它的最大容量，或者简称为容量。磁盘容量是由以下技术因素决定的：
        
         *  记录密度（recording density）：一英寸的段中可以放入段位数。
         *  磁道数（track density）:从盘心出发半径一英寸的段内可一有的磁道数。
         *  面密度（areal density）:记录密度与磁道密度的乘积。
     *  一个磁盘的容量=![image-20210205102107772][]
 *  3、磁盘操作
    
     *  ![image-20210205102926171][]
     *  读/写头冲撞( head crash)：盘面有灰尘，读写头撞上了。
     *  访问时间分为三部分：
        
         *  寻道时间：磁头移动到特定磁道上，通常为 3～9ms。
         *  旋转时间：转到特定扇区。![image-20210205103407753][]
         *  传送时间；读写数据的时间，一般是经过这个扇区的时间。![image-20210205103458403][]
     *  有以下特点：
        
         *  访问一个磁盘扇区中 512 个字节的时间主要是寻道时间和旋转延迟。访问扇区中的第一个字节用了很长时间，但是访问剩下的字节几乎不用时间。
         *  因为寻道时间和旋转延迟大致相等，所以将寻道时间乘 2 是估计磁盘访问时间的简单而合理的方法。
         *  访问时间是DRAM的100x数量级（视频，书上是1000x）
 *  4、逻辑磁盘块
    
     *  磁盘封装中有一个小的硬件/固件设备，称为磁盘控制器，维护着逻辑块号和实际（物理）磁盘扇区之间的映射关系。即逻辑盘号转物理盘号（三元组）。
 *  5、连接IO设备
    
     *  例如图形卡、监视器、鼠标、键盘和磁盘这样的输人/输出（I/O)设备，都是通过 I/O总线
     *  有三种不同类型的设备连接到总线：
        
         *  **通用串行总线**（Universal Serial Bus, USB)控制器是一个连接到 USB 总线的设备的中转机构，USB 总线是一个广泛使用的标准。USB 3.0 总线的最大带宽为 625MB/S。USB 3.1 总线的最大带宽为 1250MB/s。
         *  **图形卡**（或适配器）包含硬件和软件逻辑，它们负责代表 CPU 在显示器上画像素。
         *  **主机总线适配器**将一个或多个磁盘连接到 I/O 总线，使用的是一个特别的主机总线  
            接口定义的通信协议。
         *  ![image-20210205115144094][]
 *  6、访问磁盘
    
     *  书中介绍了DMA方式，即传输控制由DMA负责，传输完成再给CPU发中断。

##### 6.1.3 固态硬盘 #####

*  固态硬盘（Solid State Disk , SSD)是一种基于闪存的存储技术
 *  SSD封装插到 I/O 总线上标准硬盘插槽（通常是 USB 或 SATA)中，行为就和其他硬盘一样，处理来自 CPU 的读写逻辑磁盘块的请求。
 *  ![image-20210205115836011][]
 *  如上所示，SSD由许多闪存芯片以及闪存翻译层（flash translation layer）组成，其中闪存翻译层主要扮演与磁盘控制器相同的角色，将对逻辑块的请求翻译成对底层物理设备的访问。
 *  读 SSD 比写要快。随机读和写的性能差别是由底层闪存基本属性决定的。
    
     *  一页512B～4KB，32~128页组成块。数据一般是按页为单位读写的，但在写的时候必须等这一页所属的块整个被擦除之后，才  
        能写这一页（通常是指该块中的所有位都被设置为 1 )。不过，一旦一个块被擦除了，块中毎一个页都可以不需要再进行擦除就写一次。
     *  除了需要擦除整块之外，如果写操作试图修改一个包含已经有数据（也就是不是全为 1)的页那么这个块中所有带有用数据的页都必须被复制到一个新（擦除过的）块，然后才能进行对页的写。

##### 6.1.4 存储技术趋势 #####

*  不同的存储技术有不同的价格和性能折中。SRAM 比 DRAM 快一点，而 DRAM 比磁盘要快很多。
 *  不同存储技术的价格和性能属性以截然不同的速率变化着。
 *  DRAM 和磁盘的性能滞后于 CPU 的性能。

#### 6.2 局部性 ####

*  一个编写良好的计算机程序常常具有良好的局部性（locaUty)——它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。
 *  局部性分为：时间局部性（temporal locality )和空间局部性（spatial locality)。

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

*  如：对二维数组的求和，按行双重遍历（行在外层）是种有良好空间局部性的方案（内存中存储一般是行优先）：
    
     *  ![image-20210205121918146][]
     *  如果按列在外层的那种就不具有良好的空间局部性

##### 6.2.2 取指令的局部性 #####

*  就6.2.1中的代码截图来说，for循环具有良好的空间局部性和时间局部性——循环体内部的指令是顺序执行；循环体不断被调用
 *  代码区别于程序数据的一个重要属性是在运行时它是不能被修改的。当程序正在执行时，CPU 只从内存中读出它的指令。CPU 很少会重写或修改这些指令。

##### 6.2.3 局部性小结 #####

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

#### 6.3 存储器层次结构 ####

*  ![image-20210205122527584][]

##### 6.3.1 存储器层次结构中的缓存 #####

*  cache——高速缓存
    
     *  ![image-20210205135053818][]
     *  从上图可以看出，层级结构中每一层缓存都来自下一层的数据对象，即多重缓存结构。
     *  **1 . 缓存命中**（cache hit）
        
         *  命中哪层就的到哪层的缓存
     *  **2. 缓存不命中**（cache miss）
        
         *  当发生缓存不命中时，第々层的缓存从第k +1 层缓存中取出包含 d 的那个块，如果第k层的缓存已经满了，可能就会覆盖（replacing/evicting）现存的一个块。被驱逐的这个块有时也称为牺牲块（victim block)。
         *  这里有替换策略，就是LRU，随机，先到先出这种
     *  **3. 缓存不命中的种类**
        
         *  一个空的缓存有时被称为冷缓存（cold cache), 此类不命中称为强制性不命中（compulsory miss)或冷不命中（cold miss)。
            
             *  冷不命中很重要，因为它们通常是短暂的事件，不会在反复访问存储器使得缓存暖身（warmed up )之后的稳定状态中出现。即指存在刚开始（刚启动）的时候。
             *  只要发生了不命中，第k层的缓存就必须执行某个放置策略（placement policy)，确定把它从第k +1 层中取出的块放在哪里。
     *  **4. 缓存管理**
        
         *  存储器层次结构的本质是，每一层存储设备都是较低一层的缓存。

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

*  ![image-20210205145027709][]

#### 6.4 高速缓存存储器 ####

*  随着 CPU 和主存之间的性能差距不断増大，系统设计者不得不在寄存器与主存中插入L1缓存，后来又插入L2、L3缓存。

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

*  ![image-20210205145543179][]
 *  如上图所示，高速缓存是一个高速缓存组的数组，类似于组相联的效果，每组E行，每行将地址分为标记，组索引，块偏移，这就是我们平时学计组的时候老师忽略却又必考的重点内容（地址怎么分，根据地址找块判断存在之类的）。

##### 6.4.2 直接映射高速缓存 #####

*  最简单，假设b位块偏移，根据地址，从块偏移往高位数s位作为组索引（其实是缓存中的行号）来决定存储位置。
    
     *  具体分为：
        
         *  组选择：![image-20210205150153965][]
         *  行匹配：![image-20210205150422346][]
         *  字选择
         *  行替换（不命中时）：对于直接映射高速缓存来说，每个组只包含有一行 ，策略非常简单：用新取出的行替换当前的行。
     *  还会发生一种奇特的现象：冲突不命中：即高速缓存反复地加载和驱逐相同的高速缓存块的组（这样来回一次是冲突不命中，多次就称为抖动现象）。

##### 6.4.3 组相联高速缓存 #####

*  下图为二路组相联，组号直接映射，组内全相联
 *  ![image-20210205174214995][]

##### 6.4.4 全相联高速缓存 #####

*  任何一块都是可以映射到缓存中的任何一块
    
     *  等价于只有一个组：
        
         *  ![image-20210205174533256][]

##### 6.4.5 有关写的问题 #####

*  有两种写的设置：
    
     *  写分配（write-allocate)，即写回法，等缓存换出的时候再写回内存
     *  非写分配（not-write-dlocate)，即写直通法，避开高速缓存，直接把这个字写到低一层中（实际上应该是缓存内存同时写）。

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

*  髙速缓存既保存数据，也保存指令。即数据缓存与指令缓存，这玩意可以分成两个缓存存放（可以提升性能）

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

*  有下面几个参数：
    
     *  不命中率（miss rate)。在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。
     *  计算方式：不命中数量/引用数量。
     *  命中率（hit rate)。命中的内存引用比率。它等于 1一不命中率。
     *  命中时间（hit time)。从高速缓存传送一个字到 CPU 所需的时间，包括组选择、行确认和字选择的时间。对于 L1 高速缓存来说，命中时间的数量级是几个时钟周期。
     *  不命中处罚（miss penalty)。由于不命中所需要的额外的时间。L1 不命中需要从 L2得到服务的处罚，通常是数 10 个周期；从 L3 得到服务的处罚，50 个周期；，从主存得到的服务的处罚，200 个周期。
 *  几个影响因素
    
     *  高速缓存大小的影响
        
         *  较大的高速缓存可能会提高命中率。
         *  较大的高速缓存可能会增加命中时间。
     *  块大小的影响
        
         *  较大的块能利用程序中可能存在的空间局部性，帮助提高命中率。
         *  对于给定的高速缓存大小，块越大就意味着高速缓存行数越少。
         *  较大的块对不命中处罚也有负面影响，因为块越大，传送时间就越长。
         *  现代系统（如 Core i7)会折中使高速缓存块包含 64 个字节。
     *  相联度的影响
        
         *  较高的相联度降低了高速缓存由于冲突不命中出现抖动的可能性。
         *  但成本较高，速度也不快。
     *  写策略的影响
        
         *  越往层次结构下面走，传送时间增加，减少传送的数量就变得更加重要。一般而言,高速缓存越往下层，越可能使用写回而不是直写。
 *  高速缓存行、组和块有什么区别？
    
     *  块是一个固定大小的信息包，在高速缓存和主存(或下一层高速缓存)之间来回传送。
     *  行是高速缓存中的一个容器，存储块以及其他信息（例如有效位和标记位）。
     *  组是一个或多个行的集合。直接映射高速缓存中的组只由一行组成。组相联和全相联高速缓存中的组是由多个行组成的。

#### 6.5 编写高速缓存友好的代码 ####

*  原则如下：
    
     *  让最常见的情况运行得快——要把注意力集中在核心函数里的循环上，而忽略其他部分。
     *  尽量减小每个循环内部的缓存不命中数量。
     *  对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器文件中（时间局部性）。
     *  步长为 1 的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块（空间局部性）。

#### 6.6 综合：高速缓存对程序性能低影响 ####

##### 6.6.1 存储器山 #####

*  用函数测试各级缓存以及主存性能，然后得出一个存储器山。

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

*  考虑一对nXn矩阵相乘的问题：C=AB。例如，如果 n=2, 那么
    
     *  ![image-20210205182622914][]
     *  通过观察我们发现，调整c的计算顺序，可以得到不同的局部性。
     *  且一般计算矩阵用到的是三重循环（二维数组二重，加上每个值计算的时候的一重），记为ijk，于是得到书中的6种顺序（排列组合）（拓展到n阶）
        
         *  ![image-20210205183121330][]
         *  根据这六种算法，计算出其在i7下的矩阵运算性能
            
             *  ![image-20210205183351010][]
             *  可以看到不同顺序方案的速度有时候差距悬殊，对于大的n 值，最快的一对版本（kij和ikj）的性能保持不变。

##### 6.6.3 在程序中的局部性 #####

*  将注意力集中在内循环上，大部分计算和内存访问都发生在这里。
 *  通过按照数据对象存储在内存中的顺序、以步长为 1 的来读数据，从而使得你程序中的空间局部性最大。
 *  一旦从存睹器中读人了一个数据对象，就尽可能多地使用它，从而使得程序中的时间局部性最大。

[image-20210204230813579]: /images/20221024/620ffd10cb3142e7b7b1e4e41cc05d0e.png
[image-20210204234002155]: /images/20221024/8540ff84224b46928f71e19a4c750a02.png
[image-20210205100901612]: /images/20221024/be6364f63e394640b8fca9eaef2f3e37.png
[image-20210205101354819]: /images/20221024/49cc94fa80ce4d428a713b19f6c12b65.png
[image-20210205101510746]: /images/20221024/dbe625f1596846b38e73ca7e399b7ba1.png
[image-20210205102107772]: /images/20221024/c474bf5edfbe458b8e1a9c29bc1a5962.png
[image-20210205102926171]: /images/20221024/2f221b700450471fab2b27eca175bf50.png
[image-20210205103407753]: /images/20221024/b9366decd8374bfea282908fcfdf4d1b.png
[image-20210205103458403]: /images/20221024/6f3bf18953334fb2b25622e62f8f727a.png
[image-20210205115144094]: /images/20221024/817043a8880a45af80df4150c29b5ccd.png
[image-20210205115836011]: /images/20221024/afad0c9b4d284068b686f07bfc2cdb59.png
[image-20210205121918146]: /images/20221024/988907f6d0c248caaa61035038ba99f2.png
[image-20210205122527584]: /images/20221024/bc71a398ea554ef6b4e3608859c3ea63.png
[image-20210205135053818]: /images/20221024/d4b0c21927034d7d88f1fd45902f7591.png
[image-20210205145027709]: /images/20221024/577b1e2985bf4869a82f4c623e25032f.png
[image-20210205145543179]: /images/20221024/921eaab839c14e29998e7c5cabe318a6.png
[image-20210205150153965]: /images/20221024/60670d4050994a0699054196d48848d3.png
[image-20210205150422346]: /images/20221024/8a54a82b749b40fcabc7a75451388181.png
[image-20210205174214995]: /images/20221024/47544112ffba4e6e9d14178dc5a4c41b.png
[image-20210205174533256]: /images/20221024/afd8b7abac004ac08571f85f0debeaf0.png
[image-20210205182622914]: /images/20221024/8fffe0b0da7340c796aaed680f8cec1c.png
[image-20210205183121330]: /images/20221024/c3b30721816f446b84bd13340b274c61.png
[image-20210205183351010]: /images/20221024/7b7d0e1ea37942a194e9241cb7cab372.png