本实验应用了Valgrind这一强大的工具来辅助我们完成Cache的设计与评测，为了方便同学们理解memory trace（即我们所说的内存访问记录），并理解我们如何获取矩阵转置函数的内存访问记录，我们对Valgrind和实验中的评测代码进行进一步的说明（此部分不理解完全不影响实验的完成，只需成功安装Valgrind用于本地实验评测即可）。

Valgrind简介

Valgrind 是运行在Linux 上的多用途代码剖析和内存调试软件。主要包括Memcheck、Callgrind、Cachegrind 等工具，每个工具都能完成一项任务调试、检测或分析。可以检测内存泄漏、线程违例和Cache 的使用等。Valgrind 基于仿真方式对程序进行调试，它先于应用程序获取实际处理器的控制权，并在实际处理器的基础上仿真一个虚拟处理器，并使应用程序运行于这个虚拟处理器之上，从而对应用程序的运行进行监视。应用程序并不知道该处理器是虚拟的还是实际的，已经编译成二进制代码的应用程序并不用重新进行编译，Valgrind 直接解释二进制代码使得应用程序基于它运行，从而能够检查内存操作时可能出现的错误。

Valgrind的安装

由于valgrind没有提供Windows版本，因此建议是使用Linux系统（可以使用虚拟机）来进行相关的调试。

关于Mac：官方的valgrind不支持Mac或对Mac后续版本支持的不好，需要安装Mac的镜像版本，可以在github上找到：https://github.com/LouisBrunner/valgrind-macos

在安装时遇到的常见问题，可以参考博文：https://zhuanlan.zhihu.com/p/508470880

笔者用的是ubuntu，在ubuntu下直接使用系统包管理工具即可安装（无特殊需要建议直接以此方式安装）：

sudo apt-get install valgrind

如果有特定需求需要安装一些其他版本，可以进入valgrind官网，下载对应的源码并make安装（本实验不推荐此种安装方式）：

• 首先是进入官网下载对应版本：https://sourceware.org/pub/valgrind/valgrind-3.12.0.tar.bz2

• 然后解压缩：

  tar -jxvf valgrind-3.14.0.tar.bz2
  

• 进入目录,进行安装,其中/home/user1/valgrind是你想安装的目录：

  cd valgrind-3.14.0
  ./configure --prefix=/home/user1/valgrind
  make
  make install
  

• 配置环境变量，首先打开~/.bashrc，将下面一段话加入该文件，路径即为安装目录下bin目录：

  export PATH=$PATH:~/valgrind/bin/
  

  使改变生效：

  source ~/.bashrc
  

Valgrind的使用

valgrind的使用可以简要概括为以下表示：

valgrind [valgrind-options] <your-prog> [your-prog-options]

其中，<your-prog> [your-prog-options]部分是需要进行内存调试的程序执行命令，与在shell命令行中执行命令的方式完全相同。[valgrind-options]是我们重点需要关注的部分，通过这些options我们得以应用valgrind的功能。valgrind提供了丰富的调试选项，以下列出一些常用的选项。

• --tool=<toolname> [default: memcheck]

  最核心的命令，选择了valgrind当前的工作模式。

• -h --help

  与一般的帮助选项相同，可以比较便捷的查看valgrind的命令用法。

• -v --verbose

  输出详细信息。

• --log-fd=<number> [default: 2, stderr]

  打印输出访问记录的位置，number为1表示stdout，number为2表示stderr，用此命令时一般设number为1在命令交互界面查看输出。

• --log-file=<filename>

  与上一条命令类似，但是将记录日志输出到对应的文件中（更加推荐这种方式）。

Valgrind在Cache评测中的应用

Part1：Cache的模拟器实现

valgrind可以通过简单的命令生成程序模拟执行过程中产生的记录日志（memory trace）。

memory trace的格式如下：

本次实验共包括两个部分，在Part1中我们将首先完成一个Cache模拟器，从而模拟每条访存指令的命中/缺失情况，在Part2中我们将基于Part1实现的Cache模拟器，针对特定大小的矩阵，给出矩阵转置的优化策略，使得miss（即缺失数）尽可能低。我们只需要根据下发的实验代码，补全文件csim.c和trans.c即可。

Part1 Cache模拟器实现（5分）

