计算机结构基础-课堂笔记

计算机结构基础

讲义复习
BUL EE2623 Computer Architecture and Interface
Dr. Takebumi Itagaki

冯诺依曼架构

组成部分： CPU/ALU,I/O, Buses, Main Memory 特征： 所有的部分都通过总线连接 总线的类别： 数据总线，地址总线，控制总线

数制

十六进制，十进制，八进制，二进制的相互转化。

二进制整数的表达和运算

Unsigned

不表示负数，因此第一位比特位到最后一位都可以用来表示数
- 逻辑运算
AND（乘法） OR（加法） NOT（取反） XOR（取异） #### Signed
可以表示正数，负数，0， 第一位比特位表示正负号：0为正，1为负。
因此表示范围折半，以8比特为例，Unsigned表示的范围为0_{255，而Signed表示的范围为-128}127（中间有0，故不是128）。
- 转换
转换为Signed的方法是先找到十进制绝对值对应的二进制数，取反码后+1得到二补码，即Signed Number。
- 加减法
二补码的加法是异或运算，比特相同取0，不同取1。
减法看做是与负数相加。

加法要注意判断是否发生溢出，有两种思路可以判断是否发生了溢出。
1. 转换为十进制加减法，看是否发生了溢出 2. 遵循两个原则：
a. 进位值的比特位数与数据的比特位数相同
b. 如果进位值的前两位是"01"或者是"10"，那么就发生了溢出。

• 乘法
  类似于十进制乘法：第一行的所有位与第二行的每一个比特位分别相乘并作移位，最后相加。 单个比特位的乘法遵循：“除了\(1×1=1\)外，其余结果都为0。（与0相乘都为0。）”

二进制浮点数的表达

IEEE 754

IEEE 754是用来表示二进制浮点数的标准，基于二进制。其中有32位，64位，128位表示方法，以32位为例：32位浮点数的表示方法为：

Width of Bits	1	8	23
Content	Sign	Exponent	Fraction
bias: +127

• Bias
  为了让Signed更方便的进行比较，将Signed转换成二进制后的指数部分人为地加一个Bias使得指数部分转变到Unsigned的范围内（0和255特殊处理）便于比较。
  Bias的值规定是exp位十进制数的中位数或中间两个数的平均数。
  IEEE 754 能够表示0， 规格数（Exp部分不为0），非规格数（Exp部分为0，如果Exp小于0则把Exp划到0后，剩下的部分进入小数部分），无穷和其他未规定的计算结果（NaN）。
  

• 十进制转IEEE754

  1. 确定正负
  2. 小数部分（\(2^{-k}\)）和整数部分（\(2^{k}\)）分别写出二进制形式（负数不需要转化为补码），合并，中间以小数点隔开
  3. 将小数点移动到第一位和第二位末尾，假设移动距离为\(x\)，后面的指数部分写作\(2^x\)。
  4. 取现在的小数部分，并在末尾补0直到小数部分的总比特数为23位。
     
  5. 取现在的指数部分\(x+bias\)，并转换为二进制填入Exp中。
     

• IEEE754转十进制
  \[(-1)^s(1+x)2^{exponent-127}\]
  其中\(s\)为符号位，为0则表示正数，反之1为负数；\(x\)为第9～31位共23位所表示的小数的十进制；\(exponent\)为第1～8位表示的幂数。

• 运算规定
  规定如下的情况结果会是Not A Number(e全是1，f=0)：

  1. \(⨦0 ÷ ⨦0\)
     
  2. \(∞-∞\)
     
  3. \(⨦∞÷⨦∞\)
     
  4. \(⨦∞ × 0\)

  规定如下的情况结果会是无穷(e全是1,f$̸=$0)：

  1. \(∞ × ∞\)
     
  2. \(∞ + ∞\)
     
  3. \(nonezero ÷ 0\) 规定\(n ÷ ∞=0\)(e全是0,f全是0)。

