Computation Structure

Assembly Language 课程地址: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c10/c10s1/ 汇编语言是对指令集的抽象，用一些单词的缩写来替代指令集的opcode, 从而更容易记忆和理解。 本课程中使用的汇编语言叫USAM，课程Lab里面有详细的cookbook, 就不再记录了，下面主要记录图灵机相关的内容。 FSM的局限 FSM是一个很强大的计算模型，前面章节中我们已经用电路实现了通用FSM, 那么FSM是否可以计算所有能用数字设备计算的功能或者说函数呢？ 答案是不能，比如简单的括号匹配。因为FSM要靠状态来记住(和)的个数，当有一个长度无穷大的序列时，FSM便无法构造。 为了解决这个问题，Alan turing提出了图灵机的模型。 图灵机 图灵机的核心还是FSM, 不过现在多了一条无限长的纸带，FSM可以通过存储在纸带上的符号来记录额外的信息，从而避免了状态数过多而无法构造FSM的问题。 因为一段纸带上的符号可以被编码为一个整数，所以图灵机就是一个整数函数$y = TM_I(x)$。 其中$I$是用来标识特定功能即有特定FSM的图灵机，我们可以将FSM的真值表编码成数字来表示$I$。 Church’s Thesis $f(x) computable <=> for some k, all x f(x) = T_k[x]$ 该定理由图灵的老师Church提出，但目前并没有证明，不过已经被普遍接受（可能是还没找到反例吧）。 通用图灵机 对于不同的计算任务，其构造的FSM不同，所构造的图灵机便也不同，那么为了各种计算任务，就需要构造各种各样的图灵机（实际上只有FSM不同）。那么存在一种或者一个图灵机，能够计算所有图灵机能计算的函数吗？ 从21世纪的结果来看，当然是存在的！ 如上图所示，$U(k, j) = T_k[j]$是一个Universal Function, 实现这个函数的图灵机便是通用图灵机。 实际上，这里的关键在于$k$。 $k$在这里是表示program，理论上讲就是对FSM的编码，比如用FSM的真值表来编码，而从上层计算机的角度来讲的话，$k$就是可执行的二进制程序，而PC本身就是一个通用图灵机！通用图灵机的计算便是对$k$的interpret，实际上就是把$k$本身的计算步骤走一遍。 现在的各种编码算法，实际上就是把一个FSM编码成整数从而输入给通用图灵机。 不过由于内存的空间是有限的，所以实际中的计算机还是只能计算数据量不超过内存大小的任务。 Uncomputability 如下是一个不可计算函数的例子，也就是所谓的图灵停机问题。

Design Tradeoffs 课程地址 本章从CMOS的电能消耗出发，讲如何减少不必要的能量损失，同时也讲了很多时间和空间的tradeoff. Power dissipation 电路优化的几个metrics CMOS能耗 一个减小能耗的简单例子 Carry-select Adder 设计一个N位的加法器，最直观的设计就是把N个全加器串联。 但是这样的$t_{PD}$是$\theta(N)$级别的。 现在将一个32位的加法器分成两个16位的部分分别计算再组合，$t_{PD}$就差不多减小了一半。 按这个思路一直二分下去，$t_{PD}$便能达到$O(\log n)$。 Carry lookahead Adder(CLA) 从$C_{out}$的计算公式中可以看出，一个FA的输入可以转换成3个变量$P$,$G$和$C_{in}$ ，其中只有$C_{in}$需要该位的前一位的$C_{out}$。 如果知道了两个相邻位置的$P$和$G$，那么可以把这两位当作一个整体，计算出这个整体的$P$和$G$，这时$P$和$G$任然还保留着原来的性质，所以，我们可以用倍增来计算整个电路的$P$和$G$。 下图是一个8-bits的CLA的G&P generate的部分： 然后是计算Carry的方法： 完整版： Multiplier binary multiplication 就是普通的竖式乘法，但是要注意如果值是补码，那最高位的全值为$-2^{N-1}$而不是$2^{N-1}$。 如下是值为补码的情况： pipelined multiplier 虽然pipeline化了，但每个stage的$t_{PD}$还是$O(N)$的，主要问题在于要按行传递carry。 Carry-save multiplier 讲每行需要传递的carry降到下一行（反正都是加在同一列，所以对结果没影响），这样可以将每个stage的$t_{PD}$优化到$O(1)$，但是需要更多的行，也就是面积增加了。 用时序电路减少面积 求和->移位->求和。 Summary

