性能优化和简易缓存

更新ysyxSoC

SoC团队已经提供了32位的流片SoC, 我们也在2024/07/26 13:00:00把ysyxSoC修改成32位, 以帮助大家在接入流片SoC之前在本地环境中进行测试. 如果你在上述时间之前获取ysyxSoC的代码, 请进行以下步骤:

执行以下命令获取新的32位ysyxSoC:

cd ysyxSoC
git pull origin master # 你可能需要解决一些代码冲突

将NPC顶层的AXI数据位宽修改为32位, 并去除相关的数据位宽转换代码
重新使用32位的ysyxSoC环境进行仿真

接入ysyxSoC后, 你设计的NPC已经可以正确与各种设备交互, 从功能上来说已经可以参与流片了. 根据"先完成, 后完美"的系统设计法则, 我们现在可以来讨论如何开展性能优化了.

说是要开展性能优化, 但这只是最终目的. 在一个复杂系统中, 我们将面临很多选择, 例如: 哪些地方是值得优化的? 应该采用什么方案进行优化? 预期收益是多少? 这些方案的开销是什么? 如果我们花费了很大的力气, 发现性能只提升了万分之一, 这肯定不是我们所期望的. 因此, 相比于盲目地编写代码, 我们更需要一套可以指导我们可以回答上述问题的科学方法:

评估当前的性能
寻找性能瓶颈
采用合适的优化方法
评估优化后的性能, 对比获得的性能提升是否符合预期

性能评估

要谈优化, 首先要知道当前的系统运行得如何. 因此我们需要对性能有一个量化的衡量指标, 而不是凭我们的感觉来判断“运行得好不好”. 用这个指标来对当前的系统进行评估, 就是性能优化的第一步.

在我们的理解中, "性能高"基本上等同于"跑得快". 因此, 一个直接衡量性能的指标就是程序的执行时间. 所以, 评估一个系统的性能, 就是评估程序在这个系统上的执行时间.

基准程序选择

那应该评估哪些程序呢? 程序五花八门, 要对所有程序进行评估是不现实的, 因此我们需要选择一些具有代表性的程序. 所谓的具有代表性, 就是指优化技术在这些程序上带来的性能收益, 与真实应用场景中的性能收益趋势基本一致.

这里提到了“应用场景”, 说明对于不同的应用场景, 上述趋势很可能不尽相同. 这意味着不同的应用场景需要不同的代表性程序, 这就产生了不同的benchmark. 例如, Linpack用于代表超级计算场景, MLPerf用于代表机器学习训练场景, CloudSuite用于代表云计算场景, Embench用于代表嵌入式场景. 对于通用计算场景, 最著名的benchmark就是SPEC CPU, 用于评估CPU通用计算能力. SPEC(Standard Performance Evaluation Corporation)是一个组织机构, 目标是建立维护用于评估计算机系统的各种标准, 它定义并发布了多种场景下的benchmark在新窗口中打开. 除SPEC CPU外, 还有面向图形, 工作站, 高性能计算, 存储, 功耗, 虚拟化等各种场景的benchmark.

一个benchmark通常还由若干子项构成, 例如, SPEC CPU 2006的整数测试包括如下子项:

子项	简介
400.perlbench	Perl语言检测垃圾邮件
401.bzip2	bzip压缩算法
403.gcc	gcc编译器
429.mcf	大型公共交通中单站车辆调度的组合优化问题
445.gobmk	围棋, 人工智能搜索问题
456.hmmer	使用隐马尔可夫模型的基因识别方法进行基因序列搜索
458.sjeng	国际象棋, 人工智能搜索问题
462.libquantum	量子计算模拟素数分解
464.h264ref	对YUV格式源文件进行H.264视频编码
471.omnetpp	大型CSMA/CD协议以太网模拟
473.astar	A*算法寻路
483.xalancbmk	XML到HTML的格式转换

除了整数测试, SPEC CPU 2006还包含浮点测试, 测试程序覆盖流体力学, 量子化学, 生物分子, 有限元分析, 线性规划, 影像光线追踪, 计算电磁学, 天气预报, 语音识别等不同领域.

当然, benchmark也需要与时俱进, 从而代表新时代的程序. 截至2024年, SPEC CPU已经演进了6版, 从一开始的1989年, 1992年, 1995年, 到2000年, 2006年, 最后是最新版本2017年. SPEC CPU 2017加入了一些新程序来代表新的应用场景, 例如生物医学成像, 3D渲染和动画, 采用蒙特卡罗树搜索的人工智能围棋程序(很大概率受2016年AlphaGo的影响)等.

CoreMark和Dhrystone不是好的benchmark

CoreMark和Dhrystone属于合成程序(synthetic program), 意思是用若干个代码片段拼接起来的程序. 例如, CoreMark由链表操作, 矩阵乘法和状态机转移操作这三个代码片段组成; Dhrystone则由一些字符串操作的代码片段组成.

合成程序作为benchmark, 最大的问题是其代表性较弱: CoreMark和Dhrystone能代表什么应用场景呢? 相比于SPEC CPU 2006中的各种真实应用, CoreMark中的代码片段顶多只能算C语言的课后作业; Dhrystone就离应用场景更远了, 其代码非常简单(使用短字符串常量), 甚至在现代编译器的作用下, 循环体中的代码片段很可能被深度优化(是否还记得NEMU中的pattern_decode()), 使得评估结果虚高, 无法客观反映系统的性能. 这篇文章在新窗口中打开详细分析了Dhrystone作为benchmark的缺陷.

讽刺的是, 今天不少CPU厂商发布产品时, 仍然采用CoreMark或Dhrystone的评测结果来标识产品的性能, 甚至其中还不乏宣称是面向高性能场景的产品. 体系结构一代宗师, 图灵奖得主David Patterson在介绍Embench时在新窗口中打开, 评价Dhrystone已经过时很久, 应该停止使用. 事实上, Dhrystone的第一版是1984年发布的, 从1988年之后Dhrystone就再也没有得到维护和升级. 和上世纪80年代相比, 今天的计算机领域已经发生了翻天覆地的变化, 应用程序早已更新换代, 编译技术日趋成熟, 硬件算力也大幅提升, 使用40年前的benchmark来评测今天的计算机, 其合理性确实有所欠缺.

不过对于面向教学的"一生一芯"来说, SPEC CPU的程序有点过于真实了: 一方面它们的规模很大, 即使在x86真机中也需要花费小时量级的时间来运行; 另一方面它们需要运行在Linux环境中, 这意味着我们首先需要设计一个能正确启动Linux的CPU, 然后才能运行SPEC CPU这个benchmark.

相反, 我们希望有一套适合教学场景的benchmark, 满足以下条件:

规模不算太大, 在模拟器甚至在RTL仿真环境中的执行时间不到2小时
可在裸机环境中运行, 无需启动Linux
程序具有一定代表性, 不像CoreMark和Dhrystone那样采用合成程序

事实上, am-kernels中集成的microbench就是一个不错的选择. 一方面, microbench提供了多种规模的测试集, 模拟器可以采用ref规模, RTL仿真环境可以采用train规模; 另一方面, microbench作为一个AM程序, 无需启动Linux即可运行; 此外, microbench包含10个子项, 覆盖排序, 位操作, 语言解释器, 矩阵计算, 素数生成, A*算法, 最大网络流, 数据压缩, MD5校验和等场景. 因此, 当后续讲义提到性能评估但未明确说明相应的benchmark时, 将默认指代microbench的train规模.

如果处理器的应用场景比较明确, 例如运行超级玛丽, 那么还可以直接把超级玛丽作为benchmark, 相当于把“超级玛丽的游戏体验”作为“运行得好”的标准. 和microbench不同, 超级玛丽是一个不会运行结束的程序, 因此可以采用FPS作为量化指标来评估, 而不是采用运行时间.

寻找性能瓶颈

性能公式和优化方向

我们可以测量benchmark的运行时间, 来得到系统的性能表现. 但运行时间是一个单一的数据, 我们很难从中找到系统的性能瓶颈来优化运行时间, 因此, 我们需要一些更细致的数据.

事实上, 我们可以把程序的运行时间分解成以下3个因子:

        time      inst     cycle     time
perf = ------- = ------ * ------- * -------
        prog      prog      inst     cycle

性能优化的目标是减少程序的运行时间, 也即减小其中的每个因子, 这也揭示了性能优化的三个方向.

第一个优化方向是减少程序执行的指令数量(即动态指令数), 可能的措施包括:

修改程序, 采用更优的算法.
采用更优的编译优化策略. 以gcc为例, 除了使用-O3, -Ofast等通用的优化等级参数外, 还可以对目标程序进行针对性的调参. gcc中与生成代码质量相关的编译选项有大约600多个, 选择合适的编译选项, 能大幅优化程序的动态指令数. 例如, yzh在开展某课题项目时, 仅使用-O3编译CoreMark, 运行10轮的动态指令数约312万条; 若额外打开一些针对性的编译选项, 则上述动态指令数可下降到约225万条, 程序运行的性能显著提升.
设计并使用行为更复杂的指令集. 我们知道, CISC指令集包含行为较复杂的指令, 若编译器使用这些复杂指令, 则可以降低动态指令数. 另外, 也可以在处理器中添加自定义的专用指令, 并让程序使用这些专用指令.

第二个优化方向是降低平均每条指令执行所需的周期数, 也即CPI(Cycles Per Instruction). 一般也称提升CPI的倒数, 即IPC(Instructions Per Cycle), 即提升平均每周期所执行的指令数. 这个指标反映了处理器的微结构设计效果, 强大的处理器通过每周期能执行更多的指令. 因此, 通常通过优化处理器的微结构设计来提升IPC, 从而使处理器更快地完成程序的执行. 微结构设计的优化又有不同的方向, 我们将在下文简单讨论.

第三个优化方向是减少每个周期的时间, 也即提升单位时间内的周期数, 后者就是电路的频率. 可能的优化措施包括:

优化数字电路的前端设计, 减小关键路径的逻辑延迟.
优化数字电路的后端设计, 减小关键路径的走线延迟.

如果可以量化地评估上述3个因子, 我们就能更好地评估上述三个优化方向的潜力, 从而指导我们找到性能瓶颈. 幸运的是, 这些指标其实不难获取:

动态指令数可在仿真环境中直接统计
有了动态指令数, 再统计周期数, 即可计算出IPC
电路的频率可查看综合器的报告获取

统计IPC

尝试在仿真环境中统计IPC.

实际上, 我们在实现总线的时候要求你评估程序的运行时间, 用的就是上述性能公式. 不过当时我们是通过程序执行所需的周期数 / 频率来计算, 上述性能公式只是把程序执行所需的周期数进一步拆成两个因子而已. 但这样拆分还是能给我们提供更进一步的信息, 毕竟程序执行所需的周期数与程序和处理器都相关, 而平均每条指令执行所需的周期数就只和处理器的处理能力相关了.

简单处理器的性能模型

即使IPC不难统计, 但就如统计得到的运行时间无法指导我们如何优化运行时间, 统计得到的IPC也并不能指导我们如何优化IPC. 为了找到性能瓶颈, 我们需要分析IPC受哪些因素的影响, 正如上文分析运行时间的因子一样. 为此, 我们需要重新审视处理器是如何执行指令的.

       /--- frontend ---\    /-------- backend --------\
                                  +-----+ <--- 2. computation efficiency
                             +--> | FU  | --+
       +-----+     +-----+   |    +-----+   |    +-----+
       | IFU | --> | IDU | --+              +--> | WBU |
       +-----+     +-----+   |    +-----+   |    +-----+
          ^                  +--> | LSU | --+
          |                       +-----+
1. instruction supply                ^
                    3. data supply --+

上图是一个简单的处理器结构图, 我们之前都是从功能的角度来理解这个图, 现在我们需要从性能的角度来理解它. 我们可以将处理器划分成前端和后端, 其中, 前端包括取指和译码, 剩余的模块属于后端, 负责真正执行指令并改变处理器状态. 注意, 处理器的前后端划分和上文提到的数字电路的前后端设计并不相同. 事实上, 处理器的前后端设计都属于数字电路的前端设计环节.

要提升处理器的执行效率, 就需要做到:

处理器前端需要保证指令供给. 如果前端取不到足够的指令, 就无法完全发挥处理器的计算能力. 因为每一条指令的执行都需要先取指, 因此前端的指令供给能力将影响所有指令的执行效率.
处理器后端需要保证计算效率和数据供给
- 对于大部分计算类指令, 其执行效率取决于相应功能单元的计算效率. 例如, 乘除法指令的执行效率还受乘除法器的计算效率的影响. 类似的还有浮点执行和浮点处理器单元FPU等.
- 对于访存类指令, 其执行效率取决于LSU的访存效率. 特别地, 对于load指令, 处理器需要等待存储器返回数据, 然后才能将数据写回寄存器堆. 这意味着, load指令的执行效率取决于LSU和存储器的数据供给能力. store指令则比较特殊, 因为store指令不需要写入寄存器堆, 原则上处理器不必等待数据完全写入存储器. 在高性能处理器中, 通常会设计一个store buffer部件, 处理器将store指令的信息写入store buffer后, 即认为store执行结束, 后续由store buffer部件控制将数据真正写入存储器中. 当然, 这增加了处理器设计的复杂度, 例如load指令还需要检查最新的数据是否在store buffer中.

那么, 我们应该如何量化地评估处理器的指令供给, 计算效率和数据供给呢? 换句话说, 我们真正想了解的是, 处理器在运行指定的benchmark时, IFU和LSU等模块有没有全速工作. 为此, 我们又需要收集更多的信息.

性能事件和性能计数器

为了量化地评估处理器的指令供给, 计算效率和数据供给, 我们需要进一步理解影响它们的细致因素. 以指令供给为例, 指令供给能力怎么算强呢? 能直接反映指令供给能力的, 就是IFU是否取到了指令. 为此, 我们可以把"IFU取到指令"看作一个事件, 来统计这个事件发生的频次, 如果这个事件经常发生, 指令供给能力就强; 否则, 指令供给能力就弱.

这些事件称为性能事件(performance event), 通过它们, 我们可以将性能模型中一些较为抽象的性能指标转化为电路上的具体事件. 类似地, 我们还可以统计"LSU取到数据"这个事件发生的频次, 来衡量数据供给能力的强弱; 统计"EXU完成计算"这个事件发生的频次, 来衡量计算效率的高低.

要统计性能事件发生的频次, 我们只需要在硬件中添加一些计数器, 在检测到性能事件发生时, 计数器的值就加1. 这些计数器称为性能计数器(performance counter). 有了性能计数器, 我们就可以观察"程序在处理器上运行的时间都花在哪里"了, 相当于对处理器内部做profiling.

要在电路上检测性能事件的发生并不难, 我们可以利用总线机制的握手信号进行检测. 例如, IFU取指的R通道握手时, 表示IFU接收到AXI总线返回的数据, 从而完成一次取指操作, 因此当R通道握手时, 我们就可以让相应的性能计数器加1.

