Nand2Tetris I - ALU & Memory

Posted on 繁/简： set

这门课将带领我们使用普通的与非门 (NAND gate) 从零开始搭建一个完整的 general-purpose computer；不得不说这真是太极客了，很符合我对计算机科学的酷炫想象。

这门课课时并不长，但涵盖了从最底层的 logic gate，中层的 assembly languages 到顶层的 programming languages 与 OS 等一系列计算机的基本组成部分，可谓是具体而微。目标：一个月内 (10.6 之前) 搞定！

我将该课程中所有 projects 的 HDL 代码实现储存在 ThisisXXZ/Nand2Tetris - GitHub 中，仅供参考。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


Boolean Functions & Gate Logic

这门课确实做到了完全的 non-prerequisite；本节的内容十分基础，但我还是从中学到了不少新东西。

Boolean Identities

三个基本的布尔函数：AND \(\land\), OR \(\lor\) 与 NOT \(\lnot\) .一个 Boolean Algebra 具有以下性质：

  • Commutative Laws (交换律).
    • \((x\land y)=(y\land x)\).
    • \((x\lor y)=(y\lor x)\).
  • Associative Laws (结合律).
    • \((x \land (y\land z))=((x\land y)\land z)\).
    • \((x\lor (y\lor z))=((x\lor y)\lor z)\).
  • Distributive Laws (分配律).
    • \((x\land(y\lor z))=(x\land y)\lor (x\land z)\).
    • \((x\lor (y\land z))=(x\lor y)\land (x\lor z)\).
  • De Morgan Laws.
    • \(\lnot(x \land y)=(\lnot{x})\lor(\lnot y)\).
    • \(\lnot(x\lor y)=(\lnot{x})\land (\lnot y)\).

应用这些性质，我们能够对任意的 Boolean algebra 进行化简/等价变形；但需要注意的是，找到给定的 Boolean algebra 的最简化形式这个问题是 NP-hard 的；不存在解决该问题的 general algorithm。

Truth Table to Boolean Expression

对于一张给定的真值表，如何找到等价的布尔表达式？这个问题很有应用价值。至少当我在写 project 时发现，这一准则在 chip design 中作用很大。我们来看一个例子：

A 3-variable boolean function

对于每个值为 1 的行，我们查看对应的变量；若为 0，则对其取反。最后把所有变量与起来 (保证最后的结果为 1)：以第一行为例，由于 \(x,y,z\) 均为 0，该行对应的 constraint 为 \((\lnot x)\land (\lnot{y})\land (\lnot z)\)；而第三行中 \(y\) 的值为 1，我们不需要对其取反，因此对应的 constraint 为 \((\lnot{x})\land y\land (\lnot{z})\).

把这一步得出的所有 constraints 再或起来，就得到了这张真值表对应的布尔表达式。

Multiplexer

当初在 ENGG1310 中接触了 multiplexer (多路复用器) 这个概念，奈何该课实在过于水，只知道猛灌大量的概念，因此时至今日我只对这个名字产生了些许印象。而在 Nand2Tetris 这门课程中，仅仅用了 10 分钟我就掌握了 multiplexer 的基本原理，课程质量高下立判。

multiplexer 与 demultiplexer 其实是一种 chip design，其宏观表现即为通讯系统中著名的复用器/解复用器。用 HDL (Hardware Description Language) 描述的 multiplexer 与 demultiplexer 的 API 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/** 
 * Multiplexor:         * Demultiplexor:
 *                      *                        
 * out = a if sel == 0  * {a, b} = {in, 0} if sel == 0
 *       b otherwise    * {0, in} if sel == 1
 */

CHIP Mux {
    IN a, b, sel;
    OUT out;
    ...  // implementation
}

CHIP DMux {
    IN in, sel;
    OUT a, b;
    ...  // implementation
}