Performance Measures 本章主要是讲pipeline的原理以及如何将一般的逻辑电路转换为pipeline，最后简单提到了一下异步电路和同步电路的区别。 Latency and Throughput Latency: the delay from when an input is established until the output associated with that input becomes valid. Throughput: The rate at which inputs or outputs are processed. Pipelined Circuites 如上图所示，在计算$P(X)$时，F和G一直处于空闲状态，那么有没有办法把这段时间利用起来呢？ 我们可以用寄存器来保持F和G的输出，从而在$P(X)$的工作时间内，可以让F和G去进行其他计算。 Pipelining Methodology 如上是将一般逻辑电路pipeline化的一般步骤 Circuit Interleaving Pipeline的瓶颈在于$t_{PD}$最大的那个module, 我们可以用如下的方式将两个相同的module组合在一起，提高throughput. 异步及同步 同一个module对于不同的输入，所需要的时间可能也不一样。按之前的CLK驱动来设计电路的话，计算CLK的时候需要用module的最长计算时间，才能保证正确性。但对于一些计算较快的输入，这样做肯定是浪费了时间的。 上图展示了用同步和异步两种方式来实现一个简单的握手协议，对于异步电路来说，不再需要全局的CLK，所以效率非常高，但实际设计非常困难；对于同步电路来说，不再需要靠CLK来在module之间传输数据，效率也提高了，虽然还是在CLK上升沿才会有数据输入输出，但CLK不需要用最长计算时间的输入来计算了。 这个简单的握手协议如下： In phase 1, when the upstream stage has a new output and GOT-X is deasserted, it asserts its HERE-IS-X signal and then waits to see the downstream stage’s reply on the GOT-X signal. In phase 2, the downstream stage, seeing that HERE-IS-X is asserted, asserts GOT-X when it has consumed the available input. In phase 3, the downstream stage waits to see the HERE-IS-X go low, indicating that the upstream stage has successfully received the GOT-X signal. In phase 4, once HERE-IS-X is deasserted, the downstream stage deasserts GOT-X and the transfer handshake is ready to begin again. Note that the upstream stage waits until it sees the GOT-X deasserted before starting the next handshake. ...

Finite State Machine 有穷自动机本身是一个比较简单的概念，不过这里的主要难点是考虑将异步信号转换为同步 课程地址: Finate State Machine 本课程中自动机的表示图 异步时钟 当电路中的时钟信号和输入变量的时钟信号不一样时，需要将输入的时钟信号转换为与电路时钟同步的信号，从而使得电路能正常工作。 The bounded-time Synchronizer 当IN和CLK的上升沿到来时间$t_{IN}$和$t_{CLK}$相差大于$t_{E}$时，Synchronizer将输出至少持续$t_{D}$时长的0或1。但如果IN和CLK的上升时间沿到来时间之差小于$t_E$时，就无法确定Synchronizer的输出。为什么无法确定？个人理解是因为上升沿实际是要一段时间才能完成的，如果两者上升沿到来时间相差太短，当CLK达到1时，IN可能还在中间。 那么该如何用逻辑电路来实现这个Synchronizer，当然要靠D-Register啦！ 上图是用D-Register实现的Synchronizer, 用$t_{setup}$和$t_{hold}$来充当$t_{E}$，看起来很美好，但还没有解决IN和CLK的上升沿同时到来的问题！ 当IN和CLK的上升沿同时到来时，可能会让D-latch进入metastable状态： 解决办法：加D-Register!

