二进制

抽象

借助于抽象的威力，年迈的祖母可以通过计算机上网，而不用考虑电子的量子波动或计算机中的存储器组织问题。

抽象是必要的，略去了可以忽略的复杂性：

  • 应用软件：程序
  • OS：设备驱动程序
  • 体系结构：指令寄存器
    • 程序员观点的计算机抽象
  • 微结构：数据路径控制器
    • 将逻辑和微结构连接在一起
    • 将逻辑组件组合在一起以实现体系结构中定义的指令
  • 逻辑：加法器、存储器
    • 利用数字电路构建更复杂的组件，如加法器、寄存器
  • 数字电路：与门、非门
    • 将电压控制在离散范围内表示0/1
    • 数字电路是模拟电路的子集
  • 模拟电路：放大器、滤波器
    • 输入输出都是连续的电压值
  • 器件：晶体管、二极管
    • 器件具有明确的外部连接点，成为端子
  • 物理学：电子

一个具有NN个状态的离散值变量的信息量D=log⁡2ND=\log _2Nbits，一个二进制状态量包含1位的信息。

编码

原码、反码、补码

在补码中，正数最高位都是0，负数最高位都是1，这样保证了在进位时加法的正确性（利用了数位的溢出）

最高位可以看作符号位，但是其他数位的解释和原码中的负数有所不同：取反加一，使得能够实现加法

补码可以表示范围[−2N−1,2N−1−1][-2^{N-1},2^{N-1}-1]，没有-0

当二进制补码扩展到高数位时，需要将最高位一次复制到扩展的数位中，如3（0011）变为（0000011），-3（1101）变为（1111101）

逻辑门

门后如果有气泡，表示取反操作

  • N输入与 AND门在所有输入为1时输出为1

  • N输入或门OR在有一个输入为1时输出为1

  • N输入异或门XOR在有奇数个输入1时输出为1

逻辑电平

通过定义逻辑电平，将连续变量映射到离散的二进制值

驱动源产生输出：

  • LOW：0~VOLV_{OL}
  • HIGH：VOHV_{OH}~VODV_{OD}

接收端输入：

  • LOW：0~VILV_{IL}
  • HIGH：VIHV_{IH}~VDDV_{DD}

VOHV_{OH}和VOLV_{OL}称为高/低输出逻辑电平

VIHV_{IH}和VILV_{IL}称为高/低输入逻辑电平

中间称为禁止区域

噪声容限

噪声容限：输出上加入噪声，但依然可被输入检测到正确的逻辑电平

低电平噪声容限：NHL=VIL−VOLNH_L=V_{IL}-V_{OL}

低电平噪声容限：NHH=VOH−VIHNH_H=V_{OH}-V_{IH}

image-20230811173925884

逻辑电平的界定

对于非门，输出-输入电压的变换如下图所示：

image-20230811185944107

可以看到并不是一个良好的线性变化。理想的反应器应该在V=VDD2V=\frac{V_{DD}}{2}处产生一个跳变，但实际上并非如此。一种处理方式是选取dV(Y)/dV(A)=−1dV(Y)/dV(A)=-1的位置，在图像中会有两个位置，称为单位增益点，也即VIL,VIHV_{IL},V_{IH}，在这个两个点，可以最大化噪声容限，如果VILV_{IL}增加一点，那么VOHV_{OH}会显著降低，如果VILV_{IL}减小一点，那么VOHV_{OH}仅会增加一点。

晶体管

晶体管，即MOS管，是控制电子导通的开关。

称Ⅴ族元素为n类半导体，称Ⅲ族元素为p类半导体。p类硅和n类硅之间的连接点称为二极管。n类区域为阳极，p类区域为阴极。

n型的载流子为电子，p型为空穴，电子流动速度比空穴快，因而n型速度比p型快。晶体管数量越多越明显。

晶体管利用了半导体在电压高于一定值后导通的特点作为开关：由电压控制的开关

image-20230811213240685

衬底是硅晶片，一般接地。栅极过去是金属，现在是多晶硅。栅极与衬底之间的SiO2SiO_2形成了电容。具体的导通原理见黑书P18。nMOS在p型衬底上有两个与栅极相连的n型掺杂区。pMOS则相反。

