计算机系统结构

第一章：导论

概念部分

第一台通用电子计算机诞生于1946年

计算机技术的飞速发展得益于：计算机制造技术的发展、计算机系统结构的创新

纷纷放弃高性能转向多核，标志着系统结构的重大转折：从单纯依靠指令集并行转向开发线程级并行和数据集并行

计算机系统的层次结构

L6: 应用语言虚拟机

L5: 高级语言虚拟机

L4: 汇编语言虚拟机

L3: 操作系统虚拟机

L2: 传统机器级

L1: 微程序机器级

L1-L3通常使用解释实现（一条一条来）

L4-L6通常使用翻译实现（全部翻译成下面一个低级再执行）

计算机系统结构定义：计算机系统结构是程序员所看到的计算机属性，即概念性结构与功能特性，是计算机系统的软硬件的界面

广义的系统结构：指令结构、组成和硬件

包括：指令系统、寻址方式、数据表示、寄存器定义、中断系统、工作状态的切换、存储系统、信息保护、I/O结构等

计算机组成：计算机系统结构的逻辑实现

计算机实现：计算机系统结构的物理实现

一种体系结构可以有多种组成，一种组成可以有多种物理实现

系统结构的分类 冯氏分类法：按照最大并行度（字宽×一次能处理的字数）分 Flynn分类：按指令流和数据流的多倍性分，分为以下四类：

①单指令流单数据流（SISD）

②单指令流多数据流（SIMD）

③多指令流单数据流（MISD）

④多指令流多数据流（MIMD）

冯诺依曼结构

最大特点：以运算器为中心

虚拟机：用软件实现的机器

系列机：同一个厂家生产的具有相同系统结构但具有不同组成和实现的一系列不同型号的计算机

兼容机：由不同厂家生产的具有相同系统结构的计算机

软件兼容：向上兼容、向下兼容、向前兼容和向后兼容，其中向后兼容是系列机的根本特征

模拟：用软件的方法在一台计算机上实现另一台计算机的指令集（本机要解释执行另一台机子的程序）

仿真：用一台现有计算机上的微程序去解释实现另一台计算机的指令集（本机要实现另一台机子的指令集）

并行性：包括同时性（同一时刻）和并发性（同一间隔）

提高并行性的措施：时间重叠、资源重复、资源共享

耦合度：反应计算机之间物理连接的紧密程度和交互强弱，分为紧密耦合系统和松散耦合系统

计算机系统设计经常使用的4个定量原理

1. 以经常性事件为重点

2. Amdahl定律

3. CPU性能公式

4. 程序的局部性原理

计算部分

Amdahl定律（P7）

$加速比 = \frac{执行时间_{改进前}}{执行时间_{改进后}} = \frac{1}{（ 1 - 可改进比例 ）+ \frac{可改进比例}{部件加速比} }$ 依赖于可改进比例和部件加速比

CPU时间（P9）

$CPU时间 = IC \times CPI \times 时钟周期时间$

$时钟周期 = \frac{1}{f}$

$MIPS速率 = \frac{f}{CPI} $

执行时间和吞吐率（P11）

性能比较（P14）

第二章：指令集结构

概念部分

区别不同指令集结构的主要因素是CPU中用来储存操作数的储存单元的类型，因此可以把指令集结构分为堆栈结构、累加器结构和通用寄存器结构

寻址方式： 指一种指令集结构如何确定所要访问的数据的地址

对指令集的基本要求： 完整性、规整性、高效率和兼容性

指令集结构设计涉及的内容

① 指令集功能设计，主要由CISC和RISC两种方向

② 寻址方式设计

③ 操作数表示和操作数类型

④ 寻址方式的表示

⑤ 指令集格式的设计，变长、固定长度、混合

指令集三种编码格式：

可变长度编码

固定长度编码

混合型编码

RISC遵循的原则

① 指令条数少而简单

② 采用简单而又统一的指令格式

③ 指令的执行在单个机器周期内完成

④ 只有load和store能访问存储器

⑤ 大多数指令采用硬连逻辑

⑥ 强调优化编译器的作用

⑦ 充分利用流水线

I类指令： load、store等

