Week 1 notes

• How: Implementation
• What: Abstraction

• 抽象层可以分为多层
• 任何的实现层都可以作为下一层的抽象层，通过接口提供功能即可
• 复杂的系统就是这么堆砌起来的

使用 hardware simulatior 来设计：

Boolean 使用 0 和 1 表示状态。

Boolean 的基础运算有三种：AND / OR / NOT。其结果可以用真值表（Truth Table）表示：



以上的这些逻辑运算可以组合成复杂的表达式，比如：

1 AND (0 OR (NOT (1)))

如果将表达式中的 0 和 1 以变量表示，那么得到的函数就被称为逻辑函数（Boolean Functions）：

f(x,y,z) = (x AND (y OR (NOT (z))))

# Commutative
(x AND y) = (y AND x)
(x OR y) = (y OR x)

# Associative
(x AND (y AND z)) = ((x AND y) AND z)
(x OR (y OR z)) = ((x OR y) Or z)

# Distributive
(x AND(y OR z)) = (x AND y) OR (x AND z)
(x OR(y AND z)) = (x OR y) AND (x OR z)

# De Morgen (when NOT involved)
NOT(x AND y) = NOT(x) OR NOT(y)
NOT(x OR y) = NOT(x) AND NOT(y)

#Idenpotence 
x AND x = x

#Double Negation
NOT(NOT(x)) = x

真值表是通过逻辑函数使用不同的变量计算出来的。但在硬件设计的过程中，这个过程是相反的。我们已经知道结果（真值表），而我们希望得到实现这个结果的功能（硬件/逻辑函数）。

一种方法是构建真值表的析取范式 (Disjunctive Normal Form)。其步骤：

1. 按行遍历真值表，找出所有函数值为 1 的行
2. 对每符合条件的行，写出一个能够得到函数值的逻辑函数
3. 将得到的所有符合条件的逻辑表达式，进行 OR 运算

比如下面的例子：

# line 1
NOT(x) AND NOT(y) AND NOT(z)
# line 3
NOT(x) AND y AND NOT(z)
# line 5
x AND NOT(y) AND NOT(z)

上述的三个表达式进行 OR 运算以后，还存在着化简的空间。化简的结果可能存在多种，也存在一个最短的表达式。我们将求这个最短表达式的问题称为NP困难问题 （NP hard problem)。

但无论如何，已经被证明的是：

Any Boolean function can be repersented using an expression contining AND, OR, NOT operations.

也就是说，无论效率怎样，所有的逻辑函数，都是可以通过有限的逻辑运算来表达的。不过，该定理可以被进一步的简化：

Any Boolean function can be repersented using an expression contining AND, NOT operations.

证明的过程很简单：如果可以用 AND 和 NOT 表示 OR，那么上面的推论就是成立的：

# proof
# using De Morgen
(x OR y) = NOT(NOT(x) AND NOT(y))

计算机学家们总结出了一种逻辑函数，NAND，用于作为构建逻辑表达式的基础。其真值表如下：



其逻辑表达式为： $$ \texttt{(x NAND y) = NOT (x AND y)} $$ NAND 的好处在于，只要使用这么一个逻辑运算，就能表达出所有的逻辑表达式。证明的过程也很简单：只要证明 NAND 既可以实现 AND，又可以实现 NOT 即可：

## proof 
# NOT
NOT(x) = (x NAND x)
# AND
(x AND y) = NOT(x NAND y) -> ((x NAND y) NAND (x NAND y))

门（Gate，也称为(Chip)）是一种实现了逻辑函数的物理设备。gate 的描述分为两个部分：

• 接口（Interface）来诠释其功能。其 obstruction 只能有一种
• 实现：可以有非常多种

gate 根据复杂性也分为两种：

• Elementary（Primitive） gate: 比如 AND, OR, NOT, NAND。
• Compulicated gate：通过组合基础逻辑运算的逻辑函数的实现。

gate 的接口与逻辑函数的输入和输出是一致的，不同的是其实现的方法。