栅极是控制极，栅极的电压和导通的电压无关。导通的电压是源极和漏极之间的，栅极电压只是一个控制信号。真正的导通是源极漏极之间。

nMOS在栅极电压为高电平时导通，但导通低电平容易。pMOS在栅极电压为低电平时导通，但导通高电平容易，这是本身的性质

工作原理

在MOS结构中，金属和半导体衬底之间的极薄SiO2绝缘层形成了一个电容。

对于nMOS，当正电压加在电容的上表面，建立一个电场，上层吸引电子。当电压足够大时，大量的电子积聚在栅极下层，使此区域由p型转变为n型，有一个从n型沟道到n型漏极之间的通道。反转区称为沟道，是n到p的电流通道，电流可以从源极流到漏极，晶体管处于导通状态。

此电压，栅极电压，也称为门限电压，一般在0.3~0.7V左右。

image-20230811213839391

而对于pMOS，则正好相反。其衬底电压为V_DD，当为其时，处于截止状态，为0时，沟道反转为p类型，处于导通状态。

逻辑门

利用MOS馆的导通特性，在GND和VDDV_{DD}之间构造门，在不同的输入条件下输出不同的电平。

以与非门为例：

image-20230811221624688

上拉网络并联，只要有一个输入为高电平，nMOS管导通，则整体输出为高电平。下拉网络串联，当且仅当全部输入为低电平才输出为低电平。

在具有正常功能的逻辑门中，上拉或下拉网络必然有一个导通，一个截止。即pMOS并联时nMOS必串联，反之。这是因为一定要让电路有一个确定的输出值，而不是悬空在高低电平之间。

传输门

nMOS可以很好导通0，pMOS可以很好导通1，利用这两个特性构造一个理想的开关：传输门。

传输门是双向的，不区分输入和输出。控制信号称为使能。

image-20230901194107315

类nMOS逻辑

n型的载流子为电子，p型为空穴，电子流动速度比空穴快，因而nMOS速度比pMOS快。晶体管数量越多越明显。

为了提高速度，会使用类nMOS逻辑：将上拉网络中的pMOS替换为单个始终导通的pMOS，称为弱上拉。这个弱上拉pMOS满足当所有nMOS不导通时，其可以维持输出高电平。但只要有一个nMOS导通，就能将压过这个弱上拉，将输出拿到地，产生逻辑0。

输出为低电平时，弱pMOS和所有nMOS都导通，在电源和地之间产生短路，持续消耗能量，需谨慎使用。

image-20230811223059294

功耗

系统需要将电容充电，产生动态功耗，分为静态功耗和动态功耗。

动态功耗是信号在0和1之间变化过程中电容充电所耗费的能量。

静态功耗是信号不变时，系统处于空闲状态下的功耗。

真实的世界是模拟世界，但是数字电路将模拟值约束起来，仅仅使用可能信号的离散子集

组合逻辑设计

组合逻辑电路概要

数字电路中，电路是可以处理离散值变量的网络。

含有：

  • 离散值输入端
  • 离散值输出端
  • 描述输入和输出关系的功能规范
  • 描述当输入改变时输出响应延迟的时序规范

数字电路又可分为组合电路和时序电路。

组合电路：输出值仅取决于输入的序列

  1. 每个电路组件本身都是组合电路
  2. 每一个电路节点或者时一个电路的输入，或者仅仅连接到一个电路组件的输出端口
  3. 电路不能包含回路

布尔代数

和离散数学的数学意义一致。化简得到最小项的意义在于得到最简单的电路。

最好的：门的数量最少、速度最快、设计时间最短、花费最少、功耗最大等等

非法值和浮空值

非法值X

表示电路节点有未知或非法值。也可以用来表示没有初始化的值

浮空值Z

表示既没有被高电平，也没有被低电平驱动，称为浮空、高阻态。

时序逻辑设计

时序的基本概念

时序问题的关键：如何让电路运行的最快。真实的电路传递的电压值是连续值，会有时间上的先后变化，不是立即的。