R类指令： ALU等

第三章：流水线技术

概念部分

流水线技术的概念： 把一个重复的过程分解为若干个子过程，每一个子过程用一个专门的部件来实现。多个处理过程在时间上错开依次通过各段，让每个子过程和其他过程并行，这就是流水线技术

流水线技术的特点：

① 流水线把一个处理过程分解为若干个子过程，每个子过程由一个专门的功能部件来实现，依靠它们的并行工作来缩短程序的执行时间

② 流水线各段时间应该尽可能相等

③ 流水线的每一个功能部件的后面都要有一个缓冲存储器

④ 流水线适合于大量重复的时序过程

⑤ 流水线需要有通过时间和排空时间

流水线分类

单功能流水线：只能完成一种固定功能

多功能流水线：可以实现不同的功能

静态流水线：同一时间各段只能按照同一种功能的连接方式工作

动态流水线：同一时间各段可以有不同的连接，执行多种功能

部件级流水线：把运算部件分段

处理机级流水线：把指令的解释执行过程分段

处理机间流水线：在处理机间流水

线性流水线：没有反馈回路

非线性流水线：有反馈回路

顺序流水线：任务流出流入的顺序一致

乱序流水线：任务流出的顺序和流入的顺序可以不一样

解决流水线瓶颈问题的方法 细分瓶颈段、重复设置瓶颈段

经典的五段流水线划分

一条指令的执行过程可以划分为以下五个部分：

取指令周期（IF）

指令译码/读寄存器（ID）

执行/有效地址计算（EX）

存储器访问/分支完成（MEM）

写回周期（WB）

相关的概念：相关是指两条指令之间存在某种依赖关系

相关的分类

数据相关：指令之间有数据关联（有传递性）

名相关：名指的是寄存器名或存储器名，数据不关联但是用了相同的名，名相关又分为反相关（一写一读）和输出相关（都写）

控制相关：由分支指令引起的相关

流水线冲突的概念： 对于具体的流水线而言，由于相关的存在，导致指令流的下一条指令不能在指定的时钟周期执行

流水线冲突的分类

结构冲突：硬件资源无法满足重叠执行的要求
     — 消除结构冲突：气泡停顿、设置独立指令数据存储器、Cache分为指令Cache和数据Cache 数据冲突：重叠执行时需要用到前面的数据
     — 数据冲突分为：写后读（RAW）、写后写（WAW）

     — 解决数据冲突：定向技术（直接从产生的地方送到需要的地方）、通过编译器指令调度解决 控制冲突：分支指令等引起的冲突
     — 解决控制冲突：冻结或排空流水线（最简单但是分支延迟大）、尽早判断分支是否成功（提前到ID段末尾）、软件方法

减少分支延迟的静态方法

预测分支失败

预测分支成功

延迟分支（在延迟槽中放入有用的指令，三种调度方法：从前调度、从目标处调入、从失败处调入）

不采用单周期的原因：

① 单周期效率低，不同指令需要的时钟周期不一样

② 单周期需要重复设置部件，而多周期可以共享

流水寄存器的作用：

① 将各段隔开来，使之不会相互干扰

② 保存相应段的处理结果

③ 向后传递后面要用到的数据或控制信息

流水线的实现（P82 - P90）

计算部分

吞吐率：单位时间内流水线完成的任务数量

$TP = \frac{n}{T_k}$

加速比：不用流水线所用的时间和用流水线所用时间之比

$S = \frac{T_s}{T_k}$

效率：设备实际使用时间与整个运行时间之比（画图之后即为阴影面积/完整面积）

易出大题（P61 例题3.1、P104 章后习题3.11） 务必注意题目里说的是静态流水线还是动态流水线，静态流水线必须一个操作做完之后 才能开另一个功能，参见P60例3.1个P60例3.2

第四章：指令级并行

概念部分

指令级并行概念：利用流水线使指令重叠并行执行，这种指令之间潜在并行性称为指令级并行（ILP，Instruction-Level Parallelism）

CPI：（Cycles Per Instruction）每条指令所消耗的时钟周期数 IPC：（Instructions Per Cycle）每个时钟周期完成的指令条数

