1. 图灵机的工作方式 


图灵机的基本组成如下:
  • 有⼀条纸带,纸带由⼀个个连续的格⼦组成,每个格⼦可以写⼊字符,纸带就好⽐内存,⽽纸带上的 格⼦中的字符 就好⽐内存中的数据或程序。
  • 有⼀个读写头,读写头可以读取 纸带上任意格⼦中的字符,也可以把字符写⼊到纸带的格⼦中。
  • 读写头上有⼀些部件,⽐如存储单元、控制单元、运算单元:
  1. 存储单元:⽤于存放数据。
  2. 控制单元:⽤于识别字符 是数据还是指令,以及控制程序的流程等。
  3. 运算单元:⽤于执⾏运算指令。

例:简单运算 1+2 的执行过程
1. ⾸先,⽤读写头把 "1"、"2"、"+" 这 3 个字符 分别写⼊到纸带上的 3 个格⼦,然后读写头先停在 "1" 字符对应的格上:

2. 接着,读写头读⼊ "1" 到存储设备中 (这个存储设备称为 图灵机的状态):


3. 然后读写头向右 移动⼀个格,⽤同样的⽅式把 ”2” 读⼊到图灵机的状态,现在图灵机的状态中 存储着两个连续的数字, 1和2:

4. 读写头再往右 移动⼀个格,就会碰到 "+" 号,读写头读到 "+" 号后,将 "+" 号传输给控制单元,控制单元发现是⼀个 "+" 号⽽不是数字,所以没有存⼊到状态中 (因为 "+" 号是运算符指令,作⽤是 加和⽬前的状态),于是通知运算单元⼯作。运算单元收到 要加和状态中的值 的通知后,就会把状态中的 ”1”和"2" 读⼊并计算,再将计算的结果 "3" 存放到状态中:

5. 最后,运算单元将结果 返回给控制单元,控制单元将结果 传输给读写头,读写头向右移动,把结果 3 写⼊到纸带的格⼦中:

总结:从上⾯图灵机计算 1+2 的过程,可以发现图灵机主要功能 就是通过读写头读取纸带格⼦中的字符,然后交给控制单元识别字符 是数字还是运算符指令。如果是数字则存⼊到图灵机状态中,如果是运算符,则通知运算单元 读取状态中的数值并进⾏计算,计算结果最终返回给读写头,读写头再把结果 写⼊到纸带的格⼦中。

2. 冯诺依曼模型

在1945年,冯诺依曼和其他计算机科学家们提出了 计算机具体实现的报告,其遵循了图灵机的设计,⽽且还提出 ⽤电⼦元件构造计算机,并约定了⽤⼆进制进⾏计算和存储,还定义计算机基本结构为 5 个部分,分别是中央处 (CPU)内存输⼊设备输出设备总线。(这 5 个部分也被称为 冯诺依曼模型)


(1) 内存:
  • 我们的程序和数据都是 存储在内存,存储的区域是线性的
  • 数据存储的单位 是⼀个进制位 (bit),即0或1。最⼩的存储单位 是字节 (byte)。(1字节等于8位)
  • 内存的地址是 从0开始编号然后⾃增排列,最后⼀个地址为内存总字节数-1,这种结构好似我们程序⾥的数组,内存读或写任何⼀个数据的速度 都是⼀样的。