传播延迟tpdt_{pd}：通过电路中关键路径（最长）的延时。

最小延迟tcdt_{cd}：从有信号输入，到输出信号改变，即最短的延时。

数据/控制关键

实际的电路会有数据信号和控制信号两种，哪一种信号晚到达，则曾这个电路为该型号关键。

控制关键：数据输入在控制输入前到达，则采用最短控制-输出延迟的设计方案

数据关键：控制输入在数据输入前到达，则采用最短数据-输出延迟的设计方案

毛刺

由于信号的传播需要时间，在不同信号先后到达的情况下，输出信号可能会出现多次波动，称该现象为毛刺。如：

image-20230901212144263

这个电路的输出信号会发生如图的波动，短暂的0状态即为毛刺。在电路最后稳定时，毛刺消失。

通过增加电路元件可以消除毛刺，但总有些电路的毛刺是无法消除的。毛刺的关键不在于消除之，而是要意识到毛刺的存在。

锁存器和寄存器

时序逻辑的输出值取决于当前的输入值和先前的输入值。

锁存器和寄存器都能储存信息，区别在于在何时更新自身储存的值。

S-R锁存器

S-R锁存器的特殊之处在于当R和S输入都是0时，Q将保持原来的值不变，记住了之前的内容。

S-R锁存器是一个在Q上存储1位状态（两个稳态，可以存储log⁡22=1\log_22=1位信息）的双稳态元件。

image-20230902094633309

D锁存器

锁存：将信息锁在自身中，利用时钟信号CLK作为是否更新信息的“钥匙”

image-20230902094553591

当CLK=0时，R=0，S=0，Q=Qprev,Q‾=Qprev‾Q=Q_{prev},\overline{Q}=\overline{Q_{prev}}

当CLK=1时，R=D，S=D，Q‾=D‾\overline{Q}=\overline{D}

当时钟信号变化时，在每个高电平，D锁存器将输出（存储）的信息更新为输入值D。D锁存器是电平敏感锁存器。

D触发器

D触发器是很关键的。需要深入理解D触发器的**“在时钟沿更新值”**

简单的D触发器由两个D锁存器组成，通过一个非门实现接受相反的时钟信号，在不同的时钟信号电平时进行不同的操作。左边的锁存器称为主锁存器，右边的称为从锁存器。

image-20230902095320986

当CLK=0时，主锁存器将输出Q1更新为输入D，但此时中间输入N1对从锁存器无效，输出Q依然是之前的状态Q0。

当CLK=1时，主锁存器依然维持原先状态，此时从锁存器将信息更新为中间输入N1，输出Q变为输入D。即使在CLK由0-1的变化过程中，D发生了改变，输出也依然是D。

在宏观上看，只有CLK的输入由0变为1的这个过程，触发器的值才会更新，对于其他状态：CLK=0、CLK=1、CLK由1变为0，在整体上看触发器依然保持原先的输出不变，故称为D触发器在时钟上升沿更新自身值。

值得注意的是，数字信号高低电平只是对真实的抽象，实际的上升沿是连续的信号变化，故可理解为在这个过程中D触发器更新了值。

因而D触发器是时钟沿敏感的。

6740fddf00cdd6f952b8dd7805d1a769

使能端

使能端决定了触发器并不是在每个时钟沿都更新值，而是在使能端开启的时钟沿才更新。

这是一个很巧妙利用了复用器的设计：

image-20230902100533169

通过将Q回接到复用器中，保证了当使能端处于低电平时触发器的输出值不变，循环Q原来的状态。

image-20230902100702926

如果使用与门代替复用器，则无法将寄存器由1更新为0.

复位功能

复位分为同步和异步。将触发器的值更新为0.

同步即为在时钟上升沿更新为0：

image-20230902100855743

异步则是只要打开开关，任何时候都更新值为0，需要改变内部晶体管实现。

寄存器

寄存器的本质就是由共同时钟信号控制的多个D触发器。

image-20230902100321861

同步设计逻辑

对于时序电路而言有这样的一个问题：不同的路径会导致电信号到达的时间不同，可能会导致电路的不稳定状态。