基本程序块：一段除了入口和出口之外不包含其他分支的线性代码段（就是指中间没分支）

循环级并行：让一个循环中的不同循环体并行执行

开发循环级并行的技术：循环展开技术、采用向量指令和向量数据表示

指令顺序：由源程序确定的在完全串行方式下指令的执行顺序

正确执行程序必须保持的最关键的两个因素：数据流（数据从其产生者指令到消费者指令的实际流动）和异常行为（无论怎么改变顺序，都不影响程序中异常的发生情况）

指令调度：通过在编译时让编译器重新组织指令顺序或者通过硬件在执行时调整指令顺序来消除冲突

静态调度与动态调度：第三章为静态调度，第四章为动态调度，以下为二者区别： ① 静态调度发生在编译过程中，动态调度发生在运行过程中 ② 动态调度相比静态有更多优点：能够处理一些编译时不明确的相关、能够套用在其他流水线上

精确异常和不精确异常： 精确异常：发生异常时，处理机的现场和严格按程序顺序执行时的现场相同 不精确异常：发生异常时，处理机的现场和严格按程序顺序执行时的现场不同

Tomasulo算法

保留栈：在采用Tomasulo算法的MIPS处理器浮点部件中，在运算部件的入口设置的用来保存已经流出并等待到本功能部件执行的指令 CDB：公共数据总线

ROB

动态分支预测技术：根据分支指令过去的表现来预测其将来的行为 BHT：分支历史表，用于记录相关分支指令最近几次的执行情况并根据此进行预测 分支目标缓冲：是一种动态分支预测技术，将执行过的成功的分支指令的地址和预测的分支目标地址记录在一个硬件表中，每次取指令时比较，达到减少分支开销的作用 前瞻执行：解决控制相关的方法，对分支指令的结果进行预测，按照这个预测结果继续后续的过程，不过指令执行的结果不是放在寄存器或存储器中，而是放在ROB缓冲器中，相应指令确认后才将结果写到寄存器或存储器 ROB：前瞻执行缓冲器

多流出处理机的两种基本风格

超标量：一种多指令流出技术，每个时钟周期流出的指令条数不确定，但有个上限 超长指令字：一种多指令流出技术，每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者指令包，通过编译器静态调度

超流水 一个时钟周期内分时流出多条指令

计算部分

实际CPI：

$CPI_{流水线} = CPI_{理想} + 停顿_{结构冲突} + 停顿_{数据冲突} + 停顿_{控制冲突}$

第五章：存储系统

概念部分

人们追求的储存器特性：容量大、速度快、价格低

走出困境的唯一方法：采用多级存储层次结构

多级存储层次：采用不同的技术实现的存储器，处在离CPU不同位置的层次上，各存储器之间一般满足包容关系，任何一层存储器中的内容都是其下一层的储存器内容的子集。目标是达到离CPU最近的存储器的速度，最远的存储器的容量。

“Cache-主存”与“主存-辅存”的区别

映像规则 全相联映像：主存中的任意一块可以被放置到Cache中的任意一个位置，空间利用率最高、冲突概率最低、实现最复杂 直接映像：    主存中的每一块只能被放到Cache中唯一的位置，空间利用率最低、冲突概率最高、实现最简单 组相联映像：主存中的每一块可以被放置到Cache中唯一一组中的任何一个位置，是上面二者的折中

查找算法 查找Cache在哪，通过查找目录表实现，目录表项与储存器块对应

目录表

有效位为1表示有效，标识tag标识了存放的信息存在于哪个主存块中

主存地址

替换算法

随机法

FIFO

LRU

LRU算法的硬件实现

堆栈法

比较对法

写策略

写直达法：执行写操作时，不仅写入Cache，而且也直接写入下一级存储器（易于实现） （不按写分配，不命中直接写入下一级而不调块）

写回法：执行写操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存（速度快） （按写分配，不命中时调块）

Cache对低CPI、高时钟频率的CPU来说更为重要

改进Cache性能 包括三个方面：

① 降低不命中率（8种）

② 减少不命中开销（5种）

③ 减少Cache命中时间（4种）