Diagram:


Specification:

if (a==1 and b==1)
    out = 0
else
    out = 1

Composite gate 由基础门组合而来。比如下面的 Three way And，实际上是通过两个基础 and gate 构建的：


可以看到前者是接口，而后者是实现。

AND：

• 使用了灯泡来表示 output，灯亮为 1，灯灭 0
• 使用了relay 来作为输入：开着的时候为 1，关着的时候为 0。显然，只有 relay a 和 b 都开着时，灯才会亮。

Or：

• 任意一个 relay 连上时，灯都会亮：

Hardware Description Languge(HDL) 是一种允许设计者在电脑上设计并模拟测试硬件结构的语言。设计者可以通过 HDL 模拟硬件，并在硬件模拟器中使用，测试。一个典型的 HDL 程序应该包括如下的信息：

• Interface
  • 硬件的功能描述
  • 硬件名
  • 硬件的输入输出
• Implementaion

比如下面的例子：

/** API documentation: what the chip does. */
CHIP ChipName {
IN inputPin1, inputPin2, ... ;
OUT outputPin1, outputPin2, ... ;
PARTS:
// Here comes the implementation.
chipPart(connection, ... , connection);
chipPart(connection, ... , connection);
}

以 XOR 为例。在最开始设计时，我们会得到硬件的结果信息，大多数情况下是真值表。根据真值表，我们可以反推出需要实现的逻辑函数是什么，比如 XOR 的逻辑函数可以通过其真值表的第二第三行判断：

根据上述的信息，可以将上面的逻辑转化为包含基础逻辑运算的 idea：

out  = 1 when:
    a And Not(b)
or
    b And Not(a)

1. 画出该硬件的边界：边界外部的内容是接口，内部的内容是实现：
   
   
   
2. 根据之前 idea 中的逻辑，a 和 b 都产生了两路信号。以 a 为例，存在 a 和 Not(a) 的信号。我们需要根据这些信号将存在的链接画出来：
   1. 画出每一个链接
   2. 对每个链接都给与有意义的命名
      
      

接下来的工作是如何将上面的设计图用 HDL 表达出来。HDL 的描述也分为接口和实现两部分：

• 接口（header）：描述目标芯片 的输入输出（XOR）
• 实现：从左到右描述所有实现中用到的芯片的输入输出，以设计图中的命名（Inner Pins）：

/** out = (a And Not(b)) Or (Not(a) And b)) */
CHIP Xor {
   IN a, b;
   OUT out;
   /* implementations */
   PARTS:
   Not(in = a, out = nota);
   Not(in = b, out = notb);
   And(a = a, b = notb, out = aAndNotb);
   And(a = nota, b = b, out = notaAndb);
   Or(a = aAndNotb, b = notaAndb, out = out);
}

当完成 HDL 的设计后，我们使用硬件模拟器对其进行测试。测试可以通过：

• 模拟器本身（Interactive）
• Scripting Based

测试完毕后都会得到一个结果文件（compare files）用于验证测试结果。

测试的过程：

1. 加载 HDL
2. 赋予输入端不同的数据（0 & 1）
3. 验证结果：
   1. out pins (out)
   2. internal pins

我们可以通过创建后缀为 .tst 的文件来手动指定需要运行的测试。下面脚本示例可以用于测试 XOR：

// loading file
// every chips reload before each testing
load Xor.hdl;

// series of test command
set a 0, set b 0, eval;
set a 0, set b 1, eval;
set a 1, set b 0, eval;
set a 1, set b 1, eval;

测试后，模拟器会返回一个后缀为 .out 的结果文件。如果我们的 HDL 正确，那么返回的结果会与真值表一致。比如 XOR 正确的返回：

|   a   |   b   |  out  |
|   0   |   0   |   0   |
|   0   |   1   |   1   |
|   1   |   0   |   1   |
|   1   |   1   |   0   |

//setting output file
output-file Xor.out;

//output
set a 1,
set b 1,
eval,
output;