在本节中，我们将完成一个Cache模拟器，它通过读取memory trace（内存访问记录文件），模拟访问内存的过程，并且给出每条访问记录在Cache中的命中/缺失情况。本实验只需要补全csim.c文件中的内容，提交评测也只需提交该文件。

题目描述

我们要求实现的Cache模拟器需要满足的功能详情描述如下。

读入文件（memory trace）格式

我们实现的Cache模拟器将从文本文件中逐行读取内存访问记录，每一条记录代表了一次内存相关操作。为了评测方便，内存访问记录的格式与valgrind（一个强大的程序内存检测工具，后文会有介绍）的输出格式相同，具体格式如下：

[space]<operation> <address>,<size>

• <operation>表示操作类型，共分为4类
  • I 表示取指
  • L 表示取数（Load）
  • S 表示存数（Store）
  • M 表示修改（可以视为先Load后Store）
• [space]为空格，当<operation>为除I类型之外的类型时，会在行首保留一个空格（这一安排是为了与valgrind的格式保持一致）。
• <address>为16进制数，表示一个64位地址（注意地址大小可能会超过32位）
• <size>为10进制数，表示存/取的内存大小（单位：字节）

memory trace示例：

I 0400d7d4,8
 M 0421c7f0,4
 L 04f6b868,8
 S 7ff0005c8,8

Cache使用方法

./csim [-hv] -s <s> -E <E> -b <b> -t <tracefile>

• -h: 输出帮助信息（帮助信息选做，不在评测范围内）
• -v: 输出详细trace信息（可以选择是否输出详细信息，输出格式见后文）
• -s <s>: set bits （$S=2^s$ 代表组的数量，评测保证 s 不超过10）
• -E <E>: lines bits （$E$ 代表每组的block个数，即行数/路数，评测保证 E 不超过 8）
• -b <b>: block bits （$B=2^b$ 代表block的大小，单位为字节，评测保证 b 不超过10）
• -t <tracefile>: 内存访问记录文件（memory trace）

我们的Cache程序需要完成以下操作：

Cache运行与冲突替换

Cache运行流程

如下图所示，当我们对一个地址进行访存操作时，我们按照前文所述的地址结构进行匹配。

首先我们根据地址中的组号（set），查找到Cache中的对应组（图中绿色箭头所指的部分）。之后我们将标记（tag）与Cache中该组所有行的tag进行比较（即图中左部比较的部分）。

如果Cache中某行的tag能够匹配，则说明Cache中有对应的数据块，即命中（hit）。当命中时，处理器直接对Cache进行对应的访存操作，可以通过地址中的offset，查找Cache存储的block中的offset，从而找到该地址对应的数据信息。

如果Cache中没有对应的数据块，那么就是不命中（miss）的情况。当不命中时，缓存从主存中取出包含该地址的块，并需要放入缓存中。假如Cache中该地址所属组的所有行均已被占用，那么就需要覆盖一个现有的块，这一过程通常称为替换/驱逐（eviction）。在本实验中，我们假设当Cache的块被换出时，被换出块中如果发生数据更改则此时写回主存。

这里我们就会遇到一个问题，当需要替换时，如何在Cache中选择被替换的块？我们的目的是使得发生替换的情况尽可能少，从理论上来说，我们应当选择现有块中将来不再使用的块，或者选择现有块中经过最长时间才会使用到的块，因为这最大程度上推迟了下一次发生替换的时刻，我们可以证明，如果我们能够预知程序未来将要访问的地址的话，上述的替换策略是最优的，这一策略被称为最佳置换算法（OPT，OPTimal selection）。

事实上，我们很难达到预知未来的要求，我们的替换选择往往通过已有的命中情况来推算，因此我们介绍以下三种常见的替换算法。

常见替换算法

先进先出法（FIFO，First-In-First-Out），顾名思义，即选择最早装入的块进行替换。它的实现比较简单，不需要记录各个块的访问情况，比较容易实现，开销小。但是这种算法没有依据访存的局部性原理（最早调入的块有可能是经常访问的块），因此不能提高Cache的命中率。

FIFO策略的实现：

• 缓存的每一块都设定一个计数器，初始时均为0。
• 当某块被装入或被替换时该块的计数器清为0，而同组的其它各块的计数器均加1，
• 当需要替换时就选择计数值最大的块被替换掉。