多路复用器根据输入的 sel 流同时将多路的输入比特流转化为一路的输出比特流；解复用器则是上述过程的逆过程。整个流程是 simultaneous 的，使得多路信息能在单条信道上同时进行传输。

Each sel bit is connected to an oscillator producing alternating 0/1 signals


ALU Implementation

这一节我们将使用 project 01 中设计的众多 chips 来构建一个 ALU (Arithmatic Logic Unit, 算术逻辑单元)。

2's Complement

Definition. Represent Negative number \(-x\) using the positive number: \(2^n-x\).

这是因为 binary addition 本质上是 modular addition。对于 \(n\)-bits 下的 binary addition，overflow bit (溢出位) 将会被直接舍弃；这实质上相当于将结果对 \(2^n\) 取模。

这样，计算 substraction \(x-y\) 也变得十分简单：\(x-y=x+(-y)\)。给出 \(y\)，我们能通过下面的方式迅速计算出 \(-y\) 的 2s complement：将 \(y\) 取反后加 1。这是因为：\(2^n-y=1+(2^n-1)-y\)。

Adder

所有算术运算的基础是加法运算：因此，ALU 的一个基础单元是 adder (加法器)。此外由于 2's complement 的存在，adder 可以同时完成 addition 与 substraction。

一个 binary adder 由一个 half adder (半加器) 与若干个 full adder (全加器) 组成：

  • Half Adder: 模拟 LSB 的加法运算。输入 a, b；输出 out 与 carry.
  • Full Adder: 一个 full adder 可以由两个 half adders 组成 (这也是半加器名称的来源)；模拟普通位的加法运算。输入 a, b 与 carry (前一位), 输出 out 与 carry。

注意，若 MSB 在进行加法运算后产生了 carry bit，该 carry bit 将被忽略。

Arithmatic Logic Unit

ALU 的基本模型如下：

  • 输入 input1, input2 与某个 pre-defined arithmetic/logical function \(f\).
  • 输出 \(f(\)input1, input2\()\).
  • 输出两个 output control bits zr 与 ng.

其中，函数 \(f\) 被 6 个 input control bits 所 specified：zx, nx, zy, ny, f 与 no，每个 input control bit 指定了一种特定的 operation。ALU 将根据每个 control bit 的值依次执行这一系列 operations，最后得到的输出将与某个算数/逻辑函数 \(f\) 一致。

Only 18 different fs are defined

理论上来说，6 个 input control bits 可以代表 \(2^6=64\) 种不同的 \(f\)；但本课程中只要求我们实现 18 种。真正的 ALU 的确能够支持远超 18 种的函数以执行不同的算数/逻辑运算。

两个 output control bits zr, ng 则用于标识 ALU 计算结果 out 的性质：

  • if out == 0 then zr = 1, else zr = 0.
  • if out < 0 then ng = 1, else ng = 0.

当我们构建整个计算机的结构时，这两个 output control bits 提供的信息将至关重要 [stay tuned].


Problematic Combinatorial Logic

到目前为止，我们构建的所有 chips 都是 combinational chips (组合逻辑芯片/器件)；combinatorial logic (组合逻辑) 意味着芯片任意时刻的稳态输出仅仅取决于该时刻的输入 (i.e., \(\mathtt{out}(t)=f(\mathtt{in}(t))\))。组合逻辑器件使得计算机具有了「计算」(compute values) 的能力。

其实在写 projects 的时候就能感觉到这一点：由于所有 HDL 语句都是 synchronized 的，chips 的输入与输出仿佛是同时发生的。像这样，仅仅建立在组合逻辑器件上，缺少时间概念的计算机有两个致命的问题：

  • It cannot store and recall values (i.e., it cannot memorize things).
  • The system state is not stablized.

第一点很好理解：组合逻辑器件的输出仅仅与该时刻的输入有关，而与前一时刻的状态无关；这一定义本身就与「记忆」这一概念相悖。

