从 0.7 FPS 到 15 - 20 FPS：自定义 CPU 运行《毁灭战士》的艰难提速之旅！

《毁灭战士》简介《毁灭战士》是 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 上运行游戏。感谢阅读如果您有任何问题请随时联系我