深入理解计算机系统笔记

阅读数: 次 2020-05-18

[toc]

存储器层次结构

存储器层次结构

高速缓存存储器

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

定义符号：考虑一个计算机系统，每个存储器地址m位，形成$M=2^m$个地址，其高速缓存被组织成一个有$S=2^s$个高速缓存组 (cache set) 的数组，每个组包含$E$个高速缓存行 (cache line)，每个行由一个$B=2^b$字节的数据块 (block) 组成，一个有效位 (valid bit) 指明这个行是否包含有意义的信息，$t=m-(b+s)$个标记位 (tag bit) (当前块的内存地址的位的一个子集)，标记位唯一标识存储在高速缓存行中的块。

数据以块为大小在层与层之间传输。

理解：对一个地址 (32 bits or 64 bits)，将其划分为高位、中间位、低位，用中间位进行上一级缓存中某个地址的块的映射，这样可以保证连续内存映射到不同的高速缓存组；用高位 (标记位) 对高速缓存行进行唯一标识；用低位表示高速缓存行中数据块每个字节的偏移。

1	m(地址长度) = t(高位) + s(中间位) + b(低位)

直接映射高速缓存

每个 cache set 只有一个 cache line。

组相联高速缓存

每个 cache set 有$1<E<C/B$个 cache line，$C$为缓冲区大小(字节)，$B$为块大小(字节)。

全相联高速缓存

由一个包含所有高速缓存行的组组成，仅仅将地址划分为标记位 (高位) 和块偏移 (低位)。由于高速缓存电路需要并行搜索许多标记位，构造又大又快的相联高速缓存很困难而且价格昂贵，知识和做小的高速缓存。

有关写的问题

如何写一个已经缓存了的字$w$（写命中）？
- 直写 (write-through)，立即将$w$的高速缓存块写回到紧接的低一层中。缺点为每次写都会引起总线流量；
- 写回 (write-back)，只有当替换算法要驱逐这个更新过的块时，才把它写道紧接着的第一层中。由于局部性，可以显著减少总线流量，缺点是增加了复杂性，需要维护一个表明该高速缓存块是否被额外修改过的修改位（dirty bit）；
如何处理写不命中？
- 写分配 (write-allocate)，加载相应的第一层的块到高速缓存中，然后更新这个高速缓存块，缺点为每次写不命中都会导致一个块从低一层到高速缓存；
- 非写分配 (not-write-allocate)，避开高速缓存，直接把这个字写道低一层中；
采用使用写回和写分配的高速缓存模型，这两种处理方式都利用局部性，因此我们可以在高层次开发程序，展示良好的空间和时间局部性。

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

一个高速缓存存储器既存储指令又存储程序数据。

只存储指令的高速缓存称为$i-cache$
只存储数据的高速缓存称为$d-cache$
既保存数据有保存指令的高速缓存称为统一的高速缓存

下图为 Intel Core i7 处理器的高速缓存层次结构。

编写高速缓存友好的代码

局部性较好的程序更容易有较低的不命中率，因此也运行得更快。

把注意力集中在核心函数里的循环上，忽略其他部分；
尽量减小每个循环内部的缓存不命中数量；

结论：

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

对于一个二维数组求和的程序：在数组大小大于高速缓存大小更大的时候，按行访问数组比按列访问数组快很多，因为按列访问数组时，每一次访问都会发生读不命中。

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

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

在计算矩阵乘法时，考虑$C=A*B$：
$$
\begin{equation}\left[\begin{array}{c}
c_{11} c_{12} \
c_{21} c_{22}
\end{array}\right]=\left[\begin{array}{l}
a_{11} a_{12} \
a_{21} a_{22}
\end{array}\right]\left[\begin{array}{l}
b_{11} b_{12} \
b_{21} b_{22}
\end{array}\right]\end{equation}
$$
那么性能最好的三层循环：

for (k = 0; k < n; k++)
    for (i = 0; i < n; i++) {
        r = A[i][k];
        for (j = 0; j < n; j++)
            C[i][j] += r*B[k][j];
    }

它的不命中率最低。

在程序中利用局部性

将注意力集中在内循环，大部分计算和内存访问都发生在内循环；
按照数据对象存储在内存中的顺序、以步长为1来读数据，使得程序空间局部性最大；
一旦从存储器读入了一个数据对象，就尽可能使用它，最大化时间局部性；

链接

链接是将各种代码和数据片段收集并组合为一个单一文件的过程，可以执行于：

编译时 (compile time)
加载时 (load time)
运行时 (run time)

编译器驱动程序

编译器驱动程序：调用

预处理器
编译器
汇编器
链接器

Linux 运行可执行文件时，调用一个叫做加载器的函数，将可执行文件中的代码和数据复制到内存，然后将控制转移到这个程序的开头。

静态链接

Linux LD是一个静态链接器 (static linker)，以一组可重定位目标文件和命令行参数为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。

可重定位目标文件由不同的代码和数据节 (section)组成。

链接器的任务：

符号解析 (symbol resolution)，唯一关联每个符号引用和符号定义；
重定位 (relocation)，把每个符号定义与一个内存位置关联起来，从而重定义这些节，然后修改所有对这些符号的引用，使得他们指向这个内存位置。链接器使用编译器产生的重定位条目 (relocation entry)的详细指令，不加甄别地执行重定位。

目标文件

目标文件有三种形式：

可重定位目标文件，包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件；
可执行目标文件，包含二进制代码和数据，其形式可以直接复制到内存并运行；
共享目标文件，共享库，包含静态库和动态库；

编译器和汇编器生成可重定位目标文件、共享目标文件；链接器生成可执行目标文件。

目标文件是按照特定的目标文件格式来组织的：

Windows使用 Portable Executable, PE 格式；
Mac OS-X 使用 Mach-O 格式；
现代x86-64 Linux和Unix系统使用 Executable and Linkable Format, ELF 格式；