本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
Week 1 notes
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))))
这样的函数也可以通过真值表来将其所有可能的结果列出,比如当 (x,y,z) = (1,0,1)
时,其真值表为:
# 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
的行# 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 的描述分为两个部分:
gate 根据复杂性也分为两种:
gate 的接口与逻辑函数的输入和输出是一致的,不同的是其实现的方法。
AND:
1
,灯灭 0
1
,关着的时候为 0
。显然,只有 relay a
和 b
都开着时,灯才会亮。物理层面的实现是 EE 的内容。CS 只关注功能实现。
Hardware Description Languge(HDL) 是一种允许设计者在电脑上设计并模拟测试硬件结构的语言。设计者可以通过 HDL 模拟硬件,并在硬件模拟器中使用,测试。一个典型的 HDL 程序应该包括如下的信息:
比如下面的例子:
/** 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);
}
HDL 是一种静态描述语言(functional & declarative)。HDL 的执行会在之后交给解释器执行,但 HDL 编程本身不涉及任何的执行。因此,HDL 可以以任意顺序书写。
即便如此,为了维护可读性,HDL 的约定是按照设计图,从左到右依次描述 gate.
根据上述的信息,可以将上面的逻辑转化为包含基础逻辑运算的 idea:
out = 1 when:
a And Not(b)
or
b And Not(a)
根据该 idea,可以进一步的将输入输出和逻辑运算转换为初步硬件设计图。具体可以分一下的步骤:
a
和 b
都产生了两路信号。以 a
为例,存在 a
和 Not(a)
的信号。我们需要根据这些信号将存在的链接画出来:如果设计中使用了别的成品 gate (off the shelf gate),其命名和输入输出必须严格按照其定义在设计图上标记。
接下来的工作是如何将上面的设计图用 HDL 表达出来。HDL 的描述也分为接口和实现两部分:
/** 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 的设计后,我们使用硬件模拟器对其进行测试。测试可以通过:
测试完毕后都会得到一个结果文件(compare files)用于验证测试结果。
测试的过程:
out
)
我们可以通过创建后缀为 .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 |
.out
file 的输出可以在 .tst
文件中设置:
//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;
comapare 文件是如何制作的?
就像我们生成 out 文件一样,compare 文件是通过正常的测试流程来制作的。唯一不同的是,我们使用高级语言(比如 JAVA),而不是 HDL 来制作 compare 文件。该过程被称为 Behavioral simulation。
.tst
).cmp
)
在硬件的设计过程中,有时候需要对一组 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 写成了类似数组一样的形式。
buses 中访问 bit 与数组中访问元素一致,都是使用下标访问。下标也是从 0 开始。比如 a
是一个 4bit 的 bus,访问其第一个 bit 的表达式为:
a = a[0];
下边是一个 4bit 按位 AND 的门的实现:
/* 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);
}
HDL 中的下标是从右到左的。 a[0] 是最右边一位 bit.
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];
根据上面的写法可以简单的实现一个将两个 8bit 数据合并为一个 16 bit 数据的门:
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]);
true
和 false
代表对应的(1 & 0)任意长度的输入输出:
Add16(a=true, b=false, out=out2);
internal pin 的带宽会被自动推断:
// single bit width
x = lsb[i];
//j-i+1 bit width
y = lsb[i..j];
internal pin 不允许使用下标访问,比如 y[i] 是非法的。
sel
的开启和关闭可以选择接入 a
还是 b
。sel
可以输入周期性的信号,可以使输出在 a
和 b
之前自动切换。$$\texttt{Mux(a, b, sel) = (a And Not(sel)) Or (b And sel)}$$
\[ \begin{align*} &\texttt{DMux(in, sel)} \\ &\texttt{a = in And Not(sel) }\\ &\texttt{b = in And sel} \end{align*} \]
作业中通常涉及到组多路的基础门。这种牵涉到多路的情况一般都是用一个多 bits 的 sel 来控制输出状态。只要搞清楚哪一位 bit 控制的是哪一个层级的 switch 即可。层级可以通过真值表来判断。比如 4 way 的需要用 00 01 10 11 来控制。如果 00 对应 a
, 01 对应 b
,发生变化的只有 index 0,因此其控制层级就为 sel[0]
。
另外一点需要注意的是区分多个输入和多个输出的情况: