目录
1 实验目的 3
2 实验设备 3
3 实验任务 3
4 前置知识 3
5 实验步骤 4
6 实验环境 5
7 示例 Cache 的实现 7
7.1 直接映射Cache结构 …………………………………. 7
7.2 写直达-写不分配策略…………………………………. 8
7.3 状态机的设计 …………………………………….. 9
7.4 如何存储Cache ……………………………………. 10
7.4.1 使用LUT(查找表)………………………………. 10
7.4.2 使用BRAM ………………………………….. 11
7.5 代码实现……………………………………….. 12 7.5.1 指令Cache…………………………………… 12 7.5.2 数据Cache…………………………………… 14
8 提升 cache 性能 18
8.1 写回………………………………………….. 18
8.2 提高相联度………………………………………. 18
8.2.1 LRU替换算法…………………………………. 19 8.2.2 伪LRU替换算法 ……………………………….. 20 8.2.3 随机替换算法 …………………………………. 21
8.3 块多字 ………………………………………… 21
8.4 其他相关cache优化性能方法 …………………………….. 21
1
9 关于调试 22 9.1 使用trace进行调试 ………………………………….. 22 9.2 测试程序汇编代码…………………………………… 22 9.3 调试方法示例 …………………………………….. 22 9.4 波形图的导入与导出、波形图的调试小技巧………………………. 24 9.5 示例波形图………………………………………. 25 9.6 调试建议……………………………………….. 28 9.7 常见错误……………………………………….. 28
2
实验二 Cache 设计与实现
Cache 是计算机体系结构中最热门的研究问题之一。通过 Cache，可以弥补 CPU 和内存间的速度鸿沟。 而 Cache 的思想也可以被广泛应用于其它领域，如磁盘访问，网络访问等等。通过计组课程的学习，我们已 经知道 Cache 有 3 种常见的结构——直接映射、组相联和全相联。
本次实验将引导同学们设计并实现一个基本的 Cache 模块，并介绍常见几种 Cache 的性能优化方法。 本实验同时提供了一个 vivado 工程，同学们完成自己的 Cache 模块后，可以将其添加到一个提供好的 SoC 环境中。然后运行仿真，该环境会运行一个矩阵分块乘法程序，并输出运行花费的时钟周期数，同学们可以 以此观察自己实现 Cache 的性能。
1 实验目的
1. 加深对 Cache 原理的理解
2. 通过使用 verilog 实现 Cache，加深对状态机的理解
2 实验设备
1. 装有 Xilinx Vivado 的计算机一台
2. [可选]Nexys4 DDR 实验开发板(用于上板观察运行时间)
3 实验任务
1. 最低要求:参考指导书中直接映射写直达 Cache 的实现，实现写回策略的 Cache
2. 替换实验环境中的 Cache 模块，并通过仿真测试
3. [选做][较高要求] 性能优化，实现 2 路组相联的 Cache
4. [选做][更高要求] 性能优化，使用伪 LRU 等替换策略实现 4 路以上组相联的 Cache 5. [选做][最高要求] 实现其它 Cache 性能优化方法，如 axi burst 传输
4 前置知识
1. Cache 理论知识 2. 类 sram 接口协议
3
5 实验步骤 此次实验大概分为以下几个步骤
首先，阅读实验环境介绍，明白 Cache 模块所处的位置与作用。
然后，阅读示例 Cache 实现过程，了解设计并实现 Cache 的主要步骤。其中类 sram 接口部分可以参 考文档《A12_ 类 SRAM 接口说明》
接着，阅读 Cache 性能提升章节写回 Cache 内容，并参照示例代码，实现写回 Cache。其中以下过程 比较重要
分析写回 Cache 的流程图 分析写回 Cache 的状态机 分析写回 Cache 输入输出波形图
接着，阅读调试章节的内容，用自己实现的 Cache 模块，替换掉示例 Cache 模块，然后运行仿真程序， 进行调试。
(选做) 可以阅读 Cache 性能提升章节其余内容，来提升 Cache 性能。
4
6 实验环境
本次实验需要实现一个 Cache 模块，该模块接口已经定义。如图1，黄色部分即为需要实现的 Cache 模
块，其它部分已给出。
图1显示了 CPU 顶层模块结构图。MIPS core 模块内部包含一个 5 级流水的 CPU 核，实现了 MIPS I 的
57 条基本指令。MIPS core 通过两个类 sram 接口对外进行指令访问和数据访问。
当 MIPS core 向 Cache 模块请求指令和数据时，Cache 模块如果命中，则可以马上返回数据，不用再 访问内存，否则需要访问内。而访问内存时，Cache 模块只需产生类 sram 信号，该类 sram 信号经过一个类 sram-axi 转换桥后，会被转换成 axi 信号，因此 CPU 顶层对外接口为 axi 接口。
mycpu_top
指令访问 数据访问
指令访问 数据访问
类sram Master端
类sram Master端
类sram Slave端
类sram Master端
Cache
类sram Slave端
类sram Master端
MIPS core
类sram Slave端
类sram Slave端
类sram-AXI转换桥
AXI Master端
图 1: cpu 顶层结构图
如图2所示，在添加内存模块，和外设模块后，便可以构成一个完整的片上系统 (Soc)。CPU 运行的程序 通过 coe 文件可以直接加载进内存模块。而外设模块主要用于控制板子上的 GPIO(如拨码开关，七段数码 管，双色灯等)。AXI 1×2 bridge 为 ip 核，已经配置好了内存和外设的地址空间。从而可以根据访问的地址， 决定是访问内存模块还是外设模块。注:此 Soc 为龙芯杯比赛提供，图中省略了部分细节。
总结，此次实验已经将 Cache 模块与其它模块交互部分统一封装为了类 sram 接口。同学们在对 Soc 整体结构有了一个认识后，便可以聚焦于 Cache 内部的设计，主要考虑 Cache 的结构，状态机，替换策略等 内容。
5
soc_axi _lite_top
mycpu_top
MIPS core
指令访问 数据访问
指令访问 数据访问
Cache
类sram-AXI转换桥 AXI Master端
AXI Master端
AXI Master端
AXI slave端
AXI 1 x 2 bridge
AXI slave端 Confreg(外设)
AXI slave端 Ram(内存)
图 2: soc 顶层结构图
6
7 示例 Cache 的实现
上面介绍了 Cache 模块所处的位置与作用，接下来我们将介绍如何实现一个简单的直接映射写直达
的 Cache，并给出示例代码。 7.1 直接映射 Cache 结构
原始的内存数据可以看成一个一维的字节数组，内存地址作为一个索引，可以通过索引访问到对应的 内存字节。地址和数据是一一对应的。而直接映射的 Cache 可以看成一个二维数组，内存地址被拆成 Tag, index 和 offset 三部分。其中 index 和 offset 构成这个二维数组的索引，通过 index 访问一个 cache line，通过 offset 确定 cache line 中数据块中对应的字。而由于 Cache 的容量远小于内存的容量，因此无法做到一一对 应。当地址的 index 和 offset 都相同时，就会将两个地址映射到 cache 中的同一个位置造成冲突。因此此时 就需要 tag 来表示两个不同的地址。
直接映射 Cache 结构如图3所示。
Tag
Index
offset
/t /k
/b-2
valid tag data block
2 lines
hit data word
图 3: 直接映射 Cache 结构图
设计 Cache 时，我们首先确定 cache 块的大小和行数，也就是 index 和 offset 的位宽。这也同时确定 了 Cache 的容量。本次示例程序将实现 4KB 的 Cache，且块大小为 1 个字。从而我们可以计算出行数为
4𝐾𝐵 = 210。因此 index 为 10 位，offset 为 2 位。tag 为 32 中剩下的 20 位。 1𝑊
说明:块大小为 1 字的缺点是不能利用访存的空间局部性，即访问一个地址，也会很有可能访问其周 围的地址。对于指令 Cache 则更是如此。如果块大小为多个字，则每次 Cache 缺失，可以一次性读取多条 相邻指令到 Cache 中，从而大大提高 Cache 的命中率。但块大小为多字需要能够一次访存，取得多个字的 数据，而这涉及到 AXI 的 burst 传输。并且块多字也会增加 Cache 读，写缺失时的逻辑。因此为了简化，采 用块大小 1 个字进行说明。
7
示例代码最终实现的 Cache 配置如表1所示。
表 1: 示例 Cache 配置
指令 Cache
数据 Cache
结构
直接映射
直接映射
写策略
无
写直达
容量
4KB
4KB
块大小
1 word
1 word
行数
1024
1024
tag
20 bit
20 bit
index
10 bit
10 bit
offset
2 bit
2 bit
7.2 写直达-写不分配策略
当 CPU 执行 store 类指令时，对 Cache 应该如何操作呢?当 Cache 命中时，最简单的想法是将数据同 时写入到 Cache 和内存。这样保证了 Cache 和内存中的数据都是修改后最新的数据，保持了一致性。但也 导致了大量的写内存操作，因此效率非常低。而另一种想法是只写入 Cache，同时标记该 Cache line 为已修 改，等到万不得已的时候(该 cache line 被替换时)再写入内存。这可以大大减少写内存的次数。这两种策 略分别为写直达 (Write Through) 和写回 (Write Back)。本示例出于简单考虑，使用写直达策略。
上面讨论的是写命中的情况，当写缺失时。针对是否需要将数据写入 Cache，可以分为写分配 (Write Allocate) 和写不分配 (Non-Write Allocate)。写直达通常结合写不分配策略一起使用，即写缺失时，直接写 入内存，而不写入 Cache。而写回通常结合写分配策略一起使用，即写缺失时，只写入 Cache，而不写入内 存。
8
7.3 状态机的设计
Load
开始
Load/Store
Yes
Store
No Hit?
Yes
Hit? No
从内存读取1个字
将数据写入Cache
将数据写入内存
将数据写入对 应的Cache line
将数据返还给 CPU
结束
图 4: 示例数据 Cache 处理流程
由于指令 Cache 不包含写的情况，我们以数据 Cache 为例进行分析。经过上面的分析，我们可以画出
Cache 读写处理的流程图，如图4所示。
CPU 发来的访存请求可能是读 (load 类指令)，也可能是写 (store 类指令)。如果是读请求的话，判断是 否命中。如果命中了的话，便立刻返回数据。而如果缺失了，则需要从内存读取数据。再将数据写入 Cache， 并返回数据给 CPU，这两个操作可以同时进行。如果是写请求的话，判断是否命中。如果缺失的话，将数据 写入内存。如果命中了的话，则既需要将数据写入内存，也需要写入 Cache。
因此，我们可以设计一个简单的状态机如图5。图中定义了三种状态，IDLE 表示空闲状态也就是初始 状态，RM 表示读取内存的状态，WM 代表写内存的状态。以读为例，当读命中时，因为可以马上返回数据， 因此仍然保持 IDLE 状态。当读缺失时，则进入 RM 状态，直到读取内存数据完成时(data_ok)，Cache 返回 数据给 CPU，写入 Cache，然后返回到 IDLE 状态。
9
~data_ok
RM
read & miss
data_ok
(write finish)
IDLE
read & hit
~data_ok
WM
write (hit or miss)
data_ok
7.4 如何存储 Cache
图 5: 示例数据 Cache 状态机
在本次实验中，我们需要一些存储单元来存储 Cache。我们知道，一般使用 SRAM(静态随机存储器) 来实现 Cache，因为 SRAM 是一种非常快的存储器，和 CPU 的速度接近。在 FPGA 上，可以使用两种方式 组织存储器。
7.4.1 使用 LUT(查找表)
LUT 是 FPGA 中最重要的资源之一，因为 FPGA 通常使用 LUT 来实现任意的组合逻辑。简单来说，
LUT 由一些 SRAM 比特和多选器组成，感兴趣的同学可以搜索具体原理。 我们可以采用 reg 定义二维数组的方式实现存储，如:
// Cache 配 置
parameter INDEX_WIDTH = 10, OFFSET_WIDTH = 2;
localparam TAG_WIDTH = 32 – INDEX_WIDTH – OFFSET_WIDTH; localparam CACHE_DEEPTH = 1 << INDEX_WIDTH;
// Cache 存 储 单 元
reg cache_valid [CACHE_DEEPTH - 1 : 0]; reg [TAG_WIDTH-1:0] cache_tag [CACHE_DEEPTH - 1 : 0]; reg [31:0] cache_block [CACHE_DEEPTH - 1 : 0];
上面的代码根据 Cache 的配置，定义了 Cache 所需要的存储单元。再通过以下代码便可以实现对 Cache line 的访问。
// 访 问 地 址 分 解
10
wire [OFFSET_WIDTH -1:0] offset; wire [INDEX_WIDTH -1:0] index; wire [TAG_WIDTH -1:0] tag;
assign offset = addr[OFFSET_WIDTH - 1 : 0];
assign index = addr[INDEX_WIDTH + OFFSET_WIDTH - 1 : OFFSET_WIDTH]; assign tag = addr[31 : INDEX_WIDTH + OFFSET_WIDTH];
// 访 问 Cache line
wire c_valid;
wire [TAG_WIDTH -1:0] c_tag; wire [31:0] c_block;
assign c_valid = cache_valid[index]; assign c_tag = cache_tag [index]; assign c_block = cache_block[index];
上面的方式可以看作是“纯手工”打造了一个 ram。事实上，还可以使用 dram ip 核 (Distributed Memory Generator) 生成 ram。使用 ip 核的好处是接口比较统一，不必关心 ram 内部的组织细节。比可以很容易配 置成有着读写双端口的 ram，而不必关心其内部是如何解决同时读写的冲突的。
7.4.2 使用 BRAM
上面实现 ram 的方式都使用的是 LUT 资源，其实 FPGA 中提供了专门用于实现 ram 的 bram 资源
(Block RAM)，有更高的速度。可以使用 Block Memory Generator ip 核生成各种类型的 ram。
一般来说，在容量较小，性能要求低的情况下使用 dram，在容量较大，性能要求高的情况使用 bram。对 于我们的 Cache 来说，数据部分要求的容量还是比较大的，且对性能要求较高，因此采用 bram 比较合适。 但使用 bram 的缺点是读数据时，无法像 dram 那样是组合逻辑，需要一个时钟的延迟。因此出于简化实验 的目的，示例使用 reg 实现。但也鼓励同学们使用各种方式实现 Cache。
11
7.5 代码实现 7.5.1 指令 Cache
第一步，判断 Cache 命中 逻辑如下:
我们需要知道如何判断 cache 命中，参考图3直接映射 cache 的结构图，hit 判断
// 判 断 是 否 命 中
wire hit, miss;
assign hit = c_valid & (c_tag == tag); //cache line的valid位为1，且tag与地址中tag相
等
assign miss = ~hit;
第二步，Cache 的状态机 分析状态机，能让我们对 Cache 的整体逻辑更加明确。同时状态机的状态变量 也可以用于之后控制一些信号。
// FSM
parameter IDLE = 2’b00, RM = 2’b01; // i cache只有read reg [1:0] state;
always @(posedge clk) begin
if(rst) begin state <= IDLE;
end
else begin
case(state)
IDLE: state <= cpu_inst_req & miss ? RM : IDLE; RM: state <= cache_inst_data_ok ? IDLE : RM;
endcase end
end
第三步，画出命中和缺失时的输入输出波形图 我们的 Cache 主要在和 CPU 和外界这两方打交道。这里 对应两组类 sram 信号。分析状态机让我们从整体上了解 Cache 的内部逻辑，而分析输入输出信号的波形 图则是具体到实现。
图 6: 指令 cache 命中时
12
如图6是指令 Cache 命中的情况，整个过程如下:刚开始 cpu_req 为 1，cpu_addr 为读指令地址。由于 hit 是组合逻辑，因此在这个周期产生 hit 信号。图中对应为 1，表示命中。由于 Cache 命中，因此我们不必 发出 cache_req 请求，而可以直接给 cpu 返回数据。因此我们将 cpu_addr_ok 和 cpu_data_ok 都设置为 1，将 cpu_rdata 设置为从 cache 读取到的数据，表示 cpu 可以来取数据。
图 7: 指令 cache 缺失时
如图7是指令 Cache 缺失的情况，整个过程如下:同样刚开始 cpu_req 为 1，cpu_addr 为读指令地址。由 于 Cache 缺失，对应图中 hit 信号为 0，因此我们下周期发出 cache_req 请求。之后的过程便是一次标准的类 sram 读事务。我们只需要在收到 cache_addr_ok 后，将 cpu_addr_ok 也设置为 1。并且在收到 cache_data_ok 后，向 cpu 返回数据。
第四步，根据波形图实现输入输出信号 代码中，使用了 read_req, addr_rcv, read_finish 变量来辅助生成类 sram 信号。read_req 代表读请求整个过程，addr_rcv 代表地址已经收到了，而 read_finish 代表读请求结束。 根据类 sram 接口协议，req 信号在 addr_ok 后需要拉低，便可以通过以下代码来实现
cache_inst_req = read_req & ~addr_rcv;
完整代码如下
// 读 内 存
//变量read_req, addr_rcv, read_finish用于构造类sram信号。
wire read_req;
reg addr_rcv;
wire read_finish;
always @(posedge clk) begin
//一次完整的读事务，从发出读请求到结束 //地 址 接 收 成 功(addr_ok)后 到 结 束
//数 据 接 收 成 功(data_ok)， 即 读 请 求 结 束
addr_rcv <= rst ? 1’b0 :
cache_inst_req & cache_inst_addr_ok ? 1’b1 :
read_finish ? 1’b0 : addr_rcv; assign read_req = state==RM;
end
13
7.5.2
数据 Cache
assign read_finish = cache_inst_data_ok;
// output to mips core
assign cpu_inst_rdata assign cpu_inst_addr_ok assign cpu_inst_data_ok
= hit ? c_block : cache_inst_rdata;
= cpu_inst_req & hit | cache_inst_req & cache_inst_addr_ok;
= cpu_inst_req & hit | cache_inst_data_ok;
// output to axi interface
assign cache_inst_req assign cache_inst_wr assign cache_inst_size assign cache_inst_addr assign cache_inst_wdata
第五步，实现写入Cache等工作
只有在 cpu_inst_req 为 1 期间才能保证 cpu_inst_addr 的值是有效的，因此我们需要将地址存下来，防止之 后发生变化(事实上提供的 CPU 在整个期间 addr 都会保持不变，这里是为了更加严谨)
// 写 入 Cache
//保存地址中的tag, index，防止addr发生改变 reg [TAG_WIDTH -1:0] tag_save;
reg [INDEX_WIDTH -1:0] always @(posedge clk) tag_save <= rst
index_save;
begin
= read_req & ~addr_rcv;
= cpu_inst_wr;
= cpu_inst_size;
= cpu_inst_addr;
= cpu_inst_wdata;
end
integer t;
always @(posedge clk) begin
if(rst) begin
for(t=0; t
//new_data = old_data & ~mask | write_data & mask
assign write_cache_data = cache_block[index] & ~{{8{write_mask[3]}}, {8{write_mask
[2]}}, {8{write_mask[1]}}, {8{write_mask[0]}}} |
cpu_data_wdata & {{8{write_mask[3]}}, {8{write_mask[2]}},
integer t;
always @(posedge clk) begin
if(rst) begin
for(t=0; t
(b). cpu_inst_addr。Mipscore–>Cache 接口。MipsCore 读写地址。
(c). cpu_inst_rdata。Cache–>Mipscore 接口。Cache 返回给 MipsCore 的数据。
(d). cpu_inst_addr_ok。Cache–>Mipscore 接口。Cache 返回给 Mipscore 的地址握手成功。
(e). cpu_inst_data_ok。Cache–>Mipscore 接口。Cache 返回给 Mipscore 的数据成功。
(f). cache_inst_req。Cache–>axi_interface接口。Cache发送的读写请求，可因为cache缺失或者脏的
cacheline 被替换产生的写请求。
26
图 19: 指令 cache 信号量
(g). cache_inst_rdata。从内存返回给指令 cache 的数据。
(h). cache_inst_addr_ok。从内存中返回，如果是读请求，表示成功收到地址，地址握手成功;如果是
写请求，则表示成功收到地址数据。
(i). cache_inst_data_ok。从内存中返回，如果是读请求，表示从返回cache的数据。如果是写请求，代
表写入数据成功。
(j). hit。hit 为 1，表示 cache 命中。为 0，表示缺失。
(k). state。cache 状态机所处状态。
5 D_Cache。主要是跟数据 cache 有关，跟指令 cache 几乎一样，不再赘述。对上面未涉及的四个信号量
进行解释。
图 20: 数据 cache 信号量
(a). cpu_data_wr。MipsCore–>Cache。代表当前请求是否是写请求。
(b). cpu_data_size。Mipscore–>Cache。结合地址最低两位，确定数据的有效字节，详情请参考类sram
接口相关文档。
(c). cache_data_wr。Cache 输出接口。代表当前请求是否是写请求。
27
(d). cpu_data_size。Cache 输出接口。结合地址最低两位，确定数据的有效字节。详情请参考类 sram 接口相关文档。
9.6 调试建议
1. 本次实验提供通过测试的Soc环境。实验内容是要求同学们自实现cache。因此，如果测试出现问题， 极大概率是 cache 实现错误。
2. verilog 是并行编程，要求较复杂的时序分析能力。调试时请关注类 sram 接口的时序逻辑，以及 cache 在读命中、读缺失、写命中、写缺失等情况下的时序逻辑。
3. 在调试中，如果出现写数据错误，在这种情况下，可以默认 debug_wb_rf_wdata == cpu_data_rdata。因 为 Mipscore 这部分是没有错的，如果是写数据错误，那么意味着从 cache 返回来的数据有误，即同学 们自己的实现有误。
9.7 常见错误
在使用 trace 比对机制调试的情况下，由于 mipscore 是正确的，所以写寄存器地址不会错误。即有可能 是 PC 值和写寄存器数据不一样的错误。如果是 PC 值错误，那么应该是指令 cache 实现错误。如果是写寄 存器数据错误，那么应该是数据 cache 实现错误。
欢迎同学们补充!
28