CSAPP 学习笔记 (第六章)
2023-08-24 17:10:00 # Book #C #CSAPP

Chapter 6: 存储器层次结构

6.1 存储技术

6.1.1 随机访问存储器

Random-Access Memory (RAM) 分两类
静态RAM(SRAM): 快, 贵

SRAM 把每个位存储在 一个双稳态的存储器单元里, 使用一个六晶体管电路实现
它可以无限期地保持在两个不同的电压状态之一, 其他任何状态都是不稳定的

由于这种双稳态特性, 只要有电他就会永远保持他的值
即使有干扰扰动电压, 干扰消除时电路也会恢复到稳定值

动态RAM(DRAM):

DRAM 把每个位存储为 对一个电容的充电, 电容大概是 $30\times 10^{-15}F$
电容的电压被扰乱之后, 它就永远不会恢复了

很多原因导致的漏电会让 DRAM 在 $10ms$ 到 $100ms$ 失去电荷
所以内存系统必须周期性地通过读出, 重写来刷新每一位
也可以使用纠错码, 其中计算机的字会被多编码几个位, 这样电路可以发现并纠正一个字中任何单个的错误位

传统的 DRAM

工作方式:

  1. 内存控制器 通过 addr 引脚向 DRAM 芯片传入两位的行地址 $Row Access Strobe (RAS)$
  2. 内部行缓冲区存储行号所在的行
  3. 内存控制器 通过 addr 引脚向 DRAM 芯片传入两位的列地址 $Column Access Strobe (CAS)$
  4. DRAM 芯片从内部行缓冲区取出一个字节的数据通过 data 返回到内存控制器

内部组成:

DRAM 中有 $d$ 个超单元, $r$ 行 $w$ 列, $r \times w = d$
每个超单元由 $w$ 个 DRAM 单元组成, 总共存储 $rcw = dw$ 位的信息

二维阵列的优点: 传入的地址引脚可以是 2 位, 否则 16 个线性排列的单元需要 4 位寻址
二维阵列的缺点: 两次传入地址, 增加访问时间

内存模块

八个 DRAM 芯片组合在一起, 通过地址引脚获取行地址和列地址
把八个 DRAM 芯片的八位结果组合在一起得到存储的 64 位值

增强的 DRAM

一些厂商为了跟上 CPU 处理速度而做出的一些优化

非易失型存储器

断电之后, RAM 会失去它的存储信息, 是 易失的
现在的很多种 非易失性存储器 因为历史原因被称为 $Read-Only \ Memory (ROM)$

  1. $PROM$ 可编程 ROM, 只能被编程一次, 它的每个存储器单元有一种 熔丝, 只能用高电流熔断一次
  2. $EPROM$ 可擦写可编程 ROM, 大概能编程 1000 次
  3. $EEPROM$, 电子可擦除 ROM, 大概能编程 10000 次
  4. $flash \ memory$ 闪存, 基于 $EEPROM$ 的存储技术

存储在 ROM 中的程序通常被称为固件, 计算机系统通电之后就运行这些固件

访问主存

数据流通过 总线 的共享电子电路在处理器和 DRAM 主存之间来回
CPU 和主存之间的数据传送通过一系列步骤来完成的, 称为总线事务, 分为读事务和写事务

6.1.2 磁盘存储

比 DRAM 慢了十万倍, 比 SRAM 慢了百万倍

磁盘构造

磁盘容量

  1. 记录密度: 一英寸磁道可以放入的位数
  2. 磁道密度: 盘片中心半径一英寸有多少磁道
  3. 面密度: 上两者相乘

$$
磁盘容量 = 每扇区字节 \times 每磁道扇区 \times 每面磁道数(柱面数) \times 每盘面数 \times 盘片数
$$

磁盘操作

  1. 寻道时间: 传动臂到特定磁道的时间 $T_{seek}$
  2. 旋转时间: 找扇区 $T_{max \ rotation} = \frac{60}{RPM}$, 也是转一圈需要的时间
    $T_{avg \ rotation} = T_{max \ rotation} / 2$
  3. 传送时间: $T_{avg \ transfer} = T_{max \ rotation} / 每磁道扇区数$

