康威生命游戏中的简易CPU设计与实现

生命游戏中的简易CPU - 第4部分这是关于在生命游戏中创建数字逻辑门系列文章的第四篇。前几篇文章从如何创建数字逻辑门开始并利用它们来构建简单的电路。在这篇文章中我们将实际构建第一台真正的计算机一个2级流水线无限寄存器机器。稍后[第5部分]我们还会制造一台更好的计算机。下图展示的是一个正在执行程序的无限寄存器机器的运行情况该程序对数字15进行因式分解整个过程仅需几分钟。你可能会认为这是一个简单的任务但请允许我提醒你就在几年前量子计算机才完成了这一令人印象深刻的壮举。背景此时我不打算解释什么是康威生命游戏或者我如何使用它在生命游戏中构建运行电路。我之前已经做过三次了这些背景介绍写起来很枯燥。幸运的是尽管这是我第四次写这个话题但实际上你只需要阅读上一篇文章就能理解本文的内容。CPU 概述在你能合理地理解我为何做出这些设计决策之前我最终必须告诉你URM到底是什么。URM最初被描述为一种可计算性的数学形式化模型它是一个图灵完备的、仅含四条指令的CPU理论上拥有无限数量的寄存器每个寄存器可以保存无限大的整数。由于我们处理的是现实世界我们的CPU将只允许16个寄存器每个寄存器能够保存4位数据。一个无限寄存器机器只能在寄存器上执行三种操作增量 (INC Rx)将目标寄存器加一。减量 (DEC Rx)将目标寄存器减一。跳转 (JNZ Rx, Addr)如果当前寄存器不为零则跳转到目标指令。这三个简单的操作看起来不多但事实证明它们实际上是图灵完备的。这有点令人惊讶。为了证明这一点我们首先观察一下我们可以使用这些基本操作来模拟其他一些常见指令清零 (ZRO Rx)通过持续递减目标寄存器直到它为零DEC Rx; JMP Rx, -1。无条件跳转 (JMP Addr)通过保留一个始终为正的临时寄存器Ry并运行JNZ Ry, Addr来实现。因此例如如果我们想把寄存器1的内容加到寄存器2中你可以实现如下操作ADD: jnz R1, END dec R1 inc R2 jmp ADD END:这将导致R2最终包含R1R2的结果并在过程中将R1清零。解决了这个问题请看一个实现了上述功能的CPUCPU布局我们计算机的整体布局将完全标准化。在左上角是我们的时钟它的工作原理与上次描述完全一样。这将保持所有部分的同步以便我们逐条执行指令。时钟的右边是寄存器文件它使用我们上次开发的D触发器保存16个4位寄存器。这就是这台机器的全部RAM——64位。寄存器文件的右边是一个小小的算术逻辑单元ALU它计算CPU支持的实际数学函数。因为这是一个URM它只能进行增量操作。寄存器文件下方是另一系列D触发器这次用于存储程序计数器它保存着我们正在执行的当前指令。程序计数器下方是ROM它保存着我们将要执行的程序文本。这个ROM最多可以保存128条不同的4位指令。程序ROM的左边是另一组触发器。这些触发器实际上使这个CPU能够拥有一个两级流水线可以同时进行取指和执行。最后右侧是计算机的输出形式为四个7段数码管。这些几乎与我在上一篇文章中构建的7段数码管完全相同。高效的电路设计准则CPU的基本构建实际上相对简单我们只需要做几件事就能将一堆数字逻辑门变成一个完整的计算机。因为这篇文章旨在专注于设计生命游戏中的计算机而不是通用计算机所以我不想花太多时间在那些让你能用普通逻辑门设计计算机的通用部分上。其他人已经做过了。相反我想关注的是在生命游戏之上构建CPU时会发生哪些变化。让我们从关键区别开始。在构建真实计算机时最终的设计准则是尽量减少比如所使用的晶体管总数或者更准确地说是电路的深度但我们不要过于学究。这之所以重要是因为在物理硬件上晶体管无论是在实际成本还是延迟方面都是最昂贵的。虽然电可以以接近光速的速度流过导线但当你通过一个晶体管时会有相当大的传播延迟因此从头到尾有大量晶体管的深层电路其速度将远慢于只有几个晶体管的电路。相比之下在生命游戏中唯一重要的是电路沿着最长路径的总长度。无论这是通过我们所谓的“导线”还是通过与门或或门都没有关系唯一重要的是滑翔机覆盖的总距离。这两种情况大致相同。因此我们的设计不会专注于最小化我们必须使用的单个组件的总数因为使用一个电路的成本只比让导线穿过空白空间稍大一点。因此有许多巧妙的设计在实际硬件中更高效因为它们最小化了晶体管的深度但在生命游戏中构建时效率却低得多因为它们需要更多的空间在二维网格上布局。另一个重要的区别是一切都可以保证完全确定性地运行。重复上一篇文章中讨论过的一个例子真实硬件上的实际时钟会以几乎相同的频率振荡但在一个时钟周期和下一个时钟周期之间可能会有一些微小的变化。相比之下数字逻辑生命游戏中的时钟每次都有完全相同的频率永远不会漂移。这使我们能够依靠导线的精确长度来确定将要发生的操作序列。你可能还记得之前我们如何利用这一事实来设计一个边沿检测器通过构建一个A AND (NOT B)的小电路并将相同的输入连接到A和B但由于通向B的导线稍长它就能可靠地确定信号何时从1变为0。右侧是这种应用的一个例子。ALU让我们从ALU开始因为它无疑是这里最简单的部分。它所做的一切就是接收一个4位整数作为输入然后要么 (a) 将输入加一(b) 将输入减一要么 © 对输入不做任何操作。但是我们并没有构建单独的增量/减量电路而是利用了这样一个事实对一个整数减一等同于先按位取反然后加一再对结果按位取反。所以我们只需要控制是否对所有位取反然后使用一个单一的增量电路。不幸的是关于ALU没有什么更有趣的东西能说明它在生命游戏上实现的特殊性了。所以我们继续往下看。寄存器文件再次提醒这里的目标是最小化电路的总面积而不是单个门的数量。更多门紧密排列比更少门松散排列要好。寄存器文件的整体设计相当简单。寄存器文件的左上角接收当前时钟和一个4位选择器作为输入该选择器表示应该激活哪个寄存器。从右侧寄存器文件接收应该写入其中一个寄存器的数据由来自左上角的选择寄存器决定。唯一的输出也在右侧它输出当前被选中的寄存器的值。这种布局的原因再次是为了最小化电路的总长度。一旦我们有一条指令要执行例如增加寄存器五我们需要做的是检索寄存器五的值然后该值从电路右侧输出进入ALU。在这里我们执行增量操作然后立即将它反向发送回去以存储我们刚刚得到的值。请注意这使我们一次只能访问一个寄存器进行读取和写入这严重限制了我们的程序设计因为它不允许我们使用例如x86风格的指令将寄存器一的值加到寄存器二。我们在任何时钟周期内只能访问一个寄存器。我在这里做的一件事是找到那些设计一种新的逻辑门会有所帮助的地方这种逻辑门能做一些非常特殊的事情但能让所有电路的布局更好一些。例如寄存器文件实际上有两种专用逻辑门。第一种是一个计算与操作的逻辑门但它只有一个输出而是有两个输出。第一个输出正是你所期望的A AND B。但第二个输出只是第二个输入的精确副本。右侧展示了这个电路的实际应用注意无论是否存在A信号从底部传来的值总是会继续传递到顶部但只有当两个信号都存在时我们才有输出到右侧正如我们执行与操作一样。另一种逻辑门接收来自左侧的信号并向下方发出该信号的否定同时仍然允许输入信号向右传递。左侧展示了一个例子。这类门之所以有用是因为它允许我们更优地布局电路而无需额外的导线来绕线和多次复制信号。与寄存器文件的设计最相关的是这两个门实现了一个非常高效的2x2盒子它的行为像一个锁存器实际上我在上一篇文章中展示过由于这个锁存器尺寸很小我们可以构建一个总面积比初始设计小60倍的D触发器。ROMROM的工作原理是将单个比特编码为一个由与门组成的二维网格32行32列其中与门的存在表示该位被置位不存在表示该位未被置位。虽然这个想法听起来很简单但困难的部分在于如何从这个格式中读取数据。为了从这个网格中读取数据我们从右侧发送一个恒定的1流向左并从顶部发送一个恒定的1流向下。所以通常情况下无论是否存在与门信号都会正常继续不会发生什么有趣的事情。为了从特定列读取数据我们向该列发送一个0而不是1。这使得通常携带1的水平线现在在与门存在的位置开始携带0在其他位置则携带1。因为我们一次只激活一列这个部分开启、部分关闭的信号将不受影响地到达电路的左端穿过所有从顶部接收到1信号的其余与门。最后在左边我们只需将四组32位信号的结果进行或运算。指令执行好了所有底层细节都讲完了计算机最后需要描述的部分是我们如何实际执行每条指令。每条指令被编码为8位格式其中前4位直接设置CPU的控制线后4位始终是被访问的寄存器因为每条指令恰好访问一个寄存器。跳转指令需要一个地址该地址作为跳转指令后的第二个8位指令存储。指令写回跳转清零减量寄存器索引额外数据空操作0000Reg增量1000Reg减量1001Reg置零1010Reg条件跳转0100Reg8位地址无条件条件跳转0111Reg8位地址大多数普通指令都很容易实现实际上正如你所见我还包含了清零寄存器的指令以及无条件分支因为这很容易做到。跳转指令的工作方式是在第一个时钟周期它们计算然后在一个锁存器中存储一个周期是否应在下一个周期执行跳转。然后当我们加载下一条指令时如果锁存器表明我们正在加载一个应该执行的跳转我们就不将其视为一条指令而是将ROM的内容写入程序计数器。2级流水线我们CPU的最后一点复杂性在于它实际上采用了二级流水线。从高层来看这是一个经典的2级流水线CPU其中一级进行指令解码/执行/写回另一级从ROM中获取下一条指令。值得注意的是这几乎使我们的计算机速度翻倍。或者更准确地说它使得在不会引起任何问题的情况下将时钟速度加倍成为可能。这里的原因是事实证明滑翔机从程序计数器出发经过ROM到达电路左侧控制逻辑所需的路径几乎与控制逻辑经过寄存器文件、ALU再返回的路径一样长。跳转指令和2级流水线有一个问题那就是如果发生了跳转那么下一条指令还没有准备好进入流水线。所以我们有两个选择。一种是暂停一个周期什么也不做。这相当浪费所以我不打算这样做。相反我将借鉴MIPS的做法声明分支之后的指令总是被执行无论条件是否为真如果你有一些总是应该执行的工作可以放在这里否则就在那里放一个空操作假装它是一个暂停。结束更多精彩内容 请关注我的个人公众号 公众号办公AI智能小助手或者 我的个人博客 https://blog.qife122.com/对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号网络安全技术点滴分享