计算机组织与体系结构实习Lab3——高速缓存的模拟、配置和优化

博主： Rainshaw
发布时间：2020 年 05 月 10 日
840 次浏览
1 条评论
9849字数
分类： C++ 计算机组织与体系结构实习

# 高速缓存的模拟、配置和优化

## 单级Cache模拟

单层Cache模拟器，主程序在`source-code/CacheMain.cpp`中，主要负责读取`trace`文件，并执行Cache模拟。由于第二阶段需与CPU模拟器级联，故新编写`Cache.cpp`文件并修改原有文件使得可以正确运行。

### `MemoryManager`模块修改

主存在本次试验中是最底层的存储器，故对于主存必然命中。主存对于读取字节的响应延迟应为总线延迟和主存命中延迟之和。主存对于写若干字节的响应延迟应为总线延迟和主存命中延迟之和。

将原有`get`,`set`函数修改，均加入延迟时间计算。

### `Cache`模块设计

缓存在运行过程中，会不停接收到读、写请求，根据自身情况，分别响应读命中、读不命中、写命中、写不命中。

对于读命中，从存储中取出内容，经过总线延迟和命中延迟完成动作。

对于读不命中，首先找到空闲块或待替换的块，若`write_back`为真，则将被替代块写回下一层存储，再向下一层存储发出读请求替换至准备好的块中，再进行读命中操作，需经过总线延迟和命中延迟再加上下一级的延迟来完成。

对于写命中，若`write_back`为真，则设置`dirty`为真，之后进行写入操作。若`write_back`为真，需经总线延迟与命中延迟完成；否则，需向下一级存储发出写请求，等待下一级存储也写入完成，需总线延迟、命中延迟和下一级的延迟完成。

对于写不命中，若`write_alloc`为真，则需先替换块，再根据`wirte_back`决定写入时的操作。需要总线延迟、命中延迟再加上下一级的延迟完成；否则，直接向下一级传递请求，需总线延迟、命中延迟、下一级延迟完成。

### Miss Rate 随 Block Size 的变化