三种类型的不命中 强制性不命中：首次访问就没命中 容量不命中：某些块被替换了，之后又访问了这些块（原因主要是容量小了） 冲突不命中：组相联或直接映像很多块映到了同一组（块）中，原块被替换，之后又访问了这些块

相联度越高，冲突不命中就越少（因为每块可选的位置变多了，冲突几率下降），对强制不命中和容量不命中没什么影响

Cache容量增加，容量不命中下降，对强制性不命中没影响

减少三种不命中的方法： 强制性不命中：增加块大小，预取（本身比例很少） 容量不命中：增加容量 冲突不命中：提高相联度（理想情况：全相联）

降低不命中率的八种方法

① 增加Cache块大小
            最简单，减少强制不命中，但增加了冲突不命中（因为块的个数少了），同时也会增大不命中开销

② 增加Cache容量
            最直接，但会增加成本和命中时间

③ 提高相联度
            会增加命中时间          （2:1Cache经验规则：容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多）

④ 伪相联Cache
            访问如果命中就和直接映像一样，如果不命中就检查另一个位置是否匹配，简单的方法是将索引的最高位取反。保持命中速度和低不命中率，会让CPU流水线的设计复杂化

⑤ 硬件预取
            指令和数据在处理器提出访问之前进行预取，由Cache之外的硬件完成，放入一个缓冲器中。预取应当利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能

⑥ 编译器控制的预取
            由编译器在程序中加入预取指令实现预取。每次预取需要花费一条指令的开销

⑦ 编译器优化
            三种方法：代码和数据重组、内外循环交换、分块

⑧ 牺牲Cache
            在Cache和下一级之间设置一个全相联小Cache来存储被替换掉的块，减少冲突不命中很有效，尤其是小容量Cache

减少Cache不命中开销的五种方法

① 采用两级Cache（有计算）

② 让读不命中优先于写             会增加命中时间

③ 写缓冲合并
            写入的数据与缓冲器已有地址比较，如果有地址匹配的就合并

④ 请求字处理技术
            从下一级调入Cache的块只有一个字是立即需要的，称为请求字，两种方法：尽早重启动、请求字优先
            在Cache块较小或者下一条指令正好访问Cache块的另一部分时，效果不明显

⑤ 非阻塞Cache技术
            在Cache不命中时仍允许CPU进行其他的命中访问

减少Cache命中时间的四种方法

① 容量小、结构简单的Cache
            增大不命中率

② 虚拟Cache
            可以直接用虚拟地址进行访问的Cache

③ Cache访问流水化
            把对第一级Cache的访问按流水方式组织

④ 踪迹Cache
            存放CPU所执行过的动态序列，包含分支预测展开的指令
            地址映像机制复杂，相同的指令序列可能被重复存放，提高了Cache的空间利用率

主存主要的性能指标：延迟和带宽

并行主存系统：在一个访存周期内能并行访问多个储存字的存储器

并行存储器结构包括： 单体多字存储器 多体交叉存储器

计算部分

平均每位价格C、命中率H、平均访存时间（P155）

$M_1{T_1, S_1, C_1}、M_2{T_2, S_2, C_2}$

T: 平均访存时间，S: 存储容量，C: 平均每位价格

平均每位价格 = $\frac{M_1C_1 + M_2C_2}{M_1 + M_2}$

命中率 = $\frac{N_1}{N_1+N_2}$

平均访存时间 = $HT_1 + (1-H)(T_1+T_M) = T_1 + (1-H)T_M = T_1 + FT_M$ 不命中开销 $T_M = T_2 + T_B$

Cache的容量（P163）

Cache容量 = $2^{index} \times$ 相联度 $\times$ 块大小

程序执行时间

$CPU$时间 = $IC \times (CPI + $每条指令的平均访存次数$\times $不命中率$ \times $不命中开销$) \times $时钟周期时间

（P172例题）

第六章：输入输出系统

概念部分

I/O系统包括：I/O设备、I/O设备与处理机的连接

系统的响应时间：从用户输入命令开始，到得到结果所花费的时间（等于I/O系统的响应时间+CPU的处理时间）

