Valgrind与Cache评测

本实验应用了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安装（本实验不推荐此种安装方式）：

首先是进入官网下载对应版本：http://valgrind.org/downloads/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的格式如下：

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

其中operation表示操作类型，address和size则对应其操作的地址和字节数。

关于操作类型，共分为以下四类：

I 表示取指
L 表示取数（Load）
S 表示存数（Store）
M 表示修改（可以视为先Load后Store）

对于Cache而言，我们只需关心 “L” “S"和"M"三类操作。

具体来说，我们的Cache模拟器从trace文件中读取对应的操作，并根据操作类型和操作内容更新Cache，通过与参考Cache比对命中和缺失情况来判断Cache是否正确。

Part2：矩阵转置缺失率评测

评测的核心即，如何通过valgrind获取矩阵转置过程中的内存访问情况，并通过Cache模拟器进行检验。

在实验的评测代码test-trans.c中给出了完整的评测逻辑：

首先考察tracegen程序，在tracegen.c中，调用了我们在trans.c中补全的转置函数，并完成了矩阵的初始化、转置及检验全过程。
首先执行tracegen生成对应的记录日志trace.tmp（test-trans.c第71行）：
```
sprintf(cmd, "valgrind --tool=lackey --trace-mem=yes --log-fd=1 -v ./tracegen -M %d -N %d -F %d  > trace.tmp", M, N,i);
flag=WEXITSTATUS(system(cmd));
```
该访问记录包含了矩阵初始化、转置、检验全过程的记录日志。
我们需要根据trace.tmp，找到我们执行矩阵转置的部分，将其中涉及到存数/取数的命令提取出来，放到trace.f0（可以同时评测多个转置函数，对应trace.f1，trace.f2…）。
如何识别出trace.tmp的哪一部分是矩阵转置呢？也即如何识别出tracegen程序的哪一部分是矩阵转置呢？这里用到了一个小trick：
- 首先在tracegen.c中声明了两个volatile变量，volatile变量的特点是，会分配在内存中指定地址，不随着程序的执行而改变。
```
volatile char MARKER_START, MARKER_END;
```
  之后保存这两个变量的内存地址：
```
fprintf(marker_fp, "%llx %llx", (unsigned long long int) &MARKER_START, (unsigned long long int) &MARKER_END );
```
- 然后在调用转置函数的前后，标记这两个变量：
```
MARKER_START = 33;
(*func_list[selectedFunc].func_ptr)(M, N, A, B);
MARKER_END = 34;
```
- 在读取trace.tmp的时候，所检测到的夹在两个变量之间的部分也就是矩阵转置的部分。
最后将矩阵转置函数的内存访问记录输入到我们的Cache模拟器中，得到最终的缺失结果（test-trans.c第140行）：
```
sprintf(cmd, "./csim-ref -s %u -E %u -b %u -t trace.f%d > /dev/null", 
                s, E, b, i);
system(cmd);
```

此外需要特别注意，实验二评测中实际给出的miss数量一般会比理论分析多出3次，这3次是在仿真过程中产生的与矩阵转置过程无关的其他开销，我们的评测以实际给出的miss数量为准。