![](https://blog.ruixiaolu.com/usr/uploads/20200510152623.png)

如图所示为在不同Cache Size的条件下，Miss Rate 随 Block Size的变化趋势，取associativity为8。可以看出，随着Block Size的增大，Miss Rate会逐渐减小至一稳定值。

### Miss Rate 随 Associativity 的变化

![](https://blog.ruixiaolu.com/usr/uploads/20200510152634.png)

如图所示，为固定Block Size 为64Byte，Miss Rate随Associativity的变化趋势。可以看出，绝大多数情况，随着associativity的增大，Miss Rate也会逐渐减小至一稳定值。

### Write Through, Write Back, Write Allocate和 No-write Allocate访问延时差异

![](https://blog.ruixiaolu.com/usr/uploads/20200510152651.png)

如图所示，在不同的写策略时，总访问延时有一定区别。可以看到，Write Back策略访问延时明显低于Write Through；Write Allocate对延时的减小有微弱的帮助。

## 与CPU模拟器级联

修改`Simulator`模块、主程序模块，将Cache加入至流水线模拟之中。

这里采用Cache模块计算访存延迟并返回给流水线模拟器，再将该延迟加入到流水线模拟器的周期数中，以便计算CPI

| Level | Capacity | Associativity | Block Size | Write Policy | Hit Latency |
| - | - | - | - | - | - |
| L1 | 32KB | 8 ways | 64 | Write Back | 1 CPU Cycle |
| L2 | 256KB | 8 ways | 64 | Write Back | 8 CPU Cycle |
| LLC | 8MB | 8 ways | 64 | Write Back | 20 CPU Cycle |

### 程序运行结果

```bash
$ ./Sim ../$dir/others/ackermann.riscv
Ackermann(0,0) = 1
Ackermann(0,1) = 2
Ackermann(0,2) = 3
Ackermann(0,3) = 4
Ackermann(0,4) = 5
Ackermann(1,0) = 2
Ackermann(1,1) = 3
Ackermann(1,2) = 4
Ackermann(1,3) = 5
Ackermann(1,4) = 6
Ackermann(2,0) = 3
Ackermann(2,1) = 5
Ackermann(2,2) = 7
Ackermann(2,3) = 9
Ackermann(2,4) = 11
Ackermann(3,0) = 5
Ackermann(3,1) = 13
Ackermann(3,2) = 29
Ackermann(3,3) = 61
Ackermann(3,4) = 125
Program exit from exit() system call
-------STATISTICS---------
Number of Cycles: 520797
Number of Instructions: 430659
Avg Cycles per Instrcution: 1.2093
Number of JALR Instructions: 13740
Number of JAL Instructions: 20734
Number of LOAD Instructions: 95400
Number of STORE Instructions: 68308
Number of BRANCH Instructions: 27451
Number of Successful Prediction: 13847
Number of Unsuccessful Prediction: 13604
Branch Prediction Accuracy: 0.5044 (Using Strategy: Always Not Taken)
Number of Control Hazards: 61860
Number of Data Hazards: 307250
Number of Structural Hazards: 27192
-----------------------------------
```

从中可以看出，运行结果正确。

### CPI对比

下表给出带Cache和不带Cache的程序运行CPI

| 文件名 | CPI of IdealMemory | CPI with Cache | CPI withoutCache |
| - | - | - | - |
| `helloworld` | 1.2168 | 7.5524 | 27.0909 |
| `quicksort` | 1.3427 | 1.2753 | 49.2958 |
| `matrixmulti` | 1.2254 | 1.2320 | 39.0974 |
| `ackermann` | 1.2060 | 1.2295 | 39.2194 |

在没有Cache的模拟器中，所有访存周期都为1个周期，当引入Cache后，CPI均有所增加，这是因为引入Cache后，我们访存操作都需要不止一个周期。

从表中可以看出，不同程序其CPI差异很大，局部性好的程序CPI增加幅度小，如矩阵乘法，其数据大多在一个block内，引入Cache带来的性能损失非常小。

当我们去掉Cache并设置访存周期为100时，我们发现引入Cache基本上都能将CPI下降很多，这说明减小访存延迟，合理设计Cache规模对计算机性能的影响是巨大的。

## 高速缓存管理策略优化

采用两级Cache，默认配置如下

| Level | Capacity | Associativity | Line size(Bytes) | Write Policy | Bus Latency | Hit Latency |
| - | - | - | - | - | - | - |
| L1 | 32KB | 8 ways | 64 | Write Back | 0 CPU Cycle | ? |
| L2 | 256KB | 8 ways | 64 | Write Back | 6 CPU Cycle | ? |
| Mem | $\infty$ |   |   |   | 0 | 100 CPU Cycle |

其中Bus Latency为总线延迟，即本层接到上层发来请求和本层返回数据给上层时间延迟之和，Hit Latency为本层查找数据所需时间，只要没使用bypass该延时始终存在。假设CPU和主存频率为2GHz，主存无限大。

### 计算Hit Latency

安装cacti依赖库

```bash
sudo apt install gcc-multilib g++-multilib
```

修改`cacti`配置文件

```ini
-size (bytes) ???
-block size (bytes) ?
-associativity ?
-technology (u) 0.032
-cache type "cache"
```

得到运行结果

从图中可以看出，

```bash
默认配置下，32nm工艺节点下，L1 Cache的 Hit Latency 为（1.47944）ns，约等于（3）cycle
- 默认配置下，32nm工艺节点下，L2 Cache的 Hit Latency 为（1.9206）ns，约等于（4）cycle
```

故，默认配置下，Cache的全部参数如下表

| Level | Capacity | Associativity | Line size(Bytes) | Write Policy | Bus Latency | Hit Latency |
| - | - | - | - | - | - | - |
| L1 | 32KB | 8 ways | 64 | Write Back | 0 CPU Cycle | 3 CPU Cycle |
| L2 | 256KB | 8 ways | 64 | Write Back | 6 CPU Cycle | 4 CPU Cycle |
| Mem | $\infty$ |   |   |   | 0 | 100 CPU Cycle |

### 默认配置运行trace2017

使用LRU替换算法，无任何优化算法，使用命令

```bash
./CacheYouhuaSim ../cache-trace/???.trace 100
```

运行提供的两个trace文件共一百次。

| Trace | Level | Latency | Miss Rate | AMAT |
| :- | - | :- | :-: | - |
| 01-mcf-gem5-xcg.trace | L1 | 3 | 0.200455 | 11.548831 |
|   | L2 | 10 | 0.396080 |   |
|   | Mem | 100 | x |   |
| 02-stream-gem5-xaa.trace | L1 | 3 | 0.113404 | 11.501351 |
|   | L2 | 10 | 0.755171 |   |
|   | Mem | 100 | x |   |

其中AMAT计算公式为

$$
AMAT1 = (1-0.200455)*3+0.200455*[(1-0.396080)*10+0.396080*100]\\
AMAT2 = (1-0.113404)*3+0.113404*[(1-0.755171)*10+0.755171*100]
$$

### 优化策略

#### 替换策略

默认策略是LRU策略，考虑使用随机算法、PLRU算法替换，测试100轮。

| Trace | Level | Miss RateLRU | Miss RateRandom | Miss RatePLRU | AMATLRU | AMATRandom | AMATPLRU |
| :- | - | :-: | :- | - | - | - | - |
| 01-mcf-gem5-xcg.trace | L1 | 0.200455 | 0.204337 | 0.200588 | 11.548831 | 11.017709 | 11.399391 |
|   | L2 | 0.396080 | 0.358196 | 0.387487 |   |   |   |
| 02-stream-gem5-xaa.trace | L1 | 0.113404 | 0.113483 | 0.113404 | 11.501351 | 11.651742 | 11.501351 |
|   | L2 | 0.755171 | 0.769313 | 0.755171 |   |   |   |

从上表中可以看出，Random算法和PLRU算法与LRU算法的性能差不多。但由于Random算法具有随机性和不稳定性，所以Random算法不能作为好的替代算法。 虽然PLRU算法比LRU算法提高幅度较小，但由于其为稳定的算法，所以PLRU是好的替代算法。再，LRU的时间复杂度为O(associativity)，而PLRU为O(log(associativity))，可见PLRU速度也要比LRU快，虽然一般来说associativity都不大。

所以，采用PLRU算法替代LRU算法是合理的。

#### Bypass策略

我们能想象到，在程序执行过程中，可能仅一次执行某些指令，且在这些指令周围的其他指令也不被执行，那么对于这类指令，如果我们需要其的时候，将其更新至Cache，这就发生了一次很长的访问，首先从主存中加载到L2 Cache，再从L2 Cache加载到L1 Cache然后返回。这样的数据装入Cache，只使用一次，使得Cache的表现变得糟糕。因此，对于这种情况，不应该加载到Cache中，应该直接从下层存储中返回该数据，即Bypass.

使用MCT决定Bypass，MCT为一个记录历史载入Line的表格，其一行对应一个associativity，每行中可以有若干个Tag，遵循FIFO原则。对于上述提到的现象，我们只需考虑由于CacheSize引起的Capacity Miss即可，即在Cache Set和MCT均已满且在MCT中找不到相应的Tag时，进行Bypass防止Cache污染。

采用默认配置，使用PLRU算法，分别在L1和L2上开启Bypass策略且每个MCT最多8个Tag，测试100轮。

| Trace | Level | MRNo | MRL1 | MRL2 | MRL1+L2 | AMATNo | AMATL1 | AMATL2 | AMATL1+L2 |
| - | - | - | - | - | - | - | - | - | - |
| mcf.trace | L1 | 0.200588 | 0.246338 | 0.200588 | 0.246338 | 11.399391 | 12.593709 | 9.770219 | 13.380823 |
|   | L2 | 0.387487 | 0.354947 | 0.367518 | 0.390450 |   |   |   |   |
| xaa.trace | L1 | 0.113404 | 0.223658 | 0.113404 | 0.223658 | 11.501351 | 13.331245 | 12.275317 | 20.152812 |
|   | L2 | 0.755171 | 0.435468 | 0.831003 | 0.774357 |   |   |   |   |

从上表中可以看到，对于局部性好的trace，当开启L2 Bypass时AMAT有较好的优化性能，而开启L1 Bypass均会降低性能。对于流水式的trace，局部性很差，这时关闭Bypass可以降低Miss Rate。这一试验结果不难理解，当局部性好时，偶尔一个远距离的内存访问，Bypass可以防止Cache被污染以获得较好的性能。

所以，Bypass优化策略为仅对L2开启。

然后，通过实验选择不同的MCT Size，每组测试10次。

| Trace | MCT Size | MR L1 | MR L2 | AMAT |
| - | - | - | - | - |
| mcf.trace | 1 | 0.200588 | 0.331128 | 10.381955 |
|   | 2 | 0.200588 | 0.322439 | 10.225081 |
|   | 4 | 0.200588 | 0.324212 | 10.257096 |
|   | 8 | 0.200588 | 0.367518 | 11.038902 |
|   | 16 | 0.200588 | 0.386600 | 11.383383 |
|   | 32 | 0.200588 | 0.387629 | 11.383383 |
|   | 64 | 0.200588 | 0.387487 | 11.401952 |
|   | 128 | 0.200588 | 0.387487 | 11.399391 |
|   | 256 | 0.200588 | 0.387487 | 11.399391 |
| xaa.trace | 1 | 0.113404 | 0.831003 | 12.275317 |
|   | 2 | 0.113404 | 0.831003 | 12.275317 |
|   | 4 | 0.113404 | 0.831003 | 12.275317 |
|   | 8 | 0.113404 | 0.831003 | 12.275317 |
|   | 16 | 0.113404 | 0.831003 | 12.275317 |
|   | 32 | 0.113404 | 0.776347 | 11.463847 |
|   | 64 | 0.113404 | 0.755171 | 11.501351 |
|   | 128 | 0.113404 | 0.755171 | 11.501351 |
|   | 256 | 0.113404 | 0.755171 | 11.501351 |

上表中 mcf.trace代表局部性良好的trace，xaa.trace代表局部性不好的trace，权衡考虑，取Size为2。由于绝大多数程序都是局部性较好的程序，此时若MCT Size为零，则会出现Cache污染，若MCT Size较大，所有出现过的都会被记录下来不再bypass，也会造成性能的降低。

综上所述，L2缓存使用Bypass策略，且MCT Size（即历史Tag）为2.

#### Prefetch策略

由于程序的局部性，如果每次miss时不止从下一级存储中取出本次Miss的Cache Line，而是同时取出连续的若干个Line防止之后出现的Miss，则可以提高性能。

采用 MCT Next-line Prefetch 策略，即使用Bypass的MCT判断预取的Line是否有用。并设置一参数num表示预取的Line的数量，上限设置为4。

采用默认配置，使用PLRU算法，在L2上开启Bypass策略且每个MCT最多2个Tag，在L1和L2上均开启Prefetch，测试10轮。

| Trace | Prefetch Num | MR L1 | MR L2 | AMAT |
| - | - | - | - | - |
| mcf.trace | 0 | 0.200588 | 0.322439 | 10.225081 |
|   | 1 | 0.179660 | 0.323874 | 9.494491 |
|   | 2 | 0.173573 | 0.323232 | 9.264405 |
|   | 4 | 0.171114 | 0.323960 | 9.186874 |
| xaa.trace | 0 | 0.113404 | 0.831003 | 12.275317 |
|   | 1 | 0.056723 | 0.713223 | 7.038136 |
|   | 2 | 0.039000 | 0.674949 | 5.642094 |
|   | 4 | 0.023070 | 0.640304 | 4.490949 |

从上表中可以看出，使用Prefetch可以有效提高性能。

所以，启用Prefetch策略，设置预取数量为4，并通过MCT判断是否加载。

#### 优化结果

将之前所得的结论总结如下

L1 Cache：32KB，8路，Line=64B，WA+WB写策略，PLRU替换策略，预取数量为4的预取策略，无Bypass

L2 Cache：256KB，8路，Line=64B，WA+WB写策略，PLRU替换策略，预取数量为4的预取策略，MCT Size为2的Bypass策略

在上述配置条件下，运行trace 100遍。

| Trace | Level | 无优化Miss Rate | 无优化AMAT | 优化Miss Rate | 优化AMAT |
| :- | - | :-: | - | - | - |
| 01-mcf-gem5-xcg.trace | L1 | 0.200455 | 11.548831 | 0.171114 | 9.186874 |
|   | L2 | 0.396080 |   | 0.323960 |   |
|   | Mem | x |   |   |   |
| 02-stream-gem5-xaa.trace | L1 | 0.113404 | 11.501351 | 0.023070 | 4.490949 |
|   | L2 | 0.755171 |   | 0.640304 |   |
|   | Mem | x |   |   |   |

从上表中可以看出，在使用上述优化策略后，程序的性能得到了很大改善。

最后修改：2020 年 10 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

1 条评论

xiaoming Edge 97.0.1072.76 Windows 10 中国湖南张家界
August 13th, 2022 at 05:40 pm

您好，请问源代码方便分享嘛？我在跟着做实验，想看看具体结果

回复

计算机组织与体系结构实习Lab3——高速缓存的模拟、配置和优化

Rainshaw • 2020 年 05 月 10 日

# 高速缓存的模拟、配置和优化

## 单级Cache模拟

### `MemoryManager`模块修改

将原有`get`,`set`函数修改，均加入延迟时间计算。

### `Cache`模块设计

缓存在运行过程中，会不停接收到读、写请求，根据自身情况，分别响应读命中、读不命中、写命中、写不命中。

对于读命中，从存储中取出内容，经过总线延迟和命中延迟完成动作。

### Miss Rate 随 Block Size 的变化

![](https://blog.ruixiaolu.com/usr/uploads/20200510152623.png)

如图所示为在不同Cache Size的条件下，Miss Rate 随 Block Size的变化趋势，取associativity为8。可以看出，随着Block Size的增大，Miss Rate会逐渐减小至一稳定值。

### Miss Rate 随 Associativity 的变化

![](https://blog.ruixiaolu.com/usr/uploads/20200510152634.png)

### Write Through, Write Back, Write Allocate和 No-write Allocate访问延时差异

![](https://blog.ruixiaolu.com/usr/uploads/20200510152651.png)

如图所示，在不同的写策略时，总访问延时有一定区别。可以看到，Write Back策略访问延时明显低于Write Through；Write Allocate对延时的减小有微弱的帮助。

## 与CPU模拟器级联

修改`Simulator`模块、主程序模块，将Cache加入至流水线模拟之中。

这里采用Cache模块计算访存延迟并返回给流水线模拟器，再将该延迟加入到流水线模拟器的周期数中，以便计算CPI

### 程序运行结果

从中可以看出，运行结果正确。

### CPI对比

下表给出带Cache和不带Cache的程序运行CPI

在没有Cache的模拟器中，所有访存周期都为1个周期，当引入Cache后，CPI均有所增加，这是因为引入Cache后，我们访存操作都需要不止一个周期。

从表中可以看出，不同程序其CPI差异很大，局部性好的程序CPI增加幅度小，如矩阵乘法，其数据大多在一个block内，引入Cache带来的性能损失非常小。

## 高速缓存管理策略优化

采用两级Cache，默认配置如下

### 计算Hit Latency

安装cacti依赖库

```bash
sudo apt install gcc-multilib g++-multilib
```

修改`cacti`配置文件

```ini
-size (bytes) ???
-block size (bytes) ?
-associativity ?
-technology (u) 0.032
-cache type "cache"
```

得到运行结果

从图中可以看出，

故，默认配置下，Cache的全部参数如下表

### 默认配置运行trace2017

使用LRU替换算法，无任何优化算法，使用命令

```bash
./CacheYouhuaSim ../cache-trace/???.trace 100
```

运行提供的两个trace文件共一百次。

其中AMAT计算公式为

$$
AMAT1 = (1-0.200455)*3+0.200455*[(1-0.396080)*10+0.396080*100]\\
AMAT2 = (1-0.113404)*3+0.113404*[(1-0.755171)*10+0.755171*100]
$$

### 优化策略

#### 替换策略

默认策略是LRU策略，考虑使用随机算法、PLRU算法替换，测试100轮。

所以，采用PLRU算法替代LRU算法是合理的。

#### Bypass策略

采用默认配置，使用PLRU算法，分别在L1和L2上开启Bypass策略且每个MCT最多8个Tag，测试100轮。

所以，Bypass优化策略为仅对L2开启。

然后，通过实验选择不同的MCT Size，每组测试10次。

综上所述，L2缓存使用Bypass策略，且MCT Size（即历史Tag）为2.

#### Prefetch策略

由于程序的局部性，如果每次miss时不止从下一级存储中取出本次Miss的Cache Line，而是同时取出连续的若干个Line防止之后出现的Miss，则可以提高性能。

采用 MCT Next-line Prefetch 策略，即使用Bypass的MCT判断预取的Line是否有用。并设置一参数num表示预取的Line的数量，上限设置为4。

采用默认配置，使用PLRU算法，在L2上开启Bypass策略且每个MCT最多2个Tag，在L1和L2上均开启Prefetch，测试10轮。

从上表中可以看出，使用Prefetch可以有效提高性能。

所以，启用Prefetch策略，设置预取数量为4，并通过MCT判断是否加载。

#### 优化结果

将之前所得的结论总结如下

L1 Cache：32KB，8路，Line=64B，WA+WB写策略，PLRU替换策略，预取数量为4的预取策略，无Bypass

L2 Cache：256KB，8路，Line=64B，WA+WB写策略，PLRU替换策略，预取数量为4的预取策略，MCT Size为2的Bypass策略

在上述配置条件下，运行trace 100遍。

从上表中可以看出，在使用上述优化策略后，程序的性能得到了很大改善。

计算机组织与体系结构实习Lab3——高速缓存的模拟、配置和优化

发表评论取消回复

1 条评论

Typecho 评论异步通知插件——Notice

Typecho 插件——MacHighlight 代码语法高亮插件

Handsome 主题解决 CodePrettify 代码高亮插件与 Vditor 兼容问题

修复 Handsome 主题评论可见内格式错乱问题

Typecho 复制版权提醒插件

LNMP 环境一键包 Redis 的安装与配置

使用百度云加速获取真实用户 IP

pjax无刷新加载后百度统计失效解决方案

在Django3中使用 pathlib.Path 生成 BASE_DIR 时，Pycharm 无法找到静态文件

MacBook Pro 2018 进入 WTG 系统后安装驱动时卡住“Apple USB 虚拟主机控制器”

计算机组织与体系结构实习Lab3——高速缓存的模拟、配置和优化

发表评论 取消回复

1 条评论

计算机组织与体系结构实习Lab3——高速缓存的模拟、配置和优化

发表评论取消回复