内容来源
1.可计算性理论
可计算性理论通过建立计算的数学模型,精确区分哪些是可计算的,哪些是不可计算的.
可计算性理论确定了哪些问题可能用计算机解决,哪些问题是不可能用计算机解决的.
2.图灵机
- 是否所有数学问题都有明确答案/可解?
- 有明确答案的问题,是否可通过有限步骤得到答案?
- 对于那些有可能在有限步骤得到答案的数学问题,是否存在一种假象的机器,对该问题不断运算,机器停下来时,答案就计算出来了?
图灵机严格来讲是一种数学模型,计算理论模型. 定义了计算机能力边界:有限步骤内可以得到答案的问题.
3.冯·诺依曼体系结构/存储程序计算机
冯·诺依曼体系结构确立了当代计算机硬件的基础架构.
运算器,控制器+存储器+输入,输出设备
3.0.计算机程序抽象框架
- 程序首先加载到内存
- 用户通过输入设备输入信息
- CPU执行加载到内存中的程序
- 将结果输出到输出设备
3.1.电脑/服务器
- CPU/中央处理器/Central Processing Unit
- 计算机的核心,处理所有的计算
- 相当于运算器+控制器
- 内存
- 程序需要加载到内存里才能运行
- 内存中的程序和数据,需要被CPU读取,CPU计算完之后,还需要把数据写回到内存.
- Motherboard/主板
- CPU,内存都要插在主板上
- 主板的 芯片组 和 总线 解决了CPU和内存如何通信的问题.
- 芯片组
- 控制了数据传输的流转,即数据从哪里到哪里
- 总线
- 实际数据传输的高速公路
- 总线速度决定了数据能传输的多块
- 南桥
- 连接鼠标,键盘,硬盘 和 CPU 之间的通信
- 北桥
- 连接CPU 和 内存,显卡 之间的通信.
- 现在,北桥芯片已经被移到了CPU内部.
- IO设备/输入输出设备
- 显示器,鼠标键盘等.
- 显卡/Graphics Card
- 显卡里有GPU/Graphics Processing Unit/图形处理器
- 可以做计算工作
3.2.手机
- 将CPU,内存,网络通信,及摄像头芯片,都封装到1个芯片,再嵌入到手机主板上.
- 这种方式叫做SoC/System on a Chip/系统芯片
4.冯诺依曼机和图灵机的区别
图灵机是一个思维实验,而冯诺依曼机则是这个思维实验的"物理实现".
5.冯诺依曼机特点
冯诺依曼机也要存储程序计算机.2个特点:
- 可编程:可以执行不同逻辑的运算.
- 比如简单的计算器只能执行加减乘除固定逻辑,不可编程.
- 可存储:程序本身是存储在内存中,可以通过加载不同的程序执行不同的逻辑运算.
6.计算机组成原理知识地图
7.参考书籍
- 程序是怎样跑起来的
- 计算机是怎样跑起来的
8.性能是什么
- 计算机的计时单位:CPU时钟周期时间/Clock Cycle Time
- CPU内部有一个晶体振荡器/晶振.
- 晶振的每一次'滴答'间隔,就是CPU的时钟周期时间.
- 2.8G的CPU,其CPU时钟周期时间就是 1S/2.8G
- 每条指令的平均时钟周期数量/CPI
- 不同指令,对应的时钟周期数量不同.
- 通过优化CPU设计,降低1条指令需要的CPU周期数量
- 程序的CPU运行时间
- 程序的CPU运行时间 = 指令数 * CPI * Clock Cycle Time
- 指令数的优化,通常由编译期完成,同样的代码,不同的编译期编译出的计算机指令数量不同.
- Clock Cycle Time依赖于CPU主频不断的提升.
9.指令就是机器码
- CPU或计算机本身,并不能理解C,JAVA这种高级编程语言,只能处理'机器码',即一连串的'0'和'1'这样的数字.
- 高级语言最终都要转换成'机器码'交给CPU执行.
- 指令就是机器码.
- 不同的CPU,支持不同的指令集-->即支持不同的'机器码'.
10.指令如何实现高级语言中类似if/else及while这样的程序控制流程
- CPU中有多种不同功能的寄存器:
- PC寄存器/指令地址寄存器
- 存放下一条需要执行的指令的内存地址
- 指令寄存器
- 存放当前正在执行的指令
- 条件码寄存器
- 存放CPU进行算术或逻辑计算的结果
- 其他寄存器
- 存储数据的寄存器,如 整数寄存器,浮点数寄存器,向量寄存器.
- 存储内存地址的寄存器
- 有些寄存器既能存放数据,又能存放地址,称为通用寄存器.
- PC寄存器/指令地址寄存器
- 1个程序对应的一条条指令,在内存中是连续存储的.
- 指令可以顺序执行,也可以跳转执行.
- 跳转执行实现了if/else和while这样的程序控制流程.
- 指令顺序执行
- CPU根据PC寄存器中的地址,从内存中将需要执行的指令读取到指令寄存器执行.
- 根据指令长度自增,顺序读取下一条指令.
- 指令跳转执行
- CPU根据PC寄存器中的地址,从内存中将需要执行的指令读取到指令寄存器执行.
- 执行结果被存储到 条件码寄存器 中.
- PC寄存器自动自增,执行下一条指令.
- 如果对应的是程序控制逻辑,下一条指令就会查看刚刚存到 条件码寄存器 中的条件码.
- 如果条件码指示需要指令跳转,PC寄存器中的地址就会被设置为指定的地址,而不是自增.
- CPU继续读取PC寄存器中的地址,将要跳转到的位置的指令读取到指令寄存器,执行.
- 高级语言中的逻辑控制,对应到CPU指令,都只是简单的指令地址跳转.
11.程序栈 及 栈溢出
- func1调用func2,func2继续调用func3,..funcN
- 栈顶的是funcN.
- funcN调用完成会出栈,funcN-1变成栈顶执行...
- 程序栈的深度是有限的,调用层级过高触发栈溢出
- 避免栈溢出:函数内联
- func1调用func2,实际会从func1当前指令地址跳转到func2指令位置
- 压栈
- func2执行完毕
- 出栈
- 返回到func1指令位置继续执行
- 函数内联,会直接将func2的指令展开放到func1处,避免了指令地址的跳转,压栈,出栈操作,避免栈溢出
- 但是如果func2在func1中被先后调用多次,那么func2的指令就会被展开并复制多次放到func1,会增大func1实际占用的空间.
12.程序是怎么加载到内存中(非Java这种运行于虚拟机上的程序)
- 虚拟内存
- 每个程序只关心虚拟内存即可,虚拟内存地址和实际物理内存地址之间存在一个映射.
- 不同程序可能存在相同的虚拟内存地址
- 程序对应的虚拟内存,是存在磁盘/硬盘上的.
- 内存分页
- 将指定长度的连续物理内存空间称为1页.linux上一个内存分页是4K.
- 虚拟内存到物理内存的映射,实际是关联了1个个内存分页地址.
- 内存分页的存在,使得程序加载时,不必一次性将程序加载到物理内存中,仅加载当下用到的页到物理内存.
- 当要读取特定的页,发现为空,就将数据从对应的虚拟内存中读取出来,加载到该内存分页.
- 内存交换
- 当需要在内存分页中继续加载数据,但物理内存空间不够,会触发内存交换.
- 内存交换会将物理内存中当下'不活跃/长期不使用'的内存分页中的数据存储到硬盘中,释放对应的内存分页,释放的内存分页用于加载当下需要的数据.
- 内存交换类似于Java中的垃圾清理/释放物理内存.
13.Java 这样使用虚拟机的编程语言里面,我们写的程序是怎么装载到内存里
- jvm是一个可运行的程序,而jvm运行时需要的内存,是靠承载jvm的操作系统去维护解决的,会涉及到内存分页,内存交换及虚拟内存映射.
- java程序是加载到jvm运行的,jvm已经是上层应用,不涉及内存分页和内存交换,一般更直接是考虑对象本身的空间大小
14.动态链接
- 概述
- 一个函数/一段可复用的代码Func,实际上会被多个不同的程序调用.
- 如果APP1, * APPN调用Func都要将其重复加载到物理内存中,则会浪费大量的内存空间.为了解决可复用逻辑的内存占用,引入了'动态链接'.
- 实现
- 首先将Func加载到物理内存中
- App1,App2都调用Func,不需要将其重复加载到内存,只需要查找到Func1对应的物理内存地址及Func1需要的数据的内存地址即可.
- 每个App都各自持有1张GOT表.里面存储了需要调用的 所有动态链接/Func 及 外部变量 的虚拟内存地址.
- App1调用Func
- 首先查询PLT表,找到Func在其GOT表中的地址.
- 找到GOT表中对应地址,进而找到Func在App1的虚拟内存中的地址,进而找到Func1在设备物理内存中的地址
- App1需要访问外部变量,也是通过GOT表找到变量对应的虚拟内存地址进而访问.
- 不同的App都调用Func,Func在不同的App中对应的虚拟内存地址是不同的.
15.数字逻辑电路中的逻辑运算法则
- 与/and, 或/or, 非/not, 与非/nand, 或非/nor, 异或/xor, 同或/xnor
- 与/and
- 有0出0,全1出1
- 1,1-->1 , 1,0-->0 , 0,1-->0 , 0,0-->0
- 或/or
- 有1出1,全0出0
- 1,1-->1 , 1,0-->1 , 0,1-->1 , 0,0-->0
- 非/not
- 1出0,0出1
- 1-->0 , 0-->1
- 与非/nand
- 先按与运算,然后结果取反
- 1,1-->0 , 1,0-->1 , 0,1-->1 , 0,0-->1
- 或非/nor
- 先按或运算,然后结果取反
- 1,1-->0 , 1,0-->0 , 0,1-->0 , 0,0-->1
- 异或/xor
- 相异出1,相同出0
- 1,1-->0 , 1,0-->1 , 0,1-->1 , 0,0-->0
- 同或/xnor
- 相同出1,相异出0
- 1,1-->1 , 1,0-->0 , 0,1-->0 , 0,0-->1
16.门电路标识
17.原码表示法
最左边一位代表正负号,1为负,0为正.
剩余几位的累加值, * 1 或 * -1;
- 7
- 0111
- 8
- 0000 1000
- -7
- 1111
18.补码表示法
最左边一位代表的值 * -1 ,再加剩余几位的值.
对于正数,源码表示法 和 补码表示法 都一样,负数不一样
- 7
- 0111
- 8
- 0000 1000
- -7
- 1001
19.无符号数的加法器
- 对于无符号数/正数,原码表示法 和 补码表示法 没有差别, 都是 0*** .
- 加法器
- 当前位 异或/xor 表示当前位初始结果. result-ori
- 当前位 与/and 表示是否进位初始值. next-ori
- 上一位的是否进位值. next-pre
- next-pre 与 result-ori 做 异或/xor 运算得到当前位最终值. result-final
- next-pre 与 result-ori 做 与/and 运算得到当前位是否进位第二个值. next-another
- next-pre 与 next-ori 做 或/or 运算得到当前位是否进位最终值. next-final
- 对于次高位的是否进位最终值. next-pre-final 为1,则结果溢出. next-pre-fianl 为0,则不溢出.
20.使用补码表示的有符号数的加法器
- 正 + 正 , 正 + 负 , 负 + 负 都有可能
- 最高位为A,B, 次高位是否进位为 C.
- 如何判断溢出
- 溢出的场景:
- 2个正数相加,且次高位要进位: 0,0 1
- 2个负数相加,且次高位不进位: 1,1 0
- 溢出场景的逻辑表示
- xnor(A,B) and xor(A,C)
- xnor(A,B) 表示最高位是否一致,都是正数或都是负数
- xor(A,C)/xor(B,C) 表示最高位的任意一个,是否和进位值不同
- xnor(A,B) and xor(A,C)
- 溢出的场景:
- 如果不溢出,如何计算每位上最终值
- 和无符号数的加法器一致
- 当前位xor 和 上一位next-pre 做 xor 的值,作为当前位最终值
- (当前位 做and) 和 (当前位xor及上一位next-pre 做and) 做 or 的值,作为当前位是否进位的值.
- 和无符号数的加法器一致
21.乘法器
- 乘法器本质就是: 加法 + 位移
- 乘法器示例 : 13/1101 * 9/1001
- 上述乘法器的缺点:太慢
- 串行执行,下一个中间结果的值,依赖于上一个中间结果.
- 上述乘法器的优化/不理解:
- 将电路变得复杂,增加该乘法器占用的晶体管的数量,可以降低耗时
- 将电路变得复杂可以增加效率的根本原因:
- 电路天然的并行性
- 电路只要接通,输入的信号自动传播到了所有接通的线路里面
22.浮点数及其产生的运算精度问题
-
浮点数分为单精度浮点数/32位/float 及 双精度浮点数/64位/double
-
浮点数的实际含义
- 浮点数其实是用二进制的科学计数法来表示的
- (−1)s × 1.f × 2e
-
单精度浮点数 32位
- 符号位 s:1位
- -1的0次方,或-1的1次方
- 有效位数 f:23位
- 即二进制下小数点后有23位
- 指数位 e:8位
- 从-126 到 127
- 符号位 s:1位
-
2进制小数部分转10进制
- 2进制小数 0.1001 转换为 10进制.
- 1×2−1 + 0×2−2 + 0×2−3 + 1×2−4 = 0.5625
-
10进制小数部分转二进制
- 小数部分转换成二进制是用一个相似的反方向操作,就是乘以 2,然后看看是否超过 1。如果超过 1,我们就记下 1,并把结果减去 1,进一步循环操作。
- 在这里,我们就会看到,例如十进制中的 0.1 其实变成了一个无限循环的二进制小数,0.000110011。这里的“0011”会无限循环下去.
0.1: 0.1 * 2 = 0.2 -> 0.2 < 1 => 0 0.2 * 2 = 0.4 -> 0.4 < 1 => 0 0.4 * 2 = 0.8 -> 0.8 < 1 => 0 0.8 * 2 = 1.6 -> 1.6 > 1 => 1. 1.6 - 1 = 0.6 0.6 * 2 = 1.2 -> 1.2 > 1 => 1. 1.2 - 1 = 0.2 *** 无限循环 0011
-
10进制数9.1转换为浮点数/2进制
- 整数部分
- 9 -> 1001
- 小数部分
- 0.1 -> 0.0001100110011**
- 整数部分连接小数部分
- 1001.0001100110011**
- 根据浮点数的定义,浮点数就是2进制的科学计数法表示,以上可转换为:
- 1.0010001100110011-- * 2的3次方
- 小数部分是23位
- 再次转换为10进制,就和9.1有微小的差别了
- 整数部分
-
浮点数加减法导致的精度问题
- 浮点数本质上是2进制的科学计数形式 的加减
- 如果2个浮点数,其2对应的指数不一致,相加/相减,首先会转换为指数较大的那个/指数对齐,然后再计算.
- 指数较小的浮点数,转换为指数较大的指数值,需要向右移动,导致其有效位数部分会被抹掉一部分.
- 若抹掉的部分不都是0,就会产生精度问题.
- 32位的浮点数,有效位数只有23位,当两个浮点数相差达到 2的24次方,差不多1600W, 则两者相加,指数值更小的浮点数会因为进位>=24次,导致直接变成0,被完全抹掉.
- double也是类似.
- 精度问题java代码验证
//两者相差超过1600W倍,小的数字会被完全抹掉 float a = 20000000.0f; float b = 1.0f; float c = a + b; System.out.println("c is " + c); float d = c - a; System.out.println("d is " + d); double result = 1.0d - 0.9d; System.out.println(result); System.out.println(0.3f + 0.6f); System.out.println(1 - 0.8); c is 2.0E7 d is 0.0 0.09999999999999998 0.90000004 0.19999999999999996
-
浮点数运算精度问题解决 BigDecimal
23.指令周期
- 指令周期包括:
- Fetch/取得指令
- 从PC寄存器中找到对应的指令地址
- 根据指令地址,将指令从内存中加载到 指令寄存器 中
- PC寄存器自增
- Decode/指令译码
- 根据指令寄存器中的指令,解析成具体操作指令
- Execute/执行指令
- 实际执行具体操作指令,进行算数逻辑运算,数据传输,或直接进行地址跳转
- 重复执行 Fetch -> Decode -> Execute
- Fetch/取得指令
- 永不停息的 Fetch -> Decode -> Execute 循环,称之为指令周期.
- 指令周期 , CPU周期, 时钟周期 的关系
- CPU周期
- 一般把从内存读取一条指令的最短时间,称为CPU周期
- 时钟周期
- 和CPU主频相对应
- 取出一条指令,并执行完毕,至少需要2个CPU周期
- 取出指令至少需要1个CPU周期,执行指令也至少需要1个CPU周期
- 1个CPU周期,通常包含几个时钟周期
- CPU周期
- 控制器
- 从PC寄存器中获取指令地址,从内存中将机器码加载到指令寄存器,将机器码decode成具体指令,都是由控制器完成.
- CPU所需要的硬件电路
- ALU这样的组合逻辑电路
- 根据输入进行计算,得到输出结果
- 寄存器/可以进行数据读写的电路
- 可以存储上一次的计算结果,在需要时候读取使用
- 包括锁存器/Latch , 及 D触发器(Data/Delay Flip-flop)
- 实现PC寄存器的计数器电路
- 高级程序进行各种函数调用、条件跳转,其实只是修改 PC 寄存器里面的地址。
- PC 寄存器里面的地址一修改,计算机就可以加载一条指令新指令,往下运行.
- 控制器/用于指令寻址及解码的译码器电路
- 控制器实际是很复杂的.
- ALU是一种固定功能的电路,需要接受控制器翻译后的不同的具体指令,进行不同的运算.
- 现代CPU支持几千种具体指令,则控制器翻译后的具体指令,至少要有对应的几千种组合.
- 正是控制器的存在,才让'可编程'得以实现.
- ALU这样的组合逻辑电路
24.时钟信号的硬件实现
上面的图就是1个不断将输出当做输入的反向器/非门.
通过1个反相器实现时钟信号:
25.D型触发器
RS触发器电路及其记忆功能
RS触发器电路继续添加2个与门和1个时钟信号/CLK作为电路输入
通过一个时钟信号,我们可以在特定的时间对输出的 Q 进行写入操作
RS触发器电路将R和S两个开关使用反向器进行合并,并加入1个输入的数据信号D/Data,便形成了D触发器
- 使用反向器代替R和S两个开关,相当于保证R和S两个开关的打开状态总是不同的,总是1个打开另一个关闭.
- 至于为什么要使用反向器,还没弄清楚
- 当CLK为0,输出值Q不变
- RS触发器的记忆功能
- 当CLK为1,输出值由Data决定
- Data决定了R和S与之后的与门的输出
- 进而决定A->B->Q的值
D型触发器
- 一个 D 型触发器,只能控制 1 个比特的读写,但是如果我们同时拿出多个 D 型触发器并列在一起,并且把用同一个 CLK 信号控制作为所有 D 型触发器的开关,这就变成了一个 N 位的 D 型触发器,也就可以同时控制 N 位的读写。
- CPU 里面的寄存器可以直接通过 D 型触发器来构造。我们可以在 D 型触发器的基础上,加上更多的开关,来实现清 0 或者全部置为 1 这样的快捷操作
- 电路的输出信号不单单取决于当前的输入信号,还要取决于输出信号之前的状态。最常见的这个电路就是我们的 D 触发器,它也是我们实际在 CPU 内实现存储功能的寄存器的实现方式
26.2-1选择器 - 看了知乎也没看懂
www.zhihu.com/question/29… www.zhihu.com/question/34…
27.卡诺图 - 按顺序看
28.最简单的CPU组成
- PC寄存器
- 时钟信号 + D型触发器 + 加法器 实现了PC寄存器.
- 单指令周期处理器
- 让每一条指令,从程序计数,到获取指令,到执行指令,都在1个时钟周期内完成
- 1个时钟周期内,确保可以执行完一条最复杂的指令
- 内存
- 数据可以存储在D型触发器里,我们可以将内存理解为很多个D型触发器放到一起形成的很大一块存储空间.
- 译码器
- 地址译码器
- 指令译码器
- 地址译码器/寻址译码器
- 通过PC寄存器中的值,找到其对应的内存地址
- 寻址最简单的情况,就是从2个地址中选择1个,这样的电路叫 2-1选择器
- 2-1选择器的实现
- 1个反向器只能由1和0两种状态,所以只能从2个地址中选择1个.
- 如果输入的信号有N个不同的开关,我们就能从2的N次方个地址中选择1个.
- CPU是64位的,意味着我们的寻址空间是2的64次方,我们就需要1个有64个开关的地址译码器
- 译码器的本质
- 从输入的多个位的信号中,根据一定的开关和电路组合,选择出自己想要的信号
- 除了能够进行“寻址”之外,我们还可以把对应的需要运行的指令码,同样通过译码器,找出我们期望执行的指令,就是 指令译码器.
- CPU实现的抽象逻辑图
29.指令流水线归纳总结 中山大学 写得非常好
30.单指令周期CPU示意
- 单指令周期CPU会浪费大量的时间用于指令执行完毕后的等待,效率低下.
31.面向流水线的指令设计的CPU
-
把1条指令的 获取指令-指令译码-执行指令 分为3级,就是三级流水线
-
将 执行指令 进一步切分为 ALU计算-内存访问-数据写回,就是五级流水线
-
我们不需要确保最复杂的那条指令在时钟周期里面执行完成,而只要保障一个最复杂的流水线级的操作,在一个时钟周期内完成就可以
-
如果某一个操作步骤的时间太长,我们就可以考虑把这个步骤,拆分成更多的步骤,让所有步骤需要执行的时间尽量都差不多长
-
现在的ARM或Intel的CPU,流水线已经达到14级.
-
N级流水线,意味着在同一个时钟周期内,可以运行N条指令的不同阶段/流水线级.
-
通过同时在执行多条指令的不同阶段,我们提升了 CPU 的“吞吐率”.
-
面向流水线的指令设计的CPU示意
-
超长流水线的性能瓶颈
- 流水线可以增加CPU的吞吐率,但不能无限制增加流水线级的数量
- 增加流水线深度是有性能成本的
- 我们用来同步时钟周期的,不再是指令级别的,而是流水线阶段级别的。每一级流水线对应的输出,都要放到流水线寄存器(Pipeline Register)里面,然后在下一个时钟周期,交给下一个流水线级去处理。所以,每增加一级的流水线,就要多一级写入到流水线寄存器的操作.
- 如果我们不断加深流水线,这些操作占整个指令的执行时间的比例就会不断增加.会成为新的性能瓶颈.
32.超长流水线的问题
- 同主频情况下,增加流水线深度,其实是降低了CPU的性能.
- 1个流水线级,就需要1个时钟周期.所以1个11级流水线1G的CPU,和1个33级的3G的CPU,性能是差不多的,
- 而每个流水线级都要增加对应的流水线寄存器的开销,实际性能实际更差
- 增加流水线深度,可以同时执行执行多条指令的不同流水线级,这是理想情况
- 增加流水线级,需要增加电路数量,功耗变大了
- 前后指令之间往往存在依赖,多条指令并行执行的比例并不大,因而实际吞吐率不一定能提升
33.流水线设计需要解决的三大冒险: 结构冒险, 数据冒险, 控制冒险
- 结构冒险
- CPU在同一个时钟周期,同时运行两条计算机指令的不同阶段,但是这两个不同阶段,会用到同样的硬件电路.
- 结构冒险,本质上是对同一个硬件电路的竞争问题.
- 结构冒险最典型的例子就是内存的数据访问.
- 内存,只有一个地址译码器/硬件电路
- 指令A需要读取内存中的1条数据,指令B需要读取内存中的指令代码
- 如果A和B在同一个时钟周期执行上述流水线级,就会产生竞争/资源冲突
- 为解决内存数据访问的结构冒险,现代CPU对CPU内部的告诉缓存进行了区分:将高速缓存分成了 指令缓存 和 数据缓存.
- 现代CPU不会直接访问主内存,会将指令和数据加载到自身的高速缓存中
- 指令缓存和数据缓存的拆分,使得CPU在同一个时钟周期进行数据访问和取指令时候,避免资源冲突.
- 结构冒险的解决:本质上是增加硬件电路资源.例如对高速缓存进行区分.
- 数据冒险
- 数据冒险,就是在同时执行的多个指令之间,有数据依赖的情况.
- 数据冒险的解决: 流水线停顿,也叫流水线冒泡
- 在进行指令译码时,会拿到对应指令所需要访问的寄存器和内存地址,可以判断出来,是否对前面的指令存在数据依赖.
- 如果存在数据依赖,可以让该指令流水线停顿一至多个时钟周期
- 时钟周期会不断运行,实际上我们是在执行后续步骤前,插入一至多个NOP(什么都不做)的操作