第二点则需要稍微进行说明：虽然组合逻辑器件刻意忽略了时间的概念，但现实中，无论是器件的输入与输出之间还是不同器件间信号的传输都会产生时间造成的误差。举例来说，ALU 此时需要计算 \(x\), \(y\) 两数之和：

  • \(x\) 位于 ALU 临近的某个 register [stay tuned]。
  • \(y\) 位于某个比较偏远的 RAM register。

In this case，\(x\) 与 \(y\) 到达 ALU 的时间一定会有差异。于是，在产生稳定的 \(x+y\) 输出之前，ALU 的输出完全没有意义 (generate garbage)。当器件数较少时这个问题的影响可能不会太大；但计算机是一个含有成千上万个元件的精密结构，如果无法实现 architecture synchronization，微小的误差将会导致巨大的混沌。

为了解决以上的问题，一个新的设计逻辑 - sequential logic (时序逻辑) 应运而生。在该逻辑下，芯片在某时刻的稳态输出不仅取决于当前的输入，还与前一时刻输入形成的状态有关 (i.e., \(\mathtt{state}(t)=f(\mathtt{state}(t-1))\))。

注意在 sequential logic 的定义中，我们使用了 state (状态) 这一概念：这也是其与 combinatorial logic 的最根本区别之一。sequential chips (register, binary cell, RAM 等等) 几乎都与计算机的存储功能相关。


Sequential Logic & DFF

如何实现 sequential logic，亦即，如何使一个元件在某时刻的输出能够被前一个时刻的状态影响？如何定义所谓的「时刻」与「状态」？sequential logic 又如何解决 combinatorial logic 产生的两个致命问题？

接下来我们介绍实现 sequential logic 的两个重要基本元件：The Clock (钟) 与 Flips-Flops (正反器/触发器).

The Clock. The Clock 是一个不断在 0-1 (tick-tock) 两信号中交替的 oscillator。该信号 (0-tick, 1-tock) 同时向所有 sequential chips 进行广播，宣布当前的 clock phase。从某个 tick 开始到随后的 tock 结束之间的时间称为 cycle (周期)，每个周期代表了一个离散的时间单位 (discrete time unit)，即所谓的「时刻」。

Flip-Flops. Data Flip-Flops (DFF) 是能够实现 sequential logic 的最小单位。DFF 接受从 master clock 传输的隐藏输入，从而具有了时刻的概念。在此基础上，DFF 能够实现 \(\mathtt{out}(t)=\mathtt{in}(t-1)\): 即，在某时刻 \(t\) 的 DFF 能够输出其在 \(t-1\) 时刻接受的输入，\(\mathtt{in}(t-1)\) 的值从时刻 \(t-1\) 到时刻 \(t\) 被 DFF 所「记忆」。

被 DFF 所记忆的值，我们称之为 DFF 的「状态」 (state)。从另一个角度来看，DFF 创造的是一个长度为 \(1\) (或者说，\(1\) 个时刻) 的时间延迟 (inherent time delay)：本该在 \(t-1\) 时输出的值直到 \(t\) 时刻才被输出。

DFF 是由两个互相连接的与非门构建的。由 DFF 开始，我们能够构建从 register 到 RAM 的所有记忆器件。DFF 与 sequential logic 给予了计算机 maintain values 的能力 - 组合逻辑束手无策的第一个问题得以解决。

第二个问题的解决则更加巧妙：我们计算出计算机中相距最远的两个元件传输信号所需的时间，并将 clock 控制的时间单元周期 cycle 设为稍微高于该时间的某个值。这样我们能够保证在每个 cycle 的末尾 (即 tock 信号结束的瞬间) 所有元件的输出都是稳定且有意义的。


Memory Units & Counters

接下来我们以 DFF 为基础构建一系列经典的记忆单元：registers (寄存器)，RAM units (random-access memory unit, 随机访问存储器) 与 program counters (程序计数器)。