对于比较复杂的检测，我们不可能去一位一位的检查结果是否正确。通用的做法是使用 .cmp 文件存储正确的真值表结果，并使用之前生成的 .out 文件与其进行对比。比较的过程是按行比较，如果两行不相同，那么模拟器会报错。

.cmp 文件的指定也是在 .tst 文件中设置：

// compare result with file
compare-to Xor.cmp;

1. 首先由系统架构师提出需求，并交由团队中的所有人来讨论实现方法
2. 系统架构师来决定哪些基础芯片需要设计
3. 对于每个基础芯片，系统架构师会指定
   1. 芯片的 API
   2. 测试脚本（.tst）
   3. 校验文件（.cmp）
4. 开发者进行开发（使用 HDL）

在硬件的设计过程中，有时候需要对一组 bit 进行操作（比如数字，就可以被视作是一组 16 位 的 bit）。这一组 bit 往往被我们视作整体，并称之为 buses（拉丁语，many or multiple 的意思）。为了支持此类操作， HDL 中提供了相应的实现方法。

以两个数字相加为例，门实际上接收的是两个 16 bit 的数据，返回的是一个 16 bit 的数据：

上述的 gate 在 HDL 的定义可以写为：

/* Adds two 16-bit values */
CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    //...
}

buses 中访问 bit 与数组中访问元素一致，都是使用下标访问。下标也是从 0 开始。比如 a 是一个 4bit 的 bus，访问其第一个 bit 的表达式为：

a = a[0];

/* ANDs together all 4 bits of the input*/

CHIP And4Way {
    IN a[4];
    OUT out;

    PARTS:
    AND (a = a[0], b = a[1], out = t01);
    AND (a = t01, b = a[2], out = t012);
    AND (a = t012, b = a[3], out = out);
}

buses 本身也可以作为芯片的输出，这使得按位返回得以实现。比如下面的芯片实现了按位 AND 并按位返回的效果：

/* 
Computers a bit-wise and of its two 4-bits input buses
*/

CHIP And4 {
    IN a[4], b[4];
    OUT out[4];

    PARTS:
    AND (a = a[0], b = b[0], out = out[0]);
    AND (a = a[1], b = b[1], out = out[1]);
    AND (a = a[2], b = b[2], out = out[2]);
    AND (a = a[2], b = b[3], out = out[3]);
}

HDL 允许定义子bus。写法如下：

//a full bus
a[16];
//two sub buses
a[0..7];
a[8..15];

IN lsb[8], msb[8];
OUT a[16];
Add16[a[0..7] = lsb, a[8..15] = msb, b=..., out =...);

sub-buses 输出时，允许基于 output buses 的带宽来进行重叠：

// 16bits input is truncated in 14bits output
Add16(a=Bus1[0..15], b=Bus2[0..15], out[0..14]=out2[0..14]);

Add16(a=true, b=false, out=out2);

// single bit width
x = lsb[i];
//j-i+1 bit width
y = lsb[i..j];

$$\texttt{Not(a) = a Nand a}$$

$$\texttt{a And b = Not(a Nand b)}$$

$$\texttt{a Or b = Not(Not(a) And Not(b))}$$

$$\texttt{a Xor b = (Not(a) And b) Or (a And Not(b))}$$

• Multiplexor(Mux) 充当了一个 switch 的角色，通过 sel 的开启和关闭可以选择接入 a 还是 b。
• sel 可以输入周期性的信号，可以使输出在 a 和 b 之前自动切换。

• 实现：

$$\texttt{Mux(a, b, sel) = (a And Not(sel)) Or (b And sel)}$$

• Demultiplexor(Dmux) 是 Mux 的反向操作，可以将单个输入分解为两个输出

• 实现：

\[ \begin{align*} &\texttt{DMux(in, sel)} \\ &\texttt{a = in And Not(sel) }\\ &\texttt{b = in And sel} \end{align*} \]

• HDL guide
• The Hack Chip Set