添加性能计数器

尝试在NPC中添加一些性能计数器, 至少包含如下性能事件的性能计数器:

IFU取到指令
LSU取到数据
EXU完成计算
译码出各种类别的指令, 如计算类指令, 访存指令, CSR指令等

性能计数器本质上也是由电路实现的. 随着性能计数器的数量增加, 它们占用的电路面积将越来越大, 甚至有可能影响电路中的关键路径. 因此我们不要求性能计数器参与流片, 你只需要在仿真环境中使用它们即可: 你可以用RTL实现性能计数器, 在仿真结束时通过$display()等方式输出它们的值, 然后在综合时通过配置的方式选择不实例化它们; 或者将性能事件的检测信号通过DPI-C接入到仿真环境, 在仿真环境中实现性能计数器. 这样, 你就可以随心所欲地添加性能计数器, 不必担心影响电路的面积和频率.

实现后, 尝试运行microbench的test规模, 收集性能计数器的结果. 如果你的实现正确, 语义相近的不同性能计数器的统计结果应存在一致性. 例如, 译码得到的不同类别的指令的总数, 应与IFU取到指令的数量一致, 也与动态指令数一致. 尝试挖掘更多的一致性关系并检查这些关系是否成立.

相比于事件发生, 有时候我们更关心事件什么时候不发生, 以及为什么不发生. 例如, 其实我们更关心IFU什么时候取不到指令, 以及IFU为什么取不到指令, 梳理其中的缘由有助于我们理解指令供给的瓶颈在哪里, 从而为提升处理器的指令供给提供指导. 我们可以把"事件不发生"定义成一个新的事件, 并为新事件添加性能计数器.

添加性能计数器(2)

在NPC中添加更多性能计数器, 并尝试分析以下问题:

每种类别的指令占多少比例? 它们各自平均需要执行多少个周期?
IFU取不到指令的原因有哪些? 这些原因导致IFU取不到指令的几率分别是多少?
LSU的平均访存延迟是多少?

性能计数器的trace

前文介绍的性能计数器的使用方式都是在仿真结束后输出并分析. 如果我们每周期都输出性能计数器的值, 我们就能得到性能计数器的trace! 根据这种trace, 借助一些绘图工具(如python的matplotlib绘图库), 我们可以绘制出性能计数器的值随时间变化的曲线, 将仿真过程中性能计数器的变化过程可视化, 从而帮助我们更好地判断性能计数器的变化过程是否符合预期.