• 范围

  • 最大正数：
    \((2-2^{-23}）2^{127}≈2^{128}\)
    (0 | 1111 1111 | 1111 1111 11111 1111 1111 111)
    

  • 最小非规格数：
    \(2^{-23}×2^{-127}=2^{-150}\)
    (0 | 0000 0000 | 0000 0000 0000 0000 0000 001)
    

    请注意，这是在不考虑移位的情况下，如果考虑移位，那么这个数应该为\(2^{-23}×2^{-126}=2^{-149}\)

  • 最小正数：
    \(2^{-126}\)
    (0 | 0000 0001 | 0000 0000 0000 0000 0000 000)

IBM Float System

IBM Float System是基于基于十六进制的浮点数表示方法。
32位IBM 浮点数的表示方法为：

Width of Bits	1	7	24
Content	Sign	Exponent	Fraction
bias: +64

• IBM Float转十进制 \[(-1)^s\frac{M}{2^{24}}16^{exponent-64}\] \(M\)是24位小数部分转成10进制后的数。

• 范围 \(16^{-88}\)-\(16^{64}\)

内存

分级存储

由于CPU的速度受到内存读取速度的牵制，因此有必要将内存进行分级，读写速度越快的内存越靠近CPU，但是由于成本等原因，其储存空间越小。 将内存可以大致分为几层：
- CPU内部的寄存器：用于存放临时数据，读写速度非常快，储存空间非常小，断电消失。
- CPU外部的存储（RAM）： 用于存放程序和数据，读写速度相对快，储存空间相对大，断电消失。
- 外部的永久储存（硬盘）：读写速度慢，储存空间大，断电可以保存。
### 数据的组织 \[\begin{array}{c} bit & 1 \\ byte & 4 \\ word & 8 \\ Longword & 16 \end{array}\] 在主存储器中，每一个Byte都对应了一个地址，但是英特尔和摩托罗拉有两种不同的存放数据的方式，一种(Intel)是先存最低位（LSB），再存最高位(MSB)，称为小端模式（Small Endian）另一种（摩托罗拉）是先存最高位（MSB），再存最低位（LSB），称为大端模式（Big Endian）。
具体而言，小端的LSB被存储到最小的地址，然后下一个字节被存储到更大的地址，直到MSB被存储到最大的地址。
大端的MSB被存储到最小的地址，然后下一个字节被存储到更小的地址，直到LSB被存储到最大的地址。
因此数据在两种机器间必须先要转换，才能存放再另一种机器中。

程序与指令

CPU中模块的连接方式

寄存器： 数据总线
ALU： 地址总线
控制单元(CU): 控制总线

寄存器

寄存器可以分为用户可见（数据寄存器，地址寄存器，条件寄存器 ）和不可见的两种寄存器。 状态和控制寄存器：
PC（指针）：指向下一条指令对应的地址 MAR（内存地址寄存器），MBR（Memory Buffer Register 有时也被称为MDR,Memory Data Register,内存缓冲寄存器）：将指令从内存放入缓冲区，协调CPU与存储的速度。 指令寄存器： 存放当前的指令

指令的运行

1. 将PC指向的内容移到MAR,PC指向下一条指令
2. 将MAR的内容移到MBR
3. 将MBR的内容移到IR
4. 将IR的控制内容交给CU，地址内容交给MAR
5. 将MAR的内容移到MBR
6. ALU执行
7. ALU返回结果到指定内存

有两种执行指令的方式：
- 硬件连接（Hardwiring） 一种指令对应一个硬件
优点：
快速，一个时钟内就能够解码一条指令

• Micro-Programming 每条指令都转换成最原始的指令（Micro-instructions），对应了一个指定的门或者触发器等等，在CU中被执行。
  因此Micro-Programming 是仅次于逻辑电路的第二层级，它也被称作微码(Micro-code)，将软件与硬件连接起来。
  优点：
  1. 可以创建任何复杂的指令或指令集
  2. 灵活，能够允许用户进行micro-program
  3. 有更高级的语言层

栈和缓存

栈

原则：后进先出
入栈（Push）： 将新节（node）放入栈顶
出栈（Pop）： 将栈顶节移除栈
溢出： 节数量超过了栈能够容纳的最大限度
优点： 1. 分配简单
2. 当函数退出的时候栈会自动回收

缺点：
1. 有溢出可能 2. 由于函数结束后栈会自动回收，因此如果有别的函数想要使用当前函数的返回值时，就必须要在当前函数执行结束前复制返回值以避免被回收。

使用栈结构与使用寄存器结构相比：
1. 指令更小，因为操作对象（操作数）不需要指定地址 2. 执行速度更慢，因为堆栈在外部内存中

缓冲

原则： 先进后出 溢出： 写速度大于读速度 空缓冲： 读速度大于写速度 缓冲分为两种：线形缓冲和环形缓冲（应用：视频处理）。 缓冲区大小的影响：
- 缓冲区过大
1. 启动时间长
2. 填满缓冲区的时间也长

• 缓冲区过小
  

1. 更容易溢出
   
2. 如果缓冲区不够容纳所有的中断，系统会出错

拓扑结构（物理）

类型	优点	缺点
Liner	1. 连接简单 2.用线短	1. 如果主线断所有都断 2. 主线断时难以查错 3. 两端需要端子
Ring	1.加入简单	1. 一处断，处处断
Star*	1. 连接简单 2.设备之间不会有干扰 3.简单查错 4.加入和移除新设备简单	1. 需要更多的线 2. Hub断，所有断 3.成本高(因为需要Hub)
Tree*	1.点对点的连线	1.难以布线 2.主线断，处处断

拓扑协议*

以太网

如果网络没人广播，目标就广播。如果有人广播，目标等待其他人结束广播后广播。

本地会话

如果目标需要传输和发送空令牌，数据就会附加到空令牌上，在Token Ring中传输直到找到接收者。

ATM

所有的数据以固定大小的小包传送，通常在两个局域网间使用。

I/O 接口

I/O 接口的功能是为CPU和总线提供一个标准的借口。同时兼容各种I/O设备的借口需求，并且释放CPU对于I/O设备的管理。

I/O的控制方式

1. 程序I/O
   在I/O执行命令时，CPU一直等待并检测I/O是否完成任务，直到I/O执行完成。
   特点：
   程序I/O损失了CPU大部分的计算力，是一种低下的连接方式。
   
2. 中断I/O
   CPU发出一个指令到I/O，之后做其他的任务直到I/O完成操作。 I/O完成操作后，会发出中断指令中断CPU当前的任务。 CPU处理完来自I/O的任务后，继续执行之前的任务。
   
3. DMA
   由于冯诺依曼架构中内存，I/O，存储都通过总线连接，使得数据在I/O 与内存之间能够直接传输数据成为可能。
   整块数据在I/O与内存之间的传送在DMA控制器的控制下完成，仅在传输数据块的开始和结束时才需要CPU干预。 DMA会在CPU不使用总线时接管总线。

I/O接口的类型

PCI，ATA，ISA，USB等等……

串行和并行连接

串行连接： 一比特一时钟发送数据
并行连接： 所有的比特会一起发送
### 串行连接的方式 1. 串行连接的时分复用
CPU在每一个单位时间内都处理不同并行通道内的一个数据包。 每个通道的前几个比特是用来与系统进行时间同步的。
例子： GSM（2G），TD-CMDA（3G） 2. Teletype Teletype的一个数据包内通常包括： Start bit， Content， Stop Bit， Parity Bit。
串行需要信号去控制数据传输的暂停和恢复以适配不同速度的数据流。

硬件-UART

UART 遵循先进先出原则，传输异步信号。

并行连接

并行连接往往需要不止一条数据线传输，因此体积会更大，同时数据传输更容易受到线长的限制。
并行连接一般有4种Pins： Data Pins, Control Pins, Status Pins, Ground Pins。

对比

1. 通常串行传输比并行传输速度更快。
   
2. 串行传输不易出现Clock Skew（时钟信号在不同组件中到达的时间有差异）。
3. 串行传输占用空间更少。
4. 串行线路不容易受到周围线路的影响。
5. 串行线路避免内Crosstalk（数据在传输时对另外的线路产生影响）。
   
6. 串行线路由于Pin数更少，因此更便宜。

并行算法

并行算法的类型*

1. Pipline 在执行第一个任务的同时准备后面的任务。
   所有的任务都不可能比整个任务链的处理速度更快，先前的任务必须要完成后才能完成之后的任务。 但是大多数的算法都不会有太长的计算链。

并行计算

并行计算体现在两点：
1. 一个处理器执行时分复用（多线程）
2. 拥有不止一个处理器 （多核心）
弗莱因分类法将并行计算机按照指令和数据流分为四类：SISD，MISD，SIMD，MIMD。 即单/多指令，单/多数据流。
通常n个并行处理器比n倍快的单个处理器效率更慢，但是并行系统更便宜。

基本定律

阿姆达尔定律: 理想中对整个系统最大的改进是对系统中的部分进行改进。
古斯塔夫森定律*: \(S_{latency}=1-p+sp\)
\(S_{latency}\)： 整个任务执行延迟的理论加速。
\(s\)：受益于系统资源改善的部分的加速。
\(p\)：整个任务中，相对于改进前受益于改善后的部分所占的百分比。

并行计算的层级

1. 比特层级
   加倍字长。 部分需要两个字长才能运行的指令（需要两个时钟）变成一个字，进而在一个时钟内就能运行。
   
2. 指令层级 基础的分量级处理器只能在一个时钟内运行不到一个指令。
   对这些指令重排，并整合成指令群。现代处理器还将pipline分成了多级，因此在一个时钟内可以运行一条指令。
   超标量处理器有多个处理单元，因此可以在一个时钟内运行多条指令。但是指令来源于同一个指令流。多核处理器也可以在一个时钟内运行多条指令，但指令来源于多个指令流。
   
3. 任务层级 将任务分成多个子任务并交给不同的处理器运行。

并行计算的例子*

1. 分布式计算
   与并行计算并无太多区别，可以理解为并行计算。
   
2. 网格计算
   通过Internet将不同的计算机连接（需要中间件兼容），但是由于Internet的低带宽高延迟特性，因此性能往往不好。
   
3. 可重构计算（FGPA）
   将一个可编程门
4. GPU
5. 向量处理器

哈佛架构

和冯诺依曼架构最大的不同是：内存被分为了两部分：Program Memory（静态内存）和 Data Memory（动态内存）。

与冯诺依曼架构对比

1. 哈佛架构的CPU可以在同一时间读取指令和数据（同时性），且指令和数据不会在fetch时竞争（独立性）。
   
2. 哈佛架构允许Program Memory 和 Data Memory的储存介质不同。
   
3. 哈佛架构允许像访问数据一样访问指令储存器的内容。
4. 冯诺依曼架构中代码被视为数据，数据也被看作代码。 因此冯诺依曼架构允许从硬盘中读取和执行程序。
   现代的处理器通常是哈佛架构和冯诺依曼架构的混合架构，通常被视作是改进的哈佛架构。 如：x86，ARM， PowerPC。

校验码

奇偶校验码

在数据包后加上一个校验位，使得所有的比特位中1的总数为奇数/偶数。
缺点： 无法探测错误的位置。 对于两位以上的错误，无法矫正错误。

汉明码

在一串\(d\)位数据的\(2^{n-1}\)位上加入校验位，校验位的数量\(c\)满足：\(2^c-1>=d\)。
第\(n\)个校验码的校验条件满足： 从第\(2^n\)位开始，使用偶校验检测\(2^n\)位，再跳过\(2^n\)位，再检测\(2^n\)位，重复直到检测最后一位。
数据和校验码的位置序号是相反的,数据的比特位编号是从右到左依次减小，校验码的比特位是从右到左依次增大 缺点： 当只有一个校验码出错时，有50%的概率是数据出错，有50%的概率是校验码自己出错，无法确定。 有两个比特出错时可以检验，但无法校正。

前向纠错码

前向纠错是一种差错控制方式，它是指信号在被送入传输信道之前预先按一定的算法进行编码处理，加入带有信号本身特征的冗码，在接收端按照相应算法对接收到的信号进行解码，从而找出在传输过程中产生的错误码并将其纠正的技术。
前向纠错码分为两种：卷积码（一个比特一个比特地处理）和块码（一个块一个块地处理）。 块纠错码的代表是里得-所罗门码。

循环冗余校验

循环冗余校验是利用里得-所罗门码进行校验的一种方式，具体是将整个数据包的每一位转换成多项式的系数（值）和次数（位置）。在伽罗瓦域中以输入值作为被除数做多项式除法，得到的余数作为校验的结果。
循环冗余校验不能检测恶意插入的错误。

哈希函数

将原数据输入哈希函数，得到的将是一个哈希值序列的信息摘要。对原数据任何的更改都会导致哈希值序列发生改变，因此可以检测恶意或偶然出现的错误。

应用

Internet--和校验
数字卫星电视信号--循环冗余校验
硬盘--循环冗余校验
条形码
快速响应矩阵（QR二维码）--循环冗余校验

CPU的类型

CPU按照指令集的复杂程度可以分为5类架构：
Complex/ Reduced/ Minimal/ One/ Zero Instruction Set Computer

CISC

每一条指令都能够运行一些复杂的低层级的操作，比如算术运算或者从内存加载等等，所有的操作都在一条指令内被执行。
优点： 一些复杂或者高级的操作（例如循环）能够直接被整合为一条指令。
缺点： 从简单的指令加载复杂的操作并不一定能够提高电脑的性能。
常见的CISC处理器架构： x86
现代x86处理器能够解码并将指令划分到动态的缓冲微操作中，以便能够在单线程中运行更大的负指令集，同时精简了并行计算。

RISC

RISC 的设计遵循： 如果简化的指令集能够使得每条指令更快的运行，那么简化的指令集就能提高性能。 特点：
1. 基本上大多数的指令都有相似的结构和固定的长度。通常为一个字长加上固定比特位的操作码。
2. 寄存器大多相似且通用（浮点寄存器除外），能够简化编译设计。
3. 简单的地址模型。
4. 硬件支持的数据类型更少。
优点：有更好的pipeline stagesstages 和更快的时钟频率 因此更高效。
常见的RISC处理器架构： ARM 和 PowerPC

MISC

处理器有很少的基本操作和对应的操作码，通常基于栈结构。
优点： 指令和解码单元更小，因此单个指令的运行速度更快。
缺点： 指令更依赖于串行结构，减少了并行计算。
常见的MISC处理器架构： INMOS

OISC 和 ZISC

OISC： 只使用一条指令，不需要操作码。
ZISC： 基于纯模式匹配而不需要微指令。

特殊化处理器*

Cell Processor

Cell Processor是一种拥有很多sub-processor的处理单元，其特征在于： 1. 所有的子处理器都是独立的，但是公用一个总线，在通信上并不是独立的。
2. 只要任务的粒度（Granularity）能够让所有的子处理器都能够同时工作，那么任务就能够被快速处理。

GPU

GPU是一种用于加速建图和图像处理的专门化处理器。 GPU内部高度并行化。
功能： 加速渲染多边形和纹理匹配， 解码高清视频等等。

DSP

专门化的数字信号处理器，用于声音、图像、雷达系统。
功能： 数字信号与模拟信号的转换和处理。
DSP 的指令集优化用于处理数学运算、特殊的地址模型、特殊化的循环控制。
DSP 中的数学计算常常是Fixed-point 计算。
DSP 不支持虚拟内存和内存保护。