芯片存储器层次结构概述

芯片存储器层次结构概述

导读：本文详细介绍了计算机存储器层次结构中的Cache系统，包括其作用、结构特点、优化技术、替换策略和写策略等。通过图文结合的方式，深入浅出地解释了复杂的计算机存储系统概念，具有较高的专业性和实用性。

1. Cache的作用

Cache结构与作用，如图2-5所示。

图2-5 Cache结构与作用

介绍一下Cache具有特征。Cache没有程序上的意义，只是为了降低访存延迟；处理器访问Cache和访问存储器使用相同的地址。

Tag存储cache块在主存中的首地址（cache每个字节都给一个地址太浪费，所以cache以块为单位存储数据）。

2. Cache的结构特点

同时存储数据和地址，通过地址的比较判断相应数据是否在Cache中；需要考虑所需要的数据不在Cache中的情况，替换机制，写策略等。例如处理器发送地址Add的高位和cache的地址标记进行比对，如果Add在cache中即为命中，从cache中返回数据，否则从主存读入数据块，返回数据给处理器的同时更新cache，更新cache时要考虑替换策略。Cache结构，如图2-6所示。

图2-6 Cache结构

cache有三种主要类型，直接相联、全相联、组相联，这代表了三种不同的内存和cache的映射方式，假设内存和cache都按照相同大小分块，其中内存一共分了32块，cache分了8块。接下来看看内存的每一项内容是如何放到cache中的。Cache结构三种主要类型，如图2-7所示。

图2-7 Cache结构三种主要类型

1）直接相联：每项内存单元只能映射到cache的一个位置，假设要把内存的12号单元放到 cache中，因为 cache只有8个单元，12除以8余数为4，12号单元就只能放在4 号单元，别的地方都不能放。4,12,20,28 号都映射到这个单元，如果冲突了怎么办？那只有替换。这就是直接相联,硬件简单但效率低。

2）全相联：每个内存块都可以放到任何一个 cache行中，4号12号20号28号同时进来都放得下。全相联硬件复杂但效率高。

3）组相联：是直接相联和全相联的折中。以二路组相联为例,0、2、4、6号一路,1、3、5、7号一路，每路4个cache块；12除以4余数为0，既可以把12号单元放在0路的0号单元,也可以放在1路的0号单元（即1号单元）（注意路和组概念不同，组是将两路拆开成单个的，然后将两个两个组合组成了四组）。

3. Cache的优化技术统计

Cache的优化技术统计，见表2-8。

4. 替换策略

即在 cache 放不下时把谁替换出去给新cache 行腾位置。

直接相联 cache 不存在替换谁的问题，因为每个内存块对应到一个 cache行的位置

在全相联和组相联 cache 中,由于每个存储行可以放在 cache 中不同的位置，因此就有替换谁的问题。常见的替换算法有 随机替换、LRU（最近少使用替换） 和 FIFO（先进先出）。

5. 写策略

1)写命中时：

①写穿透（Write Through）：写cache的同时写回内存

②写回（Write Back）：只写cache不写内存，cache块被替换时整体写入内存

2)写失效时（发现写回的地址没在cache）：

①写分配：把内存中对应的块读入cache然后更改再写回内存（常与写回配合，很自然的考虑）

②写不分配：直接写入内存（常与写穿透配合）

2.3.2 存储器层次结构示例

1. Cache相关问题

(a)块的放置：在Cache中，根据不同的策略一个块能被放置在哪里?

①直接映射（Direct Mapping）：每个块只能映射到Cache中的特定位置。通过块地址的一部分来决定放置位置。

②组相联映射（Set-Associative Mapping）：Cache被划分为多个组，每个组可以容纳多个块。块可以映射到组内的任何位置。

(b)块的标志：如果一个块在 Cache 中，如何找到它?

①在Cache中找到一个块通常需要使用地址的一部分作为标记（Tag）来识别。

②地址的一部分用于标记块的唯一性，另一部分用于选择Cache中的特定位置。

(c)块的替换：如果没有命中，哪个块该被替换，列举三种策略?

①最近最少使用（Least Recently Used, LRU）：替换最长时间没有被访问的块。

②先进先出（First-In-First-Out, FIFO）：替换最早进入Cache的块。

③随机替换：随机选择一个块进行替换。

(d)写时策略：通常有哪两种基本策略来写 Cache，写缺失时又有哪两种基本策略?

①写回（Write Back）和写通过（Write Through）：写回只在块被替换时才将数据写回主存，而写通过则在写操作同时更新Cache和主存。

②写缺失策略：

写分配（Write Allocate）：在写缺失时，先将整个块从主存读入Cache，然后 进行写操作。

非写分配（Write No-Allocate）：在写缺失时，直接更新主存而不将整个块加

载到Cache中。

2. 数组合并

将Key和Value放在一起，而不是两个数组，如图2-8所示。

图2-8 数组合并示例

3. 循环交换

因为二维数组中一行中的数据是相邻的，一列上的数据距离更远，如图2-9所示。

图2-9 循环交换示例

4. 循环合并

增加一个循环体内值的重用次数，如图2-10所示。

图2-10 循环合并示例

5. 数组分块

数组分块示例，如图2-11所示。

图2-11 数组分块示例

6. 数组分块2

完成双精度浮点数矩阵乘法，X=Y*Z，代码如下。

for(i=0;i<N;i=i+l)
for(j=0;j<N;j=j+1){
r=0;
for(k=0;k<N;k=k+1){
r=r+y[i][k]*z[k][j];};
x[i][j]=r;
}

假设系统 cache 大小为32KB，矩阵大小N足够大。写出将矩阵按 cache大小分块进行优化的代码，并计算分块前后Y和Z矩阵的 cache 失效次数。

双精度浮点数占用 8 个字节（64位）。

32 KB = 32 * 1024 = 32768 字节

若每个双精度浮点数占用 8 字节，则：32KB 能容纳 32 * 1024 / 8 = 4096 个双精度浮点数。

所以，可以容纳 64 * 64 大小的矩阵。

本文原文来自博客园