一.计算机系统概述

计算机

通用电子数字计算机（ general-purpose electronic digital computer）

通用：不是一种专用设备；所有计算机在给予足够时间和容量存储器的条件下，都可以完成同样的计算；当希望完成新的计算时，不需要对计算机重新设计

电子（非机械）：采用电子元器件

数字（非模拟）：信息采用数字化的形式表示

组织与结构

组织（Organization）：对编程人员不可见

• 操作单元及其相互连接

• 包括：控制信号，存储技术，……

​ • 例如：实现乘法是通过硬件单元还是重复加法？

结构（Architecture）：对编程人员可见

• 直接影响程序逻辑执行的属性

• 包括：指令集，表示数据类型的位数，…

​ • 例如：是否有乘法指令？

指令集体系结构（ISA）

简史

第一代：真空管

第二代：晶体管

第三代：中小规模集成电路

第四代：（超）大规模集成电路

摩尔定律

摩尔定律（Gordon Moore, 1965）

当价格不变时，单芯片上所能包含的晶体管数量每年翻一番 (1965-1969) / 1970年起减慢为每18个月翻一番

更小的尺寸带来更多灵活性和可能性；

由于单个芯片的成本几乎不变，计算机逻辑电路和存储电路的成本显著下降；

减少了对电能损耗和冷却的要求；

集成电路上的内部连结比焊接更可靠，芯片间的连接更少

冯·诺伊曼结构

三个基本原则：

  1. 二进制
  2. 存储程序
  3. 5个组成成分
    1. 主存储器：地址和存储的内容
    2. 算术逻辑单元 / 处理单元：执行信息的实际处理
    3. 程序控制单元 / 控制单元：指挥信息的处理
    4. 输入设备：将信息送入计算机中
    5. 输出设备：将处理结果以某种形式显示在计算机外

冯·诺伊曼的最重要的思想是==“存储程序（Stored-program）”==

性能

计算机设计的主要目标是：提高CPU性能

CPI：平均执行一条指令所需要的周期数

每秒百万条指令（MIPS）：
$$
MIPS = \frac{I_c}{T \times 10^6} = \frac{f}{CPI \times 10^6}
$$
$$
\frac{1}{CPI}是一个周期执行多少条指令， \times f就是每秒执行多少条指令
$$
每秒百万条浮点操作：
$$
MFLOPS = \frac{N_{floating-point \ op}}{T \times 10^6}
$$
基准程序
$$
算术平均： R = \frac{\sum^m_i R_i}{m}\ 适合度量所有测量值的总和是一个有意义的数值
$$
$$
调和平均： R = \frac{m}{\sum^m_i \frac{1}{R_i}}\适用于以系统的执行速率来衡量系统价值
$$
$$
几何平均： R = \sqrt[\frac1n]{\Pi R_i}\适用于衡量计算机的相对性能
$$
其他： 系统加速比、大事件优先原则、Amdahl定律（改进越多效果越差）

计算机的关键问题

CPU的频率不能无限提高

改进CPU芯片结构

内存墙的存在

采用高速缓存

CPU等待I/O传输数据

采用中断机制

兼顾存储容量、速度和成本

层次式存储结构

在本门课及相关作业中，主存不等同于内存；内部存储器（内存）包含寄存器、高速缓存和主存

I/O设备传输速率差异大

采用缓冲区和改进I/O操作技术

计算机部件互连复杂

采用总线

二、数据的机器级表示

二进制

  1. 制造两个稳定态的物理器件容易
  2. 二进制编码、计数运算规则简单
  3. 对应逻辑命题中的“真”和“假”
  4. 便于使用逻辑电路实现算术运算

整数：补码

解决正负号问题

使用补码的原因：二进制原码、反码、移码进行加法运算时都会导致不必要的硬件需求

浮点数：IEEE

规格化数(正)范围：$2^{-126}$ ~ $(2 - 2^{23}) \times 2^{128}$

九、数据校验码

差错

差错：数据在计算机内部进行计算、存取和传送过程中，由于元器件故障或噪音干扰等原因，会出现差错

​ 硬故障：永久性的物理故障，由恶劣的环境、制造缺陷和旧损引起