I/O系统的三个性能指标 可靠性：一直连续提供服务的能力，用平均无故障时间MTTF衡量，其倒数为失效率（计算时失效率可累加，倒数相加再倒） 可用性：正常工作的时间在连续两次正常服务间隔中的比例    可用性=$\frac{MTTF}{MTTF+MTTR}$ 可信性：服务的质量（无法度量）

磁盘阵列：使用多个磁盘的组合来代替一个大容量的磁盘 阵列的并行性包括：多个请求可以由多个盘来并行处理、一个请求访问多个块也可以多个块合作地并行处理

各种RAID （检测盘个数是数据盘个数为8个时所需要的检测盘个数）

实现盘阵列的方式

软件方式

阵列卡方式

子系统方式

通道处理机

专门负责整个计算机的输入输出工作，通道处理机只能执行有限的一组输入输出指令

输入输出系统的层次

CPU->通道->设备控制器->外设

通道的主要硬件

寄存器

控制逻辑

通道的工作过程（3步）

① 在用户程序中启动一个访管指令，由管理程序来编制一个通道程序，并启动通道

② 通道处理机执行通道程序，完成指定的数据的输入输出工作

③ 通道程序结束后向CPU发出中断请求

通道的种类（3种）

① 字节多路通道，为多台低中速外设服务，以字节交叉的方式分时轮流服务，可以包含多个子通道，每个子通道连接一台设备控制器

② 选择通道，为多台高速外围设备服务，一段时间内只为一条高速外设独占

③ 数组多路通道，适用于高速设备，每次选择一个高速设备后传送一个数据块，轮流为多台外围设备服务

计算部分

通道流量分析（P238）

字节多路通道：（连一个外设，传一个字节，再连一个外设，传一个字节...）

p台设备传输n个数据所需时间：$T_{BYTE}=(T_S+T_D)\times p\times n$

最大流量：$f_{MAX-BYTE} = \frac{1}{T_S+T_D}$

选择通道：（一台设备的数据传输工作全部结束后通道才为另一台设备服务）

p台设备传输n个数据所需时间：$T_{SELECT}=(\frac{T_S}{n}+T_D)\times p\times n$

最大流量：$f_{MAX-SELECT} = \frac{1}{\frac{T_S}{n}+T_D}$

数组多路通道：（连一个外设，传一个k个字节的数据块，再连一个外设，传一个k个字节的数据块...）

p台设备传输n个数据所需时间：$T_{BLOCK}=(\frac{T_S}{k}+T_D)\times p\times n$

最大流量：$f_{MAX-BLOCK} = \frac{1}{\frac{T_S}{k}+T_D}$

第八章：多处理机

概念部分

MIMD的成为通用多处理机系统结构的选择的原因

MIMD具有灵活性

MIMD可以充分利用现有微处理机的性价比优势

MIMD的分类：

集中式共享存储器结构（CSMA、UMA、对称式共享存储器多处理机SMP）

多个处理器共享一个集中式的物理存储器，单一主存而且主存对于各处理器而言是对等的

分布式存储器多处理机

存储器分布到各个处理器上，优点：

①降低对存储器和互联网络的带宽要求

②对本地存储器的访问延迟时间小；

缺点：处理器之间的通信较为复杂，访问延迟大

两种储存器系统结构

共享地址空间：物理上分离的所有储存器作为一个统一的共享逻辑空间进行编址，不同处理器的同一个物理地址指向同一个存储单元

独立编址：每个节点的存储器编址为一个独立的地址空间，不同处理器的地址是独立的。每一个处理器-存储器模块实际上是一台单独的计算机

两种通信机制

共享存储器通信机制：处理器之间通过store-load对相同存储器地址进行读写来实现的 优点：

① 与常用的SMP通信机制兼容

② 易于编程

③ 数据量小时开销较低

④ 可以采用cache来减少远程通信的频度

消息传递通信机制：处理器之间通过发送消息来进行通信

优点

① 硬件简单

② 通信是显式的

③ 减少不当的同步带来的可能的错误

④ 显式通信让编程者重点关注主要通信开销

Cache一致性协议

监听式协议

目录式协议

Cache一致性问题解决方法

写作废协议

写更新协议

同时多线程技术：

一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技术