组合逻辑电路的传播延迟是稳定的，将时序电路拆分为组合逻辑电路和保存有前一个状态的寄存器组成的时序电路，能够让传播延迟稳定。寄存器包含了系统的状态，总在时钟沿改变值，也称为同步与时钟信号：寄存器，等等你缓慢的时钟信号。

这样的同步时序电路，需要满足如下的条件：

  1. 每一个电路元件是寄存器或组合电路
  2. 至少有一个电路元件是寄存器
  3. 所有寄存器都接受同一个时钟信号
  4. 每个环路包含至少一个寄存器

两种常见的同步时序电路称为有限状态机和流水线。

有限状态机

构成一个有限状态机的六元组为：状态集合，输入集合，输出集合，状态转移函数，输出函数，初始状态。给定以上六个集合，函数或元素，就可以确定一个有限状态机。

据此，有限状态机具有以下特征：

  • 在任何时间点，状态、输入、输出均为给定的有限种情况之一。
  • 对于一对确定的当前状态和输入，只有一个固定且唯一的次态（下一个周期的状态）。
  • 对于一对确定的当前状态和输入，只有一种固定且唯一的输出情况。

Moore型的输出仅取决于机器的当前状态，Mealy型取决于当前状态和当前输入。

不是说输入就无法决定Moore型的输出，而是当前输入可能影响下一个周期的输出。

对于同功能的状态机，如果用两个实现，则可能Moore型要多出一两个状态，延后周期输出对应结果

具体实现

  1. 对状态进行二进制编码，将每一位作为一个输入
  2. 根据功能，画出对应的状态转换图、状态转换表，得到相应的最简布尔表达式
  3. 由布尔表达式绘制相应的电路图
    • 由于存在相应的状态转移，前一个状态会对当前造成影响，故需要寄存器存储上一个周期的状态
    • 在环路中实现了读取寄存器上一个状态-和当前状态（输入）共同作用-输出/影响下一个状态

可以将复杂的有限状态机拆分为多个相互作用的、更简单的状态机，往往结构更清晰，计算更简单。

由电路图得到状态机

  1. 分析电路，找到输入、输出、状态
  2. 写出对应的“真值表”，即考虑了不同的输入、状态
    • 事实上对于数字电路来讲，稳定后电路的信号总是可测的，所谓的状态就是不同电平的组合，找出不同状态的本质就是找出电路 的电平排列组合
  3. 分析得到电路的状态转移图、状态转移表，将一些电位组合成为状态码，可撇去无用信息
  4. 找出有限状态机

时序逻辑的时序

在正式情况下，信号不是稳定的，那么信号需要保持多久呢？在孔径时间内输入必须稳定，触发器才能产生明确意义的输出。时序元件的孔径时间用时钟沿之前稳定的建立时间和时钟沿之后稳定的保持时间定义。

并且正式情况下，时钟信号到达时序原件的时间也是不一致的。

需要考虑的延迟

以下图电路为例：

  • 时钟到输出Q的延时tpcqt_{pcq}
  • 时钟到输出Q的最小延迟tccqt_{ccq}
  • 建立时间tsetupt_{setup}
  • 保持时间tholdt_{hold}
  • 组合逻辑块之间的传播延迟tpdt_{pd}

image-20230902161732211

建立时间约束

给下一个时间周期预留时间：tpd<=Tc−(tpcq+tsetup)t_{pd}<=T_c-(t_{pcq}+t_{setup})

image-20230902161623796

保持时间约束

寄存器存储的上一状态，需要稳定到建立时间之后，这样才能达到时序作用：tccq+tcd>=tholdt_{ccq}+t_{cd}>=t_{hold}

tccqt_{ccq}和tcdt_{cd}是寄存器属性，通常难以控制，可以调控tholdt_{hold}，通常直接调整其为0，但保持时间又很重要，无法调和时需要重新设计电路

并行

通常将空间并行称为并行，时间并行称为流水线，据能够显著提高效率

延迟：任务从开始到结束所需要的时间

吞吐量：系统在单位时间内产生的任务数量

