计组理论
\(\mathcal{Author:gpf}\)
考题
10*单选
简答：逻辑函数化简、内存扩展（译码器生成片选信号、二维地址结构）、页式存储、cache命中率、mips汇编
概述
进制转换
组合逻辑
逻辑函数化简：吸收律、配项法……
多路选择器：74151、函数生成器
时序逻辑
有限状态机：moore、mealy型，状态转换图、表、函数表达式（考试说明再化简）
主存
二维地址结构、译码器生成片选信号
汇编
指令格式：操作码结构、指令长度（定长快、变长小）
各种指令：R、I、J
寻址方式
mips流水线
基本概念
数据冒险
cache
直接映射：区地址（tag）+区内快递至
命中率（能否替换）
中断
DMA、中断
浮点数
以单精度浮点数为例，浮点数共由以下3部分组成
- 1位数符S：0表示正数，1为负数
- 8位阶E（双精度为11位）：偏移量为 \(2^{n-1}-1\)
- 23位尾数m（双精度为52位）：规格化成小数点左侧为1，且1作为隐含位被忽略，即1.m
\((178.125)_{10}=(10110010.001)_2=1.0110010001\times2^{111}\) ：S=0，E=00000111+01111111=10000110，m=01100100010000000000000
单精度浮点数的表示约定：
| E | M | 浮点数N |
|---|---|---|
| 1-254 | 不为0 | 规范浮点数 \(N=(-1)^s\times1.m\times2^{E-127}\) |
| 0 | 0 | 0 |
| 0 | 不为0 | 非规范浮点数 \(N=(-1)^s\times0.m\times2^{-126}\) |
| 255 | 0 | 无穷（有正负） |
| 255 | 不为0 | NaN（不是一个数） |
组合逻辑
基础知识
晶体管类器件
P(positive)型半导体掺三价元素，导电以空穴为主；N(negtive)型半导体掺五价元素，导电以电子为主。
PN结（晶体二极管）P极接正极为正向偏置，导通；反之为反向偏置，截止
三极管
集电极C，N型；基极B，P型；发射极E，N型
TTL与非门的两个状态通常称为关态和开态，当输入全为高电平时对应的是关态，此时输出为高电平；当输入有一为低电平时，对应的是开态，此时输出为低电平。
逻辑电路的符号表示
组合逻辑电路
- 从结构看，组合逻辑电路由门电路构成，不含存储电路，也不含反馈电路，信号从输入开始单向传输到输出。对于组合逻辑电路，任何时刻电路的输出仅由当时的输入信号决定。
- 将加在电路若干输入端中的某一个输入端的信号变换成相应的一组二进制代码输出的过程叫做编码
- 将二进制代码所表示的信息翻译成对应输出的高低电平信号的过程称为译码；n位二进制译码器有n个输入，有2^n个输出，工作时译码器只允许有一个输出有效。
理论运算
符号
与：\(\cdot\) 或 \(\land\)
或：\(+\) 或 \(\lor\)
非：\(\overline{}\) 或 \(\neg\)
异或：\(\oplus\)
同或：\(\odot\)
优先级：括号、非、与、异或、或 \(()>\neg>\cdot>\oplus>+\)
运算律
交换律、结合律、0-1律（与0做运算）、互补律
重叠率、吸收律、还原律
吸收律
\(A+\bar{A}B=A+B\)
分配律
\(A\cdot(B+C)=A\cdot B+A\cdot C\)
\(A+B\cdot C=(A+B)\cdot(A+C)\)
反演律（德摩根律）
\(\overline{A+B}=\overline{A}\cdot\overline{B}\)
\(\overline{A\cdot B}=\overline{A}+\overline{B}\)
包含律
\(A\cdot B+\overline{A}\cdot B+B\cdot C=A\cdot B+\overline{A}\cdot B\)
\((A+B)\cdot(\overline{A}+C)\cdot(B+C)=(A+B)\cdot(\overline{A}+C)\)
规则
代入规则、反演规则、对偶规则
逻辑函数的标准表达式
最小项
最小项：由n个变量组成的 “与” 项中，每个变量以原变量或反变量的形式出现且仅出现一次，则这个与项称为最小项。n个变量有 \(2^n\) 个最小项
最小项编号：按照变量顺序将最小项中的原变量用1表示、反变量用0表示，得到一个二进制数，与其对应的十进制数，即该最小项的编号 i
性质：
对于任何一个最小项，只有对应的一组变量取值，使其值为1，其余情况下均为0
全体最小项之和为1
任意两个最小项的乘积为0
相邻最小项：除一个变量互为相反外，其余变量都分别相同的两个最小项。
具有相邻性的两个最小项之和，可以合并为一个乘积项，消去一个以原变量和反变量形式出现的变量，保留由没有变化的变量构成的乘积项。
例：\(\bar{A}\bar{B}\bar{C}+\bar{A}\bar{B}C=\bar{A}\bar{B}\)
- 最小项推导法（从真值表推出表达式）：把输出为1的输入组合写成乘积项的形式，其中取值为 1 的输入用原变量表示，取值为 0 的输入用反变量表示，然后把这些乘积项加起来
\(F=\bar{A}BC+A\bar{B}C+AB\bar{C}+ABC\)
\(F(A,B,C)=m_3+m_5+m_6+m_7\)
\(F(A,B,C)=\sum m(3,5,6,7)\)
最大项
最大项：设有n个变量，它们所组成的具有n个变量的“或” 项（和项）中，每个变量以原变量或反变量的形式出现且仅出现一次，则这个和项称为最大项。n个变量有2 n个最大项
最大项编号：按照变量顺序将最大项中的原变量用0表示、反变量用1表示，得到一个二进制数，与其对应的十进制数即该最大项的编号i
性质：
对于任何一个最大项，只有对应的一组变量取值，使其值为0，其余情况下均为1
全体最大项之积为0
任意两个最大项之和为1
相邻最大项： 若2个最大项中只有1个变量分别以原变量和反变量的形式出现，其余的变量分别相同，则称这2个变量具有相邻性，或相邻最大项。具有相邻性的两个最大项之积可以合并为一个和项，消去一个以原变量和反变量形式出现的变量，保留由没有变化的变量构成的和项。
例：\((\bar{A}+B+\bar{C})(A+B+\bar{C})=[\bar{A}+(B+\bar{C})][A+(B+\bar{C})]=B+\bar{C}\)
1
化简
一般由EDA工具完成
“与或”表达式化简：
乘积项最少（与门最少）
乘积中变量最少
用最少的门、门的输入也最少
方法：
合并乘积项（互补律）
吸收项法（吸收律、包含律）
配项法（利用互补律）
卡诺图化简
常见器件
| 输入 | 输出 | 功能 | |
|---|---|---|---|
| 7485四位比较器 | A3-A0,B3-B0,I0-I2 | F>,F<,F= | 比较4位二进制数的大小 |
| 8线-3线编码器 | Y0,Y1...Y7 | C,B,A | 用3位二进制代码对8个信号进行编码 |
| 8421BCD编码器 | Y0,Y1...Y9 | D,C,B,A | 用4位二进制代码对10个十进制数字进行编码 |
| 74LS148优先编码器 | 低电平有效 | 反码 | 同8-3，优先编码7 |
| 74LS147优先编码器 | 低电平有效 | 反码 | 同8421，优先编码9 |
| 3线-8线译码器(74138) | A2,A1,A0,S2,S1,S0 | Y7-Y0，低电平输出有效 | S0,S1,S2为100时使能，3-8 |
| BCD译码器 | DCBA | Y9-Y0，低电平输出有效 | 10-4 |
| 74151多选器 | D7-D0,A2-A1,~en | Y,~Y | 8选1数据选择器 |
时序逻辑
基础知识
时序逻辑电路由组合逻辑电路和存储电路两部分组成
时序逻辑电路按触发器时钟端的连接方式不同可以分为同步时序逻辑和异步时序逻辑两类。
锁存器
基本RS锁存器
功能：
保持原来状态： \(\overline{R_D}=1,\overline{S_D}=1\)
置0（次态变0）：\(\overline{R_D}=0,\overline{S_D}=1\)
置1：\(\overline{R_D}=1,\overline{S_D}=0\)
约束条件：\(\overline{R_D}+\overline{S_D}=1\)
特性方程：\(Q^{n+1}=S_D+\overline{R_D}Q^n\)
钟控RS锁存器
功能：
\(CP=0\) 时，保持状态
\(CP=1\) 时，具有RS锁存器的功能
约束条件：\(S*R=0\)
特性方程：\(Q^{n+1}=S+\overline{R}Q^n\)
钟控D锁存器
功能：
\(CP=0\) ，保持
\(CP=1\) ，\(Q=D\)
特性方程：\(Q^{n+1}=D\)
D触发器
功能：CP（clk）上升沿更新Q，Q=D
可带使能端、复位
多个D触发器可以组成寄存器
JK触发器
功能：
\(CP=0\) ，保持
\(CP=1\) ，RS锁存器功能，且 \(J=K=1\) 时翻转
特性方程：\(Q^{n+1}=J\overline{Q^n}+\overline{K}Q^n\)
T触发器
功能：
\(T=0\) ，保持
\(T=1\) ，翻转
特性方程：\(Q_{n+1}=T\oplus Q_n\)
有限状态机
相关概念
概念：可描述有限个状态以及这些状态之间的转移及引起转移的动作等的离散数学模型。
次态逻辑：组合逻辑，根据当前状态和输入计算下一状态。
状态寄存器：在时钟沿到来之前，保持现态，并为输出逻辑和次态逻辑提供稳定输入；在时钟沿到来时，锁存次态逻辑输出的状态值。
输出逻辑：组合逻辑，根据现态形成输出信号。
分类：Moore型状态机：输出状态仅与当前状态有关
Mealy型状态机：输出信号与当前状态和输入信号有关
建立方法
确定输入、输出、状态
画出状态转换图，进而得到状态转换表、次态与输出逻辑表达式
时序问题
\(T_c>=T_{ctq}+T_{cd}+T_{setup}+时钟偏移\)
\(T_c\) ：时钟周期
\(T_{ctq}\) ：稳定时间（clock-to-Q）：——从触发时钟边沿到输出稳定的时间
\(T_{cd}\) ：组合逻辑电路最长时延
\(T_{setup}\) ：建立时间——触发时钟沿之前，输入需稳定的时间
\(T_{hold}\) ：保持时间：触发时钟沿之后，输入仍需稳定的时间
保持约束：\(T_{ctq}+T_{cd}\geqslant T_{hold}\)
寄存器
数据寄存器：多个边沿触发器组成
数据锁存器：多位电位触发器组成
移位寄存器：
4位双向移位寄存器(CT74194)
同步计数器：所有触发器的时钟端并在一起
异步计数器：时钟脉冲只作用于最低位
主存储器
分类
RAM（随机访问存储器）、ROM（只读存储器）
RAM可分为SRAM（静态存储器，Cache）、DRAM（主存）
ROM可分为Flash（闪存，可擦写）、不可在线更改的等等
描述
存取时间：读或写操作所用的时间
存取周期：两次访问存储单元的最小时间间隔
存储器带宽：单位时间访问的存储量
存储芯片容量=字单元数*字单元的位数，即 \(2^n\times m\) 。其中 \(2^n\) 为字单元数量，n为地址线数量，m为数据线数量（字单元位数）
地址线=log2(字单元数)，（按字寻址）
数据线=字单元位数
扩展
位扩展：字单元位数不够
字扩展：字单元数不够
DRAM刷新
刷新间隔：同一行两次被刷新之间的时间
刷新周期：所有行被刷新一次的时间
集中式：间隔=刷新周期
分散式：间隔=刷新行数*存储周期
分布式（异步）：间隔=刷新周期
MIPS汇编
指令格式
操作码+操作数（操作数地址，0123）
定长/变长
寻址
立即寻址：机器码中给出立即数
直接寻址：操作数在寄存器中，机器码里有寄存器编号
间接寻址：操作数在内存中，机器码里有存储着内存地址的寄存器的编号
基址寻址/变址寻址：间接寻址+立即数（lw $s1,100($s2)）
相对寻址：PC作为基址寄存器+立即数
堆栈寻址
mips中的寻址
立即寻址：ori中的立即数
寄存器寻址：add中操作数在寄存器里
基址寻址：lw，根据寄存器中的数据+偏移量得出内存地址，取数
PC相对寻址：beq
伪直接寻址：j
一些指令
跳转相关
| 指令 | 位数 | 跳转空间 |
|---|---|---|
| beq | 16位立即数+左移2 | 256K |
| j | 26位立即数+左移2 | 256M |
| jr | 寄存器，32位 | 4G |
罕见指令
bgez：大于等于0跳转 bgtz：大于0跳转 blez：小于等于…… bgeal：大于等于0，则跳转+写入ra
lbu：加载无符号数……lhu、lwu、sbu
sll：逻辑左移，5位立即数 sllv：寄存器代替立即数 srl：逻辑右移 sra：算数右移……
slti：小于立即数置1 sltiu：小于无符号立即数置1
流水线CPU
数据相关性：设指令i在指令j前面
- 写读相关（RAW）：指令i将数据写入寄存器后，指令j才能读取
- 读写相关（WAR）：指令i读出数据后，指令j才能写寄存器
- 写写相关（WAW）：指令i写入后，指令j才能写入，否则寄存器内容不是最新值
冒险类型：
- 数据冒险：数据存在相关性，可用转发、暂停解决
- 控制冒险：分支跳转指令“撤回”等问题，可用延迟槽、分支比较前移解决
- 结构冒险：两条指令使用同一部件如同时读写寄存器堆，可通过把指令寄存器和数据寄存器分开解决
Cache
注意主存地址位数（多少字节）、字节、字之间的换算！！！
Cache结构
SRAM组成，以数据块为单位。块大小与主存相同
数据块（block）：主存与cache交换数据的最小单位，多个字节组成
标记（tag）：保存该数据块对应的主存数据块的地址信息
有效位（valid bit）：该数据块中是否包含有效数据
行：1行=数据块+标记+有效位
组：若干块构成一组
实际Cache容量=行数*(tag+有效位等+数据块字节数)
Cache映射机制
全相联
主存中某一数据块可以映射到Cache中的任意一数据块
Cache的tag内容：与该数据块对应的主存的数据块的块地址
主存地址格式：块地址+块内地址
直接映射
主存中某一块J映射到Cache中的固定块K，\(K=J\mod M\) ，M是Cache包含的块数
Cache的tag内容：主存中与该数据块对应的区地址，即第几个能映射到Cache中该块的数据块
主存地址格式：区地址+区内块地址+块内地址
组相联
Cache分成K组，每组L块，主存的块J映射到Cache中组I的任意一块，其中$ I=JK$
实际上，主存与Cache都分为K组，但组内块数不同，组内任意映射
Cache的tag内容：主存中与该数据块对应的组内块地址
主存地址格式：组内块地址+组地址+块内地址
缺失损失与替换策略
缺失损失
缺失时，CPU等待数据装入Cache后才能访问
取出块的时间：第一个字的延迟时间（存储器访问）+块的剩余部分的传送时间
计算方法1：访问Cache发现缺失的时间+访问DRAM的时间*字数+传输时间*字数
传输时间可能会因为并行数而改变
缺失处理
- 块装入后访问
- 尽早重启：块中各字按顺序装入Cache，一旦所请求的字装入Cache，CPU立刻访问
- 请求字优先：先把所请求的字装入Cache，再装入其他字
替换策略
最近最少使用法（LRU）：最近没有被使用的块被替换。替换的块计数清零，其他计数器+1；访问命中时，计数值小于等于命中块计数值的+1，然后命中块清零；替换时选择计数值最大的块来替换
先进先出法（FIFO）：最先装入数据的块被替换
最小使用频率法（LFU）：使用次数最少的块被替换
随机法（RAND）
辅助存储与虚拟存储
辅助存储
磁介质
磁记录编码方式：
编码效率：记录一位信息的最大磁化翻转次数的倒数，调频、调相为0.5，不归零制为1
自同步能力：从读出的信号中提取同步信号。PM、FM有
可靠性：归零制低，调相制高
磁盘
RPM：每分钟转多少圈
容量：盘面数*每面磁道数*每磁道扇区数*扇区容量
访问时间=寻道时间+寻区时间
数据传输率：单位时间传输的数据位数
RAID：廉价磁盘冗余阵列，多个物理磁盘构成，但被操作系统当成一个逻辑磁盘，数据分布在不同的物理磁盘上，冗余磁盘用于保存数据校验信息，校验信息保证在出现磁盘损坏时能够有效地恢复数据。
- RAID0：每一数据条带分布在不同物理磁盘上，改善数据传输性能，但完全没有冗余
- RAID1：简单镜像磁盘冗余，利用率50%。写操作性能不高（同时写两组）
- RAID2：海明校验，完整的并行访问技术
- RAID3：奇偶校验的并行传送，校验码保存在独立的冗余磁盘对应位置
- RAID4：奇偶校验吗的独立磁盘结构
- RAID5：分布式奇偶校验的独立磁盘结构。校验信息保存在磁盘组的不同磁盘中
MIPS存储管理
从低到高32位：用户2G，KSeg0（有MMU的操作系统内核）512M，KSeg1 512M，KSeg2 1G
PC初始值：0x00400000
$gp：0x10008000，静态数据区为0x10000000-0x1000FFFF
$sp：0x7FFFFFFF
虚拟存储
虚地址：编写程序时使用的地址，地址格式为虚页号+页内地址
实地址：物理内存的访问地址，地址格式为实页号+页内地址
页表：每道程序一个，以虚页号为索引，实页号、有效位为页表项，存储在内存中
快表（TLB）：用Cache存储部分活跃的页表项，内容为虚页号、对应实页号、有效位、修改位
调度方式：页式调度、段式调度、段页式调度
总线与I/O接口
总线
分类：片内总线、系统总线、通信总线。其中系统总线可分为数据总线、地址总线、控制总线
总线的信息传送：请求总线、总线仲裁、寻址、信息传送、状态返回
总线仲裁方式（分布式、集中式）：链式查询、计数器定时查询、独立请求
总线通信方式：同步、异步（不互锁、半互锁、全互锁）
I/O接口
分类：串行/并行、同步/异步、程序查询/中断/DMA/通道控制接口
I/O操作过程：
- CPU查询接口状态
- I/O回送设备状态
- CPU发出命令，请求传送
- I/O获得来自外设的数据
- 数据从I/O接口传送至CPU
编址方式：独立编址、统一编址（存储器与I/O地址统一考虑）
程序查询I/O：I/O操作全部由CPU直接完成，与CPU串行，效率低
中断I/O：当前指令执行完毕后，响应中断。外设准备阶段可认为是并行的。目前最主要的方式。
DMA：CPU不再介入具体的I/O操作，DMA控制总线，数据传送效率更高。周期窃取方式（单字、一个总线周期），停止CPU访问内存（成组传送方式）。指令周期的任一存取周期结束时响应
通道I/O：有自己指令系统的专业控制器，CPU基本不需要管理I/O。选择通道的数据传输率=一台设备的数据传输率，字节多通道、数组多通道数据传输率=各设备数据传输率之和
DMA与中断
响应时机：中断在一条指令结束后响应；DMA在指令周期内任一存储周期结束时响应
现场保护：中断要中断现有程序，保护现场；DMA不中断现有程序，无须保护现场
适应场合：中断适于处理紧急或异常事件；DMA适合传送大批数据（如磁盘、网卡等）
传送方式：中断靠程序传送数据；DMA靠硬件