生命游戏中的简易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最终包含R1+R2的结果（并在过程中将R1清零）。解决了这个问题，请看，一个实现了上述功能的CPU：

CPU布局

我们计算机的整体布局将完全标准化。在左上角是我们的时钟，它的工作原理与上次描述完全一样。这将保持所有部分的同步，以便我们逐条执行指令。时钟的右边是寄存器文件，它使用我们上次开发的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触发器。

ROM

ROM的工作原理是将单个比特编码为一个由与门组成的二维网格（32行，32列），其中与门的存在表示该位被置位，不存在表示该位未被置位。虽然这个想法听起来很简单，但困难的部分在于如何从这个格式中读取数据。

为了从这个网格中读取数据，我们从右侧发送一个恒定的1流向左，并从顶部发送一个恒定的1流向下。所以通常情况下，无论是否存在与门，信号都会正常继续，不会发生什么有趣的事情。为了从特定列读取数据，我们向该列发送一个0而不是1。这使得通常携带1的水平线现在在与门存在的位置开始携带0，在其他位置则携带1。

因为我们一次只激活一列，这个部分开启、部分关闭的信号将不受影响地到达电路的左端，穿过所有从顶部接收到1信号的其余与门。最后，在左边，我们只需将四组32位信号的结果进行或运算。

指令执行

好了，所有底层细节都讲完了，计算机最后需要描述的部分是我们如何实际执行每条指令。

每条指令被编码为8位格式，其中前4位直接设置CPU的控制线，后4位始终是被访问的寄存器（因为每条指令恰好访问一个寄存器）。跳转指令需要一个地址，该地址作为跳转指令后的第二个8位指令存储。

指令	写回	跳转	清零	减量	寄存器索引	额外数据
空操作	0	0	0	0	Reg
增量	1	0	0	0	Reg
减量	1	0	0	1	Reg
置零	1	0	1	0	Reg
条件跳转	0	1	0	0	Reg	8位地址
无条件条件跳转	0	1	1	1	Reg	8位地址

大多数普通指令都很容易实现，实际上，正如你所见，我还包含了清零寄存器的指令以及无条件分支，因为这很容易做到。

跳转指令的工作方式是，在第一个时钟周期，它们计算（然后在一个锁存器中存储一个周期）是否应在下一个周期执行跳转。然后，当我们加载下一条指令时，如果锁存器表明我们正在加载一个应该执行的跳转，我们就不将其视为一条指令，而是将ROM的内容写入程序计数器。

2级流水线

我们CPU的最后一点复杂性在于它实际上采用了二级流水线。从高层来看，这是一个经典的2级流水线CPU，其中一级进行指令解码/执行/写回，另一级从ROM中获取下一条指令。

值得注意的是，这几乎使我们的计算机速度翻倍。（或者更准确地说，它使得在不会引起任何问题的情况下将时钟速度加倍成为可能。）这里的原因是，事实证明，滑翔机从程序计数器出发，经过ROM，到达电路左侧控制逻辑所需的路径，几乎与控制逻辑经过寄存器文件、ALU再返回的路径一样长。

跳转指令和2级流水线有一个问题，那就是如果发生了跳转，那么下一条指令还没有准备好进入流水线。所以我们有两个选择。一种是暂停一个周期，什么也不做。这相当浪费，所以我不打算这样做。相反，我将借鉴MIPS的做法，声明分支之后的指令总是被执行，无论条件是否为真；如果你有一些总是应该执行的工作，可以放在这里，否则就在那里放一个空操作，假装它是一个暂停。

结束

更多精彩内容 请关注我的个人公众号 公众号（办公AI智能小助手）或者 我的个人博客 https://blog.qife122.com/
对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号（网络安全技术点滴分享）