空间并行需要多套相同的硬件，时间并行需要将任务分为多段，但是流水线不需要提供新的硬件（除寄存器外），可以达到相同的效果。

并行的克星是依存关系：下一个任务依赖于前一个任务的结果

image-20230902162419485

数字模块

存储器

用触发器组成的寄存器是一种存储少量数据的存储器。存储器阵列可以有效存储大量数据。

存储器通常由一个二维存储单元阵列组成，可以读出或写入阵列的某一行，由地址决定，读出或写入的值称为数据。

一个有N位地址和M位数据的阵列有2N2^N行和MM列，每行数据称为一个字。

深度/字大小：有多少行。宽度：多少列

体系结构

汇编语言Mips

体系结构：指令集（汇编语言）和操作数（寄存器和存储器）来定义

微体系结构：寄存器、存储器、ALU和其他模块形成微处理器的特定方式。

由于硬件方面的原因，CPU 所直接处理的都是一条条二进制机器码指令。而这些单纯的机器码是很难以阅读和理解的，汇编语言是一种助记符：用一些符号代表特定含义的机器码，用标签（Label）来替代地址。

寄存器

对寄存器的访问速度远大于对存储器的访问速度，因而将少量常用的指令、数据保存到寄存器中。

MIPS通常有32个寄存器，其地址就是其编号（5位）。序号命名 $0~$31，也可以按照功能命名。

registers（也就是其地址） Name usage
$0 $zero 常量0
$1 $at 汇编器临时变量
$2-$3 $v0-$v1 函数返回值
$4-$7 $a0-$a3 函数参数
$8-$15 $t0-$t7 temp：临时变量
$16-$23 $s0-$s7 save：需要保存的变量
$24-$25 $t8-$t9 temp：临时变量
$26-``$27 $k0-$k1 操作系统临时变量
$28 $gp 全局指针
$29 $sp 栈指针
$30 $fp 帧指针
$31 $ra 函数返回地址

$0 始终为0，因为0经常在计算机程序中使用

存储器

Mips使用字节寻址寄存器，按照地址访问外部的存储器。在计算地址上，可以使任何一个寄存器的地址作为基地址+偏移量来访问对应的地址，但常用$0寄存器作为基地址（0的作用）

1
2
lw $s3, 1($0) # load word 读出
sw $s7, 5($1) # store word 写入

基地址+偏移量：访问了存储器的对应地址

对于偏移量的计算：Mips是字节地址，也就是说每个字节都有一个地址，但是lw和sw都是访问的一行，故每一行的地址相差字节数*行数差。一般来说（32位机器）每一行包含4个8位字节。

image-20230916112941346

大端存储：第0个字节在最高有效字节（字节寻址存储器的最左边）

小端存储：第0个字节在最低有效字节（字节寻址存储器的最左边）

对于十六进制数0x12345678，大端存储的表示方式是0x12 0x34 0x56 0x78，而小端存储的表示方式是0x78 0x56 0x34 0x12。

Mips中使用小端存储方式

立即数

立即数：常数的值可以即可被访问，采用16位补码

对立即数进行符号扩展：在高位赋值符号位，不改变补码立即数的值

指令

R指令：对3个寄存器操作

I指令：对2个寄存器和1个16位立即数操作

J指令（跳转）：对1个26位的立即数操作

所有的指令都以一个6位的op开始，若为0，则为R型，否则为I型或J型

R指令

R：register，是寄存器类型的缩写

32位指令的格式为：

image-20230916155859771

指令的操作码由op和funct组成，对于R指令，所有的op均为0，区别在于funct

前两个寄存器rs、rt是源寄存器，从中读出数据，rd为目的寄存器，向其写入数据。注意：rs、rt、rd和mips代码中的顺序不一致，需要做出区分

1
add rd rs rt # rd=rs+rt

I指令

I：immeduate type，代表立即数

指令格式为：

image-20230916160208580

通常将rs和imm作为源操作数，但有时也会把rt也作为源操作数

注意：在mips代码中，将目的寄存器放在最前面

1
op rt rs imm

但在机器代码中为：

1
op rs rt imm