Single-bit register (a.k.a., Bit, binary cell). Behavior: \(\mathtt{out}(t)=\mathtt{out}(t-1)\)。该函数恰恰是对「记忆」这一功能的定义。如何使用仅能执行 \(\mathtt{out}(t)=\mathtt{in}(t-1)\) 的 DFF 构造出这样的元件？

Register implementation
  • [write] If \(\mathtt{load}(t-1)\) then \(\mathtt{out}(t)=\mathtt{in}(t-1)\).
  • [read] else \(\mathtt{out}(t)=\mathtt{out}(t-1)\).

某个 cycle 内 register 的工作流程如下：在每个 tick 期间，Mux 根据 load 选择保留或更新 DFF 的 state；在接下来的 tock 期间，DFF 产生稳定的 out 输出；同时，在 register 内部，该输出值将被导入 Mux 以便其在下一个 cycle 开始时进行选择。

一系列的 single-bit registers 串联形成 multiple-bits registers。宽度 width 是 register 的基本参数之一，它描述了某个 register 最多能够容纳的比特数。在本课程内一个典型的 multiple-bits register 的宽度 \(w\) 是 16。

RAM unit. 一个 RAM 单元由若干个 \(w\)-bits registers/RAMs (with smaller size) 与附加的 direct (random) access logic 组成，它支持根据输入的地址 address 直接对对应的 register 执行读/写操作。

direct (random) access logic 一般由一对 DMux 与 Mux chips 组成：DMux 根据传入的 address 把 load 分配给对应的 registers/RAMs，Mux 则收集相应的输出。这一 logic 的存在使得元件具有了 random access (随机访问) 的性质：我们能够直接 访问任意存储单元中的数据，而不需要按照顺序逐个读取。

word is a w-bit content

RAM 的基本参数包括 width 与 size: width 与组成其的 register 的 width (即 word 的长度) 一致；size 则描述其含有的 registers 的个数。现代计算机的 RAMs 一般是 32/64-bit-wide 的；但其 size 却是数以亿计的。

Program counters. counter (计数器) 是一种特殊的 sequential chip；它所维护的状态在每个时间单元内都会产生一定的变化，遵循函数 \(\mathtt{out}(t)=\mathtt{out}(t-1)+c\)；其中 \(c\) 一般为 \(1\)。Counter 在现代计算机中扮演的角色是指令 (instructions) 储存器：在当前的程序中它总是储存下一个将被执行的指令的地址。

一般来说，counter 需要支持以下三种操作 (我们把 counter 维护的 state 称为 "count")：

  • resetting the count to zero.
  • loading a new counting base.
  • incrementing/decrementing the count by 1.

Sequential chips design. 现在我们能对 sequential chips 下这样的定义：A sequential chip is a chip that embeds one or more DFF gates, either directly or indirectly.

DFF 的存在使 sequential chips 具有了 maintain state (memory units) 与 operate on state (counters) 的能力。技术上来说，DFF 通过引入时间延迟 (inherent time delay) 使得 feedback loop 成为了可能。

Sequential chips always consist of a layer of DFFs sandwiched between combinational logic layers

feedback loop 是一种 (directly or indirecrly) 将某个元件的输出作为其自身输入的结构。sequential chips 能够「记忆」的本质，即为通过 feedback loop 持续不断的将上一时刻的输出重新作为该时刻的输入。

这一结构只有在 DFF 创造的时间延迟基础上才得以存在；也就是说，combinatorial logic 下 feedback loop 的存在是非法的。由于时间的概念被忽视，combinational chips 的输入与输出可以看成是同时发生的：因此将其输出作为其自身输入将会产生 mutual dependence 的悖论。


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info:

Lecturer: Prof. Shimon Shocken, Prof. Noam Nisan.

Course textbook:

(Nisan N., Schocken S., 2008) The Element of Computing Systems: Building a Modern Computer from First Principles.

-----------------------------------そして、次の曲が始まるのです。-----------------------------------