======Week1====== //Week 1 notes// ---- ====Introduction==== * **How**: Implementation * **What**: Abstraction ==Multiple layers Abstraction== * 抽象层可以分为多层 * 任何的实现层都可以作为下一层的抽象层，通过接口提供功能即可 * 复杂的系统就是这么堆砌起来的 \\ {{ :cs:comp_n_arch:courses:fnti_i:abstraction_layers.jpg |}} ==Design a chip== 使用 hardware simulatior 来设计： // // {{ :cs:comp_n_arch:courses:fnti_i:design_chip.svg?350 |}} ==Folder Structures== {{ :cs:comp_n_arch:courses:fnti_i:class_contentes.jpg?500 |}} ====Boolean Functions and Gate Logic==== Boolean 使用 ''0'' 和 ''1'' 表示状态。 ===Boolean Logic=== ==Operations & Expressions== Boolean 的基础运算有三种：//AND / OR / NOT//。其结果可以用真值表（//Truth Table//）表示： \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:truth_table.svg?500 |}} \\ \\ 以上的这些逻辑运算可以组合成复杂的表达式，比如： 1 AND (0 OR (NOT (1))) 我们将其称为逻辑表达式。 ==Boolean Functions== 如果将表达式中的 ''0'' 和 ''1'' 以变量表示，那么得到的函数就被称为逻辑函数（//Boolean Functions//）： f(x,y,z) = (x AND (y OR (NOT (z)))) 这样的函数也可以通过真值表来将其所有可能的结果列出，比如当 ''(x,y,z) = (1,0,1)'' 时，其真值表为： \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:boolean_function.svg?200 |}} \\ \\ 可见逻辑函数可以用函数或真值表的方式来表达。 ==Boolean Indentites== # 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 ===Boolean Functions Synthesis=== 真值表是通过逻辑函数使用不同的变量计算出来的。但在硬件设计的过程中，这个过程是相反的。我们已经知道结果（真值表），而我们希望得到实现这个结果的功能（硬件/逻辑函数）。 ==将真值表转换为表达式== 一种方法是构建真值表的**析取范式** (//Disjunctive Normal Form//)。其步骤： - 按行遍历真值表，找出所有函数值为 ''1'' 的行 - 对每符合条件的行，写出一个能够得到函数值的逻辑函数 - 将得到的所有符合条件的逻辑表达式，进行 **//OR//** 运算 比如下面的例子： // // {{ :cs:comp_n_arch:courses:fnti_i:truth_table_to_bool_exp.svg?200 |}} # 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) ==NP hard problem & Theorem== 上述的三个表达式进行 //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 function== 计算机学家们总结出了一种逻辑函数，//**NAND**//，用于作为构建逻辑表达式的基础。其真值表如下： \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:nand.svg?150 |}} \\ \\ 其逻辑表达式为： $$ \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)) ===Logic Gates=== **门**（//Gate//，也称为(//Chip//)）是一种实现了逻辑函数的**物理设备**。gate 的描述分为两个部分： * 接口（//Interface//）来诠释其功能。其 obstruction 只能有一种 * 实现：可以有非常多种 gate 根据复杂性也分为两种： * //Elementary（Primitive） gate//: 比如 //AND, OR, NOT, NAND//。 *// Compulicated gate//：通过组合基础逻辑运算的逻辑函数的实现。 gate 的接口与逻辑函数的输入和输出是一致的，不同的是其实现的方法。 ==Elementary logic gates: NAND== //**Diagram:**// \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:nand_gate_1_.svg?200 |}} \\ //**Specification:**// if (a==1 and b==1) out = 0 else out = 1 ==Elementary logic gates: And, Or, Not== {{ :cs:comp_n_arch:courses:fnti_i:and_or_not.svg?450 |}} ==Composite gates== //Composite gate// 由基础门组合而来。比如下面的 Three way And，实际上是通过两个基础 and gate 构建的： \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:3_way_and.svg?400 |}} \\ 可以看到前者是**接口**，而后者是**实现**。 ==Circuit implementations exmaple== //**AND：**// * 使用了灯泡来表示 output，灯亮为 ''1''，灯灭 ''0'' * 使用了//relay// 来作为输入：开着的时候为 ''1''，关着的时候为 ''0''。显然，只有 //relay// ''a'' 和 ''b'' 都开着时，灯才会亮。 {{ :cs:comp_n_arch:courses:fnti_i:circuit_and.svg?200 |}} //**Or：**// * 任意一个 //relay// 连上时，灯都会亮： {{ :cs:comp_n_arch:courses:fnti_i:circuit_or.svg?200 |}} 物理层面的实现是 EE 的内容。CS 只关注功能实现。 ===Design with HDL=== //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); } //HDL// 是一种静态描述语言（//functional & declarative//）。//HDL// 的执行会在之后交给解释器执行，但 //HDL// 编程本身不涉及任何的执行。因此，//HDL// 可以以任意顺序书写。 \\ \\ 即便如此，为了维护可读性，//HDL// 的约定是按照设计图，**从左到右**依次描述 gate. ==Design I : General Idea== 以 //XOR// 为例。在最开始设计时，我们会得到硬件的结果信息，大多数情况下是真值表。根据真值表，我们可以反推出需要实现的逻辑函数是什么，比如 //XOR// 的逻辑函数可以通过其真值表的第二第三行判断： \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:xor_1.jpg?400 |}} ==Design II : Gate diagram== 根据上述的信息，可以将上面的逻辑转化为包含基础逻辑运算的 idea： out = 1 when: a And Not(b) or b And Not(a) 根据该 idea，可以进一步的将输入输出和逻辑运算转换为初步硬件设计图。具体可以分一下的步骤： - 画出该硬件的**边界**：边界外部的内容是接口，内部的内容是实现：\\ \\ {{ :cs:comp_n_arch:courses:fnti_i:xor_ii.jpg?400 |}}\\ - 根据之前 idea 中的逻辑，''a'' 和 ''b'' 都产生了两路信号。以 ''a'' 为例，存在 ''a'' 和 ''Not(a)'' 的信号。我们需要根据这些信号将存在的链接画出来： - 画出每一个链接 - 对每个链接都给与有意义的命名\\ \\ {{ :cs:comp_n_arch:courses:fnti_i:xor_ii_b.jpg?450 |}} 如果设计中使用了别的成品 gate (//off the shelf gate//)，其**命名和输入输出**必须严格按照其定义在设计图上标记。 ==Design III: Describing diagram with HDL== 接下来的工作是如何将上面的设计图用 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); } ===Hardware simulation=== 当完成 //HDL// 的设计后，我们使用硬件模拟器对其进行测试。测试可以通过： * 模拟器本身（//Interactive//） * Scripting Based 测试完毕后都会得到一个结果文件（//compare files//）用于验证测试结果。 ==Interactive simulation== 测试的过程： - 加载 HDL - 赋予输入端不同的数据（0 & 1） - 验证结果： - out pins (''out'') - internal pins ==Scirpt-based simulation== 我们可以通过创建后缀为 ''.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; ==Result file== 测试后，模拟器会返回一个后缀为 ''.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; ==compare file== 对于比较复杂的检测，我们不可能去一位一位的检查结果是否正确。通用的做法是使用 ''.cmp'' 文件存储正确的真值表结果，并使用之前生成的 ''.out'' 文件与其进行对比。比较的过程是**按行**比较，如果两行不相同，那么模拟器会报错。\\ \\ ''.cmp'' 文件的指定也是在 ''.tst'' 文件中设置： // compare result with file compare-to Xor.cmp; //**comapare 文件是如何制作的？**// \\ \\ 就像我们生成 out 文件一样，compare 文件是通过正常的测试流程来制作的。唯一不同的是，我们使用**高级语言**（比如 JAVA），而不是 HDL 来制作 compare 文件。该过程被称为 //Behavioral simulation//。 ==硬件开发的流程== - 首先由系统架构师提出需求，并交由团队中的所有人来讨论实现方法 - 系统架构师来决定哪些基础芯片需要设计 - 对于每个基础芯片，系统架构师会指定 - 芯片的 API - 测试脚本（''.tst''） - 校验文件（''.cmp''） - 开发者进行开发（使用 HDL） ===Multi-Bit Buses=== 在硬件的设计过程中，有时候需要对一组 //bit// 进行操作（比如数字，就可以被视作是一组 16 位 的 bit）。这一组 //bit// 往往被我们视作整体，并称之为 **//buses//**（拉丁语，many or multiple 的意思）。为了支持此类操作， //HDL// 中提供了相应的实现方法。 \\ \\ 以两个数字相加为例，门实际上接收的是两个 16 bit 的数据，返回的是一个 16 bit 的数据： \\ \\ {{ :cs:comp_n_arch:courses:fnti_i:add_gate.jpg?350 |}} ==buses in HDL== 上述的 gate 在 HDL 的定义可以写为： /* Adds two 16-bit values */ CHIP Add16 { IN a[16], b[16]; OUT out[16]; PARTS: //... } 其中 //Buses// 写成了类似数组一样的形式。 ==在 buses 中访问 Bit== //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 作为输出值== //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]); } ==sub-buses 的使用== 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 =...); ==buses 的几个惯例== 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]// 是非法的。 ===Elementary Gates=== ==Not Gate== {{ :cs:comp_n_arch:courses:fnti_i:not_imp.svg?300 |}} $$\texttt{Not(a) = a Nand a}$$ ==And Gate== {{ :cs:comp_n_arch:courses:fnti_i:and_imp.svg?300 |}} $$\texttt{a And b = Not(a Nand b)}$$ ==Or Gate== {{ :cs:comp_n_arch:courses:fnti_i:or_imp.svg?600 |}} $$\texttt{a Or b = Not(Not(a) And Not(b))}$$ ==Xor Gate== {{ :cs:comp_n_arch:courses:fnti_i:xor_imp.svg?600 |}} $$\texttt{a Xor b = (Not(a) And b) Or (a And Not(b))}$$ ==Mux Gate== * //Multiplexor//(Mux) 充当了一个 switch 的角色，通过 ''sel'' 的开启和关闭可以选择接入 ''a'' 还是 ''b''。 * ''sel'' 可以输入周期性的信号，可以使输出在 ''a'' 和 ''b'' 之前自动切换。 {{ :cs:comp_n_arch:courses:fnti_i:mux.jpg |}} * 实现： {{ :cs:comp_n_arch:courses:fnti_i:mux_imp.svg?600 |}} $$\texttt{Mux(a, b, sel) = (a And Not(sel)) Or (b And sel)}$$ ==DMux Gate== * //Demultiplexor//(Dmux) 是 Mux 的反向操作，可以将单个输入分解为两个输出 {{ :cs:comp_n_arch:courses:fnti_i:dmux.jpg |}} * 实现： {{ :cs:comp_n_arch:courses:fnti_i:dmux_imp.svg?450 |}} \[ \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]''。\\ \\ 另外一点需要注意的是区分多个输入和多个输出的情况： * 多个输入的情况，输入的时候需要先通过低层级的选择器筛选，才能将结果交给更高层级的门进行运算 * 多个输出的情况则完全相反；首先需要从最高层级进行划分，再对 sub-group 进行次层级的选择，以此类推。 ====References==== * [[https://drive.google.com/file/d/1dPj4XNby9iuAs-47U9k3xtYy9hJ-ET0T/view|HDL guide]] * [[https://drive.google.com/file/d/1IsDnH0t7q_Im491LQ7_5_ajV0CokRbwR/view|The Hack Chip Set]]