所有实验文件可见github 计算机系统实验整理

实验报告

实 验（六）

题 目 Cachelab
高速缓冲器模拟　
专 业
学　　 号
班　　 级
学 生
指 导 教 师
实 验 地 点
实 验 日 期

计算机科学与技术学院

目 录

第1章 实验基本信息 - 3 -
1.1 实验目的 - 3 -
1.2 实验环境与工具 - 3 -
1.2.1 硬件环境 - 3 -
1.2.2 软件环境 - 3 -
1.2.3 开发工具 - 3 -
1.3 实验预习 - 3 -
第2章 实验预习 - 4 -
2.1 画出存储器层级结构，标识容量价格速度等指标变化（5分） - 4 -
2.2用CPUZ等查看你的计算机CACHE各参数，写出各级CACHE的C S E B S E B（5分） - 4 -
2.3写出各类CACHE的读策略与写策略（5分） - 4 -
2.4 写出用GPROF进行性能分析的方法（5分） - 4 -
2.5写出用VALGRIND进行性能分析的方法（5分） - 4 -
第3章 CACHE模拟与测试 - 5 -
3.1 CACHE模拟器设计 - 5 -
3.2 矩阵转置设计 - 5 -
第4章 总结 - 6 -
4.1 请总结本次实验的收获 - 6 -
4.2 请给出对本次实验内容的建议 - 6 -
参考文献 - 7 -

第1章 实验基本信息

1.1 实验目的
理解现代计算机系统存储器层级结构
掌握Cache的功能结构与访问控制策略
培养Linux下的性能测试方法与技巧
深入理解Cache组成结构对C程序性能的影响
1.2 实验环境与工具
1.2.1 硬件环境
X64 CPU；2GHz；2G RAM；256GHD Disk
1.2.2 软件环境
Windows10 64位; Vmware 11；Ubuntu 16.04 LTS 64位
1.2.3 开发工具
Visual Studio 2010 64位以上；TestStudio；Gprof;Valgrind等
1.3 实验预习
上实验课前，必须认真预习实验指导书（PPT或PDF）
了解实验的目的、实验环境与软硬件工具、实验操作步骤，复习与实验有关的理论知识。
画出存储器的层级结构，标识其容量价格速度等指标变化
用CPUZ等查看你的计算机Cache各参数，写出C S E B s e b
写出Cache的基本结构与参数
写出各类Cache的读策略与写策略
掌握Valgrind与Gprof的使用方法
第2章 实验预习

2.1 画出存储器层级结构，标识容量价格速度等指标变化（5分）

2.2用CPUZ等查看你的计算机Cache各参数，写出各级Cache的C S E B s e b（5分）

一级数据缓存 C: 192KB S:384 E:8 B:64 s:9 b:6 e:3
一级指令缓存 C: 192KB S:384 E:8 B:64 s:9 b: 6 e:3
二级缓存 C:1536KB S:6144 E:4 B:64 s:13 b: 6 e:2
三级缓存 C:12MB S:12288 E:16 B:64 s:14 b:6 e:4
2.3写出各类Cache的读策略与写策略（5分）
Cache读策略：

1. 缓存命中，从对应的cache向CPU中的寄存器文件传送数据或是向上一级cache传送数据。
2. 缓存未命中，从主存或是下一级cache读取需要的数据，并根据情况决定是否要驱逐数据来写入需要的数据。
   Cache写策略：
3. 写命中：
   a. 直写：立即将w的高速缓存快写回到紧接着的第一层中
   b. 写回：只有当替换算法要驱逐这个更新过的块时，才把它写到紧接着的第一层中
4. 写不命中
   a. 写分配，加载相应的第一层的块到高速缓存中，然后更新这个高速缓存块
   b. 非写分配，避开高速缓存，直接把这个字写到低一层中。
   2.4 写出用gprof进行性能分析的方法（5分）
   gprof是GNU profile工具，可以运行于linux、AIX、Sun等操作系统进行C、C++、Pascal、Fortran程序的性能分析，用于程序的性能优化以及程序瓶颈问题的查找和解决。通过分析应用程序运行时产生的“flat profile”，可以得到每个函数的调用次数，每个函数消耗的处理器时间，也可以得到函数的“调用关系图”，包括函数调用的层次关系，每个函数调用花费了多少时间。使用步骤如下：
   （1）用gcc、g++、xlC编译程序时，使用-pg参数，如：g++ -pg -o test.exe test.cpp编译器会自动在目标代码中插入用于性能测试的代码片断，这些代码在程序运行时采集并记录函数的调用关系和调用次数，并记录函数自身执行时间和被调用函数的执行时间。
   （2）执行编译后的可执行程序，如：./test.exe。该步骤运行程序的时间会稍慢于正常编译的可执行程序的运行时间。程序运行结束后，会在程序所在路径下生成一个缺省文件名为gmon.out的文件，这个文件就是记录程序运行的性能、调用关系、调用次数等信息的数据文件。
   （3）使用gprof命令来分析记录程序运行信息的gmon.out文件，如：gprof test.exe gmon.out则可以在显示器上看到函数调用相关的统计、分析信息。上述信息也可以采用gprof test.exe gmon.out> gprofresult.txt重定向到文本文件以便于后续分析。
   2.5写出用Valgrind进行性能分析的方法（5分）
   Valgrind包含下列工具：
   1、memcheck：检查程序中的内存问题，如泄漏、越界、非法指针等。
   2、callgrind：检测程序代码的运行时间和调用过程，以及分析程序性能。
   3、cachegrind：分析CPU的cache命中率、丢失率，用于进行代码优化。
   4、helgrind：用于检查多线程程序的竞态条件。
   5、massif：堆栈分析器，指示程序中使用了多少堆内存等信息。
   6、lackey：
   7、nulgrind：
   这几个工具的使用是通过命令：valgrand --tool=name 程序名来分别调用的，当不指定tool参数时默认是 --tool=memcheck