Combinational Logic 如何描述电子元件的功能 真值表 逻辑表达式 在输入变量比较多的时候，真值表就很难读/写了，所以逻辑表达式更加通用。 设计数字电路的步骤 写出真值表 写出逻辑表达式 用AND/OR/NOT三种基本逻辑门实现，或者用NAND/NOR/NOT三种逻辑门实现 因为CMOS本身就是Inverting的，所以实际中NAND/NOR更加通用。 Sum of products 将真值表中为1的项用OR连接起来就得到了相应的逻辑表达式。 在功能不变的情况下，为了减少逻辑门的数量，也就是减小$t_{pd}$和$t_{cd}$，就需要将逻辑表达式中的项数最小化。 卡诺图 卡诺图化简步骤 找出Implicants 合并 处理lenient Mux Decoder ROM Summary

CMOS MOSFET Overview Characters Two Flavors CMOS CMOS is Complementary Metal Oxide Semiconductor Two switches Inverter Basic usage of CMOS Timing specifications Propagation Delay Contamination Delay Summary

The Digital Abstraction 信息编码 信息的种类有各种各样，我们需要找到一种方式来表示这些信息。比如，生物的基因信息是通过DNA来记录和表达，在计算机中，所有的数据都是二进制，我们也需要一个物理介质来表达和存储这些二进制信息。 电压 目前用来存储和表达二进制信息的物理介质绝大部分都是使用电压，高电平表示1, 低电平表示0。 VTC和容错 VTC(voltage transfer characteristics)是用来表示一个电子原件的输入和输出电压关系的图，如下是一个Buffer的VTC： 其中$V_{IL},V_{IH},V_{OL},V_{OH}$是一个电子元件最重要的参数，解释如下（这里假设最高电压为1）： $V_{IL}$是低电平的输入有效范围，即如果输入电压为$[0,V_{IL}]$，就会被元件当成0处理。 $V_{IH}$是高电平的输入有效范围，即如果输入电压为$[V_{IH}, 1]$，就会被元件当成1处理。 $V_{OL}$是低电平的输出电压，即如果元件想输出0，则其输出电压应该为$[0, V_{OL}]$。 $V_{OH}$是高电平的输出电压，即如果元件想输出1，则其输出电压应该为$[V_{OH},1]$。 其中, $min(|V_{OL} - V_{IL}|, |V_{OH} - V_{IH}|)$即为该元件能容忍的噪声范围。 Summary

Basic of Information 信息是什么 信息是我们接收到的关于确实某个特定事件或者情况的数据。 量化信息 对于随机变量$X_i$，其发生的概率为$p_i$，则其传达的信息量为: $$I(x_i) = \log_2(\frac{1}{p_i})$$数据中的信息 假设收到data的概率$p_{data}$，则 $$I(data) = \log_2(\frac{1}{p_{data}})$$Entropy 信息论中的entropy： $$H(X) = \sum_{i=1}^{N}p_i\log_2(\frac{1}{p_i})$$其中$X$为随机变量。 物理中的entropy： $$ S = k\ln\Omega $$其中，$k$为玻尔兹曼常数 Meaning of Entropy 为了描述某一个随机变量$X$，需要传输一系列的数据，Entropy就是确定$X_i$发生与否的平均位数，即传输量。 编码 编码就是把一个数据集合映射为一系列二进制字符串。常见的编码是把英文字母用二进制来表示，比如如下表格： A B C D ABBC的编码 00 01 10 11 00 01 01 00 01 1 000 001 01 1 1 01 0 1 10 11 0 1 1 0（无法确定） 编码不能有二义性 二叉树编码 用二叉树的边当作0和1,叶子节点当作编码的值，可以去除二义性。 定长编码 所有值的编码长度都相等。 2的补码 即将二进制最高位的全值定为$-2^{N-1}$ 负数的补码，按位取反再加1,因为$-A = -1 - A + 1$ ...