《毁灭战士》简介
《毁灭战士》是 id Software 在 1993 年发布的电子游戏，它在游戏界引发革命，迅速风靡全球，奠定了现代第一人称射击游戏的基础。超高人气让“《毁灭战士》能在任何设备上运行”的说法诞生，为验证此说法，它几乎被移植到所有设备，从微控制器、烤面包机，甚至到细菌。
两周前，成功在自己搭建的 CPU 上运行（或者说“艰难运行”）了《毁灭战士》，还发布了相关视频，获得数百万浏览量。在逻辑门层面设计了自定义 CPU，将其与外设相连，适配《毁灭战士》源代码使其能在机器上运行，最后部署到现场可编程门阵列上实时运行。运行《毁灭战士》前，只运行过自己编写的简单程序，像《乒乓》和曼德勃罗集相关程序。
面临的挑战
从提出的流水线设计开始，想运行更复杂程序。但面临内存和速度两大难题。更大程序需要更大内存，最初设计只能利用 FPGA 的块随机存取存储器，其容量不足 1MB。《毁灭战士》的基础共享软件版本就有 14MB，这还只是存储程序所需内存，不包括运行时所需内存。第二个障碍是速度，《毁灭战士》在现代 PC 上运行轻松，但对该 CPU 是巨大挑战。
我和利亚姆决定分别解决这两个问题。利亚姆在为乱序处理奠定基础，我负责解决内存集成问题。
内存集成
最初的 CPU 设计中，内存管理简单。FPGA 的块随机存取存储器延迟仅 1 个周期，且接口简单。这种一致性让流水线处理器无需因内存操作停顿，稳定延迟已纳入流水线设计。此外，块随机存取存储器有粒度性，可逐字读取和编辑内存。
相比之下，DDR3 内存速度慢、延迟可变，且总线宽度宽。这使内存操作更复杂、不可预测，速度也慢得多。若所有内存操作都通过 DDR3 内存进行，CPU 运行速度将大幅下降。这时，缓存发挥作用，将活跃内存区域存储在块随机存取存储器中，提高访问速度。优化良好的缓存几乎可消除 DDR3 带来的额外延迟。
CPU 设计
这个版本的 CPU 采用相对标准的 5 级流水线：指令获取、解码、寄存器读取、执行和写回。此外，该设计将内存操作抽象为统一接口，简化核心流水线阶段。
核心流水线
-指令获取阶段：该阶段跟踪程序指针，通过指令缓存从内存中获取正确指令。与之前设计不同，它内部处理重定向和停顿。随着 DDR 内存加入，重定向更复杂。以前，内存延迟为 1 个周期，可每个周期获取一条指令，并在重定向请求到来的周期切换内存请求地址。但新设计中，若获取阶段收到重定向请求，内存可能已有请求在处理。需跟踪内存的下一个响应是否无效，然后请求正确地址。
-解码阶段：这个阶段较简单，将 32 位指令拆分成各个组成部分，保存到指令包中，再发送到流水线的下一个阶段。不过，这个阶段也有独特问题，将在后面章节详细介绍。
-寄存器读取阶段：这个阶段有重大修改。之前的寄存器文件采用组合逻辑读取，减慢了 CPU 速度。这个版本将读取操作流水线化，虽增加 1 个周期延迟，但减少了关键路径延迟。另一个变化是处理“写后读”冒险。“写后读”冒险指在待写入操作完成前读取寄存器，得到错误数据。之前的读取阶段内部跟踪通过它的最后几次寄存器写入操作，这种方法逻辑高效，但脆弱，不总是有效。更严格测试表明，特殊情况会导致它无法检测到冒险。新版本依赖由周围核心计算并输入到该阶段的“寄存器使用映射”。“寄存器使用映射”是 32 位映射，用于跟踪寄存器是否正在使用。它能自然适应不同流水线长度，无需使用特殊数字。使用“寄存器使用映射”，读取阶段可决定是否触发冒险标志并暂停前一个阶段，或让指令继续执行。
-执行阶段：该阶段决定如何处理每条指令。它将指令各部分路由到不同组件，调用算术逻辑单元进行算术运算、解析分支指令，并与内存交互。解析跳转指令时，它会向流水线前面发送刷新信号，清除错误阶段。遇到内存指令时，它会进入特定内存等待阶段，直到内存响应。
-写回阶段：这个阶段只是将值写回到寄存器文件中。
内存处理
核心流水线较标准，真正复杂的是内存处理。理想的流水线 CPU 中，指令获取阶段每个周期获取一个新字，执行阶段每个周期获取新数据。相比之下，FPGA 上的 DDR3 每 30 - 60 个周期才能返回 2 个字，远低于期望吞吐量，所以需要缓存。实际上，需要两个缓存：指令缓存和数据缓存，它们可独立运行，满足获取和执行阶段在同一周期可能请求两个不同地址的需求。
缓存设计
指令缓存和数据缓存相对简单，且彼此相似。实际上，指令缓存使用的底层代码与数据缓存完全相同，只是去掉了写逻辑。两个缓存都是简单的单路直接映射缓存。当前版本中，它们各自使用 2048 个缓存行，每行包含 4 个字。
收到内存请求时，缓存会分离出字地址（通过去掉最低两位），然后计算缓存索引。缓存索引是字地址的最低 10 位。接着，它从块随机存取存储器中提取该缓存行。缓存行由数据、标签和状态三个组件组成。数据是缓存跟踪的 4 个实际内存字；标签是字地址的高位，用于防止缓存别名问题。别名问题指多个地址指向同一个缓存索引，需确保不混淆它们。2 位的状态位表示有效和脏信号。有效信号表示该行数据是实际数据，而非初始化时的随机值；脏信号告诉我们 CPU 自从从内存中获取该行数据后是否对其进行了修改。如果提取的缓存行有效且标签匹配，缓存会根据操作进行简单的读取或读 - 修改 - 写操作，无需向内存发送请求。
然而，如果标签不匹配，缓存必须访问 DDR3 内存。有效缓存行有干净和脏两种可能状态。如果一行是干净的，可直接从内存中读取新的缓存行并丢弃当前数据。如果是脏的，缓存必须先将修改后的行写回内存，然后再请求新的数据。考虑到 DDR3 的延迟可能在 30 - 100 个周期之间，而缓存命中仅需 2 个周期，这非常慢。
坦率地说，这是个效率较低的设计。更好的缓存应使用更长的缓存行，提高存储密度和空间重用性。但选择 4 个字的行宽是为了简化与原始 FPGA 板上 128 位宽的内存接口生成器接口的交互。后来更换了不同的板子，所以这个低效设计就暂时保留了下来。
仲裁机制
如果指令缓存和数据缓存同时发出内存请求怎么办？在[6.191]中，这个问题通过为每个缓存配备一个内存芯片来解决，但板子只有一个芯片，所以这种方法不可行。这时，内存仲裁器发挥作用。它对两个缓存来说就像一个内存接口，通常只是将请求转发到实际的 DDR3 内存。但当一个请求正在处理时又收到另一个请求，它会假装内存已经收到了请求，实际上只是将其排队，直到内存空闲时再发送。当然，这可能导致死锁问题，即一个缓存会使另一个缓存无法访问内存。通过优先处理数据缓存的请求来解决这个问题，因为它在流水线中处于更下游的位置，最终会完成内存请求。
底层实现
通过上述设计，CPU 在模拟内存环境中能完美运行，但在实际硬件中却无法正常工作。首先，DDR3 内存接口非常复杂，需要精确的时序和控制。这就是赛灵思的内存接口生成器发挥作用的地方，它让原本复杂的接口变得相对简单。第二个问题是内存接口生成器在自己的时钟域中运行，如果直接将 CPU 连接到内存接口生成器，会遇到难以理解的时序问题，导致系统崩溃。第三个问题是，无法让内存接口生成器在原来的 FPGA 板（带有 128 位总线）上正常工作，所以借用了朋友[瑞安·唐]的板子，它有一个较小的、带有 64 位总线的 DDR3 芯片。
这些问题通过一系列的时钟域转换、先进先出队列和协议包装器来解决，相关代码可在 GitHub 上找到。最重要的是，最终一切都能正常工作了。有了新的内存，甚至可以运行《蜜蜂总动员》相关程序。
外设接口与 I/O
将《毁灭战士》移植到硬件前，还需做些工作。虽然 CPU 能正常工作，但无法与外界通信。需要显示输出、硬件定时器、调试输出和键盘输入等外设。决定为这些外设使用内存映射 I/O。VGA 控制器已搭建好，将其扩展到 12 位色彩，并连接到 HDMI 端口。硬件定时器简单，以微秒为单位跟踪时间，并将其保存到内存中的一个字中。调试输出稍复杂。简单版本只是将通用异步收发传输器发送器连接到可写的内存值上。但如果 CPU 连续打印多个字符，会丢失一些字符，导致输出混乱。因此，使用了一个先进先出缓冲区防止溢出。键盘输入问题更大。最初计划与瑞安借给的厄巴纳 FPGA 板上的 USB 主机芯片交互。但编写串行外设接口驱动程序后，惊讶地发现串行外设接口总线上没有数据传输。似乎板子上的 USB 端口不提供电源，无法为键盘供电。于是，连接了一个通用异步收发传输器接收器，将笔记本电脑的按键输入转发到 FPGA。虽不太完美，但至少能工作。至此，完成了运行《毁灭战士》所需的所有准备工作。
移植《毁灭战士》与调试
将《毁灭战士》移植到新芯片是具有挑战性的任务。要找到加载程序的方法，访问正确的外设，实现输入和输出，还要解决因平台特性产生的各种问题。将其移植到自定义 CPU 更具挑战性，因为程序出现问题时，不知道是代码有误，还是 CPU 本身存在问题。不过，奥兹克尔创建了[doomgeneric]，简化了移植过程。尽管有这个简化工具，还是遇到许多挑战。朋友[利亚姆]负责移植过程，他可能会在他的博客上分享见解。在众多挑战中，有文件系统问题、渲染问题，还有很多与 `printf` 相关的问题，以至于他最后不得不自己编写了一个版本。最奇怪的问题是，`printf` 有时能正常工作，有时却不行。
许多这些 bug 暴露了 CPU 的错误。例如，常看到系统陷入包含数百条指令和跳转的无限循环。有时，它似乎会随机跳转，跳到毫无意义的地址。然而，一次性调试整个《毁灭战士》程序不可行，所以将其分解成多个部分，逐步测试更复杂的程序。偶尔，缓存仲裁器和内存接口生成器的时钟域转换会出现问题，导致写回请求丢失。有时，立即数的计算会出错，还有时，数据缓存会覆盖指令数据。其中一些问题早在第一个[单周期处理器]中就存在，只是之前从未遇到过。最终，在模拟环境中让一切都正常工作了。
然而，在硬件上它就是无法正常运行。编写的任何程序都能正常工作，但《毁灭战士》不行。它似乎会在随机的地方停止，跳转到随机的地址，甚至开始读取半字指令。认为问题出在内存接口生成器模拟上，因为这是唯一难以模拟的部分，但编写的所有内存测试在模拟和硬件环境中都能完美运行。经过长时间困惑，决定在加载程序前将 DDR3 内存初始化为随机值。这导致《毁灭战士》无法运行，但其他程序不受影响。似乎《毁灭战士》假设未初始化的内存为零，而在硬件中并非如此。经过一些链接和汇编方面的修复，《毁灭战士》终于在硬件上加载成功了。
之后，进展相对顺利，让《毁灭战士》以大约 0.7 帧每秒的速度运行，实际上应该说是每帧需要几秒。原本打算在这里结束博客，因为已实现最初目标。但对 0.7 帧每秒的速度不满意。例如，本来打算坐下来学习线性代数，但最后却开始优化 CPU。可能已经上瘾了。
迈向 30 FPS 的征程
《毁灭战士》以 1 帧每秒的速度运行实在不尽人意。虽令人印象深刻，但根本无法正常游玩。想玩《毁灭战士》，而不是看幻灯片。最简单的提速方法是提高时钟速度。将时钟频率从 100MHz 提高到 125MHz，帧率提高约 20%。之所以不是 25%，是因为内存延迟与 CPU 核心速度是解耦的。接下来的优化是在 CPU 的指令获取阶段。原来的获取设计效率极低，更注重正确性而非速度。因此，它每条指令经常会向指令缓存发送 2 个请求。修复这个问题后，将帧率提高到约 2.5 帧每秒，速度提升超过 300%。
然而，到这个阶段，进一步提高性能更困难。开始增加更多指令。实现了乘法运算符，但选择不实现除法或取模运算，因为这会增加流水线的复杂性。因此，CPU 变成了一个 `RV32I-ZMMUL` CPU。这又让帧率提高了 1 帧每秒，达到 3.5 帧每秒。考虑到 15 帧每秒的目标，这虽是进步，但还是有些令人失望。
之后，仔细分析了哪些函数占用 CPU 时间，发现将屏幕缓冲区的数据复制到 VGA 控制器的块随机存取存储器中非常耗时。这不仅增加了内存带宽的压力，还刷新了缓存。因此，修改了代码，使其直接写入 VGA 的块随机存取存储器。同时，意识到可以对缓存读取命中进行流水线处理，将延迟从 2 个周期降低到 1 个周期。这两个优化措施结合起来，将帧率提高到约 6.7 帧每秒。
从这一点来看，如果不彻底改变流水线，似乎没有太多简单的方法可以提高速度。考虑到目前正在开发一个乱序流水线，它将取代现有的大部分流水线，不想在这个流水线上投入太多时间。不过，还有一个可以尝试的方法：编译器优化。当前运行的《毁灭战士》版本是使用 `O0` 编译的，这意味着编译器不会对代码进行任何优化。这应该很简单，只需要将 0 改为 2 就可以了。但每次尝试这样做时，程序都会崩溃，也不知道原因。最初，认为是 CPU 出现了错误，毕竟编译器优化怎么会导致代码崩溃呢？经过长时间的调试，终于找到了问题所在。没有将硬件定时器的内存映射 I/O 指针标记为 `volatile`。编译器会认为从未向定时器写入数据，因此将其从代码中优化掉了。发现[这篇博客文章]在学习优化方面很有帮助。修复这个问题后，游戏运行得非常流畅。
最终成果
经过编译器优化后，《毁灭战士》以 15 - 20 帧每秒的速度流畅运行，现在已经非常适合游玩，也很有趣。终于明白为什么它在当年如此受欢迎了。通过乱序处理和其他优化，希望最终能达到 30 帧每秒的目标。
总结与展望
移植《毁灭战士》是有趣但有些痛苦的经历。学到了很多关于内存和缓存的知识，但最大的收获是学会了如何调试大型系统。还有件有趣的事，发布的[9 秒运行视频]已有 200 万浏览量。至于未来计划，目前致力于实现乱序处理以及更好的内存访问模式，这应该会让游戏运行得更快。也许之后，编写基本的图形处理器后，可以尝试移植《雷神之锤 2》。希望不久后能在更大的 FPGA 上运行游戏。
感谢阅读，如果您有任何问题，请随时联系我！