最低使用频率法（LFU，Least-Frequently Used），即替换出使用频率最低的块，又称最不经常使用算法。

LFU策略的实现：

• 缓存的每一块都设定一个计数器，初始时均为0。
• 当某块被装入或被访问时该块的计数器加1。
• 当需要替换时就选择计数值最小的块被替换掉，如果计数值相同则替换出装入时间更早的块。

最近最少使用法（LRU，Least-Recently Used），含义为替换出近期用的最少的块。它与LFU的区别在于它更加关注各个块在近期的访问情况，即近期的权重会更高。LRU需要随时记录Cache中各块的访问情况，以便确定近期最少使用的块。LRU比较复杂，一般来说我们采用简化的方法，只记录每个块最近一次使用的时间，替换时选择距上一次使用经过时间最长的块。

LRU策略的实现：

• 缓存的每一块都设置一个计数器，初始时均为0。
• 访问命中时，所有块的计数值与命中块的计数值进行比较，如果某块计数值小于命中块的计数值， 则该块的计数值加 1；如果该块的计数值大于命中块的计数值，则数值不变；最后将命中块的计数器清为0。
• 访问未命中，需要替换/装入时，则选择计数值最大的块被替换/装入，其计数器清为0，而其它的计数器则加1（除了初始装入之外，计数值是不会出现相等情况的，可以思考一下为什么）。

分块技术与实验提示

分块技术

分块技术是一项很有趣的技术，它可以提高循环中的时间局部性。分块的大致思想是将一个程序中的数据结构组织成大的块（在这里，“块”指的是一个应用级的数据组块，而不是我们之前介绍的高速缓存块）。这样构造程序，使得能够将一个块加载到高速缓存中，并在这个块内进行所需的所有读和写，然后丢掉这个块再加载下一个块。

分块会使得代码更难阅读和理解，由于这个原因，它最适合优化编译器或者频繁执行的库函数。这项技术学习和理解起来还是很有趣的，因为它是一个通用的概念，可以在一些系统上获得极大的性能收益。

实验提示

我们将以 $s=5,E=1,b=5$ 结构的Cache为例，结合大小为 $32\times 32$ 的矩阵，来初步分析在矩阵转置中应用分块等技术可以优化的方面，希望能够启发同学们的思路。我们假设矩阵A和B的地址都是block大小对齐的。

最常规的转置思路即，遍历A的所有行，将其存放到B的对应列中。

void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            B[j][i] = A[i][j];
        }
    }
}

我们来结合Cache的结构分析一下转置过程中产生的缺失（miss）情况。首先block大小 $B=2^b=32$ 字节，即可以存放 $8$ 个int型值；$E = 1$ 为直接映射，即Cache中每组只有一行；$S = 2^s=32$ ，即分为 $32$ 个组，整个Cache可以存放 $32\times 8=256$ 个int型值。对应到矩阵中，我们可以发现，矩阵的前8行就正好能够填满我们的Cache。结合下方矩阵B的示意图，我们可以进行进一步的分析。

考虑到实验内容的发布早于理论课，因此补充了本章理论介绍的内容，为大家提供一些理论上的参考。

如果阅读完本章仍然有所困惑，可以参考课程教材CSAPP（深入理解计算机系统）的6.2-6.4节。

缓存与局部性原理

存储器层次结构中的缓存

早期计算机系统的存储器层次结构只有三层：CPU寄存器、DRAM主存储器和磁盘存储。不过，由于CPU和主存之间逐渐增大的性能差距，系统设计者被迫在CPU寄存器文件和主存之间插入了一个小的SRAM高速缓存存储器，称为L1高速缓存。SRAM的价格比主存贵，但因其容量远小于主存，因此能很好地解决速度和成本的矛盾。L1高速缓存的访问速度几乎和寄存器一样快，典型的是2~4个时钟周期。

随着CPU和主存之间的性能差距不断增大，系统设计者在L1高速缓存和主存之间又插入了一个更大的高速缓存，称为L2高速缓存，有些现代系统还包括有一个更大的高速缓存，称为L3高速缓存。虽然安排上有很多的变化，但是通用的原则还是一样的，在本实验中，我们可以视为CPU和主存之间只有一个L1高速缓存。