(2) 中央处理器 (CPU):
中央处理器就是CPU,32位和64位CPU最主要区别在于 ⼀次能计算多少字节数据。(这⾥的 32位和64位,通常称为 CPU的位宽
              32位CPU ⼀次可以计算 4个字节
              64位CPU ⼀次可以计算 8个字节
原因:之所以CPU要这样设计,是为了能计算更⼤的数值。如果是 8位的CPU,那么⼀次只能计算 1个字节0~255 范围内的数值,这样就⽆法⼀次完成计算10000 * 500 。于是为了能⼀次完成 更大数值的运算,CPU需要⽀持 多个byte⼀起计算,所以CPU位宽越⼤,可以计算的数值就越⼤。(⽐如:32位CPU 能计算的最⼤整数是4294967295)
  • CPU内部还有⼀些组件:常⻅的有 寄存器控制单元逻辑运算单元等。(其中,控制单元负责控制 CPU⼯作、逻辑运算单元负责计算、⽽寄存器可以分为多种类,每种寄存器的功能⼜不尽相同)
  • CPU中的寄存器主要作⽤:存储计算时的数据。(有了内存为什么还需要寄存器? 原因很简单,因为内存离CPU太远了,⽽寄存器就在CPU⾥,紧挨着控制单元和逻辑运算单元,计算过程中存取数据的速度会很快,因此计算的速度会更快)
常⻅的寄存器种类:
  1. 通⽤寄存器:⽤来存放 需要进⾏运算的。(⽐如:需要进⾏加和运算的两个数据)
  2. 程序计数器:⽤来存放 CPU要执⾏的 下⼀条指令所在的内存地址
  3. 指令寄存器:⽤来存放 程序计数器指向的指令,也就是指令本身,指令被执⾏完成之前 都存储在这⾥。

(3) 总线:
总线于 CPU和内存以及其他设备之间 的通信,总线可分为3种:
  1. 地址总线:⽤于指定 CPU将要操作的内存地址。
  2. 数据总线⽤于读写内存的数据。
  3. 控制总线⽤于发送和接收信号。(⽐如中断、设备复位等信号,CPU 收到信号后⾃然进⾏响应,这时也需要控制总线)
CPU读写内存数据时,⼀般需通过两个总线:⾸先要通过 地址总线 来指定内存的地址;再通过 数据总线 来传输数据。

(4) 输入、输出设备:
输⼊设备向计算机输⼊数据,计算机经过计算后,把数据输出给输出设备。(期间,如果输⼊设备是键盘,则按下按键时 是需要和CPU进⾏交互的,这时就需要⽤到控制总线了)

3. 线路位宽与CPU位宽

问题:数据是如何通过线路传输的呢?
              通过操作电压,低电压表示0,⾼压电压表示1。
如果构造 ⾼低⾼ 这样的信号,可以表示为 101⼆进制数据,如果只有⼀条线路,就意味着每次只能传递 1bit的数据 (即0或1),那么传输101这个数据,需要经过3次传输才能完成,这样的效率⾮常低。
这样⼀位⼀位传输的方式,称为串行传输 (下⼀个 bit 必须等待上⼀个 bit 传输完成才能进⾏传输)。若想⼀次传多位数据,则需要增加线路,这样次传输多位数据的方式,称为并行传输
为了避免低效率的 串行传输的方式,线路的位宽最好⼀次就能 访问到所有的内存地址。(CPU操作内存地址 需要地址总线,如果地址总线只有1条,那每次只能表示 0或1 这两种情况,所以CPU⼀次只能操作 2个内存地址;如果CPU想要操作 4G(2^32)的内存,那么就需要 32条地址总线)
CPU的位宽 最好不要小于线路位宽。(如果32位CPU 控制40位宽的地址总线和数据总线,⼯作起来就会⾮常复杂且麻烦,32位CPU 最好和32位宽的线路搭配,因为32位CPU⼀次最多只能操作 32位宽的地址总线和数据总线。)
如果⽤32位CPU去加和 两个64位⼤⼩的数字,就需要把2个64位的数字 分成2个低位32位数字和2个⾼位32位数字 来计算。先加和两个低位的 32位数字,算出进位,再加和两个⾼位的 32位数字,最后加上进位,就算出最后结果了,可以发现32 位CPU 并不能⼀次性计算出 加和两个64位数字的结果。
而对于64位CPU 就可以⼀次性算出 加和两个64位数字的结果,因为64位CPU 可以⼀次读⼊64 位的数字,并且64位CPU内部的逻辑运算单元 也⽀持64位数字的计算。
但是这并不代表 64位CPU性能⽐32位CPU ⾼很多,因为很少应⽤ 需要算超过32位的数字,所以如果计算的数额 不超过32 位数字的情况下,32位和64位CPU之间 没什么区别的,只有当计算 超过32位数字的情况下,64位CPU的优势才能体现出来。
另外,32 位CPU 最⼤只能操作4GB内存,如果装了8GB内存条 就会造成浪费。64位CPU可以寻址的范围更⼤,理论最⼤的寻址空间为 2^64 。
注:硬件的64位和32位 指的是 CPU的位宽,软件的64位和32位 指的是 指令的位宽。

4. 程序执行的基本过程

程序就是⼀条⼀条指令,所以程序的运⾏过程 就是把每⼀条指令⼀步⼀步的执⾏起来,负责执⾏指令就是CPU。

CPU执行程序的过程:
  • 第⼀步:CPU读取 程序计数器的值,这个值是 指令的内存地址,然后CPU的控制单元操作地址总线 指定需要访问的内存地址,接着通知内存设备 准备数据,数据准备好后 通过数据总线 将指令数据传给CPU,CPU收到内存传来的数据后,将这个指令数据 存⼊到指令寄存器
  • 第⼆步:CPU分析 指令寄存器中的指令,确定指令的类型和参数。如果是计算类型的指令,就把指令交给逻辑运算单元运算;如果是存储类型的指令,则交由控制单元执⾏。
  • 第三步:CPU执⾏完指令后,程序计数器的值⾃增,表示指向下⼀条指令。(⾃增的⼤⼩由 CPU的位宽决定,⽐如:32 位的CPU,指令是4个字节,需要消耗 4个内存地址指向的存储单元 来存放,因此程序计数器的值 会⾃增4)
总结:程序执⾏的时,CPU会根据 程序计数器⾥的内存地址,从内存中 把需要执⾏的指令 读取到指令寄存器 后执⾏,然后根据指令⻓度⾃增,开始顺序读取下⼀条指令。(CPU从程序计数器读取指令、到执⾏、再到下⼀条指令,这个过程会不断循环,直到程序执⾏结束,这个不断循环的过程被称为 CPU的指令周期

5. a=1+2 的具体执行过程

编译:CPU无法直接运行高级语言。首先,需要将高级语言程序 编译成汇编语⾔程序,再⽤汇编器 将汇编语⾔程序翻译成机器码。(机器码由 0和1 组成的机器语⾔,⼀条条的机器码 就是⼀条条的计算机指令,这才是CPU能够识别的语言)
存储:数据和指令是分开区域存放的。1和2是数据,存放数据的区域 称为数据段存放指令的区域 称为正文段

  • 数据1 被存放到 0x104位置;
  • 数据2 被存放到 0x100位置;
编译器把 a=1+2 翻译成 4条指令,存放到正⽂段中。
如图,这 4 条指令被存放到了 0x200 ~ 0x20c 区域中:
  • 0x200 的内容load指令 将 0x100 地址中的数据 2 装⼊到寄存器R0 ;
  • 0x204 的内load指令 将 0x104 地址中的数据 1 装⼊到寄存器R1 ;
  • 0x208 的内容:add指令 将 寄存器R0和R1 的数据相加,并把结果存放到 寄存器R2 ;
  • 0x20c 的内容:store指令 将 寄存器R2 中的数据 存回数据段中的 0x108 地址中,这个地址就是变量a 在内存中的地址;
编译完成后,具体执⾏程序时,程序计数器会被设置为 0x200 地址,然后依次执⾏这 4 条指令。
因为上⾯的例⼦是在 32位CPU 上执⾏的,所以⼀条指令占 32 位⼤⼩,每条指令间隔 4个字节。
⽽数据的⼤⼩ 是根据程序中指定的变量类型 而定。(⽐如:int类型的数据则占 4个字节, char类型的数据占 1个字节)


(1) 指令:
不同的 CPU 有不同的指令集,对应着 不同的汇编语⾔和不同的机器码,接下来选⽤最简单的 MIPS指集,来看看机器码是如何⽣成的,这样也能明⽩⼆进制的机器码的具体含义。
MIPS指令是⼀个 32位的二进制,高6位 代表着操作码,表示这条指令是⼀条什么样的指令,剩下的26位 不同指令类型所表示的内容不同,主要有三种类型R、I、J。

字段命名:
    op:操作码 (指令类型)
    rs:第一个源操作数寄存器号
    rt:第二个源操作数寄存器号
    rd:目的寄存器号 (存放操作结果)
    shamt:位移量 (执行移位操作时 指明需要移动的次数
    funct:功能码
  • R指令:⽤于算术和逻辑操作时,需要读取和写入数据的寄存器号;用于逻辑位移操作时,还需要位移量。当前⾯的操作码长度不够时,功能码 用来扩展操作码 来表示对应的具体指令。
  • I指令:⽤于数据传输、条件分⽀等。后面三个字段所占的11位 被合并成一个字段,这个字段表示 ⼀个地址值或常数。
  • J指令:⽤于跳转。操作码字段之后的26位 合并成一个字段,表示跳转目标地址。

将前面例子的这条指针:”add指令 将 寄存器R0和R1 的数据相加,并把结果放⼊到寄存器R2"   翻译成的机器码如下:

加和运算 add指令 是属于 R指令类型:
  • add 对应的 MIPS指令 的操作码是 000000,以及最末尾的功能码是 100000;
  • rs 代表 第⼀个寄存器R0 的编号,即 00000;
  • rt 代表 第⼆个寄存器R1 的编号,即 00001;
  • rd 代表 ⽬标的临时寄存器R2 的编号,即 00010;
  • 因为不是位移操作,所以位移量是 00000;
将上面所有的字段连起来 就是⼀条 32位 的MIPS加法指令。(⽤16进制表示的机器码 则是0x00011020)
  • 编译器编译程序时 构造指令,这个过程叫作指令的编码。 
  • CPU执⾏程序时 解析指令,这个过程叫作指令的解码

现代CPU 大多数使⽤流水线的⽅式 来执⾏指令,所谓的流⽔线 就是把⼀个任务 拆分成多个⼩任务。
如⼀条指令通常分为 4个阶段,可以构造 4级流⽔线,如下图:

四个阶段的具体含义:
  1. CPU 通过程序计数器 读取对应内存地址的指令,这个部分称为 Fetch(取得指令)
  2. CPU 对指令进⾏解码,这个部分称为 Decode(指令译码)
  3. CPU 执⾏指令,这个部分称为 Execution(执行指令)
  4. CPU 将计算结果存回寄存器 或者将寄存器的值回写内存,这个部分称为 Store(数据回写)
上⾯这4个阶段,我们称为指令周期,CPU就是⼀个周期接着⼀个周期工作,周⽽复始。
事实上,不同的阶段 是由计算机中 不同的组件完成的:
  • 取指令阶段:指令存放在存储器⾥的。实际上,通过 程序计数器和指令寄存器 取出指令的过程,是由控制单元操作的。
  • 指令译码阶段:也是由控制单元操作的。
  • 指令执行阶段:⽆论是进⾏ 算术操作、逻辑操作,还是进⾏ 数据传输、条件分⽀操作,都是由算术逻辑单元操作的 (也就是由运算器处理的)。但如果是⼀个简单的 ⽆条件地址跳转,则是直接在控制单元中完成,不需要⽤到运算器

(2) 指令的类型:
指令从功能的角度划分,可以分为 5大类:
  1. 数据传输类型的指令 (⽐如 store/load 是寄存器与内存间 数据传输的指令,mov 是将⼀个内存地址的数据 移动到另⼀个内存地址的指令)
  2. 运算类型的指令 (⽐如 加减乘除、位运算、⽐较⼤⼩等等,它们最多只能处理两个寄存器中的数据)
  3. 跳转类型的指令 (通过修改程序计数器的值 来达到跳转执⾏指令的目的,⽐如 编程中常⻅的 if-else、swtich-case、函数调⽤等)
  4. 信号类型的指令 (⽐如 发⽣中断的指令 trap)
  5. 闲置类型的指令 (⽐如 指令nop 执⾏后,CPU会空转⼀个周期)

(3) 指令的执行速度:
  • CPU的硬件参数中 有GHz这个参数。⽐如⼀个 1GHz 的CPU,指的是时钟频率是 1G,表示 1 秒产⽣1G次数 的脉冲信号。每⼀次脉冲信号 ⾼低电平转换的过程 表示一个时钟周期
  • 对于CPU来说,在⼀个时钟周期内,CPU仅能完成 ⼀个最基本的动作。时钟频率越⾼,时钟周期就越短,⼯作速度也就越快。
  • 大多数指令不能在⼀个时钟周期完成,通常需要若⼲个时钟周期。不同指令需要的时钟周期是不同的 (比如:加法和乘法 都对应着⼀条CPU指令,但执行乘法指令需要的时钟周期数 ⽐加法多)
对于程序的CPU执行时间,我们可以拆解成  CPU时钟周期数 和 时钟周期时间 的乘积

时钟周期时间 就是前⾯提及的 CPU主频,主频越⾼ CPU的⼯作速度就越快。要想CPU跑的更快,最基本的就是 提升CPU主频,但是今⾮彼⽇,摩尔定律早已失效,现在的CPU主频 已经无法做到每隔18个月 性能就翻1倍了。
缩短CPU时钟周期数 来提高CPU主频,是我们软件⼯程师无法触及的领域,但可以通过 减少程序所需的CPU时钟周期数量 来提升程序的性能。

对于 CPU时钟周期数 可以进⼀步拆解成:指令数 x 每条指令的平均时钟周期数(CPI),于是程序的 CPU执⾏时间的公式 可变成如下:

因此,要想程序跑的更快,优化这三者即可。
  • 指令数:指执行程序所需要的多少条指令,以及哪些指令。(这个层⾯是基本靠编译器来优化。因为同样的代码 在不同的编译器下,编译出来的计算机指令 会有不同的结果)
  • 每条指令的平均时钟周期数 CPI:表示执行⼀条指令 所需要的时钟周期数。(现今⼤多数CPU 通过流水线技术,使得执行⼀条指令 所需要的CPU时钟周期数 尽可能的少)
  • 时钟周期时间:指计算机主频,取决于计算机硬件。(有的CPU⽀持 超频技术,打开超频意味着 将CPU内部的时钟给调快了,因此 CPU的⼯作速度就变快了。但是这也是有代价的,因为CPU跑的越快,散热的压⼒就会越⼤,CPU也就容易奔溃)