这个顺序的不同是极其重要的重点

J指令

J：jump，为跳转类型

格式为：

image-20230916160932870

解释机器语言代码

  1. 将十六进制指令改写为二进制形式
  2. 查看前6为op，若为0则为R类型，否则为I或J型
    1. 若为R型，按照6op 5rs 5rt 5rd 6func的格式进行区分，翻译为对应的指令、寄存器地址
    2. 若不为R型，则按照op找到是I型还是J型，再按照类型进行区分
  3. 注意机器语言和汇编代码寄存器相对位置不一致的问题

指令地址

用机器语言编写的程序就是一个表示指令的32位数，将指令存储再存储器中。

一个指令32位，占4个字节，mips中存储器按字节索引，故相邻两条指令相差4

image-20230916165134090

标签所代表的地址偏移量

1
2
3
4
5
ori $t0,$0,4		#0x00003000
bne $t0,$t1,next	#0x00003004
nop				   #0x00003008
next:			   #0x0000300c
sw $t0,4($t1)		#0x00003010

以这里的next标签为例，和bne指令的地址所在差为8，但在实际计算中认为偏移量从0算起（即下一条指令差0），再除以4后（bne指令的要求）即为1。将next标签代表的指令放入指令中，得到对应的机器码

汇编程序

运算指令（逻辑、算数）

逻辑指令

逻辑指令包括and,or,xor,nor，如果指令中包含i则代表了回合立即数进行运算。指令为：

1
add rd rs rt

mips中没有not指令，可以用A NOR $0 = NOT A实现

移位指令

移位指令又逻辑左移sll，逻辑右移srl和算数右移sra，格式为：

1
sll rd rt imm	#rt中存储了待移位值

如果想要让移位位数为可变值，则有可变逻辑左移sllv，可变逻辑右移srlv，可变算数右移srav，格式为：

1
sllv rd rt rs	#r中存储了移位位数，rt为待移位值

算数指令

可以用addi生成16位常数：addi $s0 $0 0x114514

如果想要生成32位常数，则要拆分为两条指令：

1
2
lui $s0,0x114		#装入高位指令lui
ori $s0,$s0,0x514	#进行与操作实现拼接

对于乘除法，mips体系结构中有存放乘除法特殊用途的寄存器hi和lo，存放高位和地位：

  1. 两个32位数相乘得到一个64位数，高32位存放在hi，低32位存放在lo
  2. 除法商存放在lo，余数存放在hi

跳转

在顺序执行中，程序计数器执行一条指令后加4。分支指令改变程序计数器的值，跳过某段代码或返回执行之前的代码

  • 条件分支指令只有在测试为真时才跳转

  • 无条件分支称为跳转指令，直接跳转

通过跳转可以实现判断分支、循环的效果

条件分支

当两个寄存器值相等时，执行beq，当不等时，执行bne。

两条指令执行后不跳回：直接改变了程序计数器的值

跳转指令

有三个跳转指令：j、jal、jr

  • j指令直接跳转到标号所指的指令
  • jal指令和j类似，但将返回地址（jal指令的下一条指令）保存到寄存器$ra寄存器中
  • jr指令跳转到寄存器中保存的值对应的地址处

分支

利用bne指令实现跳转，达到if-else的效果

循环

根据某一个条件重复进行跳转，达到循环的效果

1
2
3
4
5
6
7
8
9
10
addi $s0,$s0,1	#对循环判断量赋初值
addi $s1,$s1,0	#计算量，相当于while() {++}
addi $t0,$0,128	#判断标志量

while:			#标签跳转实行效果
  beq $s0,$to,done	#相等时跳出循环
  sll $s0,$s0,1	    #对循环判断量判断之后等于标志量
  addi $s1,$s1,1
  j while
done:			#出口

大小比较

mips中提供了量值比较slt：slt rd rs rt，当rs<rt时，对rd赋值1，否则赋值0

尽管slt只能实现小于，但是beq一下就是大于：

1
2
3
4
slt $t1,$s0,$t0
beq $t1,0,done

#相当于if(s0>=t0) {}

数组

数组的本质是存储器中连续的地址空间