局部性原理

局部性原理是缓存设计所依托的基本思想，大量典型程序的运行情况分析结果表明，无论是存取指令或存取数据所访问的存储单元都趋于聚集在一个较小的连续存储区域中。

局部性原理通常有两种不同的形式：时间局部性和空间局部性。时间局部性可以概括为：刚被访问的存储单元可能不久又将被访问。空间局部性则可以概括为：刚被访问过的存储单元的邻近单位可能不久会被访问。

比如我们访问一个数组的某个内存单元，那么我们很可能紧接着就要访问它相邻的下一个内存单元，或者我们不久之后还要再次访问这一单元，局部性原理正是表达了这样的思想。而进一步地，如果我们能在访问这一内存单元的时候，将它还有与它相邻的一小部分内存单元加入存取速度更高的缓存中，那么在后续访问的过程中，就能够直接到缓存中访问，从而显著加快程序运行的速度，这正体现了缓存设计的基本思想。

通用高速缓存结构

基于以上的介绍，我们对高速缓存（Cache）可以建立起一些抽象的认识：

• 相对大而慢的主存而言，Cache应当是小而快的。
• 对于程序中对某个地址的访问，Cache应当能够获取一个对应的局部块。
• 当程序中对相邻地址继续访问时，可以通过访问Cache来实现，不必再次访问主存。
• Cache应当在程序经常访问的位置发生变化时，腾出空间给新的局部块。

下面我们来详细的介绍通用的Cache的结构：

考虑主存地址为 $n$ 位的计算机系统，主存大小即 $2^n$ 字节，我们取这 $n$ 位中的低 $b$ 位，以 $B=2^b$ 作为一个块的大小，从而将地址空间划分为 $2^{n-b}$ 个块（block）。对应的，地址的低 $b$ 位表示一个字节相对于本块内的位置，我们称为块内偏移（offset），地址的高 $n-b$ 位即表示块号（block number）。其地址格式即如下图所示：

我们可以理解为，Cache在从主存中存取数据时，就是以块为单位进行操作的。相应的，Cache在数据组织的过程中，自然也要以块为基本单元，在存储一个块的同时，Cache也要存储一些与此块相对应的信息，我们将Cache中这样包含了一个块和其相关信息的结构称为行（line）。

主存中有诸多的块，而Cache的大小尽管远小于主存，仍然能存放相当数量的行，我们希望解决从主存的块到Cache的行的映射关系，这里要引入组（set）的概念。我们将主存的所有块分为 $S=2^s$ 组，同时我们将Cache也作对应分组，我们使得主存中同组的那些块仅能映射到Cache中对应组的那些行中。这样我们在拿到一个地址之后，首先分析它所在的分组，再在Cache中对应的分组中查询有没有对应的行，从而降低在Cache中查询的成本。而当Cache同组的所有行都填满之后，我们也只会腾出该组中的行来存放新的数据块，不会影响其他组。

我们希望分组之后相邻的块能被分到不同的组（由于局部性原理，相邻的块也有可能同时需要访问，我们不希望把它们分到同一组来相互挤占有限的Cache资源），因此我们将块号（即内存地址的高 $n-b$ 位）的低 $s$ 位作为组号。而由于主存的分组已经和Cache的分组建立起对应关系，我们在Cache中只需要地址的高 $n-s-b$ 位作为标记（tag），就可以唯一地识别出该组中是否有哪一行存放了我们的想要的主存块。这样划分后的地址格式如下图所示：

相应的Cache结构如下图所示：首先Cache包含 $S=2^s$ 个高速缓存组（set）；每个组包含 $E$ 个高速缓存行（line）；每个行由三部分组成，一个 $B=2^b$ 字节的数据块（block），一个有效位（valid bit）指明这个行保存的信息是否有意义，还有 $t=n-(b+s)$ 个标记位（tag）来唯一地识别组内的某一行。

这样结构的Cache，我们称之为组相联的。

当 $s=0$ ，即组的数量退化为只有一组时， 主存中的任意块都可以映射到Cache中的任意行，这种情况下的Cache我们称为是全相联的。而当 $E = 1$，即Cache中每组的行数退化为只有一行时，这种情况主存中同组的若干块都只能映射到Cache中的特定一行，我们将其称为直接映射。