​ 软故障：随机非破坏性事件，由电源问题或α粒子引起

纠错：使用函数f对操作前后的数据D和D‘生成校验码C和C‘’，将C‘’与C‘比较，相同则输出D’；不同则校正；若无法校正就报告

奇偶校验码

增加1位校验码来表示数据中1的数量是奇数还是偶数

优点：代价低，只需要 1 位额外数据，计算简单

缺点：不能发现出错位数为偶数的情形；不能纠错

适用：对较短长度（1B）的数据进行检错

海明码

将数据分成几组，对每一组都使用奇偶校验码进行检错

校验码位数的确定：

假设校验码K位，可以表示$2^K$种状态。 数据有M位，每次出错一位的话，一共M种情况；校验码K位，每次出错一位的话，一共K种情况； 还有可能不出错，1种情况。
$$
2^K \geq M + K + 1
$$
根据M求最小的K

校验码位置：

Ci是对应的故障字第i位为1的数据位的异或值

将C’‘和C’异或后的结果是故障字，与上表对照得知哪一位出错

码距：同一编码中，任意两个合法编码之间不同二进制数位数的最小值

纠错理论：𝑳 − 𝟏 = 𝑫 + 𝑪, 𝑫 ≥ 𝑪（𝐿是码距， 𝐷是检错位数， 𝐶是纠错位数）

优点：1位错误时可以纠错

缺点：额外成本很大；要求把数据分为字节

循环冗余校验

适用于以流格式存储和传输大量数据

三、整数运算

全加器

实现简单；但随着位数增加会变慢

$$
F = X \oplus Y \oplus C_{in}\
C_{out} = X \cdot Y + X \cdot C_{in} + Y \cdot C_{in}
$$

串行进位加法器（行波进位加法器）

速度快；但随着位数增加电路会越来越复杂

$$
G_i = X_i \cdot Y_i
$$
$$
P_i = X_i + Y_i
$$
$$

$$

$$
C_i = G_i + P_iG_{i-1}+ P_iP_{i-1}G_{i-2}+ \dots + P_iP_{i-1}P_{i-2}\cdot \ldots \cdot C_0
$$

部分先行进位加法器

取得计算时间和硬件复杂度的权衡

布斯乘法

补码除法

浮点数

对阶，尾数运算

乘法：尾数补上隐藏位再相乘，高两位为10或11则需右规

除法：尾数补上隐藏位再相除，商高两位为01则需左规

八、内部存储器

基本概念

  • 地址是内存单元的编号。
  • 地址空间是所有可能地址的集合。
  • 寻址能力是系统能够访问的最大内存容量。

RAM

对存储器中任意数据的访问所花费的时间与数据所在位置无关

​ 易失的（Volatile）

DRAM和SRAM

DRAM 和 SRAM 的对比：

相同点：易失，需要电源供电来保持位值

不同点： DRAM 比 SRAM 具有更简单、更小的位元，但要求能够刷新的电路

​ DRAM 比相应的 SRAM 密度更高、价格更低

​ SRAM 通常比 DRAM 快

​ DRAM 通常满足大容量存储器的需求，SRAM 一般用于高速缓存，DRAM 用于主存

高级的 DRAM 架构：

​ 问题：传统的 DRAM 芯片受到其内部架构和处理器内存总线接口的限制；

​ 传统 DRAM 是异步的

​ 类型：SDRAM；DDR SDRAM

ROM

非易失的：不要求供电来维持数据

可读，但不能写入新数据

无出错处理机会

PROM(可编程ROM):只能写入一次

PROM 提供了灵活性和方便性；ROM 在大批量生产领域仍具有吸引力

主要进行读操作的存储器

特性：非易失；写操作较读操作困难

应用：读操作比写操作频繁得多的场景

EPROM： 光擦除，电写入

EEPROM： 电擦除，电写入；可以随时写入而不删除之前的内容；只更新寻址到的一个或多个字节

Flash： 电可擦除；擦除时间为几秒：优于 EPROM，低于 EEPROM；价格和功能介于 EPROM 和 EEPROM 之间

刷新

集中式刷新：

  • 方式：停止读写操作，刷新每一行

  • 缺点：刷新时无法操作内存