访问一个扇区的平均时间是上三者之和

逻辑磁盘块

磁盘中有个磁盘控制器, 维护编号和实际扇区的关系
编号会被翻译成 (盘面, 磁道, 扇区) 的三元组

连接IO设备

访问磁盘

CPU 使用 内存映射 技术来向 IO 设备发射命令
磁盘控制器将内容直接传送到主存, 不需要CPU 干涉, 这叫直接内存访问(DMA)

6.1.3 固态硬盘

$Solid \ State \ Disk (SSD)$

数据是以页为单位读写的, 只有擦除一个块才能对块里的页进行写

6.1.4 存储技术趋势

增加密度比减少访问时间容易得多

6.2 局部性

局部性原理: 程序倾向于引用临近其他使用过的数据的数据, 或者使用过的数据本身 \

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

空间局部性常见和主要的来源是步长为 $k$ 的引用模式 ($k=1$)
$k$ 增大时, 空间局部性变差

6.2.2 取指令的局部性

程序指令存放在内存中, 可以评价程序取指令的局部性

6.2.3 局部性小结

  1. 重复引用相同变量的程序有良好的时间局部性
  2. 步长为 $k$ 的引用程序, 步长越小空间局部性越好
  3. 取指令: 循环有好的时间和空间局部性, 循环体越小, 迭代次数越多, 局部性越好

6.3 存储器层次结构

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

高速缓存 cache

缓存命中
当程序需要 $k+1$ 层的数据 $d$ 时, 会在 $k$ 层查找 $d$, 找到了就是缓存命中
良好时间局部性的程序缓存命中的机会较多

缓存不命中

从 $k+1$ 层 取出 $d$ 放到 $k$ 层, 可能替代 $k$ 层中的一个块, 被驱逐的块有时称为牺牲块
替换策略有 随机替换, 最近最少被使用替换

缓存不命中的种类

强制性不命中/冷不命中: $k$ 层缓存为空

只要发生不命中, $k$ 层的缓存就要执行某个放置策略

  1. 允许 $k+1$ 层的块放到 $k$ 层的任何位置: 速度快, 代价高
  2. 允许 $k+1$ 层的块放到 $k$ 层的一个子集: $k+1$ 层第 $x$ 块被放到 $k$ 层第 $x \ mod \ 4$ 块中

冲突不命中: 访问 0, 4, 8, 12… 总是不命中

容量不命中, 要访问的对象太多 $k$ 层装不下

缓存管理

在大多时候, 缓存都是自动运行的, 不要程序采用显式行动

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

为实现更多的缓存命中, 需要程序具有良好的时间和空间局部性

6.4 高速缓存存储器

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

有 $m$ 位表示存储器地址, 形成 $M = 2^m$ 个不同地址

元组 $(S, E, B, m)$ 可以描述高速缓存的结构
高速缓存的大小 $C = S \times B \times E$, 其中去除了标记位和有效位

6.4.2 直接映射高速缓存

$E=1$ 的高速缓存被称为直接映射高速缓存

  1. 抽出组索引, 选择组
  2. 抽出地址中的标记, 与组中行的标记位相匹配, 并且行中有效位为 1
  3. 抽出块偏移, 表示所需要的字从行中块的第几个字节开始

不命中时的行替换

对于直接映射告诉缓存, 直接组索引下的一行即可

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

填充可以消除冲突不命中

6.4.3 组相联高速缓存

$1 < E < \frac CB$ 的高速缓存被称为 $E$ 路高速缓存

  1. 组选择相同
  2. 行匹配使用相连存储器, 输入 $key$ 来找到 $value$
    搜索组中的每一行, 与地址中的标记匹配

不命中时的行替换

优先替换空行, 其次有 最不常使用策略, 最近最少使用策略

6.4.4 全相联高速缓存

$E = C / B$ 只有一个组

  1. 组选择: 直接砍掉组索引位
  2. 行匹配和字选择与 组相联高速缓存相同