阿姆达尔定律(Amdahl's law)

性能计数器可以为处理器微结构的优化提供量化指导. 那么, 性能瓶颈究竟在哪里? 哪些优化工作是值得做的呢? 优化工作的预期性能收益是多少? 我们需要在开展具体的优化之前就回答这些问题, 以帮助我们规避那些预期性能收益很低的优化工作, 从而将更多时间投入到收益高的优化工作中. 这听上去像一个预测未来的工作, 但Amdahl's law可以告诉我们答案.

Amdahl's law在新窗口中打开由计算机科学家Gene Amdahl在1967年提出, 其内容是:

The overall performance improvement gained by optimizing a single part
of a system is limited by the fraction of time that the improved part
is actually used.

优化系统中某部分所获得的总体性能收益, 受限于那部分实际使用的时间占比.

假设系统某部分实际使用的时间占比是p, 该部分在优化后的加速比是s, 则整个系统的加速比为f(s) = 1 / (1 - p + p / s), 这就是Amdahl's law的公式表示.

例如, 某程序的运行过程分为独立的两部分A和B, 其中A占80%, B占20%.

若将B优化5倍, 则整个程序的加速比是1 / (0.8 + 0.2 / 5) = 1.1905;
若将B优化5000倍, 则整个程序的加速比是1 / (0.8 + 0.2 / 5000) = 1.2499;
若将A优化2倍, 则整个程序的加速比是1 / (0.2 + 0.8 / 2) = 1.6667.

<------- A --------><-B->
++++++++++++++++++++ooooo   原程序

++++++++++++++++++++o       将B优化5倍

++++++++++++++++++++        将B优化5000倍, 优化后B的运行时间很短

++++++++++ooooo             将A优化2倍

通常来说, 优化5000倍所需要付出的努力要比优化2倍大得多, 但Amdahl's law告诉我们, 把B优化5000倍, 还不如把A优化2倍. 这个反直觉的结论告诉我们, 不能仅考虑某部分的加速比, 还需要考虑该部分的时间占比, 从整系统的角度评估一项技术的优化效果. 因此, 对处理器的性能优化来说, 提前通过性能计数器测量某个优化对象在运行时间中的占比, 就显得非常重要了.

根据性能计数器寻找合适的性能瓶颈

根据性能计数器的统计结果, 尝试挖掘一些潜在的优化对象, 然后利用Amdahl's law估算它们能获取的理论收益, 从而确定系统的性能瓶颈位于何处.

从事计算机体系结构工作的专业素养

软件领域有一则广泛流传的忠告:

抛开workload谈优化就是耍流氓.

它的意思是, 优化方案的选择一定要基于负载的运行情况.

在体系结构领域更是如此, 我们不能依靠直觉来优化处理器设计, 觉得哪里有优化机会就改哪里, 否则将很容易采取一个没有效果的方案, 甚至会在实际场景中造成性能倒退. 相反, 根据评估数据采取合适的设计方案, 才是科学的做法.

事实上, Amdahl's law很容易理解, 如果不考虑专业背景, 我们甚至可以将它包装成一道数学应用题给小学生解答. 但我们也见过很多初学者"耍流氓", 说白了还是缺少相关的专业素养.

大家来学习“一生一芯”, 并不仅仅是学习RTL编码, 更重要的是学习解决问题的科学方法, 锻炼出这个方向的专业素养, 使得将来遇到真实问题时, 知道如何通过正确的方式解决.

自顶向下的调试方法

你已经调试过很多功能bug了, 但其实还有一种bug叫性能bug, 它的表现并不是程序出错或崩溃, 而是程序的运行性能低于预期. 当然, 调试性能bug的过程和性能优化的过程有相同之处, 都需要寻找系统中的性能瓶颈.

事实上, 调试功能bug和调试性能bug, 也有相似之处. 调试功能bug时, 我们首先看到的是程序出错或崩溃的信息, 但仅仅阅读这样的信息, 还很难找到bug; 于是要通过各种层次的trace工具来理解程序的行为, 找到程序出错时的具体表现; 然后再使用gdb/波形等工具, 在变量/信号层次进行细致分析.

调试性能bug时, 我们首先看到的是程序的运行时间, 但它无法直接告诉我们性能瓶颈在哪里; 于是通过性能公式将程序的运行时间分解成3个因子, 从编译, 微结构, 频率这3个方向考察优化潜力; 对于微结构, 光靠统计的IPC, 还是很难找到性能瓶颈, 于是我们需要分析影响IPC的因素, 把处理器划分成三大部分, 从指令供给, 数据供给和计算效率来理解处理器执行指令的过程, 但我们需要更具体的量化数据; 于是我们需要添加性能计数器, 来统计每个模块中性能事件发生的情况, 最后通过Amdahl's law找到真正的性能瓶颈.

调试这两种bug都用到了类似自顶向下的分析方法, 这并不是巧合, 而是计算机系统领域中抽象思维的体现: 抽象是理解复杂系统的唯一方式. 事实上, 如果你尝试一开始就使用gdb/波形来调试, 你会感到非常困难, 这是因为底层的细节数量巨大, 难以提供宏观视角的理解. 因此, 我们需要从高层语义开始, 根据合适的路径向下追溯, 在底层定位到一个很小的范围, 这才能帮助我们快速找到问题的所在.

校准访存延迟

我们将NPC接入ysyxSoC后, SDRAM控制器等模块提供了更真实的访存过程. 可以想象, 如果我们在接入ysyxSoC之前统计性能计数器, 由于访存延迟的差异, 其结果将与接入ysyxSoC后大不相同. 而不同的统计结果将会指导我们往不同的方向进行优化, 但如果我们以流片为目标, 这些不同方向的优化很可能无法取得预期的效果. 因此, 如果仿真环境的行为和真实芯片越接近, 评估结果的误差就越小, 在性能计数器的指导下开展的优化所取得的性能提升就越真实.

事实上, 之前的ysyxSoC环境是假设处理器和各种外设运行在同一频率下: verilator仿真的一个周期, 既是处理器中的一个周期, 也是外设中的一个周期. 但实际上并非如此: 受电气特性的影响, 外设通常只能运行在低频率, 例如SDRAM颗粒通常只能运行在100MHz左右, 过高的频率会导致时序违例, 使得SDRAM颗粒无法正确工作; 但另一方面, 使用先进工艺的处理器通常能够运行在更高的频率, 例如, yzh某个版本的多周期NPC在yosys-sta项目默认提供的nangate45工艺下频率达到约1.2GHz. 在上述配置下, SDRAM控制器中经过1个周期, NPC应该经过12个周期, 但verilator感知不到两者的频率差异, 仍然按照两者频率相同的假设进行仿真, 使得仿真结果比真实芯片乐观很多, 从而也可能会使得一些优化措施无法在真实芯片中取得预期的效果.

更新yosys-sta

我们在2024/04/09 08:30:00更新了yosys-sta项目, 添加了iEDA团队研发的网表优化工具, 大幅优化了yosys生成的综合网表, 使其时序评估结果更接近商业工具. 如果你在上述时间之前获得yosys-sta的代码, 请删除已有的yosys-sta项目并重新克隆.

为了获得更准确的仿真结果, 以指导我们进行更有效的优化, 我们需要对访存延迟进行校准(calibration). 校准的方式有两种, 一种是使用支持多个时钟域的仿真器, 例如VCS或ICARUS verilog在新窗口中打开. 和采用周期精确模型方式实现的verilator不同, 这种仿真器采用事件队列模型的方式实现, 把Verilog中的每次计算都看作事件, 并且可以维护事件的延迟, 从而可以正确地维护多时钟域中不同模块在不同频率下工作时每次计算的顺序. 不过为了维护事件队列模型, 这种仿真器的运行速度通常要低于verilator.

校准的第二种方式是修改RTL代码, 在ysyxSoC中插入一个延迟模块, 负责将请求延迟若干周期, 来模拟设备在低频率运行的效果, 使得NPC等待的周期数与其将来在高频率运行时所等待的周期数接近. 这种方式的实现不算复杂, 而且可以使用较快的verilator来仿真, 我们选择这种方式. 此外, 这种方式也适用于FPGA.

很自然, 为了实现延迟模块, 我们只要在延迟模块收到设备的回复后, 不马上回复给上游模块, 而是等待一定的周期数再回复, 但如何计算需要等待的周期数却是一个挑战. 考虑上文yzh的例子, 如果一个请求在SDRAM控制器中需要花费6个周期, 那NPC应该总共等待6 * 12 = 72个周期; 如果碰上SDRAM控制器在刷新SDRAM颗粒, 请求在SDRAM控制器中花费了10个周期, NPC应该总共等待10 * 12 = 120个周期; 如果请求发往flash, 在SPI master中花费了150个周期, NPC应该总共等待150 * 12 = 1800个周期. 可以看到, 延迟模块需要等待的周期数与设备服务请求所花费的时间有关, 并不是一个固定的常数, 因此需要在延迟模块中动态计算. 假设请求在设备中花费了k个周期, 处理器和设备的频率比是r(应有r >= 1), 那么延迟模块中需要计算出处理器所需等待的周期数c = k * r. 为了进行这一动态计算, 我们又需要考虑两个问题:

如何低开销地实现乘法?
如果r是小数, 如何实现小数的乘法? 例如yosys-sta项目报告的频率是550MH, 那么r = 550 / 100 = 5.5, 但如果把5.5按5来计算, 一个在设备端花费6周期请求将会在处理器端引入3个周期的误差, 对高速运行的CPU来说误差太大, 误差的积累会明显地影响性能计数器的值, 从而进一步影响优化的决策.

考虑到ysyxSoC的代码不参与综合和流片, 其实我们可以用一些简单的方法解决问题, 例如用*来计算乘法的结果, 用定点数来表示小数. 不过作为一个练习, 我们还是要求大家尝试可综合的实现方式, 将来如果你需要在可综合电路中解决类似的问题, 你就知道怎么做了.

首先我们先考虑r是整数时, 如何实现乘法. 既然延迟模块本身也需要等待设备的回复, 等待的时间正好是请求在设备中花费的周期数k, 那干脆让延迟模块在等待的每个周期中对一个计数器进行累加, 每周期加r即可. 对于给定的处理器频率和设备频率, r是个定值, 因此可以直接硬编码到RTL代码中. 在延迟模块收到设备的回复后, 就进入等待状态, 每周期让计数器减1, 减到0时再将请求回复给上游.

然后我们来考虑r是小数的情况. 既然小数部分不方便处理, 直接截断又会引入较大误差, 我们可以想办法将小数部分并入整数部分进行累加. 事实上, 我们可以引入一个放大系数s, 累加时每周期往计数器加r * s, 即累加结束时, 计数器的值为y = r * s * k, 然后在进入等待状态前, 将计数器更新为y / s即可. 因为s是一个常数, 因此r * s的结果也可以直接硬编码到RTL中, 当然这里的r * s很有可能还不是整数, 这里我们将其截断为整数, 虽然这理论上这仍然会引入一定的误差, 但我们可以证明误差比之前小很多. 不过y的值是动态计算的, 不能硬编码到RTL中, 因此对于一般的s, y / s需要计算除法. 你应该很快想到, 我们可以取一些特殊的s, 来简化这一计算的过程! 通过这种方式, 我们可以把误差减少到原来的1/s, 即原来在累加阶段累积的误差达到s时, 在这种新方法下的误差才增加1.

回顾当前的ysyxSoC, 其中SDRAM采用APB接口, 因此我们需要实现一个APB的延迟模块. ysyxSoC中已经包含一个APB延迟模块的框架, 并集成到APB Xbar的上游, 可捕捉所有APB访问请求, 包括SDRAM的访问请求. 但该框架并未提供延迟模块的具体实现, 因此默认无延迟效果. 为了校准ysyxSoC中SDRAM的访问延迟, 你还需要实现APB延迟模块的功能.

校准访存延迟

按照上文的介绍, 在ysyxSoC中实现APB延迟模块, 以校准仿真环境的访存延迟. 具体地, 如果你选择Verilog, 你需要在ysyxSoC/perip/amba/apb_delayer.v中实现相应代码; 如果你选择Chisel, 你需要在ysyxSoC/src/amba/APBDelayer.scala的APBDelayerChisel模块中实现相应代码, 并将ysyxSoC/src/amba/APBDelayer.scala中的Module(new apb_delayer)修改为实例化APBDelayerChisel模块.

为了实现APB延迟模块, 你需要根据APB协议的定义, 梳理出一个APB事务何时开始, 何时结束. 假设一个APB事务从t0时刻开始, 设备端在t1时刻返回APB的回复, APB延迟模块在t1'时刻向上游返回APB的回复, 则应有等式(t1 - t0) * r = t1' - t0.

关于r的取值, 我们假设设备运行在100MHz的环境下, 你可以根据yosys-sta的综合报告计算出r. 至于s, 理论上当然是越大越好, 不过你只要选择一个实际中够用的s即可. 至于多少够用, 就交给你来观察了, 这其实也是一种profiling.

实现后, 尝试取不同的r, 在波形中观察上述等式是否成立

寻找最高的综合频率

除了频率之外, 面积也是电路的一个评价指标. 但在工艺库的标准单元层次, 这两者本质上是互相制约的: 功能相同的一类单元, 如果希望单元的逻辑延迟低, 就需要通过更多的晶体管让其具备更强的驱动能力, 从而增大单元的面积.

鉴于面积和频率之前的制约关系, 综合器一般会用尽可能少的面积来达到给定的目标频率, 而不会去单独考虑给定的电路最高能达到多少主频. 如果你的电路质量比较高, 可能会出现综合报告的频率随目标频率提升而提升的现象, 不过电路的综合面积也会随之增加.

因此, 如果你暂时不考虑面积的开销, 可以设置一个比较高的目标频率, 让综合器尝试去达到. 在处理器设计中, 有一些因素会成为处理器频率的上限:

寄存器堆的读延迟. 通常寄存器堆的读操作需要在一个周期内完成, 无法拆分到多个周期中, 因此处理器的频率不会超过寄存器堆的最大工作频率.
位宽和处理器字长相等的加法器延迟. 通常EXU的加法操作需要在一个周期内完成, 如果这个加法操作需要多个周期完成, 将会大幅降低所有包含加法操作的指令的执行效率, 包括加法指令, 减法指令, 访存指令(需要计算访存地址), 分支指令(需要计算目标地址), 甚至是PC + 4的计算, 从而使得程序的IPC大幅降低. 因此处理器的频率不会超过这个加法器的最大工作频率.
SRAM的读写延迟. SRAM作为一种全定制单元, 无法通过逻辑设计来优化其读写延迟, 因此只要使用了SRAM, 处理器的频率不会超过SRAM的最大工作频率.

你可以编写一些简单的小模块来单独评估这些部件的最大工作频率, 为了避免I/O端口的影响, 你需要在这些部件的输入端和输出端都插入一些触发器. SRAM作为一种全定制单元, 其最大工作频率通常会记录在相应的手册中, 而且目前我们暂不使用SRAM, 你可以先不开展SRAM的评估工作.

评估后, 你可以将处理器的综合目标频率设置得比上述部件的最大工作频率更高, 来指导综合器尽可能地综合出更高频率的结果. 当然你也可以直接将目标主频设置成一个很难达到的值, 例如5000MHz, 不过我们还是推荐你通过上述评估过程了解这些部件的最大工作频率.

可编程的计数器增量

上文提到的r对RTL设计来说是个常数, 但在可以动态调频的复杂处理器中并不是这样. 对于这种复杂处理器, 我们需要把r设计成可编程的, 通过一个设备寄存器来存放r, 软件进行动态调频后, 就将新的r写入到设备寄存器中. 因此, 我们还需要将这个设备寄存器映射到处理器的地址空间中, 使其可以被处理器通过SoC访问到. 当然, s也可以设计成可编程的.

不过, 这需要对ysyxSoC进行较多的改动, 所以我们就不要求大家实现上述可编程功能了.

重新寻找优化瓶颈

添加延迟模块后, 重新运行一些测试并收集性能计数器的统计结果, 然后根据Amdahl's law寻找性能瓶颈.

评估NPC的性能

添加延迟模块后, 运行microbench的train规模测试, 记录各种性能数据, 包括主频信息和各种性能计数器.

校准访存延迟后, 在ysyxSoC中运行microbench的train规模测试预计需要花费数小时, 但我们将得到与流片环境非常接近的性能数据. 后续你可以在每次添加一个特性后, 就重新评估并记录性能数据, 来帮助你梳理每一个特性带来的性能收益.

记录性能数据

接下来, 我们要求你记录每一次评估后的性能数据. 如果你申请第六期的流片, 你将会提交这部分记录, 如果记录的情况与实际开发过程不符, 你可能无法获得流片机会. 我们希望通过这种方式强迫你去认识并理解NPC的性能变化情况, 锻炼出处理器体系结构设计的基本素养, 而不是仅仅将参考书籍中的架构图翻译成RTL代码.

具体地, 你可以按照如下方式记录:

commit	说明	仿真周期数	指令数	IPC	综合频率	综合面积	性能计数器1	性能计数器2	...
0123456789abcdef	示例, 实现cache	200000	10000	0.05	750MHz	16000	3527	8573	...

其中:

我们要求你在NPC工程目录下的Makefile中添加一条规则make perf, 使得将来执行
```
git checkout 表中的commit
make perf
```
后, 可以复现出对应表格中的性能数据. 如果复现的情况与表中记录的数据严重不符, 在无法合理说明的情况下, 可能会被判定为违反学术诚信.
- 你可以假设你正在进行一项科学研究, 你需要对研究过程中的实验数据负责: 实验数据需要是可复现的, 能够在公开场合下经得起推敲.
你可以在学习记录中新建一个名为NPC性能评估结果的工作表, 来记录这些性能数据
你可以将性能计数器1和性能计数器2更换成相应性能计数器的实际名称
你可以根据实际情况, 记录更多的性能计数器
你也可以将你对性能数据的分析记录到说明一栏
我们鼓励你尽可能多地记录性能数据的条目, 从而帮助你量化地分析NPC的性能变化情况

优化主频是否值得?

根据主频校准访存延迟后, 你会发现IPC大幅下降. 可以预料到的是, 如果主频进一步提升, 访存延迟的周期数也会增加, 从而导致IPC降低. 那么, 主频是否值得我们去优化呢? 如果值得, 优化主频带来的性能收益具体是来自于哪里? 如果不值得, 优化主频带来的性能倒退具体又体现在哪处? 尝试结合性能计数器分析你的猜想.

校准FPGA上的访存延迟

现代的FPGA上一般含有DDR内存控制器. 但受限于FPGA的实现原理, PL部分的CPU频率也与ASIC流程有很大差距, 甚至CPU频率比内存控制器的频率还低. 例如, 内存控制器可以跑在200MHz, 但CPU只能在FPGA上以数百MHz甚至数十MHz的频率运行, 而在真实芯片中, CPU通常能运行在1GHz以上(例如, 第三代香山的目标主频是3GHz). 显然, 在这样的评估环境中得到的性能数据, 对将流片作为目标的CPU性能测试来说是大幅失真的. 通过校准访存延迟解决上述内存频率倒挂的情况, 是处理器企业使用FPGA进行CPU性能评估之前必须解决的问题.

事实上, 由于真实的DDR是一个复杂的系统, 即使采用上文介绍的延迟模块的方案, 也还需要考虑更多问题:

由于模拟电路部件的差异, FPGA中内存控制器的phy模块与ASIC的内存控制器不同, 这可能会影响访存延迟
受限于FPGA的实现原理和FPGA上PLL的可配置范围, DDR控制器运行的频率也低于ASIC的内存控制器, 但DDR颗粒无法等比例降频, 导致访存延迟不准确
DDR控制器降频后, 其刷新频率等参数也与ASIC的内存控制器不一致

因此, 要在FPGA上很好地解决内存频率倒挂问题, 在业界也是一项不小的挑战. 例如, 香山团队成立了一个小组, 由工程师带队来解决这一问题.

事实上, 是否需要校准FPGA的访存延迟, 取决于FPGA的使用场景和目标:

教学: 仅仅将FPGA作为功能测试的环境. 此时FPGA起到的作用就是加速仿真过程, 无论处理器和内存控制器之间的运行频率比例如何, 理论上都不影响功能测试的结果.
比赛或科研项目: 将FPGA作为性能测试的环境, 同时也作为目标平台. 此时不以流片为目标, 故不必校准访存延迟.
企业产品研发: 将FPGA作为性能测试的环境, 但同时把流片作为目标. 我们会期望通过FPGA得出的性能数据尽可能与真实芯片一致. 这时, 校准FPGA的访存延迟将是不可或缺的.

"一生一芯"虽然作了诸多简化, 但总体上还是希望大家能体会到企业产品研发的大致流程, 同时考虑到真实DDR控制器的校准存在诸多工程挑战, 因此我们不要求大家使用FPGA. 相比之下, 在仿真环境中校准访存延迟, 要比在FPGA中容易很多, 因此我们还是推荐大家在仿真环境中进行性能评估和优化.

提升功能测试的效率

将校准访存延迟后的ysyxSoC仿真环境用于性能评估是很合适的, 但你也会感觉到, 这一环境的仿真效率明显低于之前的riscv32e-npc: 从microbench的train规模测试的运行时间来看, riscv32e-npc的仿真效率是riscv32e-ysyxsoc的数十倍甚至上百倍. 这其实反映出一种权衡关系: 要得到更准确的性能数据, 就要仿真越多的细节(例如SDRAM控制器和SDRAM颗粒), 从而需要在仿真1周期的过程中花费更多的时间, 最终导致仿真效率越低. 相应地, 仿真效率较高的riscv32e-npc, 得到的性能数据则是不准确的.

那riscv32e-npc是否没有意义呢? 事实上, 我们可以把riscv32e-npc作为一个功能测试的环境. 如果在riscv32e-npc中存在一个功能bug, 那么这个bug也很大概率存在于riscv32e-ysyxsoc之中, 但显然在仿真效率更高的riscv32e-npc中调试这个bug是一个更合适的方案. 这样, 我们就可以充分发挥两个仿真环境各自的优势, 取长补短, 从整体上提升开发和测试的效率.

尝试修改相关的仿真流程, 从而支持NPC在riscv32e-npc和riscv32-ysyxsoc中仿真. 其中, riscv32e-npc仍然采用0x8000_0000作为复位时的PC值.

经典体系结构的4类优化方法

找到性能瓶颈后, 我们就可以考虑如何对其进行优化. 经典体系结构中主要有4类优化方法:

局部性 - 利用数据访问的性质提升指令供给和数据供给能力. 代表性技术是缓存
并行 - 多个实例同时工作, 提升系统整体的处理能力. 并行方法又有很多分类:
- 指令级并行 - 同时执行多条指令, 相关技术包括流水线, 多发射, VLIW和乱序执行
- 数据级并行 - 同时访问多个数据, 相关技术包括SIMD, 向量指令/向量机
- 任务级并行 - 同时执行多个任务, 相关技术包括多线程, 多核, 多处理器和多进程; GPU属于SIMT, 是一种介于数据级并行和任务级并行之间的并行方法
预测 - 在不知道正确选择时, 先投机地执行一个选择, 在后续检查选择是否正确, 如果预测正确, 就能降低等待的延迟, 从而获得性能收益. 如果预测错误, 就需要通过额外的机制进行恢复. 代表性技术包括分支预测和缓存预取
加速器 - 使用专门的硬件部件来执行特定任务, 从而提升该任务的执行效率, 一些例子包括:
- AI加速器 - 对AI负载的计算过程进行加速, 通常通过总线访问
- 自定义扩展指令 - 将加速器集成到CPU内部, 通过通过新增的自定义扩展指令来访问
- 乘除法器 - 可以视为一类加速器, 将RVM视为RVI的扩展, 通过乘除法指令控制专门的乘除法硬件模块, 来加速乘除法的计算过程

重新审视处理器体系结构设计

很多电子类专业的同学一开始很可能会把处理器体系结构设计理解成"用RTL开发一款处理器". 但RTL编码只是处理器设计流程中的其中一个环节, 而且严格来说并不属于处理器体系结构设计的范畴.

事实上, 一名合格的处理器架构师应该具备如下能力:

理解程序如何在处理器上运行
对于支撑程序运行的特性, 能判断它们适合在硬件层次实现, 还是适合在软件层次实现
对于适合在硬件层次实现的特性, 能提出一套在各种因素的权衡之下仍然满足目标要求的设计方案

这些能力的背后其实反映出人们使用计算机的根本目的: 通过程序解决真实需求. 如果在硬件层次添加的特性给程序带来的收益很低, 甚至程序根本不会使用这一特性, 那相关方案的决策者确实算不上是专业的架构师.

事实上, 这些能力是需要刻意去锻炼的. 我们见过不少同学, 能根据一些参考资料将流水线处理器的框图翻译成RTL代码, 但却无法评估一个程序的运行时间是否符合预期, 也不知道如何进一步优化或实现新需求; 还有一些同学设计出一个乱序超标量处理器, 但性能却比不上教科书上的五级流水线. 这说明, 体系结构设计能力并不等同于RTL编码能力, 也许这些同学在开发过程中确实理解了流水线和乱序超标量的基本概念, 但却缺少全局的视野和理解, 只将关注点放在提升后端的计算效率上, 很少甚至没有关注过指令供给和数据供给, 导致处理器的访存能力远低于计算能力, 总体的性能表现不佳. 因此, 即使能设计出一个正确的乱序超标量处理器, 也算不上是一个好的处理器, 从某种程度上来说, 这些同学也还不具备处理器体系结构设计能力.

"一生一芯"尝试从另一个思路锻炼大家的处理器体系结构设计能力: 首先将程序运行起来, 从软硬件协同的视角理解程序运行的每一处细节; 然后学习处理器性能评估的基本原理, 理解程序行为在硬件层次的微观表现; 最后才是学习各种体系结构优化方法, 使用科学的评估手段理解这些优化方法对程序运行带来的真实收益.

这一学习方案和教科书有很大区别, 这是因为处理器体系结构设计能力只能通过实践来锻炼, 但采用教科书的理论课堂受限于课程体制, 无法考察学生的体系结构设计能力. 因此, 你很容易通过教科书或者参考书籍入门, 但如果你想成为这个方向的专业人士, 就要明白这些书籍的上限, 在必要的阶段跨越书籍的边界, 通过针对性的训练锻炼出真正的体系结构设计能力.

存储层次结构和局部性原理

校准ysyxSoC的访存延迟后, 你应该发现性能瓶颈在于指令供给: 取一条指令都要等待数十上百个周期, 流水线根本没法流水. 要提升指令供给能力, 最合适的就是使用缓存技术. 不过在介绍缓存之前, 我们需要先了解计算机的存储层次结构和局部性原理.

存储层次结构(Memory Hierarchy)

计算机中存在不同的存储介质, 如寄存器, 内存, 硬盘和磁带, 它们具有不同的物理特性, 因而各种指标也有所不同. 可以从访问时间, 容量和成本这几个方面评估它们.

access time     /\        capacity    price
               /  \
   ~1ns       / reg\        ~1KB     $$$$$$
             +------+
   ~10ns    /  DRAM  \      ~10GB     $$$$
           +----------+
   ~10ms  /    disk    \    ~1TB       $$
         +--------------+
   ~10s /      tape      \  >10TB       $
       +------------------+

寄存器. 寄存器的访问时间很短, 基本与CPU的主频一致. 目前的商业级高性能CPU主频大约3GHz, 因此寄存器访问时间小于1ns. 寄存器的容量很小, 通常小于1KB. 例如, RV32E有16个32位寄存器, 大小是512b. 此外，寄存器的制造成本较为昂贵, 若使用大量寄存器, 则将占用不少流片面积.
DRAM. DRAM的访问时间大约为10ns的量级, 其容量比寄存器大得多, 常用于内存. 其成本也低很多, 某电商平台上16GB内存条的价格是329元, 约20元/GB.
机械硬盘. 机械硬盘的访问时间受限于其机械部件, 如盘片需要旋转, 通常需要10ms的量级. 相对地, 机械硬盘也拥有更大的容量, 通常能达到数TB; 其成本也更便宜, 某电商平台上4TB机械硬盘的价格是569元, 约0.139元/GB.
固态硬盘. 固态硬盘也是目前流行的存储介质, 其存储单元采用NAND flash, 基于电的特性进行工作, 因此访问速度比机械硬盘快得多, 其读延迟接近DRAM, 但受限于flash单元的特性, 写延迟还是比DRAM高很多. 其成本稍高于机械硬盘, 某电商平台上1TB固态硬盘的价格是699元, 约0.683元/GB.
磁带. 磁带的存储容量非常大, 成本也非常低, 但访问时间很长, 约10s的量级, 因此目前已很少使用, 通常用在数据备份的场景. 某电商平台上30TB磁带机的价格是1000元, 约0.033元/GB.

可见, 由于存储介质物理特性的限制, 没有一种存储器能同时满足容量大, 速度快, 成本低等各种指标. 因此, 计算机通常集成多种存储器, 并通过一定的技术将它们有机组织起来, 形成存储层次结构, 在整体上达到容量大, 速度快, 成本低的综合指标. 这听上去有点不可思议, 不过关键在于如何把各种存储器有机组织起来.

局部性原理

其实上述的组织方式是有讲究的, 其中的奥秘就是程序的局部性原理. 计算机架构师发现, 程序在一段时间内对存储器的访问通常集中在一个很小的范围:

时间局部性 - 访问一个存储单元后, 短时间内可能再次访问它
空间局部性 - 访问一个存储单元后, 短时间内可能访问它的相邻存储单元

上述现象与程序的结构和行为有关:

程序大多数时候将顺序执行或循环执行, 二者分别遵循空间局部性和时间局部性
编写程序时, 相关的变量在源代码中的位置相距不远, 或者采用结构体来组织, 编译器也会为其分配分配相近的存储空间, 从而呈现出空间局部性
程序执行过程中访问变量的次数通常不小于变量的数量(否则将存在未被使用的变量), 因此必定有变量会被多次访问, 从而呈现出时间局部性
对于数组, 程序通常使用循环来遍历, 从而呈现出空间局部性

观察程序的局部性

程序的局部性和内存访问有关, 很自然地, 我们可以通过mtrace来观察它! 在NEMU中运行一些程序, 并获取mtrace. 之后, 你需要对mtrace的输出进行二次处理, 尝试借助一些绘图工具呈现你的结果.

链表的局部性

遍历链表的过程中是否呈现出局部性? 尝试比较访问数组元素和链表元素时, 何者的局部性更优.

局部性原理告诉我们, 程序对存储器的访问表现出集中的特性. 这说明, 即使慢速存储器的容量很大, 程序在一段时间内只会访问很小的一部分数据. 既然如此, 我们可以先将这部分数据从慢速存储器中搬运到快速存储器中, 然后在快速存储器中访问它们.

这就是存储层次结构中各种存储器之间组织方式的诀窍: 将各种存储器按层次排列, 上层存储器速度快但容量小, 下层存储器容量大但速度慢; 访问数据时, 先访问速度较快的上层存储器, 如果数据在当前层级(称为命中), 则直接访问当前层级的数据; 否则(称为缺失), 就在下一层级寻找, 下层将目标数据及其相邻数据传递给上层. 其中, "把目标数据传递给上层存储器"利用了时间局部性, 期望下次访问目标数据时能在速度快的存储器中命中; 而"把相邻数据传递给上层存储器"则利用了空间局部性, 期望下次访问相邻数据时也能在速度快的存储器中命中.

例如, 在访问DRAM时, 如果数据不存在, 则访问机械硬盘, 并将目标数据及其相邻数据搬运到DRAM中, 下次访问这些数据时, 即可在DRAM中命中, 从而直接访问DRAM中数据. 通过这种方式, 我们近似得到了一个访问速度接近DRAM, 容量接近机械硬盘的存储器! 在成本方面, 以上文电商平台的报价为例, 一根16GB的内存条和一块4TB的机械硬盘的总价格不到900元, 但如果要采购4TB的内存条, 则需要329 * (4TB / 16GB) = 84224元!

当然, 天下没有免费的午餐, 要实现上文的效果是有条件的, 计算机系统的设计需要满足局部性原理: 一方面, 计算机系统需要设计并实现存储层次结构; 另一方面, 程序员也需要开发出局部性较好的程序, 使其在存储层次结构中能获得较好的性能. 如果程序的局部性较差, 访问的数据不具备集中的特性, 将导致大部分访问都无法在快速存储器中命中, 从而使得整个系统的表现接近于访问慢速存储器.

简易缓存

缓存介绍

回到上文的性能瓶颈, 为了优化指令供给, 实际上我们需要做的是提升访问DRAM的效率. 为此, 我们只需要按照计算机存储层次结构的思想, 在寄存器和DRAM之间添加一层存储器即可. 这就是缓存(cache)的思想. 也即, 在访问DRAM之前, 先访问cache, 若命中, 则直接访问; 若缺失, 则先将数据从DRAM读入cache, 然后再访问cache中的数据.

上面的cache属于狭义范畴, 指的是处理器缓存(CPU cache). 事实上, 广义的cache并不仅仅是指代访存通路上的那个硬件模块, 在计算机系统中, cache无处不在: 磁盘控制器中也包含cache, 用于缓存从磁盘中读出的数据; 我们之前介绍的SDRAM中的行缓冲, 本质上也是SDRAM存储阵列的缓存; 操作系统也会通过软件的方式为磁盘等存储设备维护一个缓存, 用于存储最近访问的数据, 这个缓存本质上是一个大型结构体数组, 它在内存中分配, 因此操作系统负责在磁盘和内存之间进行数据搬运; 缓存对分布式系统也是至关重要, 如果要访问的数据不在本地缓存, 就需要访问远端, 浏览器的网页缓存和视频内容缓存都属于这种情况.

回到CPU cache, 谁来将数据从DRAM读入cache呢? 事实上, 谁来完成上下两个存储层次之间的数据搬运, 取决于谁能访问这两个存储层次. 计算机中的主体只有软件程序和硬件电路, 而软件程序的本质是指令序列. 虽然指令可以访问DRAM, 但指令集手册中定义的编程模型通常不包含cache, 也就是说从功能上来说, cache对软件程序不可见, 因此只能是硬件电路来完成上述读入操作(后面我们会看到, 本质上还是状态机). 而对于DRAM和磁盘这两个存储层次, 指令可以访问DRAM, 也可以通过MMIO访问作为设备的磁盘, 因此可以由软件负责将数据从磁盘读入DRAM, 上文提到的操作系统就是如此. 当然, 原则上你也可以设计一个硬件模块, 专门完成DRAM和磁盘之间的数据搬运工作, 但这个硬件模块通常只能适配一种磁盘, 其灵活性远不如操作系统中的驱动程序.

对软件程序可见的cache

在一些处理器中, cache是对软件程序可见的. 例如CUDA GPU编程模型中的shared memory, 在组织层次上和CPU cache一样, 都是寄存器和DRAM之间的一层存储器; 但和CPU cache不同的是, GPU提供了专门用于访问shared memory的访存指令, 因此GPU程序可以通过指令来将数据从内存中读入shared memory的指定位置.

为了方便描述, 我们将从DRAM读入的数据称为一个数据块, cache中存放的数据块称为cache块(有的教科书也称为cache行, 英文为cache line). 自然地, 设计cache需要关注如下问题:

数据块的大小应该是多少?
如何检查访存请求是否在cache中命中?
cache的容量通常比DRAM小, 如何维护cache块和DRAM中数据块之间的映射关系? cache满了后怎么办?
CPU可能会执行写操作, 从而更新数据块中的数据, cache应如何维护?

简易指令缓存

我们先来考虑指令缓存(instruction cache, 简称icache), 由于IFU的取指过程无需写入内存, 因此icache是只读的, 我们可以先不考虑如何处理CPU写入数据块的情况. 至于块大小, 我们先取一条指令的长度, 即4B. 这也许不是一个最好的设计, 但对icache来说, 小于4B肯定不是一个好的设计, 否则取出一条新指令时, 还需要进行多次访存. 至于大于4B是否更好, 我们后面再来评估.

为了检查访存请求是否在cache中命中, 很自然地, 除了存储数据块本身, cache还需要记录块的一些属性. 最直接的方式就是记录这个块的一种唯一编号, 不过我们还希望, 这个唯一编号的计算方式要足够简单. 既然数据块是从内存来的, 我们可以按块大小对内存进行编号, 内存地址addr对应的数据块的编号即为addr / 4, 这个编号称为块的标签(tag). 这样, 我们只要计算出访存地址的tag, 然后和每个cache块的tag对比, 就能知道目标块是否在cache中.

然后来考虑cache块的组织问题. 根据存储层次结构, cache的容量不可能和DRAM一样大, 通常也不可能小到只有1个cache块, 因此需要考虑读入一个新块时, 应该将其读入到哪个cache块中. 由于cache中有多个cache块, 因此我们也可以给cache块进行编号. 最简单的组织方式就是将一个新块读入到固定的cache块中, 这种组织方式称为直接映射(direct-mapped). 为此, 我们需要明确从内存地址addr到cache块号的映射关系. 假设cache可存放k个cache块, 一种简单的映射关系是cache块号 = (addr / 4) % k, 也即, 对于内存地址为addr的数据块, 它将被读入编号为(addr / 4) % k的cache块.

显然, 多个数据块可能会映射到相同的cache块, 这时需要决定应该保留已有的cache块, 还是往cache块中读入新块. 根据程序的局部性原理, 将来访问新块的概率更大, 因此读入新块时, 应该将已有的cache块替换为新块, 使得接下来一段时间内访问新块时能都在cache中命中.

我们可以把所有cache块看作一个数组, cache块号就是数组的索引(index), 因此cache块号也称为块索引. 对于块大小是b字节, 共k个cache块的直接映射cache, 有tag = addr / b, index = (addr / b) % k. 为了方便计算, 通常取b和k为2的幂, 假设b = 2^m, k = 2^n. 假设addr为32位, 则有tag = addr / 2^m = addr[31:m], index = (addr / 2^m) % 2^n = addr[m+n-1:m], 可见, index实际上是tag中的低n位. 由于在直接映射的cache中, index不同的数据块必定会被映射到不同的cache块中, 即使它们的tag的高m位(即addr[31:m+n])相同, 因此, 记录tag时只需要记录addr[31:m+n]即可.

一个访存地址可以划分成以下3部分: tag, index, offset. 其中tag部分作为数据块在cache中的唯一编号, index部分作为数据块在cache中的索引, offset部分属于块内偏移, 指示需要访问数据块中的哪部分数据.

 31    m+n m+n-1   m m-1    0
+---------+---------+--------+
|   tag   |  index  | offset |
+---------+---------+--------+

最后, 在系统复位时, cache中无任何数据, 此时所有cache块均无效. 为了标识一个cache块是否有效, 需要为每个cache块添加一个有效位(valid). valid和tag统称为cache块的元数据(metadata), 其含义是用于管理数据的数据, 此处被管理的数据就是cache块.

综上, 上述icache的工作流程如下:

IFU向icache发送取指请求
icache获得取指请求的地址后, 根据index部分索引出一个cache块, 判断其tag与请求地址的tag是否相同, 并检查该cache块是否有效. 若同时满足上述条件, 则命中, 跳转到第5步
通过总线在DRAM中读出请求所在的数据块
将该数据块填入相应cache块中, 更新元数据
向IFU返回取出的指令

整理出工作流程后, 你应该知道如何实现icache了: 还是状态机! 上述工作流程甚至包含了一次总线的访问, 因此icache的实现也可以看成是总线状态机的扩展. 你已经很熟悉总线的实现了, 因此如何实现icache的状态机, 就交给你来梳理吧!

实现icache

根据上述流程, 实现一个简单的icache, 块大小为4B, 共16个cache块. 一般来说, cache的存储阵列(包括数据和元数据)都通过SRAM来实现, 但在ASIC流程中使用SRAM涉及到选型和实例化, 其中SRAM的选型可能会影响到数据和元数据的存放. 作为第一个cache的练习, 为简单起见, 此处先通过触发器来实现存储阵列, 提高实现的灵活性.

实现时, 建议将相关参数实现成可配置的, 以便于后续评估不同配置参数的性能表现. 实现后, 尝试评估其性能表现.

适合缓存的地址空间

并不是所有的地址空间都适合缓存, 只有存储器类型的地址空间才适合缓存. 此外, SRAM的访问延迟本身就只有1周期, 因此也无需缓存, 将缓存块留给其他的地址空间是一个更合适的方案.

估算dcache的理想收益

通常, LSU也有与其配对的缓存, 称为数据缓存(data cache, 简称dcache). 在实现dcache之前, 我们可以先估计它在理想情况下的性能收益. 假设dcache的容量无限大, 访问dcache的命中率为100%, 且dcache的访问延迟为1周期, 尝试根据性能计数器估算添加这样一个dcache带来的性能收益.

如果你的估算正确, 你应该发现此时添加dcache是不值得的, 我们将在下文继续讨论这个问题.

形式化验证

借助DiffTest, 你应该很容易保证接入icache后, 给定的程序仍然可以正确运行. 但如何保证icache对于任意程序都能正确运行呢?

这看上去是一个很困难的问题, 相信你一定碰到过这种情况: 代码运行给定的测试用例都是正确的, 但哪天运行一个其他的测试, 就会出错. 无论是从原理上分析还是从实践中总结, 光靠测试是无法证明一个模块的正确性的, 除非这些测试用例覆盖了所有程序, 或者是覆盖了被测试模块的所有输入情况. 程序的数量是无限的, 要把所有程序都测试一遍并不现实, 不过被测试模块的输入是有限的, 至少遍历所有输入在理论上是可行的.

如果要遍历一个模块的所有输入, 一方面要生成可以覆盖所有输入情况的测试集, 另一方面还需要有方法能判断一个具体的输入是否正确. 即使这些能做到, 要把所有测试全部运行完, 也需要很长时间, 这通常是难以忍受的. 软件测试理论中的等价类测试方法可以把本质行为相似的测试进行归类, 从等价类中选择一个测试来代表整个等价类的测试, 从而降低测试集的大小. 但等价类应该如何划分, 是需要根据被测模块的逻辑人工决定的. 不过, 根据软件领域另一则广泛流传的忠告, 需要人工干预的流程, 都会存在出错的风险.

形式化验证的基本原理

那么, 能不能让工具帮我们自动寻找测试用例呢? 还真有这种工具! 求解器(Solver)是一类在给定约束条件下寻找可行解的数学工具, 其本质类似求解方程组或线性规划等数学问题. 例如, Z3在新窗口中打开是一个可满足性模理论(Satisfiablity Modulo Theories, SMT)在新窗口中打开问题的求解器, 它可以求解一个包含实数, 整数, 比特, 字符, 数组, 字符串等内容的命题是否成立. 事实上, 只要能将问题表达成一阶逻辑语言的某个子集, 就能交给SMT求解器来求解, 因此SMT求解器也可以用来求解类似数独的复杂问题. SMT求解器广泛应用于定理自动证明, 程序分析, 程序验证和软件测试等领域. 下面是一个在python中使用Z3求解方程组的例子.

#!/usr/bin/python
from z3 import *

x = Real('x')  # 定义变量
y = Real('y')
z = Real('z')
s = Solver()
s.add(3*x + 2*y - z == 1)    # 定义约束条件
s.add(2*x - 2*y - 4*z == -2)
s.add(-x + 0.5*y - z == 0)
print(s.check())  # 求是否存在可行解: sat
print(s.model())  # 输出可行解: [y = 14/25, x = 1/25, z = 6/25]

在测试验证领域, 有一种称为形式化验证(formal verification)的验证方法, 该方法的一种技术路线是模型检测(model checking), 相应的验证工具称为模型检测器(model checker). 模型检测的核心是求解器, 具体地, 模型检测器将设计作为约束条件, 将输入作为变量, 将"至少一个验证条件不成立"作为求解目标, 把这些内容用一阶逻辑语言表达出来, 并转换成求解器识别的语言, 然后尝试让求解器寻找是否存在可行解. 例如, 若某设计中有assert(cond1)和assert(cond2)这两个验证条件, 则尝试让求解器寻找是否存在输入, 使得!cond1 || !cond2成立. 若可行解存在, 则说明求解器找到了一个违反验证条件的测试用例, 这个反例可以帮助我们调试并改进设计; 若可行解不存在, 则说明所有输入都不会违反验证条件, 从而证明了设计的正确性! 可见, 无论求解器能否找到可行解, 对设计者来说都是极好的消息.

通常来说, 一个系统的状态还跟时间有关, 例如, 处理器每经过一个周期, 其状态都可能会发生改变. 如果支持在所有时间长度下验证某条件, 则该方法称为无界模型检测(Unbounded Model Checking). 但由于无界模型检测的检测开销很大, 因此实际上更多采用的是有界模型检测(Bounded Model Checking, BMC). BMC通常需要一个参数k, 它只验证某条件在经过最多时间k的情况下是否成立, 这个参数称为BMC的界(bound).

不要迷信UVM测试的100%覆盖率报告

如果你了解UVM, 你应该知道UVM的目标是提升覆盖率. 但如果你认为提升覆盖率是测试验证的最终目标, 那你很有可能还不了解测试验证.

事实上, 测试验证的最终目标, 是证明设计的正确性, 或者是找出设计中的所有bug. 但有经验的工程师都知道, 即使做到了100%的覆盖率, 还是可能会有一些bug没有被测出来, 而且还估算不了这些没被测出来的bug还有多少.

之所以覆盖率的目标被企业广泛采用, 一方面是因为覆盖率是一个容易量化和统计的指标. 如果用严格的语言来描述"一个事件被覆盖", 就是

存在一个测试用例, 其运行成功, 且在运行过程中触发了该事件.

这里的事件可以是执行到某行代码(行覆盖率), 某信号发生翻转(翻转覆盖率), 某状态机的状态发生转移(状态机覆盖率), 自定义条件被满足(功能覆盖率)等. 而"覆盖率达到100%", 则是

对于每个事件, 都存在一个测试用例, 其运行成功, 且在运行过程中触发了该事件.

注意我们可以通过不同的测试用例覆盖不同的事件. 按照这个定义, 只需要在仿真过程中添加一些标志即可统计出覆盖率. 甚至大多数RTL仿真器(包括verilator)都提供了自动统计覆盖率的功能, 如果你想学习如何统计覆盖率, 只需要RTFM.

另一方面, 从上述定义也可以看出, 提升覆盖率其实是验证工作的下限, 覆盖率太低, 只能说明验证工作做得还不充分, 这和"未测试代码永远是错的"是一致的. 但测试验证的最终目标是

对于所有测试用例, 均运行成功.

相比之下, "覆盖率达到100%"其实是"设计正确"的必要不充分条件, 是非常宽松的, 甚至我们很容易就可以举出一个反例: 某模块有两个功能, 针对每个功能, 已分别被各自的测试用例覆盖, 此时功能覆盖率达到100%; 但在运行那些需要两个功能进行交互的测试用例时, 就出错.

和低覆盖率的验证工作相比, 达到更高的覆盖率固然能提升设计正确的概率, 但我们想说的是, 即使覆盖率达到100%, 还是远远不够的. 尤其是对复杂系统来说, 一些藏得很深的bug通常在多个边界条件同时满足的情况下才会触发. 与其坚持以100%覆盖率作为验证目标, 我们更鼓励大家积极思考如何通过其他方法和技术寻找更多潜在的bug, 对验证工作的实际意义也更大.

形式化验证的简单示例

基于Chisel的形式化验证流程

Chisel的测试框架chiseltest在新窗口中打开已经集成了形式化验证的功能, 可以将FIRRTL代码翻译成能被BMC识别的语言, 并让BMC证明给定的assert()是否正确. 若能找到反例, 则生成该反例的波形辅助调试, 非常方便. 有了形式化验证工具, 我们再也不需要为测试用例覆盖不全面而苦恼, 甚至连测试用例也不需要编写了. 一个字, 香!

下面给出一个对Chisel模块进行形式化验证的例子:

import chisel3._
import chisel3.util._
import chiseltest._
import chiseltest.formal._
import org.scalatest.flatspec.AnyFlatSpec

class Sub extends Module {
  val io = IO(new Bundle {
    val a = Input(UInt(4.W))
    val b = Input(UInt(4.W))
    val c = Output(UInt(4.W))
  })
  io.c := io.a + ~io.b + Mux(io.a === 2.U, 0.U, 1.U)

  val ref = io.a - io.b
  assert(io.c === ref)
}

class FormalTest extends AnyFlatSpec with ChiselScalatestTester with Formal {
  "Test" should "pass" in {
    verify(new Sub, Seq(BoundedCheck(1), BtormcEngineAnnotation))
  }
}

不再使用Utest

随着Chisel版本的演进, Utest已不被支持, 因此我们也建议不再使用Utest. 如果你在2024/04/11 01:00:00之前获取chisel-playground的代码, 请参考新版本的build.sc在新窗口中打开中的object test修改你的build.sc.

上述例子的Sub模块通过"取反加1"实现了补码减法的功能. 为了验证Sub模块实现的正确性, 代码将"取反加1"的计算结果与通过减法运算符得到的结果进行对比, 我们预期assert()应该对任意输入都成立. 为了展示形式化验证的效果, 我们在Sub模块的实现中注入了一个bug: 在io.a为2时不进行"加1"操作, 此时补码减法的结果是错误的.

在调用chiseltest提供的形式化验证功能时, 上述代码还需要传入一个BoundedCheck(1)的参数作为BMC的界, 用来指定需要证明的周期数. 例如, BoundedCheck(4)表示让BMC尝试证明被测模块在复位之后的4个周期内, 在任意输入信号下都不违反assert(). 对于组合逻辑电路, 我们只需要让BMC在1周期内求解即可.

此外, 上述代码还传入了一个BtormcEngineAnnotation的参数, 表示调用模型检测器BtorMC在新窗口中打开. BtorMC基于一个不同于Z3的SMT求解器Boolector在新窗口中打开, 其基本原理与Z3类似, 但根据实测情况, 其求解效率通常Z3的数倍. 在运行上述测试之前, 你还需要获得BtorMC工具. 具体地, 你需要从这个链接在新窗口中打开下载相应的工具. 解压缩后, 将path-to-oss-cad-suite/bin加入到环境变量PATH中, 即可调用BtorMC.

完成上述配置后, 通过mill -i __.test运行测试, 输出信息如下:

Assertion failed
    at SubTest.scala:16 assert(io.c === ref)
- should pass *** FAILED ***
  chiseltest.formal.FailedBoundedCheckException: [Sub] found an assertion violation 0 steps after reset!
  at chiseltest.formal.FailedBoundedCheckException$.apply(Formal.scala:26)
  at chiseltest.formal.backends.Maltese$.bmc(Maltese.scala:92)
  at chiseltest.formal.Formal$.executeOp(Formal.scala:81)
  at chiseltest.formal.Formal$.$anonfun$verify$2(Formal.scala:61)
  at chiseltest.formal.Formal$.$anonfun$verify$2$adapted(Formal.scala:61)
  at scala.collection.immutable.List.foreach(List.scala:333)
  at chiseltest.formal.Formal$.verify(Formal.scala:61)
  at chiseltest.formal.Formal.verify(Formal.scala:34)
  at chiseltest.formal.Formal.verify$(Formal.scala:32)
  at FormalTest.verify(SubTest.scala:19)
  ...

上述信息说明BMC找到了一个在复位后第0个周期就违反assert()的测试用例. 进一步地, 开发者可以通过波形文件test_and_run/Test_should_pass/Sub.vcd辅助调试. 修正Sub模块中的错误后, 重新运行上述测试后将不再输出错误信息, 表示BMC找不到反例, 也即证明了代码的正确性.

基于Verilog的形式化验证流程

chiseltest的形式化验证流程是将FIRRTL代码转换成能被BMC识别的语言, 不涉及Verilog, 因此上述流程不支持基于Verilog开发的项目. 如果你使用Verilog进行开发, 可以使用基于Yosys的形式化验证流程, 其中SymbiYosys在新窗口中打开是这一流程的前端工具.

下面给出一个对Verilog模块进行形式化验证的例子:

// Sub.sv
`define FORMAL

module Sub(
  input [3:0] a,
  input [3:0] b,
  output [3:0] c
);

  assign c = a + ~b + (a == 4'd2 ? 1'b0 : 1'b1);

`ifdef FORMAL
  always @(*) begin
    c_assert: assert(c == a - b);
  end
`endif  // FORMAL

endmodule

上述例子的Sub模块通过"取反加1"实现了补码减法的功能. 为了验证Sub模块实现的正确性, 代码将"取反加1"的计算结果与通过减法运算符得到的结果进行对比, 我们预期assert()应该对任意输入都成立. 为了展示形式化验证的效果, 我们在Sub模块的实现中注入了一个bug: 在a为2时不进行"加1"操作, 此时补码减法的结果是错误的.

编写上述Sub.sv文件后, 你还需要编写SymbiYosys的配置文件*.sby, 这个文件一般由以下几个部分组成:

task: 可选项, 用于指定所需执行的任务
options: 必须项, 用于将代码中的assert, cover等语句和模型相对应
engines: 必须项, 用于指定求解的模型
script: 必须项, 包含测试需要的Yosys脚本
files: 必须项, 用于指定测试的文件

以下是配置文件Sub.sby的示例:

[tasks]
basic bmc
basic: default

[options]
bmc:
mode bmc
depth 1

[engines]
smtbmc

[script]
read -formal Sub.sv
prep -top Sub

[files]
Sub.sv

上述配置中的depth选项即为BMC的界, 用来指定需要证明的周期数. 例如, depth 4表示让BMC尝试证明被测模块在复位之后的4个周期内, 在任意输入信号下都不违反assert(). 对于组合逻辑电路, 我们只需要让BMC在1周期内求解即可.

在进行形式化验证之前, 你需要从这个链接在新窗口中打开下载相应的工具. 解压缩后, 执行命令行path-to-oss-cad-suite/bin/sby -f Sub.sby进行形式化验证, 输出信息如下:

SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  Checking assumptions in step 0..
SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  Checking assertions in step 0..
SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  BMC failed!
SBY 16:52:19 [Sub_basic] engine_0: ##   0:00:00  Assert failed in Sub: c_assert
SBY 16:52:19 [Sub_basic] engine_0: Status returned by engine: FAIL
SBY 16:52:19 [Sub_basic] summary: Elapsed clock time [H:MM:SS (secs)]: 0:00:00 (0)
SBY 16:52:19 [Sub_basic] summary: Elapsed process time [H:MM:SS (secs)]: 0:00:00 (0)
SBY 16:52:19 [Sub_basic] summary: engine_0 (smtbmc) returned FAIL
SBY 16:52:19 [Sub_basic] summary: counterexample trace: Sub_basic/engine_0/trace.vcd
SBY 16:52:19 [Sub_basic] summary:   failed assertion Sub.c_assert at Sub.sv:11.9-11.37 in step 0
SBY 16:52:19 [Sub_basic] DONE (FAIL, rc=2)
SBY 16:52:19 The following tasks failed: ['basic']

上述信息说明BMC找到了一个在复位后第0个周期就违反assert()的测试用例. 进一步地, 开发者可以通过波形文件Sub_basic/engine_0/trace.vcd辅助调试. 修正Sub模块中的错误后, 重新运行上述命令后将输出成功信息, 表示BMC找不到反例, 也即证明了代码的正确性.

通过形式化验证测试icache

我们的目标是通过形式化验证的方式来证明icache的正确性, 因此首先我们需要设计相应的REF, 并确定验证条件. 由于cache属于提升访存效率的技术, 它不应该影响访存结果的正确性, 也即, 无论是否有cache, 访存请求的行为应当一致. 因此, 我们可以将一个最简单的访存系统作为REF, 它接收来自CPU的访存请求, 然后直接访问内存; 与之相对的DUT, 则是让访存请求经过cache. 对于验证条件, 我们只要检查读请求返回的结果是否一致即可.

根据上文的分析, 我们很容易编写出验证顶层模块的伪代码. 这里我们用Chisel作为伪代码, 如果你使用Verilog开发, 你仍然可以借鉴相关思路来编写验证顶层模块.

class CacheTest extends Module {
  val io = IO(new Bundle {
    val req = new ...
    val block = Input(Bool())
  })

  val memSize = 128  // byte
  val mem = Mem(memSize / 4, UInt(32.W))
  val dut = Module(new Cache)

  dut.io.req <> io.req

  val dutData = dut.io.rdata
  val refRData = mem(io.req.addr)
  when (dut.io.resp.valid) {
    assert(dutData === refData)
  }
}

上述伪代码只给出了大致的框架, 你需要根据你的具体实现来补充部分细节:

屏蔽写操作, 你可以将写使能相关的信号置为0
让cache缺失时从mem中读出数据, 由于测试对象不产生写操作, 因此DUT和REF可以使用相同的存储器
由于REF直接从mem中读出数据, 没有任何延迟, 而DUT从cache中读出数据时需要经历若干周期, 因此需要对assert()的时机进行同步: REF读出数据后, 需要等待DUT返回读结果后才能进行检查, 显然, 这很容易通过状态机来实现
由于形式化验证工具会遍历每个周期的所有输入情况, 因此输入信号每个周期都会变化, 你可能需要借助寄存器暂存一些结果
借助"形式化验证工具会遍历每个周期的所有输入情况"的特性, 我们可以在测试的顶层定义一些block信号, 用于测试AXI相关的代码能否在随机延迟的场景下工作, 例如dut.io.axi.ar.ready := arready_ok & ~block1, dut.io.axi.r.valid := rvalid_ok & ~block2

通过形式化验证测试icache的实现

尽管这不是必须的, 我们还是强烈建议你尝试这一现代的测试验证方法, 体会"使用正确的工具解决问题"带来的爽感. 关于BMC的界(BoundedCheck()或depth), 你可以挑选一个合适的参数, 使cache能在形式化验证工具证明的周期内处理3~4个请求, 从而测试cache能否正确处理任意连续的请求.

形式化验证看上去全是好处, 但其实形式化验证有一个致命的缺点, 就是状态空间爆炸问题. 随着设计规模的增长和界的上升, 求解器需要遍历的空间也越大. 事实上, 一阶逻辑语言在理论上是不可判定的; 即使是可判定的子集, 在算法复杂度的意义上通常也是NP-Hard问题. 这意味着, 求解器的运行时间很可能随设计规模呈指数增长. 因此, 形式化验证一般在单元测试中使用.

缓存的优化

由于缓存技术主要用于提升访存效率, 因此很自然地, 我们应该通过访存相关的指标来评价缓存的性能表现. 通常通过AMAT(Average Memory Access Time)来评估缓存的性能表现, 假设缓存的命中率为p:

AMAT = p * access_time + (1 - p) * (access_time + miss_penalty)
     = access_time + (1 - p) * miss_penalty

其中access_time为cache的访问时间, 即从cache接收访存请求到得出命中结果所需的时间, miss_penalty为cache缺失时的代价, 此处即访问DRAM的时间.

这个等式给优化缓存的性能表现提供了指导方向: 减少访问时间access_time, 提升命中率p, 或者减少缺失代价miss_penalty. 在目前的NPC中, 访问时间在架构设计上能优化的空间不多, 更多是受具体实现的影响, 如周期数和关键路径. 因此, 后续我们重点讨论命中率和缺失代价的优化.

统计AMAT

在NPC中添加合适的性能计数器, 统计icache的AMAT.

优化命中率

要提升命中率, 也就是要降低缺失率, 为此, 我们需要先了解cache的缺失有哪些原因.

cache缺失的3C模型

计算机科学家Mark Hill在新窗口中打开在其1987年的博士论文在新窗口中打开中提出3C模型, 刻画了cache缺失的3种类型:

Compulsory miss, 强制缺失, 定义为在一个容量无限大的cache中所发生的缺失, 表现为在第一次访问一个数据块时所发生的缺失
Capacity miss, 容量缺失, 定义为不扩大cache容量就无法消除的缺失, 表现为因cache无法容纳所有所需访问的数据而发生的缺失
Conflict miss, 冲突缺失, 定义为除上述两种原因外引起的缺失, 表现为因多个cache块之间相互替换而发生的缺失

有了3C模型, 我们就可以为每种类型的缺失提出针对性的方案, 来降低相应的缺失率了.

降低Compulsory miss

为了降低Compulsory miss, 原则上需要在访问一个数据块之前就将其读入cache中, 但上述cache工作流程并不支持这一功能, 因此需要添加新的机制才能实现, 这种机制称为预取(prefetch). 不过从理论上来说, Compulsory miss只指代首次访问一个数据块时发生的缺失, 在访存次数较多的场合, Compulsory miss的占比并不高, 因此在这里我们暂不深入讨论如何减少Compulsory miss, 感兴趣的同学可以搜索并阅读预取的相关资料.

降低Capacity miss

为了降低Capacity miss, 根据其定义, 只能扩大cache容量, 从而更好地利用时间局部性. 但cache容量并非越大越好, 一方面, cache容量越大, 意味着流片面积越大, 从而增加了流片成本; 另一方面, 存储阵列越大, 意味着其访问延迟越高, 从而增加了cache的访问时间, 降低cache的性能表现. 因此, 在实际的项目中, 一味增大cache容量并不是一个合理的方案, 需要综合各方因素后做出权衡.

降低Conflict miss

为了降低Conflict miss, 需要考虑如何减少多个cache块之间相互替换的情况. 上文介绍了cache中直接映射的组织方式, 每个数据块只能读入到固定index的cache块中, 如果多个数据块的index相同, 那么后读入的数据块将会替换先读入的数据块. 因此, 一个减少替换情况的想法就是采用新的cache块组织方式, 允许数据块读入到多个cache块中.

一种极端的情况是, 每个数据块都可以存放到任意cache块中, 这种组织方式称为全相联(fully-associative). 而具体存放到哪一个cache块中, 首先当然是存放到无效的cache块中; 若所有的cache块均有效, 则由替换算法来决定. 不同的替换算法会影响cache访问的命中率, 一般来说, 替换算法需要选择一个将来最不可能被访问的cache块. 对于给定的访存序列, 我们可以设计出一套最优的替换算法, 使得Conflict miss最少; 但在实际情况中, 我们无法提前得知将来的访存序列, 因此替换算法的设计变成一个"根据过去预测未来"的问题, 即需要根据过去每个cache块的访问情况, 预测出一个将来最不可能被访问的cache块. 常见的替换算法有如下几种:

FIFO, 先进先出, 替换最旧读入的cache块
LRU, 最近最少用, 替换在最近一段时间内访问次数最少的cache块
random, 随机替换

配合合适的替换算法, 全相联组织方式能以更大的概率替换掉一个将来一段时间内最不可能被访问的cache块, 从而能够在最大程度上降低Conflict miss. 但由于全相联组织方式可以将数据块存放到任意cache块中, 这需要付出两点代价. 首先, 访存地址无需划分出index部分, 故除了offset部分外, 剩余的均为tag部分. 因此, 我们需要在存储阵列中花费更多的存储开销来存储cache块的tag部分.

 31                m m-1    0
+-------------------+--------+
|        tag        | offset |
+-------------------+--------+

其次, 判断命中时, 需要与所有cache块检查其tag是否匹配, 这需要使用很多比较器, 从而增加面积开销. 由于这些代价, 全相联组织方式一般只在cache块数量较少的场景下使用.

组相联(set-associative)是直接映射和全相联的折中, 其思想是给所有cache块分组, 在组间通过直接映射方式选出一个组, 然后在组内通过全相联方式选出一个cache块, 也即, 每个数据块都可以存放到组号为tag % 组数中的任意一个cache块. 如果每个组中有w个cache块, 则称为w路组相联(w-way set-associative).

   +----------------------+-------------------------+
   |                      |                         |
+--+--+-------+--------+  |                         |
| tag | index | offset |  |                         |
+-----+---+---+--------+  |                         |
          |               |                         |
+---------+               |                         |
|                         |                         |
|  V   tag      data      |   V   tag      data     |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
| +-+-------+----------+  |  +-+-------+----------+ |
+>+-+-------+----------+  |  +-+-------+----------+ |
  +++-----+-+----------+  |  +++-----+-+----------+ |
   |      |               |   |      |              |
 +-v-+  +-v--+            | +-v-+  +-v--+           |
 | & |<-+ == |<-----------+ | & |<-+ == |<----------+
 +-+-+  +----+              +-+-+  +----+
   |                          |
   +------------+--------------+
                |
                v
             hit way

在组相联组织方式中, 一个访存地址可以划分成以下3部分: tag, index, offset, 其中index部分作为组索引, 故其位宽为n = log2(cache块总数/w).

 31    m+n m+n-1   m m-1    0
+---------+---------+--------+
|   tag   |  index  | offset |
+---------+---------+--------+

判断命中时, 只需要与组内所有cache块检查其tag是否匹配即可, 在w不大时, 比较器的面积开销是可以接受的.

实际上, 全相联和直接映射都可以视为组相联的特例: w=1时即为直接映射, w=cache块总数时即为全相联. 现代CPU通常采用8或16路组相联.

块大小的选择

块大小是一个特殊的参数. 如果cache块较大, 一方面能够降低tag的存储开销, 另一方面则能够在cache块中存放更多的相邻数据, 从而能更好地捕捉到程序的空间局部性, 降低Conflict miss. 但为了读出更多的相邻数据, cache的缺失代价也会随之上升; 同时, 对于一定的cache容量, 更大的cache块也意味着cache块的数量更少, 如果程序的空间局部性不明显, 则意味着需要更多更小的cache块, 此时较大的cache块反而会增加Conflict miss.

// 空间局部性较差的程序
// 2个大小为4的cache块
               1111       2222        cache
|--------------oooo-------oooo-----|  memory, `o`为程序访问的热点数据

// 1个大小为8的cache块
               11111111               cache
|--------------oooo-------oooo-----|  memory



// 空间局部性较好的程序
// 2个大小为4的cache块
               11112222               cache
|--------------oooooooo------------|  memory

// 1个大小为8的cache块
               11111111               cache
|--------------oooooooo------------|  memory

设计空间探索

上文提到了非常多和cache相关的参数, 如何选择一组合适的参数, 使得在给定的资源下达到较好的表现, 则属于cache的设计空间探索(Design Space Exploration, DSE)问题. 目前, 我们关心的表现包括IPC, 主频, 面积, 其中, 主频和面积可以通过yosys-sta项目快速评估, 而对于IPC, 通常需要在校准过访存延迟的ysyxSoC环境中运行完整的程序后才能获得.

但不同参数之间的组合情况太多了, 如果针对每一种参数组合, 都要花费小时级别的时间才能得到其IPC, 设计空间探索的效率将会十分低下. 上文提到, 数据精度和仿真效率是权衡关系, 因此为了提升设计空间探索的效率, 一种方式是牺牲IPC的统计精度, 通过较低的开销来统计一个能体现IPC变化趋势的指标.

当我们调整cache的各种参数时, 直接影响的是AMAT, 因此我们可以认为CPU中其他部分的执行开销保持不变. 而根据AMAT的定义, 调整上述参数并不影响cache的访问时间, 故可以将其看作一个常数. 因此我们真正需要关注的, 只有程序在发生cache缺失时需要等待的总时间, 我们将其称为总缺失时间(Total Miss Time, TMT). 事实上, TMT可以代表IPC的变化趋势: TMT越小, 每条指令访存所需的周期数也越小, 从而IPC越大.

你之前通过性能计数器统计过AMAT时, 应该也统计过TMT了, 但这需要在ysyxSoC中运行完成的程序. 为了低开销地统计TMT, 我们从缺失次数 * 缺失代价这个角度, 考虑如何低开销地统计缺失次数和缺失代价.

对于缺失次数的统计, 我们有如下观察:

对于给定的程序, cache的访问次数是固定的. 只要获得程序运行的itrace, 将其输入到icache中, 就可以模拟icache工作的过程, 从而统计icache的缺失次数, 因此不必仿真整个ysyxSoC, 甚至连NPC都不需要.
NPC执行程序时, 需要通过当前指令的执行结果来得知下一条需要执行的指令. 但itrace已经包含了完整的指令流, 因此在统计TMT时, 我们只需要指令流的PC值, 而不需要指令本身.
icache的数据部分是用来作为指令回复给NPC的IFU的, 但由于统计TMT并不需要NPC, 因此icache的数据部分也不需要, 只需要保留元数据部分即可. 事实上, 对于给定的访存地址序列, cache的缺失次数与访存内容无关, 通过维护元数据即可统计出正确的缺失次数.

因此, 为了统计icache的缺失次数, 我们完全没有必要每次都把程序完整运行一遍. 我们真正需要的是一个简单的cache功能模拟器, 我们称它为cachesim. cachesim接收指令流的PC序列(简化版的itrace), 通过维护元数据来统计这一PC序列的缺失次数. 至于指令流的PC序列, 我们可以通过NEMU来快速生成.

而对于缺失代价, 由于cachesim不包含ysyxSoC中的访存细节, 因此原则上我们也无法准确地获取这个值. 但根据上文的讨论, 只有块大小这个参数会影响缺失代价, 因此我们可以在ysyxSoC中统计出一个平均缺失代价, 并将其作为一个常数来估算TMT.

实现cachesim

根据上文的介绍, 实现一个简单的cache模拟器.

借助cachesim, 我们可以来对icache进行性能测试的DiffTest. 具体地, 我们可以把cachesim作为性能测试的REF, 在NPC中运行一个程序得到的性能计数器结果, 应该与cachesim执行相应PC序列统计得到的缺失次数等数据完全一致. 如果不一致, 则可能是RTL实现有性能bug, 这种性能bug是无法通过和NEMU进行功能测试的DiffTest或形式化验证发现的. 例如, 即使icache一直缺失, 程序仍然可以在NPC上正确运行. 当然, 也有可能是作为REF的cachesim有bug. 但不管怎样, 能有REF作为对比, 总归是不会吃亏的.

不过为了得到一致的itrace, 你可能需要对NEMU做一些改动, 使其能运行riscv32e-ysyxsoc的镜像文件.

压缩trace

如果你得到的itrace非常大, 可以考虑从以下方面进行压缩:

采用二进制方式存储itrace, 而不是文本方式
大部分时候指令是顺序执行的, 对于一段连续的PC序列, 我们可以只记录第一个PC和连续执行的指令数量
通过bzip2相关工具对生成的itrace文件进一步压缩, 然后在cachesim的代码中通过popen("bzcat 压缩后的文件路径", "r")得到一个可读的文件指针. 关于popen()的使用方式, 请RTFM

使用cachesim进行设计空间探索

有了cachesim, 我们就可以快速评估不同cache参数组合的预期收益了. 对于一个参数组合, cachesim的评估效率比ysyxSoC能快几千倍甚至上万倍.

除此之外, 我们还能利用多核同时评估多个参数组合: 具体地, 首先让cachesim通过命令行方式传入各种cache参数, 然后通过脚本启动多个cachesim, 分别传入不同的参数组合即可. 通过这种方式, 我们可以在数分钟内获得几十组参数组合的评估结果, 从而帮助我们快速选择出合适的参数组合.

尝试打通这一快速评估的流程, 并评估若干组参数组合. 不过, 我们还没有对缺失代价进行优化, 从而评估出更合理的TMT; 另外, 我们也还没有给出面积大小的限制. 这些因素都会影响最终的决策, 因此目前你不必做出最终的设计选择.

优化缺失代价

如果cache发生缺失, 将要到下一层存储层次中访问数据, 因此缺失代价就是下一层存储层次的访问时间. 降低缺失代价的技术有很多, 目前我们先讨论其中一种: 总线传输的突发访问. 如果cache块的大小和总线的数据位宽相同, 那么只需要一次总线传输事务就可以完成数据块的访问, 此时优化的空间并不大. 但对于更大的cache块, 原则上需要多次总线传输事务才能完成数据块的访问, 其中就存在优化的机会.

块大小和缺失代价

对当前的cache设计来说, 下一层存储层次就是SDRAM. 为了进一步分析, 我们先给SDRAM的访问时间建立如下的简单模型, 把SDRAM的访问时间分成4段, 因此对于一个独立的总线传输事务来说, 开销是a+b+c+d. 假设总线的数据位宽是4字节, cache的块大小是16字节. 若采用4个独立的总线传输事务, 则所需开销是4(a+b+c+d).

+------------------------ arvalid有效
|   +-------------------- AR通道握手, 接收读请求
|   |       +------------ 状态机转移到READ状态, 并向SDRAM颗粒发送READ命令
|   |       |     +------ SDRAM颗粒返回读数据
|   |       |     |   +-- R通道握手, 返回读数据
V a V   b   V  c  V d V
|---|-------|-----|---|

支持更大的块大小

修改cachesim中的块大小, 使其为总线数据位宽的4倍, 并通过独立的总线传输事务方式来估算缺失代价.

实现后, 与之前的评估结果进行对比, 并尝试分析原因.

支持更大的块大小(2)

修改icache的实现, 使其支持更大的块大小. 实现时, 建议将块大小的参数实现成可配置的, 以便于后续的评估工作.

总线的突发传输

与SDRAM颗粒类似, AXI总线也支持"突发传输"(burst transfer), 即在一次总线传输事务中包含多次连续的数据传输, 一次数据传输称为一个"节拍"(beat). 在AXI总线协议中, 需要通过AR通道的arbusrt信号指示此次传输是否采用突发传输, 若是, 则还需要通过arlen信号指示此次突发传输的节拍数量.

当然, 光有总线协议的支持还不够, 还需要AXI的master端发起突发传输事务, 以及slave端支持突发传输事务的处理. icache作为master端, 我们将发起突发传输事务作为实验内容留给大家. 另一方面, ysyxSoC提供的SDRAM控制器确实支持突发传输事务的处理, 可以将上述4次总线传输包含在一次总线事务中, 从而有效降低完整读出一个数据块的开销: 首先, 通过突发传输, AR通道只需要进行一次握手, 与上文的方案相比, 开销可节省3a; 其次, SDRAM控制器可以将一次突发传输事务拆分成多个发往SDRAM颗粒的READ命令, 当SDRAM颗粒返回一次读数据时, 如果还有地址连续的READ命令, SDRAM控制器的状态机则直接转移到READ状态继续发送READ命令, 与上文的方案相比, 开销可节省3b; 最后, SDRAM控制器对R通道的回复可与下一次READ命令的发送同时进行, 从而将R通道握手的开销隐藏起来, 与上文的方案相比, 开销可节省3d.

  a     b      c    d
|---|-------|-----|---| <-------------------- 第1个节拍
                  |-----|---| <-------------- 第2个节拍
                        |-----|---| <-------- 第3个节拍
                              |-----|---| <-- 第4个节拍

综上, 采用突发传输所需开销为a+b+4c+d, 和上文的方案相比, 可以节省3(a+b+d)的开销. 推广到一般情况, 若cache块的大小是总线数据位宽的n倍, 则采用突发传输可以节省n(a+b+d)的开销. 虽然表面上看a, b, d都不大, 但别忘了这是SDRAM控制器视角的开销, 校准访存延迟后, 对CPU来说有可能节省数十甚至上百周期的开销.

突发传输的实现

可以看到, 要获得突发传输的收益, 首先需要让cache使用更大的块. 但根据上文的讨论, 更大的cache块也可能会增加Conflict miss, 从而带来负收益, 具体取决于程序的空间局部性. 至于何者更优, 就要通过benchmark进行评估了. 要在cachesim中评估TMT, 我们还需要获得采用突发传输时的缺失代价. 为此, 我们需要先在ysyxSoC环境中实现AXI的突发传输. 但这一改动涉及较多细节, 因此我们分多个步骤来进行.

之前我们为了方便测试, 先接入了APB接口的SDRAM控制器. 但APB协议不支持突发传输, 要采用突发传输, 首先我们需要将SDRAM控制器更换成AXI接口的版本.

切换到32位ysyxSoC

SoC团队已经提供了32位的流片SoC, 我们也在2024/07/26 13:00:00把ysyxSoC修改成32位, 以帮助大家在接入流片SoC之前在本地环境中进行测试. 如果你在上述时间之前获取ysyxSoC的代码, 请参考本页面最开始处的内容进行操作.

集成AXI接口的SDRAM控制器

你需要在ysyxSoC/src/SoC.scala的Config对象中将sdramUseAXI变量修改为true. 修改后重新生成ysySoCFull.v, 并尝试运行一些测试程序.

让icache支持突发传输

修改icache的实现, 使其采用突发传输方式访问SDRAM中的数据块.

实现正确后, 记录突发传输的波形, 并与未采用突发传输时的波形进行对比, 你应该能观察到, 采用突发传输确实能提升效率.

校准AXI接口SDRAM的的访存延迟

虽然目前突发传输方式已经可以工作, 但并未对相应的访存延迟进行校准, 得到的性能数据是不准确的. 和之前实现的APB延迟模块类似, 我们需要一个AXI延迟模块来校准相应的访存延迟.

由于AXI协议比APB协议复杂, AXI延迟模块的实现还需要额外考虑如下问题:

AXI的读写通道是独立的, 因此原则上需要为读事务和写事务分别设计用于控制延迟的计数器. 不过当前的NPC是多周期的, 不会同时发送读请求和写请求, 因此当前你也可以设计一套统一的计数器来进行控制. 但接下来实现流水线的时候, 你还是需要采用两套独立的计数器.
AXI有完整的握手信号, 等待握手也涉及到设备的状态, 因此这段时间也应该属于校准范围内, 也即, 应该将valid信号有效的时刻视为事务的开始.
AXI支持突发传输, 因此传输模式和APB不同.
- 以读事务为例, 突发传输可能包含多次数据的接收, 都需要分别分别校准. 假设一个AXI突发读事务从t0时刻开始, 设备端分别在t1, t2时刻返回数据, AXI延迟模块在t1', t2'时刻向上游返回数据, 则应有等式(t1 - t0) * r = t1' - t0和(t2 - t0) * r = t2' - t0.
- 写事务的突发传输包含多次数据的发送, 由于设备接收一次数据也需要至少花费一个周期, 这在CPU看来已经经过了r个周期, 因此也需要对数据的发送时刻进行校准. 不过目前我们还没有实现dcache, LSU不会发起突发写事务, 因此目前可暂不实现突发写事务的校准, 但对于单个写事务, 则仍需校准.

实现AXI延迟模块

按照上文的介绍, 在ysyxSoC中实现AXI延迟模块. 具体地, 如果你选择Verilog, 你需要在ysyxSoC/perip/amba/apb4_delayer.v中实现相应代码; 如果你选择Chisel, 你需要在ysyxSoC/src/amba/AXI4Delayer.scala的AXI4DelayerChisel模块中实现相应代码, 并将ysyxSoC/src/amba/AXI4Delayer.scala中的Module(new axi4_delayer)修改为实例化AXI4DelayerChisel模块.

为了简化实现, 目前你可以认为突发传输的节拍数量不会大于8. 实现后, 尝试取不同的r, 在波形中观察上述等式是否成立.

评估突发传输方式的性能表现

校准突发传输方式的访存延迟后, 运行microbench的train规模测试, 并与之前的记录结果进行对比.

快速评估缺失代价

根据上文的讨论, 当前icache的缺失代价只与块大小和总线的传输方式相关, 与cache的其他参数无关. 因此, 我们可以提前评估各种块大小和总线传输方式组合下的缺失代价, 将来直接代入这个缺失代价, 即可计算出TMT, 从而估算出不同cache参数组合的预期收益. 但根据上文的分析, 采用突发传输方式的性能表现必定优于独立传输方式, 所以实际上我们只需要提前评估各种块大小在采用突发传输方式时的缺失代价即可.

至于如何提前评估缺失代价, 又有两种方法:

建模. 根据SDRAM控制器状态机的工作流程, 拟合出SDRAM访问时间的计算公式. 代入块大小, 即可计算出相应的缺失代价. 这种方式比较直接, 但建模的精确度是一个挑战, 例如SDRAM的row buffer和刷新操作也会影响SDRAM的访问时间, 但我们很难刻画这些因素在一次SDRAM访问中带来的开销.
统计. 通过适当的性能计数器, 计算出icache缺失时访问SDRAM的TMT, 从而计算出平均缺失代价. 作为一种统计方法, 它可以通过采样后平均的方式, 将SDRAM的row buffer和刷新操作等难以建模的因素考虑进来. 但row buffer的本质也是一种cache, 其性能表现也会受到程序局部性的影响, 因此测试程序还需要具备代表性: 直接运行microbench的train规模测试的代表性是最好的, 虽然需要花费较多时间, 但只需要运行一次, 即可统计出平均缺失代价; test规模测试与train规模测试的行为不完全相同, 但也有一定的代表性, 从而可以快速统计出平均缺失代价; 但hello程序的代表性就比较弱了, 用其统计出的平均缺失代价进行估算, 可能会带来较大的误差.

在实际的项目中, 考虑到项目的复杂性, 一般很少采用建模方式, 因而此处也推荐大家采用统计方式来提前评估缺失代价.

快速评估缺失代价

根据上述内容实现缺失代价的快速评估. 你已经可以通过cachesim计算出缺失次数, 后续你将使用这些缺失代价来估算不同cache参数组合的预期收益.

程序的内存布局

程序的内存布局有时换也会明显影响cache的性能表现. 以icache为例, 当icache的块大小超过4字节时, 有时候程序中的一些热点循环可能没有对齐到cache块的边界, 使得热点循环中的指令多占用了一些cache块. 例如, 某程序的热点循环位于地址[0x1c, 0x34), 假设某icache的块大小是16字节, 将这个热点循环的指令全部读入icache, 需要占用3个cache块.

         [0x1c, 0x34)           + 0x4   =   [0x20, 0x38)
+------+------+------+------+      +------+------+------+------+
|      |      |      | 0x1c |      | 0x20 | 0x24 | 0x28 | 0x2c |
+------+------+------+------+      +------+------+------+------+
| 0x20 | 0x24 | 0x28 | 0x2c |      | 0x30 | 0x34 |      |      |
+------+------+------+------+      +------+------+------+------+
| 0x30 |      |      |      |
+------+------+------+------+

但如果我们在程序代码前填充一些空白字节, 就可以改变热点循环的位置, 从而使得热点循环的指令占用更少的cache块. 例如, 在上述例子中, 我们只需要在程序代码前填充4字节的空白内容, 就可以将热点循环的位置改变为[0x20, 0x38). 此时热点循环的指令只需要占用2个cache块, 节省出来的1个cache块可用于存放其他指令, 从而提升程序的整体性能表现.

优化程序的内存布局

尝试按照上文的方法, 在程序代码前填充若干空白字节. 具体地, 你可以通过修改代码, 或者修改链接脚本来实现这个功能. 实现后, 尝试评估填充的空白字节是否能优化程序的性能表现.

事实上, 上述例子的cache容量很小, 因此节省出来的1个cache块在整个cache中占比较高. 但现代处理器的cache的容量相对充足, 节省出来的1个cache块可能不会给程序的性能带来明显的提升. 不过我们想说的是, 程序的优化也是利用局部性原理的一个重要方向, 有的程序在优化后甚至能提升数倍的性能.

在企业中, 对于目标场景中的关键应用程序, 工程师团队通常会采用各种方法来提升其性能表现; 如果企业有能力设计自己的处理器, 除了提升处理器的性能之外, 还会根据处理器的参数对编译器进行定制化. 和采用公共版本的编译器(如开源社区的gcc)编译出来的可执行文件相比, 采用定制化编译器编译出来的可执行文件能够在目标处理器上运行得更快. 特别地, SPEC CPU中定义了两种衡量标准base和peak在新窗口中打开, 其中peak标准允许不同的子项采用不同的编译优化选项来编译, 使得整个benchmark在目标平台上达到比base更优的性能. 如果希望在peak标准中获得更高的分数, 软件层次的优化是不可或缺的.

设计空间探索(2)

我们上面介绍了cache的很多参数, 甚至还包含程序的内存布局, 这些都会影响程序在处理器上运行的性能. 现在我们就可以来综合考虑这些参数, 选择一组性能表现较好的参数组合了. 当然, 设计空间探索还需要满足面积大小的约束.

面积大小的限制

你的NPC需要在yosys-sta项目默认提供的nangate45工艺下, 综合面积不超过25000(综合工具报告的面积数据默认单位为), 这也作为B阶段流片的面积限制. 考虑到后续任务还需要实现流水线, 因此我们推荐此时NPC的综合面积不超过23000.

这个面积算不上很大, 一方面, 采用这一面积限制有助于凸显其他参数在设计空间探索中的贡献, 否则你只需要一味提升cache容量, 就可以获得很好的性能表现, 其他参数对性能提升的影响将难以得到体现; 另一方面, 项目组预期较多同学会基于B阶段流片, 更小的面积有助于项目组节省流片成本.

目前你不必严格满足上述面积限制, 如果超过的部分不到5%, 你可以选择在完成流水线后再统一进行优化; 但如果当前的综合面积已远超上述限制, 你可能需要对你的设计进行较大调整, 我们建议你马上开展一些面积相关的优化工作.

关于流片成本, 我们可以做一些简单但不太严谨的估算. 假设某晶圆厂提供nangate45工艺的流片服务, 每个block的尺寸是2mm X 3mm, 价格是50万RMB, 则每的价格为500000 / (2 * 3 * 1000000) = 0.0834元. 通常来说, 连接标准单元的线网也需要占用一定的面积, 同时为了让走线不至于过度拥塞, 标准单元之间也会多留一些空隙. 因此, 最终的芯片面积通常要大于综合面积, 根据经验, 综合面积一般是最终芯片面积的70%. 按上述估算方式, 一个综合面积为25000的设计, 最终需要花费的价格是25000 / 0.7 * 0.0834 = 2978元.

上述估算给大家带来的最大启发就是, 给CPU添加功能特性, 并不是免费的. 这一点与面向FPGA的设计有很大区别: 在一些以FPGA作为目标平台的比赛中, 参赛者通常会尽最大可能将FPGA上的资源转化成CPU的性能, 这一过程中不会产生任何经济上的成本.

但真实的流片并不是这样. 你可以将B阶段的目标看成是设计一款低成本的嵌入式处理器(rv32e就是面向嵌入式场景的基础指令集): 假设你是某嵌入式CPU厂商的架构师, 你需要在面积预算有限的情况下想办法提升处理器的性能. 如果面积超出预期, 芯片成本就会上升, 在市场上的竞争力也会有所下降. 在这样的条件下, 你需要估算添加某个功能特性的性价比: 假设某功能特性可以带来10%的性能提升, 它是否值得你为它多支付500元?

icache的设计空间探索

按照上述介绍, 探索icache的设计空间, 并确定一个设计方案, 使其在给定约束下达到较好的性能表现. 确定方案后, 通过RTL实现它, 并评估其在ysyxSoC中的性能表现.

一些优化面积的思路

如果你的评估面积大幅超过上述要求, 你大概率需要对你的设计进行优化. 面积的优化并没有什么诀窍, 但整体上来说可以从以下方向考虑:

优化逻辑开销: 考虑哪些逻辑功能是冗余的, 可以和其他现有逻辑合并
优化存储开销: 考虑哪些存储单元是冗余的
逻辑开销和存储开销之间的转换: 有时候与其存储一个信号, 不如重新将它计算一遍, 不过这可能还会影响关键路径, 需要具体情况具体分析

对大家来说, 上述面积限制的要求大概率不是随手写写就能达到, 但也并不是不可能达到. yzh的参考设计在添加icache后面积为22730, 同时频率可以达到1081MHz, 运行microbench显示的Total time为4.49s. 我们设置上述面积限制, 一方面是锻炼大家如何优化自己的设计: 如果你是初学者, 你总得需要一个契机来接触这方面的工作, 在不断的试错当中建立每一行RTL代码和面积开销之间的关联认识.

另一方面也是为了让大家再次体会到体系结构设计的目标: 性能和面积是相互制约的, 如果你觉得你的设计很难优化, 最简单的方法就是减少cache的容量, 但你需要付出性能的代价; 如果你想兼顾面积和性能, 你就需要尽可能节省不必要的面积开销, 然后规划这些面积用来做什么更有利于提升性能.

不要细抠综合的选项

有的同学试图通过探索综合器的各种选项来提升综合的质量. 尽管我们鼓励大家去了解综合的细节, 但需要说明的是, 通过改动代码提升综合质量, 和通过调参提升综合质量, 是两回事. 事实上, 后者一般只在追求极致优化目标的时候进行, 但前提也要先努力将前者做到最好. 更本质地, 前者才属于体系结构设计能力训练的内容, 而后者不是.

评估dcache的性价比

你已经在上文中估算了dcache在理想情况下的性能收益, 在这里我们继续估算这个dcache的性价比. 假设这个dcache的面积大小和icache一样, 其成本是多少元?

虽然你还没有设计dcache, 但因为dcache需要支持写操作, 其设计必定比icache复杂, 故占用的面积也应该大于同等容量的icache. 因此, 在这些条件估算出来的dcache性价比是高度乐观的, 如果考虑dcache的真实性能收益和实际面积, 设计dcache的性价比只会更低.

另一个考虑的方向是, 如果把dcache的面积用于扩大icache的容量, 能带来多少性能提升?

真正的体系结构设计

尽管上述的icache设计空间探索任务与真实处理器中的设计空间探索相比简化了很多, 但对大部分同学来说也算是第一次接触到真正的处理器体系结构设计了. 更多地, 这也很可能是大部分同学第一次接触到一个模块设计的全流程, 从需求分析, 结构设计, 逻辑设计, 到功能验证, 性能验证, 性能优化, 最后到电路层次的面积评估, 时序分析. 其中, 逻辑设计就是大家常说的RTL编码.

这个任务再次让大家看到, 体系结构设计不等于RTL编码. 体系结构设计的工作是, 在满足约束条件的设计空间中寻找一组表现较好的设计参数. 但通常设计空间非常大, 要完整评估其中一组设计参数的性能表现, 也需要花费不少时间. 因此对体系结构设计工作来说, 如何能快速评估不同设计参数的性能表现, 是一个至关重要的问题.

因此, 模拟器是体系结构设计的重要工具. 通过模拟器, 我们不必仿真电路级别的行为(不跑verilator, 而是跑cachesim), 同时只需要模拟一些必要的模块(不模拟cache的数据, 只需要模拟cache的元数据), 此外也不必由处理器驱动(不跑完整的程序, 而是回放相应的itrace). 正是这些不同, 使得模拟器的运行效率比RTL仿真有数量级的提升, 从而可以快速评估不同设计参数的预期性能表现, 帮助我们快速排除明显不合适的设计参数.

根据香山团队的经验, 在verilator上跑一轮程序需要花费1周的时间, 但在全系统模拟器gem5在新窗口中打开中跑相同的程序, 只需要2小时. 这意味着, 在RTL仿真环境中评估一组设计参数的时间, 可以用模拟器探索84组不同设计参数的效果.

对于体系结构研究来说, 模拟器也是很常见的平台. 体系结构顶会ISCA已经多次举行基于ChampSim在新窗口中打开模拟器的大赛, 包括cache替换算法大赛在新窗口中打开和cache预取算法大赛在新窗口中打开等. 研究人员都是在模拟器中评估各种算法的表现, 从而快速调整算法的整体实现及其细致参数. 尽管一个合格的算法还需要经过RTL层次的实现和验证, 但如果一开始选择在RTL层次上探索各种算法, 效率是十分低下的.

所以, 当你真正明白体系结构设计 != RTL编码的时候, 你才算是真正入门了体系结构设计这个领域.

缓存一致性

当store指令修改数据块的内容后, 按照程序的语义, 后续应从相应地址中读出新数据, 否则程序的执行将会出错. 但内存中的数据可能因为cache机制而存在多个副本, 如何保证从每个副本中都能读出新数据, 称为缓存一致性(cache coherence)问题.

在计算机系统中, 小到处理器中的cache, 大到分布式系统和互联网, 只要存在数据副本, 它们之间就会存在一致性问题. 在NPC添加icache后, 我们可以通过以下的smc.c来复现一个一致性问题:

// smc.c
int main() {
  asm volatile("li a0, 0;"
               "li a1, UART_TX;"     // change UART_TX to the correct address
               "li t1, 0x41;"        // 0x41 = 'A'
               "la a2, again;"
               "li t2, 0x00008067;"  // 0x00008067 = ret
               "again:"
               "sb t1, (a1);"
               "sw t2, (a2);"
               "j again;"
              );
  return 0;
}

上述程序首先对一些寄存器赋初值, 然后在标号again处往串口写入一个字符A, 接着将again处的指令改写为ret, 最后跳转回again处重新执行. 按照程序的语义, 程序应该在输出一个字符A后, 通过被改写的ret指令从main()返回. 这种在运行过程中修改自己的代码称为"自修改代码"(Self Modified Code).

计算机发展史中的自修改代码

在过去内存地址空间非常紧张的时代, 经常会使用自修改代码来提升内存的利用率, 从而让程序在有限的内存中实现更多的功能. 例如, 1980年代的FC红白机只有64KB的地址空间在新窗口中打开, 其中卡带上的ROM占了32KB. 有一些卡带上还有8KB的RAM, 但如果卡带上没有RAM, 那程序就只能使用CPU内部集成的2KB RAM了. 为了利用如此有限的资源开发出精彩的游戏, 开发者使用了非常多的黑科技, 自修改代码就是其中一种方法.

随着存储器技术的发展, 内存容量已经不像过去那样捉襟见肘了, 加上自修改代码难以阅读和维护, 现代程序中已经很难看到自修改代码的踪影.

复现缓存一致性问题

将上述程序编译到AM并在NPC上运行, 你发现了什么问题? 尝试给出分析, 并结合波形验证你的想法.

如果你没有发现问题, 可以尝试增加icache的容量.

为了解决上述问题, 一种直接的方案是让系统中的所有副本时刻保持一致. 例如, 在每次执行store指令时, 都马上检查系统中是否存在其他副本, 若存在, 则对其进行更新或使其无效, 从而保证后续操作无论从何处访问, 都能直接读出新数据(采用更新方式), 或因缺失而从下一层存储层次中读出新数据(采用无效方式); x86指令集采用这种方案. 但显然, 这会提升CPU设计的复杂性. 特别地, 在一些高性能处理器中, store指令执行时, 其他部件也会同时访问系统中的各种cache, 如何在store指令完成所有副本的更新或无效之前避免其他部件访问到过时的数据, 是非常有挑战的.

另一种方案则更加宽松, 允许系统中的副本在某些时刻不一致, 但在程序访问这个数据块之前, 需要执行一条特殊的指令, 指示硬件对过时的副本进行处理. 通过这种方式, 程序的执行过程仍然能够访问到正确的数据, 结果仍然符合程序的语义. RISC-V指令集采用这种方案. RISC-V中有一条fence.i指令, 其语义是让在其之后的取指操作都能看到在其之前的store指令修改的数据. 在这里, fence.i指令就像一道屏障, 让在其之后的取指操作无法跨越屏障来读取那些被store指令修改之前的旧数据. 此外, 在RISC-V手册中有如下描述:

RISC-V does not guarantee that stores to instruction memory will be made
visible to instruction fetches on a RISC-V hart until that hart executes
a FENCE.I instruction.

也就是说, RISC-V允许icache中的副本在某些时刻与内存不一致, 这也符合上文的讨论. 关于fence.i的更多信息, 建议RTFM.

RISC-V只在指令集层次定义了fence.i的语义, 但具体如何在微结构层次中实现fence.i的功能, 则有多种不同的方案:

方案	执行store指令时	执行`fence.i`时	访问icache时
(1)	更新icache中的相应块	nop	命中
(2)	无效icache中的相应块	nop	缺失, 访问内存
(3)	-	冲刷整个icache	缺失, 访问内存

事实上, 实现方案(1)和(2)就是上文提到的"让系统中的所有副本时刻保持一致"的方案, 它是"允许系统中的副本在某些时刻不一致"的特殊情况: 由于在执行store指令时, 所有副本已保持一致, 故fence.i可实现成nop. 对于方案(3), 执行store指令时暂不对icache中的副本进行处理, 故这些副本会处于不一致的状态, 因此在执行fence.i时, 需要通过冲刷icache来实现其屏障的效果, 使后续对icache的访问必定缺失, 从而访问内存中的新数据. 不过无论采用何种实现方案, 程序中都需要添加fence.i指令, 从而满足RISC-V手册对程序的要求, 否则程序将无法在采用实现方案(3)的处理器上正确运行.

事实上, 这些实现方案之间的区别只不过是将副本的一致性问题放在硬件层处理还是放在软件层处理: 如果指令集规范要求处理器在硬件层次处理副本的一致性问题, 则这个问题对软件透明, 程序员无需考虑应该在程序中的何处添加类似fence.i的指令, 但代价是硬件设计更复杂; 如果指令集规范要求处理器在软件层次处理副本的一致性问题, 则硬件设计更简单, 但代价是增加了程序员的负担. 因此这个问题的本质是硬件设计的复杂性与程序开发负担之间的权衡.

实现fence.i指令

根据你对fence.i指令的认识, 选择一种你认为合理的方案在NPC中实现fence.i指令. 实现后, 在上述smc.c中的合适位置添加fence.i指令, 并重新在NPC上运行. 如果你的实现正确, 你将看到程序输出一个字符A后成功结束.

Hint: 你可能会遇到和fence.i相关的编译错误, 尝试根据报错信息解决问题.

事实上, 在真实计算机中缓存一致性问题还有更多的表现. 后续随着处理器变得复杂, 我们也会讨论更多的缓存一致性问题.

# 性能优化和简易缓存

更新ysyxSoC

# 性能评估

# 基准程序选择

CoreMark和Dhrystone不是好的benchmark

# 寻找性能瓶颈

# 性能公式和优化方向

统计IPC

# 简单处理器的性能模型

# 性能事件和性能计数器

添加性能计数器

添加性能计数器(2)

性能计数器的trace

# 阿姆达尔定律(Amdahl's law)

根据性能计数器寻找合适的性能瓶颈

从事计算机体系结构工作的专业素养

自顶向下的调试方法

# 校准访存延迟

更新yosys-sta

校准访存延迟

寻找最高的综合频率

可编程的计数器增量

重新寻找优化瓶颈

评估NPC的性能

记录性能数据

优化主频是否值得?

校准FPGA上的访存延迟

提升功能测试的效率

# 经典体系结构的4类优化方法

重新审视处理器体系结构设计

# 存储层次结构和局部性原理

# 存储层次结构(Memory Hierarchy)

# 局部性原理

观察程序的局部性

链表的局部性

# 简易缓存

# 缓存介绍

对软件程序可见的cache

# 简易指令缓存

实现icache

适合缓存的地址空间

估算dcache的理想收益

# 形式化验证

# 形式化验证的基本原理

不要迷信UVM测试的100%覆盖率报告

# 形式化验证的简单示例

# 基于Chisel的形式化验证流程

不再使用Utest

# 基于Verilog的形式化验证流程

# 通过形式化验证测试icache

通过形式化验证测试icache的实现

# 缓存的优化

统计AMAT

# 优化命中率

# cache缺失的3C模型

# 降低Compulsory miss

# 降低Capacity miss

# 降低Conflict miss

# 块大小的选择

# 设计空间探索

实现cachesim

压缩trace

使用cachesim进行设计空间探索

# 优化缺失代价

# 块大小和缺失代价

支持更大的块大小

支持更大的块大小(2)

# 总线的突发传输

# 突发传输的实现

切换到32位ysyxSoC

集成AXI接口的SDRAM控制器

让icache支持突发传输

# 校准AXI接口SDRAM的的访存延迟

实现AXI延迟模块

评估突发传输方式的性能表现

# 快速评估缺失代价

快速评估缺失代价

# 程序的内存布局

优化程序的内存布局

# 设计空间探索(2)

性能优化和简易缓存

性能评估

基准程序选择

寻找性能瓶颈

性能公式和优化方向

简单处理器的性能模型

性能事件和性能计数器

阿姆达尔定律(Amdahl's law)

校准访存延迟

经典体系结构的4类优化方法

存储层次结构和局部性原理

存储层次结构(Memory Hierarchy)

局部性原理

简易缓存

缓存介绍

简易指令缓存

形式化验证

形式化验证的基本原理

形式化验证的简单示例

基于Chisel的形式化验证流程

基于Verilog的形式化验证流程

通过形式化验证测试icache

缓存的优化

优化命中率

cache缺失的3C模型

降低Compulsory miss

降低Capacity miss

降低Conflict miss

块大小的选择

设计空间探索

优化缺失代价

块大小和缺失代价

总线的突发传输

突发传输的实现

校准AXI接口SDRAM的的访存延迟

快速评估缺失代价

程序的内存布局

设计空间探索(2)

缓存一致性