计算机组成与体系结构
#Chapter 1
1. 硬件软件等效原理
任何可用软件实现的事情也可以用硬件实现,反之亦然。但硬件更快
2. 计算机发展史
第0代:机械计算器
算盘、计算钟、Pascaline、加法仪……
不能编程,没有存储器。
巴贝奇的差分机、分析机(穿孔卡片输入数据)
IBM的制表机
第1代:真空管计算机
电动、电子的,可编程,有存储器、算数部件、控制部件(Z1)
第一台完整的计算机系统:ABC。专用的。二进制。
第一台通用的计算机系统:ENIAC
第2代:晶体管计算机
体积小、性能可靠、速度快、功耗小
第3代:集成电路计算机
速度更快、体积更小、价格便宜
第4代:超大规模集成电路计算机
体积更小、速度更快
催生微型计算机
3. 摩尔定律
Moore的原话:集成电路中的晶体管数目将会每年翻一番
现在:硅芯片的密度每18个月翻一番
Rock定律:制造半导体集成电路的成本每4年翻一番
4. 计算机的分层组织结构
层次 | 名称 | 解释 | |
---|---|---|---|
6 | 用户层 | 各种应用任务、程序 | |
5 | 高级语言层 | C、C++、Pascal等高级语言 | |
4 | 汇编语言层 | 高级语言被编译成汇编语言,再被翻译成机器语言 | |
3 | 系统软件层 | 主要处理操作系统指令。负责多用户编程、存储器保护、过程同步等功能。从汇编语言翻译来的机器语言可以直接越过。 | |
2 | 指令集体系结构(机器层) | 机器语言。直接用硬连线电路执行程序。 | |
1 | 控制层 | 控制单元确保正确地译码并执行指令、传送数据。控制单元的设计有两种方式:硬连线、微程序。硬连线快,微程序慢,但可修改 | |
0 | 数字逻辑层 | 物理构成。逻辑门、引线。 |
5. 冯·诺依曼模型
组成部件
- 中央处理器CPU
- 控制单元×1
- 算数逻辑单元ALU×1
- 寄存器×n
- 程序计数器×1
- 主存储器系统
- 输入输出系统
具有执行顺序指令的处理能力
瓶颈
在主存系统和CPU的控制单元之间,包含一条物理/逻辑上的单一通道,可以强制改变指令和执行的周期。这一单一通道就是冯诺依曼瓶颈。
工作原理:(顺序执行)
取指-译码-执行周期
Amdahl定律:对于某种特定的系统改进,系统性能增强的可能性受到被改进的特征部位的使用次数的限制。
Chapter 2 计算机系统中的数据表示方法
字:两个或多个相邻的字节构成,有时用来对存储器进行编址,总是被作为一个集合来处理。字的大小表示了一个特定的计算机体系结构能处理的最有效的数据大小。
1. 二进制与各进制的转换
10->2:除2取余,从下往上
分数部分:乘2取整,从上往下
2->8/16:3/4位一组
2. 带符号整数的表示
符号幅值表示法
最左一位作为符号位。
N位能表示的数的范围为:-2(N-1)-1~2(N-1)-1
原码的缺点:
- 位数受限,有溢出的风险
- 正负0
- 加减法困难
反码
- 正数:不变
- 负数:符号不变,其他位取反
优点: 加法代替减法
缺点: +-0
高低两端进位循环:加法时如果有进位,加到个位上
补码
- 正数:不变
- 负数:反码+1
缺点:溢出——解决:检测
最高位进位舍弃
检测溢出条件:如果进入符号位和移出符号位的进位相等,则没有溢出。
3. 浮点表示法
- 分为符号位、指数、有效位,表示为0.1xxxxx*2n
- 有效位的第一位是1,使表示方法唯一化
- M余表示法,使指数正负皆可用正数表示。 方法:指数位有n位,则用M=2n-1-1来表示0
- 0有+-两种,算了
浮点运算
加法:将有效位对齐并相加,最终保留较大的那个指数,并删除有效位的低位多余部分
乘法:指数正常,有效位也按竖式运算,再重新规格化
###误差
128.5+0.5会加不上去,因为有效位只有8位,但这个数表示起来总共有九位,则0.5永远被舍弃,加越多误差越大。
解决:让操作数的精度比较接近。比如如果要连加4个0.5,先0.5*4,再加上去。
4. 字符编码
超级精确但有点浪费的BCD
基于拉丁字符的用1位奇偶校验位的ASCII(8位)
支持所有语言的Unicode(16位)
5. 错误检测
CRC
约定共用的模2多项式P:
- 右添P位数-1个0
- 模2除P,得余数加上
海明编码
一个有m位的数,需要r位检验位
- m+r+1≤2r (m=4,r=3;m=8,r=4)
- 将所有位从右往左排列,从1开始编码
- 2的倍数位为校验位(1,2,4,8……),其他为数据位
- 确定每个检验位会检验哪些位: 将各个位写成2的幂指数的和的形式,式子中有1的就是被1检验的位,如1 3 5 7 9 11
- 如果是偶检验,则1的所有检验位加起来得是偶数,如此可填上第1位的数。
题型:010111010110是错的吗?(4位检验位的偶检验)
找出各个出错的检验位,加起来就是出错的位。
里德-所罗门编码
处理块状错误,复杂的CRC
Chapter 3 布尔代数和数字逻辑
布尔代数
1. 基本概念
一个封闭的代数系统。(输入0、1,输出也是)
表达式:
- 非x'
- 与x·y
- 或x+y
布尔恒等式:分配律 x+yz=(x+y)(x+z)
真值表:输入值按从小到大的顺序写。证明题可用。
用真值表写表达式:所有输出值为1的项加起来
2. 化简
1. 代数法
xy+x'z+yz=xy+x'z
2. 卡诺图
x yz wx yz 00 01 11 10
将输出值0和1填在表中(0可省略),无关条件可圈可不圈
####3. 真值表
数字逻辑
3. 逻辑门
与门 ⫐
或门 🌛
非门 ▷◦
异或门⊕ )🌛 不同则真
与非门 ⫐◦ 都1则0
或非门🌛◦ 有1则0
###4. 组合/时序
组合电路
输出仅仅取决于输入,且在同一时刻。
- 半加器:输入x和y,输出sum和carry(进位)
- 全加器FA:输入x和y和进位,输出sum和carry
- 译码器
- 多路复用器
- 奇偶发生器、奇偶检验器
####时序电路
事件有顺序,被时钟控制。
- SR触发器
S | R | Q(t+1) |
---|---|---|
0 | 0 | Q(t) |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | not know |
JK触发器
J K Q(t+1) 1 1 Q'(t) D触发器:来啥出啥转进销。 寄存器由一组D触发器构成。
Chapter 4 MARIE:简单计算机模型
1. 组成
1)CPU中央处理器
①数据通道
a.寄存器
D触发器可以存1位,所以一个寄存器需要一组D
有专用、通用类型的寄存器
寄存器由控制单元进行编址和处理
b.算数逻辑单元ALU
进行逻辑运算和算术运算
②控制单元
对各操作进行排序,并保证各种正确的数据适时呈现
- 叫程序计数器的寄存器:找下一条指令的位置
- 状态寄存器:存某些特殊的操作状态
2)总线
- 点对点:连接两个特定设备
- 多点:多个设备共享 总线仲裁:
- 菊花链仲裁方式:高优先级到低优先级传递权限。不公平,低的无望
- 集中式平行仲裁:每一个设备都可以申请。会有瓶颈
- 自选择的分配式仲裁:设备自己来决定谁先
- 冲突检测的分配式仲裁:出现冲突则都重来(以太网络)
3)时钟、输入/出子系统
其中最后一个才是主频。
I/O子系统不与CPU直连,而采用接口进行信号转换:
- 内存交换的输入输出方式:访问IO就是访问内存。快但占
- 指令实现的输入输出方式:专用指令实现IO。不占但需要特殊指令
4)存储器
==作业题==
- 高位交叉存储:连续自然,存满为止
- 低位交叉存储:多个模块可同时读,更快
5)中断
改变系统正常执行流程的各种事情
2. MARIE体系结构
7种寄存器
- AC累加器:16位,保存CPU需要处理的数据
- MAR存储器地址寄存器:12位,保存被引用数据的地址
- MBR存储器缓冲寄存器:16位,保存刚读取或将写的数据
- PC程序计数器:12位,保存下一条指令的地址
- IR指令寄存器:16位,保存下一条指令
- InREG输入寄存器:保存来自输入设备的数据
- OutREG输出寄存器
指令集
ISA:指令系统体系结构,硬件、软件间的接口
二进制编号 (机器指令) |
十六进制 | 指令 (助记符号) |
描述 |
---|---|---|---|
0001 | 1 | Load X | 将地址X中的内容装入AC |
0010 | 2 | Store X | 将AC中的内容装入地址X |
0011 | 3 | Add X | 将X中和AC中的内容相加,存入AC |
0100 | 4 | Subt X | 将AC中减去X中的内容,存入AC |
0101 | 5 | Input | 键盘输入值到AC |
0110 | 6 | Output | 将AC内容输出到显示器 |
0111 | 7 | Halt | 终止 |
1000 | 8 | Skipcond | 有条件地跳过下一条指令 |
1001 | 9 | Jump X | 将X的值装入PC中 |
0000 | 0 | JnS X | 将PC中的内容存到X处,然后跳转到X+1处 |
1010 | 10 | Clear | 将AC清空为0 |
1011 | 11 | AddI X | 间接相加:取出X所存地址中所存的数加入AC中 |
1100 | 12 | JumpI X | 间接转移:跳到X所存地址中所存地址 |
寄存器传输表示法RTL/RTN
- Load X: MAR ← X MBR ← M[MAR], AC ← MBR
- Store X: MAR ← X, MBR ← AC M[MAR] ← MBR
- Add X: MAR ← X MBR ← M[MAR] AC ← AC+MBR
- Subt X: MAR ← X MBR ← M[MAR] AC ← AC-MBR
- Input: AC ← InREG
- Output: OutREG ← AC
- Halt:终止而已
- Skipcond: If IR[11-10]=00 then If AC<0 then PC ← PC+1 else If IR[11-10]=01 then If AC=0 then PC ← PC+1 else If IR[11-10]=10 then If AC>0 then PC ← PC+1 else 错误
- Jump X: PC ← IR[11-0] | PC ← X
- JnS: MBR ← PC MAR ← X M[MAR] ← MBR MBR ← X AC ← 1 AC ← AC+MBR PC ← AC
- Clear: AC ← 0
- AddI X: MAR ← X MBR ← M[MAR] MAR ← MBR MBR ← M[MAR] AC ← AC+MBR
- JumpI X: MAR ← X MBR ← M[MAR] PC ← MBR
执行指令
- 取指: MAR ← PC, IR ← M[MAR], PC ← PC+1
- 译码: MAR ← IR[11-0] IR[15-12]
- 执行: (MBR ← M[MAR])...
编译(二次通读)
- 生成符号表和操作(16进制表示)+符号的不完整指令表
- 用符号表填充地址
3. 译码两法
- 硬件译码:速度快,但电路复杂,设计、修改困难
- 微程序控制译码:修改简单,但所有指令经过额外的翻译过程,减慢执行速度
##4. CISC v.s. RISC
- CISC 复杂指令集计算机: 指令多,程序短
- RISC 精简指令集计算机: 指令少,程序长
Chapter 5 指令系统体系结构ISA
1. 指令格式
①指令集特征
- 操作数在CPU中存储方式(堆栈or寄存器)
- 指令直接作用的操作数数目
- 操作数位置
- 操作(类型、指令是否可直接访问存储器)
- 操作数的类型和数目(地址、数字、字符类型等)
②性能影响因素
- 执行指令时占用内存大小
- 指令系统的复杂程度(指令执行所需的译码数量和所执行任务的复杂性)
- 指令的长度
- 指令系统中指令的总数目
③大端小端
- 大端:自然
- 小端:处理计算方便
00 | 01 | 10 | 11 | |
---|---|---|---|---|
大端 | 00 | 00 | 12 | 34 |
小端 | 34 | 12 | 00 | 00 |
④内部机制×3
- 堆栈:操作数放在堆栈顶部 不能随机访问,效率不高
- 累加器AC:其中一个操作数隐含在AC中 降低内部复杂性,允许非常短的指令。但对存储器的访问非常频繁
- 通用寄存器GPR:多个寄存器组
- 存储器-存储器:2、3个操作数可在存储器中,允许不要操作数的指令在寄存机中
- 寄存器-存储器:混合,至少一个操作数在寄存器、一个在存储器
- 装入-存储:任何对数据的操作前,先将数据装入存储器
⑤操作数目、指令长度
指令格式:
- 固定长度:浪费空间,但快,且支持流水线
- 可变长度:节省空间,但译码复杂
堆栈采用的==后缀表示法==
不需括号。题。
###⑥扩展操作码
2. 指令类型
常见几种知道
- 数据移动
- 算术运算
- 布尔逻辑运算
- 位操作(移位和循环换位)
- 输入、输出
- 控制转移
- 专门用途
3. ‼️寻址方式×7
给指令,问装入AC的是啥
- 立即寻址:地址即数
- 直接寻址:地址是数的地址
- 寄存器寻址:地址是寄存器的地址
- 间接寻址:地址是数的地址的地址
- 寄存器间接寻址:地址是寄存器的地址,寄存器存的是数的地址
- 变址寻址:变址寄存器中存偏移量,与地址相加成为真实数的地址
- 基址寻址:基址寄存器中存偏移量
4. 指令流水线
原理
(k倍咋来的)
设k级流水线,每级时钟周期tp,共n条指令,则用流水线完成任务耗时:
所以加速比为
所以,理论上加速比S就是级数k
冲突
3类+解决办法
- 资源冲突:如存取同时进行。 解决:让取等,或者设两条独立通道
- 数据关联:前指令没结束,后指令要用到其结果。 解决:①添加专门的硬件来检测 ②特殊编译器
- 条件分支语句 解决:分支预测;对程序重新排序;两条分支都取指,等看实际用谁
5. 案例
了解
Intel
小端,双地址,可变长的指令系统
MIPS
小端,按字编址,3地址,固定长度的指令系统
Chapter 6 存储器
1. 类型
AODS区别、用在哪
- RAM随机存储器:可供读写,即主存;但断电就失
- DRAM动态随机存储器:需要电但存储密度高,功耗低——做主存
- SRAM静态随机存储器:D触发器构成,速度快但价格高——做高速缓存
- ROM只读存储器:非易失性,存运行计算机系统所需的关键信息or用于嵌入式系统
2. 层次
概念
- 命中:CPU请求的数据就在要访问的存储层中
- 缺失:不在
- 命中时间:在那个存储器层中,找到数据所需的时间
- 缺失损失:处理缺失所需的时间
大体分层
- 寄存器:CPU内
- 1级缓存:高速缓存
- 2级缓存:高速缓存
- 主存:以上都是System层
- 硬盘:Online层
- 优化磁盘:例如光盘,近线层
- 磁带、USB Flash Drive、Removable Hard Drive,离线层
###局部性*3
- 空间局部性:访问形成团簇的集中倾向
- 时间局部性:最近访问的很可能不久再访问
- 顺序局部性:指令倾向于顺序执行
3. 高速缓存
映射的三种方式
①直接映射的高速缓存
高速缓存和主存的块之间有映射关系。有合法性标记
主存地址总位数:根据主存可以分为多少个地址来决定(例如主存共可存214个字,又按字编址,那就可分为214个地址,需要14位来存)
将主存地址划分为:
- 标记域:剩余的
- 块域:按照高速缓存的总块数划分
- 字域:按照每个块的字数划分
②全关联高速缓存
主存的块可存到高速缓存的任意块中
比对标记域很费劲,很贵。需要牺牲块的置换算法
- 标记域:剩余的
- 字域
③组关联高速缓存
N路的:每组包含N个块组,将数据块映射到某个块组中
- 标记域
- 组域:组数=高速缓存的总块数÷路数
- 字域
置换策略
特点
- 最近最少被使用:但要存历史访问记录,占空间、减速
- 先进先出
- 随机选择:不会像前二者那样重复操作
有效存取时间EAT
如果用分页的虚拟存储器,主存需要访问两次
写策略
- 写通:每次写都在主存、高速缓存中写。慢,但保证一致性
- 回写:只有高速缓存中的块牺牲时,它才被写进主存。快,但同时可能数据不同,而且如果中断/崩溃,数据可能丢失
##4. 虚拟存储器
概念
用硬盘作为RAM的扩充,增加了进程可以使用的有效地址空间
分页、分段
分页:按固定大小的信息块(页帧)为各个进程分配物理存储空间,将信息写入页表来记录页的存放位置 产生内部碎片 将虚拟地址转换为物理地址:
- 算清虚拟地址长度和物理地址长度 虚拟地址长度:看虚拟地址空间能存多少字 物理地址长度:看页帧数×页帧的长度能存多少字
- 虚拟地址划分为:
- 页域:根据虚拟地址可分的总页数确定长度
- 偏移量:就是字域嘛
- 拿页域作为索引去页表中找对应的页帧
- 页帧替换页域而偏移量不变,即成为物理地址
缺点:耗时;耗主存的空间;需要专门的硬件和操作系统支持 优点:运行程序不受已有物理存储器容量大小的限制
分段:长度可变。 产生外部碎片
Chapter 7 输入/输出和存储系统
1. AMDAHL计算
是1.5倍、快1.5倍
计算机整体性能的提升速度S
性能提升1%花钱:
2. I/O体系结构
基本原理
5种控制方法
- 程序控制的I/O 每个I/O设备都要一个专用的寄存器,CPU繁忙等待着数据的到来(轮询),可以编程来控制设备的行为 应用:专用系统,如ATM
- 中断控制的I/O CPU不需要轮询,而是在有数据发送需求时由外部设备来通知CPU,没有的时候CPU可以干别的。用CPU的标志寄存器来指示中断信号(一个二进制位的中断标志)。也可以编程控制 应用:当今流行。
- 直接存储器存取DMA 用专用芯片来编程DMA子系统,CPU提供专用I/O寄存器。子系统自行处理,完成后发中断请求通知CPU DMA与CPU共享存储器总线,为了主控,会对CPU进行周期窃取
- 通道控制的I/O 用I/O处理器(IOP)来控制多个I/O路径,具有执行程序的能力。 智能特性:IOP能对协议进行协商,发出各种设备命令,将存储译码转换为内存译码,独立于CPU来传输多个完整文件 总线隔离性:单独的I/O总线,只对CPU进行小小的周期窃取 应用:大型计算机等高吞吐量的事物处理环境
- 主存映射的I/O 给每个I/O一个存储器地址。
数据传输模式
- 串行:按位传
- 并行:按字节传(8位)
3. 磁盘技术
硬盘
原理
- 驱动臂:有读写头,不可跟碟片接触
- 转轴
- 碟片:
- 磁道:每个同心圆,从外往内从0编号
- 扇区:小块
- 每条数据:记录表头、数据、记录结尾
数据块由扇区、盘面、磁道来唯一决定,读取数据:
- 驱动臂使读写头定位到指定磁道——寻道时间
- 转轴转到——旋转延迟
评价
寻道时间
旋转延迟 用平均反应时间计算
缺点:慢,易坏
解决:用不会丢失数据的RAM替代(SSD/U盘——都是闪存)
固态硬盘
和硬盘的核心差异:
闪存:先擦才能新写,折寿
==∴SSD不可挡虚拟存储器,而应该用机械硬盘==
重要指标:
- UBER不可恢复的误码率——可靠性
- TBW写入的百万兆字节——使用寿命
光盘
低成本,大空间,稳定
特点:
- 一条光轨——顺序存储
- 与硬盘区别:光轨的中心和外圈有相同的位密度
- 线速度固定
分类
- CD-ROM:存音乐或数据
- CD-R、WORM:用于数据的长期存档
- DVD数字多功能光盘:比CD更高密度、旋转速度、双面双层
- Blue-violet laser discs
- Blue-Ray:更高的存储密度(赢了)
- HD-DVD:向下兼容DVD
磁带
分类
- 传统: 九条磁道:1个字节的数据+1位奇偶校验
- 蛇形:纵向写数据
- 螺旋:斜的
独立磁盘冗余阵列RAID
*8种
Level 0 磁盘跨区
数据块以条带形式存放在磁盘表面上
最佳性能,但没有任何冗余,可靠性差
Level 1 磁盘镜像
两组磁盘存储完全相同的数据
100%冗余所以稳定,不错的性能(读好,写差);但成本高
适用:追求可靠性的,如财会、邮箱
Level 2
每个条带只写入1位数据+海明编码校验
性能差且成本高,写入需要严格同步
Level 3 精简奇偶校验的2
每次1位,交错分配;只使用1个驱动器来保存一个简单的奇偶校验位
稍微经济,不适用商业环境,适用个人系统
Level 4 具有奇偶校验的0
一块一块写,一个校验盘
适用:所有记录块的大小相同
Level 5 分散奇偶校验位的4
访问可以并发执行,提高性能和可靠性
应用:广泛应用在商业系统中
Level 6 两条纠错带
可以承受两个磁盘同时出现问题
写入性能相当差,但是容错性很好
RAID DP双重奇偶校验
思路类似,也可以出俩错
混合RAID
许多大型计算机系统不局限于一种
Chapter 9 可选择的体系结构
1. CISC v.s. RISC
- CISC 复杂指令集计算机: 指令多,程序短 大量能直接访问存储器的指令 每条指令长度不同,时钟周期也不同 微代码处理指令的复杂性问题,不可流水线 多周期指令
- RISC 精简指令集计算机: 指令少,程序长 只提供最小指令集:数据移动、ALU、分支转移 只有显式的load和store可以访问存储器 每条指令长度相同 硬连线取代微程序,将指令集的复杂性问题转移到编译器上 单周期指令 寄存器窗口组:
- 全局寄存器:对所有窗口共用
- 局部寄存器:属于当前窗口
- 输入寄存器:与前一个窗口的输出寄存器覆盖
- 输出寄存器:与后一个输入覆盖
2. Flynn计算机体系结构分类法
考虑因素:
- 指令的数目
- 流入处理器的数据流的数目
分类:
- SISD 单指令流、单数据流
- SIMD 单指令流、多数据流
- MISD
- MIMD
缺点:
- MISD没有存在的必要
- 它假定并行执行都是同构的
- MIMD还可以细分
3. 并行、多处理器体系结构
4. 新的并行处理方法
- 数据流
- 神经网络
- 脉动
Chapter 10 性能度量和分析
1. CPU时间计算
2. 4种数学平均
公式+场景
算术平均值
###加权算术平均值
几何平均值
用途:比较相对性能。在已知工作量下的系统性能指示器
参考不同,数值不同,但比值不变(因为相对性能差异不变)
调和平均值
3. 基准
各解决什么问题
4. 优化
分支优化
- 延迟转移:调换指令顺序,使分支指令延后执行。需要进行数据相关性分析
- 分支预测:
- 固定预测:假设总是采用/不采用分支
- 动态预测
代码优化
5. 磁盘性能
利用率(忙碌率)
排队系统
80%的利用率是经验中的上限
###逻辑性能
调度算法
- 先来先服务
- 最短寻道时间优先:电梯算法
预取
利用顺序局部性,同时读取目标扇区和后续的若干个扇区