分散式刷新：

  • 方式：每个存储周期内，读写操作完成时进行刷新
  • 对集中式的改进：用户不会感受到内存停止
  • 缺点：会增加每个存储周期的时间

异步刷新：

  • 方式：每行各自以 64ms 间隔刷新；两个时间间隔内保证每一行被刷新一次
  • 优点：刷新不需要占用读写时间，效率高，常用

模块组织

位扩展： 地址线不变，数据线增加

使用 8 个 4 * 1b 芯片组成 4*8b 存储器（注意此时每个地址都会同时选中 八个芯片上的对应位置）

字扩展： 数据线不变，地址线增加

使用 8 个 4 * 8b 芯片组成 32*8b 存储器（高 3 位用于选片）

字、位扩展： 数据线和地址线同时增加

使用 8 个 4 * 4b 芯片组成 16*8b 存储器（高 2 位选片；每次同时选中两片）

七、Cache

解决内存墙带来的CPU和主存协作问题

局部性原理

时间局部性：在相对较短的时间周期内，重复访问特定的信息

空间局部性：在相对较短的时间周期内，访问相邻存储位置的数据（顺序局部性是一种特殊情况，比如：访问线性表）

扩大 Cache 容量的好处与局限：

  • 好处：增加了命中率
  • 局限：增大了 Cache 的开销和访问时间

映射策略

直接映射：

关联度：1

优点：简单、快速映射、快速检查

缺点：抖动现象（如果一个程序重复访问两个需要映射到同一行中 且来自不同块的字，则这两个块不断地被交换到cache中，cache的命中率将会降低，即发生冲突失效）

适用：大容量的 Cache

关联映射：

关联度：C

优点：避免抖动

缺点：实现起来较为复杂；搜索代价大

适用：容量较小的 Cache

组关联映射：

关联度：K

优点：结合了直接映射和关联映射的优点

缺点：结合了直接映射和关联映射的缺点

适用：容量中等的 Cache

tag的判断：

tag + 组号 + 块内地址

组号在关联映射时无，直接映射时即行号

替换策略

最近最少使用算法（LRU）

先进先出算法（FIFO） 时间片轮转法 或 环形缓冲技术

​ 当同一组中的某行被替换时，将其标识位设为1，同时将其下一行的标识 位设为0

最不经常使用算法（LFU） 为每一行设置计数器

随机替换算法（Random）

写策略

写直达： 所有写操作都同时对cache和主存进行

优点：确保主存和 Cache 的内容总是一致的

缺点：产生大量的主存访问，减慢写操作

写回法： 当cache中某个数据块被替换时，如果它被修改了， 才被写回主存

利用一个脏位（dirty bit）或者使用位（use bit）来表示块是否被修改

优点：减少了主存访问的次数

缺点：部分主存数据可能不是最新的：I/O 模块存取时可能会无法获得最新的数据，为解决该问题会使得电路设计更加复杂且有可能带来性能瓶颈

搭配：写分配：读入cache后，在cache中更新内容

行大小与命中率

一开始，增大行大小会增大命中率，因为每一块有更多的内容被载入 Cache，利用 了空间局部性；

当行大小变得较大以后，继续增加行大小，命中率会下降，其一是 Cache容量一定的情况下，装入 Cache 的行数变少，数据块频繁替换；其二是每个数据块的数据在主存中位置较远，被使用的可能性减小。

Cache数目

一级：减少处理器在外部总线上的访问，从而减少执行时间

多级：L1 未命中时，减少处理器对总线上 DRAM 和 ROM 的访问（现代多级 Cache 多集成在芯片上）

统一：更高的命中率，在获取指令和数据的负载间自动平衡；只需要设计和实现一 个 Cache

分立：消除 Cache 在指令的取值、移码单元和执行单元之间的竞争，在指令流水线的设计中很重要（流水线的不同阶段可以分别访问不同的 Cache）

八、外部存储器

类型

外部存储器的类型：磁盘存储器、光存储器、磁带、 U 盘、固态硬盘SSD

磁盘增加数据密度的局限：需要更窄的磁头和更窄的磁道，增加出错风险