第3章 Cache模拟与测试
3.1 Cache模拟器设计
提交csim.c
程序设计思想：
由于程序的主体框架已经给定了，因此我们需要实现的部分主要就是cache的初始化、释放空间以及模拟cache的查询数据的过程。
首先是初始化函数，具体的函数代码如下：

可以发现我们是将cache视为一个二维的指针数组，其中第一维是 S 个 cache_set_t 类型的指针代表 S 个组，而第二维有 E 个 cache_line_t 代表每个组有E行，这样就基本形成了一个cache，接着我们对于分配空间中的每一个空间都设置了valid，tag，lru，其中我们将掩码set_index_mask 设置为（1<<s）-1，主要的目的是为了后面获得tag的时候用一个移位和按位与就可以得到我们需要的cache中行的tag。
接着是free函数，这个函数相对比较简单，主要就是使用了c语言的函数free将init中申请的空间释放。
最后是最关键的一个函数——accessData，这个函数也是模拟cache行为的最关键的函数，主要的思路就是首先求出我们需要取的数据的tag和set，如果在cache中存在这个数据的话，那么就意味着命中，那么就可以将对应的数+1，同时由于我们使用lru来标志每一个数据有多久没有被使用过了，因此命中一次之后就将该数据的lru设置为0；如果未命中的话，需要考虑是否需要驱逐，首先我们先找到lru最大的数，这个数据就是有可能需要被驱逐的数据。分为两种情况，一种是冷不命中，这种情况对应需要写入的数据位置的valid等于0，而需要驱逐的情况就对应着valid等于1。不命中情况的代码如下：

测试用例1的输出截图（5分）：

测试用例2的输出截图（5分）：

测试用例3的输出截图（5分）：

测试用例4的输出截图（5分）：

测试用例5的输出截图（5分）：

测试用例6的输出截图（5分）：

测试用例7的输出截图（5分）：

测试用例8的输出截图（10分）：

注：每个用例的每一指标5分（最后一个用例10）——与参考csim-ref模拟器输出指标相同则判为正确
3.2 矩阵转置设计
提交trans.c
程序设计思想：
首先我们需要考虑为什么需要对矩阵转置的程序进行不同方式的优化，这是因为我们知道cache 的参数为32组，每组1行，每行可存放 32个字节。也就是说cache中一行可以存储8个int型的数据，如果我们采用最简单的二维数组直接交换的话A和B在cache中总是共享同一个块，那么很显然出现的miss的情况将会非常多，这就是我们需要进行优化的原因。
1.3232
我们观察到cache中每块可以存储8个int型的数据，那么也就是矩阵的8行可以填满一个cache，也就是说矩阵中相差8行的数据是共享一个cache的，基于这个事实我们将矩阵分割成88的小矩阵，可以看如下示意图：

其中我们把每一个格子视为一个8*8的矩阵，以编号为2的矩阵为例，我们需要做的是将它放到编号为5的矩阵的位置，并进行转置，很显然，这两个小矩阵是不会共享一个块的，那么出现的不命中的情况就会大大下降。其余的格子类似。这种方法中主要出现的miss情况出现在对角线格子上，在这些小矩阵转置的时候A和B是共享一个块的，因此这是可以优化的，但是由于不优化的情况已经达到满分条件，因此不再优化，主要代码截图如下：

2.6464
在6464的情况下我们可以再次尝试一下88的分割法，发现miss的很多。这是因为在这种情况下每4行就会填满一次cache，那就意味着隔四行的两个数据是共享一个块的，再使用88势必导致前四行与后四行共享一个块，就会导致miss的情况大大增加。那么是不是可以使用44呢？显然也是不可以的，由于cache中每一行可以填写8个int型的数据，如果44意味着矩阵中相邻的两个小矩阵可能会共享一个块，这样就导致了效果不是很好。因此我们想到了使用48的情况，由于我们选择的块需要是一个方形，因此我们采用44和8*8相结合的方法进行读取。
不妨使用如下表格来表示矩阵（不完整，只是一部分）：

假设每一个小格子都是44的小矩阵，假设我们现在需要把3号矩阵转置放到9号处，那根据上述的分析，我们一次性处理3号和4号矩阵，3号直接放到9号并转置，4号可以暂时放在10号矩阵处，并进行转置。这种方法就解决了44情况下对于cache空间使用不充分带来的miss数上升的问题。接下来由于4号最后是需要放到13号的，10号应该放的是7号矩阵的转置。那么我们接下来就处理这个，我们将10号矩阵当前的内容（也就是4号的转置结果）放置到13号矩阵中，7号矩阵的内容转置放到10号，8号矩阵的内容转置放到14号。这个过程就很好地解决了44和88各自的不足，经过测试，miss数已经小于1300。主要代码截图如下：

3.6167
因为这一情况与上述不同，不是一个规则的矩阵，也不是很容易分为方阵的组合，因此这一问的解决方法主要是使用尝试的方式，发现分为1717的方阵的时候miss的数量满足小于3000的条件，因此使用这一结果。

32×32（10分）：运行结果截图

64×64（10分）：运行结果截图

61×67（20分）：运行结果截图

第4章 总结
4.1 请总结本次实验的收获
这次实验之后对于cache的基本工作机制了解更加深入了，同时对于如何编写一个高速缓存友好的代码有了更深入的了解。

4.2 请给出对本次实验内容的建议
可以在PPT上增加一些对于常见错误的解释，比如不能在共享文件夹下操作。

注：本章为酌情加分项。

参考文献

为完成本次实验你翻阅的书籍与网站等