6.4.5 有关写的问题

写命中

  1. 直写: 写到下一层中, 但每次写都会引起总线流量
  2. 写回: 当这个块要被驱逐时, 把它写到下一层中, 但要维护一个修改位

写不命中

  1. 写分配: 加载低一层的块到高速缓存中, 之后更新
  2. 非写分配: 直接写到低一层中

直写通常是非写分配, 写回通常是写分配

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

只保存指令的高速缓存: $i-cache$, 只保存数据的高速缓存: $d-cache$

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

  1. 不命中率: 不命中数量 / 引用数量
  2. 命中率: 1 - 不命中率
  3. 命中时间: 高速缓存传到 CPU 的时间
  4. 不命中处罚: 由于不命中所需要的额外时间

cache大小: 较大的高速缓存可能会提高命中率, 但也会增加命中时间
块大小: 过大提高命中率, 但增加不命中处罚, 过小反之
相联度: 相联度高则增加命中时间和不命中处罚, 所以不命中处罚越低, 使用越低的相联度
写策略: 层次越低越容易使用写回策略

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

  1. 注意力集中在核心函数核心循环上

  2. 减小每个循环内部的缓存不命中数量

  3. 对局部变量反复引用是好的

  4. 步长为 1 的引用模式是好的

6.6 综合: 高速缓存对程序性能的影响

6.6.1 存储器山

读的速度: 读吞吐量 / 读带宽

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

通过分析数组步长从而确认效率

6.6.3 在程序中利用局部性

  1. 注意力集中在内循环上
  2. 按照数据对象存储在内存中的顺序, 步长为 1 读取内存, 增大空间局部性
  3. 存储器中读入数据对象, 就尽可能多地使用, 增大空间局部性

6.6 小结

RAM, ROM, 磁盘, 硬盘
注意程序编写的局部性

练习

6.1

6.2

$2 * 2 * 10000 * 400 * 512 = 8192000000$

6.3

$8 + 2 + 0.008 = 10.008ms$

6.4

估计有两千个扇区

  1. $5 + 3 + 0.006 * 2000 = 20ms$
  2. $2000 \times (5 + 3 + 0.006) \approx 16000ms$

6.5

  1. 8 年
  2. 13 年
  3. 17535 年

6.6

大概每 一年半 价格减半, 大概到 2025 年

6.7

循环次序 $k$, $i$, $j$

6.8

clear1 > clear2 > clear3

6.9

略

6.10

$75%$

6.11

  1. $2^s$ 个块是一组
  2. 前 $2^18$ 是一组, 这样 array 所有的元素只能放在一个组里

6.12

  1. 12 ~ 5: CT
  2. 4 ~ 2: CI
  3. 1 ~ 0: CO

6.13 ~ 6.16

略

6.17

一步一步往 cache 里面塞即可


  2. 32 个字节足够容纳两个数组, 所以当每个块开始的时候会有不命中

6.18 ~ 6.20

原本的 cache 只能容得下一半的 grid 数组

  1. 每次都是不命中, 命中, 不命中, 命中循环, 答案: 512, 256, 0.5
  2. 同上次, 扩容后只有在第一次的时候会不命中, 答案: 512, 256, 0.5, 0.25
  3. 连续读 x, y, 一次不命中后接三个命中, 扩容也没有影响, 答案: 512, 128, 0.25, 0.25

6.21

$2100 / 12000 * 8 \approx 1.5 周期$

6.22

基本不等式可得 $x = 0.5$

6.23

$4 + (60000/15000) / 2 + (60000/15000) / 800 = 6.005ms$

6.24

  1. $4 + 2 + 0.004 * 4000 = 22ms$
  2. $4000 \times (4 + 2 + 0.004) \approx 24000ms$

6.25 ~ 6.33

略

6.34

src[0], src[2], dst[0], dst[2] 在块 1, 其余在块 2, 剩下模拟即可

6.35

128 字节所有的数组都能放下, 每行第一个是 m, 其他是 h