恒定角速度：增大盘片区域上信息位的间隔，是磁盘能以恒定角速度扫描信息

  • 优点：能以磁道号和扇区号直接寻址各个数据块

  • 缺点：存储容量受到最内侧磁道的最大数据密度的限制

多带式记录：将盘面划分为多个同心圆区域，每个区域各磁道的扇区数量相同；外侧磁道的扇区数多于内侧磁道

  • 优点：提升存储容量

  • 缺点：需要更复杂的电路

磁盘的磁道调度算法

先来先服务（FCFS)： 优点：公平简单 缺点：如果有大量分散的请求会性能不佳

最短寻道时间优先（SSTF）： 优点：每次寻道时间最短（局部最优），平均寻道时间缩短 缺点：可能产生饥饿现象，尤其是位于两端的磁道请求

扫描/电梯（SCAN）： 优点：性能较好，平均寻道时间较短，不会产生饥饿现象 缺点：只有到最边上的磁道才能改变磁头方向，对各个磁道响应时间不平均

循环扫描（C-SCAN）： 优点：与 SCAN 算法相比：对各个磁道的响应频率平均 缺点：平均寻道时间比SCAN长

LOOK： 优点：减少了 SCAN 需要移动到边缘的额外时间 缺点：对新加入的任务不友好（尤其是边缘处的）

C-LOOK： 优点：减少了 C-SCAN 算法的时间 缺点：略慢于LOOK算法

光存储器

CD 和 CD-ROM

优点：可以大规模复制；可以更换；CD-ROM 比 CD 更耐用且有纠错功能

​ 缺点：只读；存取时间比磁盘长得多

DVD

​ DVD 上的位组装更精密；DVD 采用双层结构；DVD-ROM 可以用两面记录数据

磁带与磁盘

读取：磁带采用顺序读取，磁盘采取直接读取

记录：磁带采用蛇形（串行）记录或并行记录，目前采取串行记录

RAID

十一、虚拟存储器

分区方式

简单固定分区：

​ 优点：简单

​ 缺点：浪费主存空间

可变长分区：

​ 优点：提高了主存的利用率

​ 缺点：时间越长，存储器中的碎片越多

缺失判断

TLB、页表和 Cache 的缺失组合：页表缺失时 TLB、Cache 必定缺失，页表缺失时 Cache 和 TLB 的缺失无关联

方式

分页式虚拟存储器：

​ 优点：实现简单，开销少

​ 缺点：数据可能跨页面

分段式虚拟存储器：

​ 优点：段的分界与程序的自然分界相对应，易于编译、管理、修改和保护

​ 缺点：段的长度不固定

段页式虚拟存储器：

​ 优点：程序按段实现共享和保护

​ 缺点：需要多次查表

十二、总线

总线的用途

专用总线：

​ 优点：高吞吐量，减少总线冲突

​ 缺点：增加了系统的规模和成本

复用总线：

​ 优点：布线少，节省空间和成本

​ 缺点：需要更复杂的控制电路，且共享可能会降低性能

总线仲裁的平衡因素

​ 优先级：优先级高的设备优先被服务

​ 公平性：优先级低的设备不能一直被延迟

集中式的仲裁方案

​ 链式查询（菊花链）：

​ 优点：确定优先级很简单；可以灵活添加设备

​ 缺点：不能保证公平性；对电路故障敏感；限制总线的速度

​ 计数器查询：

​ 优点：通过使用不同的初始计数，灵活地确定优先级；对电路故障不敏感

​ 缺点：需要添加设备 ID 线；需要解码和比较 ID 信号；限制总线的速度

​ 独立请求：

​ 优点：快速响应；可编程的优先级

​ 缺点：复杂的控制逻辑；更多的控制线路

分布式的仲裁方案

​ 自举式、冲突检测

总线的时序：

​ 同步时序：

​ 优点：更容易实现和测试

​ 缺点：所有设备共享一个时钟；总线长度受到时钟偏差的限制

​ 异步时序：

​ 优点：可以灵活地协调速度不同的设备

​ 缺点：接口逻辑复杂（三次握手）；对噪声敏感

​ 半同步时序：结合了同步时序和异步时序的优点

​ 分离事务：

​ 优点：增加总线利用率

​ 缺点：增加每个总线事务的持续时间和系统复杂度