存储器层级结构

1、概述

存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。每一层于下一层相比都拥有较高的速度和较低延迟性，以及较小的容量。

存储器层次结构，对应用程序的性能有着巨大的影响。理解系统是如何将数据在存储器层次结构中上下移动，可写出更符合系统运行的应用程序，运行更快。

2、存储器的层次结构

存储器的层次结构图如下所示：

从顶层往底层走，存储设备变得更慢、更便宜和更大。在最高层L0，是少量快速的CPU寄存器，CPU可在一个时钟周期内访问它们。接下来是一个或多个基于SRAM的高速缓存，可在几个时钟周期内访问它们。在下一层是基于DRAM的主存，可以在几十到几百个时钟周期内访问它们。接下来是速度更慢的本地磁盘…

3、存储器层次结构中的缓存

高速缓存（cache） 是一个小而快速的存储设备，它用来存储下一层更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为 缓存（caching）。

对照层次图简单来说: L0 缓存 L1 中的数据，L1 缓存 L2 中的数据，L2 缓存 L3 中的数据，依此类推。

每层都会拥有多个块（连续数据对象组成的结构），数据总是以块的大小为基本单元在层级之间传递。上一层存储器更小，拥有的块比下一层少很多，只能缓存下层部分数据。如下图所示：

当CPU从存储器中读取数据时，会发生以下几种情况：

3.1、缓存命中

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

3.2、缓存不命中

缓存不命中：第 k 层 没有缓存数据对象 d。当发生缓存不命中时，第 k 层 从 第 k+1 层取出包含 d 的那个块，来写入或覆盖第 k 层的缓存中。覆盖一个现存的块的过程称为替换或驱逐。被驱逐的这个块称为 牺牲块。

3.3、缓存不命中的种类

冷缓存：第 k 层是空的，任何数据都不会命中。

放置策略：确定把第 k+1 层中取出的块放在哪里。如：随机放置策略。

冲突不命中：每次访问数据都是不命中状态，是由某些放置策略引起的不命中。

3.4、缓存管理

在每一层上，都会有由硬件和软件组成一种逻辑进行缓存管理。不需要程序采取特殊的行动。

4、局部性原理

程序倾向于一次又一次地访问相同的数据集合，或倾向于访问邻近的数据集合。这种倾向性，我们称为局部性原理。通常有以下两种形式：

• 时间局部性：被引用过一次的存储器位置的内容在不远的将来再被多次引用。
• 空间局部性：如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

一般而言，有良好局部性的程序比局部性差的程序运行得更快。现代计算机系统的各个层次，从硬件到操作系统、在到应用程序，它们的设计都利用了局部性。举例来说：

int sumvec( int  vec[N])
{
	int i , sum = 0;
	for( i = 0; i < N; i++)
		sum += vec[i];
	return sum;
}

在这个程序中，变量sum,i在每次循环迭代时被引用一次，因此对sum和i来说，有较好的时间局部性。
对变量vec来说，它是一个int类型数组，循环时按顺序访问vec，因为一个C数组在内存中是占用连续的内存空间。因而的较好的空间局部性.

再看一个例子：

int sumarraycols(int array[M][N])
{
    int i, j, sum = 0;
    for(i = 0; i < N; i++){
        for(j = 0; j < M; j++)
            sum += array[i][j];
    }   
    return sum;
}

这是一个空间局部性很差的程序。
假设这个数组是array[3][4],因为C数组在内存中是按行顺序来存放的。所以sumarraycols对每个数组元素的访问顺序成了这样：0， 4， 8， 1， 5， 9…… 7， 11。所以它的空间局部性很差。

5、总结

通过上面的介绍可以发现，存储层级天然符合局部性原理；

利用时间局部性：当缓存了一个对象时，我们并不从缓存中删除，期望后面对该缓存有一系列的访问。

利用空间局部性：缓存数据时，都是以block块为单位缓存的，期望对该块的其它数据进行访问。

感谢大家，我是假装很努力的YoungYangD（小羊）。

参考资料：
《深入理解计算机系统》
https://www.cnblogs.com/yaoxiaowen/p/7805661.html