6.36

  1. 100%
  2. 25%
  3. 由于 LRU 策略, 被替换的块以后都不会用了, 25%
  4. 不能, 扩大总容量跟情况2一样, 25%
  5. 可以, 同样是被替换的块不会再用, $\frac 18$ 12.5%

6.37

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstring>

using namespace std;

const int S = 256;

int pre[S];

int get(int x, int y, int N) {

    int id = x * N + y;
    int which_s = (id / 4) % S;
    
    int tmp = id / 4 * 4;
    int res = int(pre[which_s] != tmp);

    pre[which_s] = tmp;

    return res;
}

double sumA(int N) {
    int vacant = 0;
    memset(pre, -1, sizeof pre);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            vacant += get(i, j, N);

    return 1.0 * vacant / (N * N);
}

double sumB(int N) {
    int vacant = 0;
    memset(pre, -1, sizeof pre);
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            vacant += get(i, j, N);

    return 1.0 * vacant / (N * N);
}

double sumC(int N) {
    int vacant = 0;
    memset(pre, -1, sizeof pre);
    for (int j = 0; j < N; j += 2) 
        for (int i = 0; i < N; i += 2) 
            vacant += get(i, j, N) + get(i + 1, j, N) +
                      get(i, j + 1, N) + get(i + 1, j + 1, N);
    return 1.0 * vacant / (N * N);
}

void test(int N) {
    cout << "N: " << N << endl;
    cout << sumA(N) << endl;
    cout << sumB(N) << endl;
    cout << sumC(N) << endl;
}

int main() {
    test(64);
    cout << endl;
    test(60);
    return 0;
}

使用程序模拟即可

6.38

  1. 1024
  2. 128
  3. 12.5%

6.39

  1. 1024
  2. 256, 有256次循环
  3. 25%

6.40

  1. 1024
  2. 128 + 128, 第一个循环 16 * 16 / 2, 第二个循环一样
  3. 25%

6.41

类似 6.39, 25%

6.42

类似 6.41, 25%

6.43

每次都不命中, 100%

6.44

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Clock frequency is approx. 2495.3 MHz
Memory mountain (MB/sec)
        s1      s2      s3      s4      s5      s6      s7      s8      s9      s10     s11     s12     s13     s14    s15
128m    48812   26028   17525   13319   10529   7781    5952    4623    3946    3485    3909    3591    3341    3140   3011
64m     57490   31492   20983   16559   13554   11475   9621    7352    6988    6282    5846    5287    5044    4868   4319
32m     60452   41773   28792   25183   19910   16338   13622   11359   10196   9620    9651    9963    9768    11949  12536
16m     67178   58971   45000   35361   27445   22549   19164   16285   15586   14616   14368   14219   14118   14115  14517
8m      68021   60963   46108   36517   27876   22910   19264   16563   15795   14827   14410   14153   14108   14068  14476
4m      68550   63219   49625   36302   27798   22959   19255   16502   15848   14751   14383   14073   14124   13954  14334
2m      68026   62334   48622   35940   27816   23165   19544   16740   15897   15026   14728   14560   14978   15366  16417
1024k   65208   54567   43391   34113   27290   23413   20342   18045   18170   18622   19378   20049   20330   20882  20890
512k    68494   65086   56633   42613   33437   28502   24430   21307   21298   21272   21333   21376   21411   21359  21272
256k    68315   65412   57003   42753   33544   28501   24591   21101   21376   21272   21237   21376   21410   21237  21534
128k    68137   65412   56633   42475   33544   27953   24590   21238   21376   21446   21623   21375   21410   20765  21804
64k     68137   64129   55907   41931   33544   27952   24590   21517   22022   21802   21235   20964   21876   23361  43607
32k     68137   62896   64125   58403   59460   60563   58401   51103   51901   65396   59447   54496   62880   46711  54496
16k     65412   68137   68133   58403   54496   54496   77852   51103   60552   54496   49539   45414   62880   38926  54496

6.45 ~ 6.46

主要使用分块的一些想法

Prev
2023-08-24 17:10:00 # Book #C #CSAPP
Next