计算机系统基础
1 一、处理器体系结构
1.1 CPU中的时序电路
1.1.1 组合电路和时序电路是什么，它们有什么区别
- 组合电路：将逻辑门组合成一张网，所构成的计算块
- 时序电路：逻辑门电路和反馈逻辑回路或器件（寄存器）组成
核心区别是：时序电路的输出不仅取决于当时的输入值，而且还与电路过去的状态有关；任意时刻的输出仅仅取决于该时刻的输入，与电路原来的状态无关。
1.2 单周期处理器的设计
单周期处理器：在一个时钟周期内完成单条指令：取指、译码、执行、访存、写回、更新PC
- 1、取指：从内存中读取指令，加载至处理器
- 2、译码：对取指令操作中得到的指令进行分析并译码，确定这条指令需要完成的操作，从而产生相的操作控制信号
- 3、执行：进行相应的逻辑或算术运算
- 4、访存：内存访问（非必要）
- 5、写回：将指令结果写回至寄存器（非必要）
- 6、更新PC：更新程序计数器（将程序计数器指向接下来要执行的指令的地址）
1.3 流水线处理器的基本原理
1.3.1 流水线处理器的概念及基本原理
可以结合单周期处理器的不足进行回答，因为流水线就是单周期处理器的改进。
！！！！一定要点出并行！！！！！
-
概念：流水线处理器将待执行的指令拆分成若干个阶段，每个阶段后添加寄存器，使每个阶段 可以在允许其独立使用的硬件电路上与其他阶段并行，以此提高系统的吞吐量。
-
流水线是如何提高程序性能的？（或者说是流水线的特点）
- 拆分指令，并且在每个阶段对应的硬件电路后添加寄存器
- 以流水线的形式执行指令，充分利用硬件，减少了硬件的闲置时间（对比单周期处理器）
1.3.2 流水线处理器的局限性
- 不一致的划分：每个阶段的延迟不一致，导致系统吞吐量取决于最慢的阶段。
- 流水线过深，收益反而下降：在组合逻辑被分成较小的块时，由寄存器更新引起的延迟成为了一个限制因素，降低了收益。
1.3.3 流水线冒险、冒险的种类及对应解决方法
流水线冒险：邻近指令之间出现了某种关联后，下一条指令无法正确执行。
冒险的种类及解决方法：
-
结构冒险：争用硬件（一个指令需要的硬件部件还在为之前的指令工作，而无法为这条指令提供服务）
- 插入气泡（流水线气泡）
- 设置相互独立的指令存储和数据存储
-
数据冒险：存在数据依赖，数据还未产生
- 插入气泡（流水线气泡或者空指令：气泡前的指令继续执行，气泡后的指令被阻塞。直到冒险条件不再满足）
- 数据转发（将结果值直接从一个流水线阶段传到较早阶段，需要在硬件结构中增加一些额外的数据连接和控制逻辑）
- 加载互锁（就是暂停加上数据转发，因为在转发将值转发到已经过去的时间中，所以要插入暂停周期）
- 乱序执行（这个CSAPP中没有，但是应用广泛，可以了解。就是分析指令间的依赖，将无依赖关系的指令提前执行，代替暂停周期，避免时钟浪费）
-
控制冒险：存在分支和跳转时可能发生，不确定下一条执行什么指令
- 插入气泡
- 分支预测策略：从不选择策略（60%），反向选择策略（40%），正向选择反向不选择（65%）
- 条件跳转语句中，可以将每个条件的结果都进行计算，计算的开销小于流水线清空带来的代建
1.3.4 影响流水线效率的因素
局限性和流水线冒险，根据上面的解释这两点
1.3.5 流水线插入气泡技术
插入气泡技术可以解决所有的流水线冒险，但是每一个气泡都会浪费一个时钟周期，代价非常高。因此尽量少用插入气泡解决流水线冒险，选用其他效率高的方法。参考上面提到的。
1.4 Data Hazard的处理
1.5 流水线设计中的其他问题
1.5.1 流水线若干问题及注意点
- 流水线并不能减少(而且一般是增加)单条指令的执行时间，但却能提高系统吞吐率。
- 适当增加流水线的深度(段数)可以提高流水线的性能。（参考流水线的局限性-不一致的划分）
- 流水线的深度(级数)受限于流水线的延迟和流水线的额外开销
- 如果流水线中的指令相互独立 ，则可以充分发挥流水线的性能。但在实际中 ，指令间可能会是相互依赖，这会降低流水线的性能。
1.5.2 解决流水线的局限性-不一致的划分，超标量技术（选看）
Intel处理器中的超线程技术的本质就是超标量技术。
在CPU中有一条以上的流水线，并且每时钟周期内可以完成一条以上的指令，这种设计就叫超标量技术。其实质是以时间换取空间。
处理器的执行阶段往往是处理器中最耗时的阶段，也就是说执行阶段往往是处理器的瓶颈。
2 二、优化程序性能
2.1 优化程序性能
2.2 优化编译器的能力和局限性以及表示程序性能
- 1、高级设计：选择合适的算法和数据结构。
- 2、基本编码原则：避免限制优化的因素，使编译器产生高效的代码
- 1)、消除连续的函数调用（消除低效率循环、减少过程调用）：在可能时，将计算移到循环外。
- 2)、消除不必要的内存引用：引入临时变量来保存中间结果，只有在最后的值计算出来时，才将结果存放到数组或全局变量中。
- 3、低级优化：结构化代码以利用硬件功能。
- 1)、展开循环，降低开销
- 2)、提高指令级并行：通过多个累积变量和重新结合技术
- 3)、用功能性的风格重写条件操作，使得编译采用数据传送。
2.3 特定体系结构或应用特性的性能优化
2.4 限制因素
- 1、寄存器溢出：并行度超过了可用寄存器的数量，就会发生溢出。将某些临时值放到内存中，通常是在运行时堆栈上分配空间。
- 2、分支预测和预测错误的惩罚：分支预测逻辑不能正确预测分支是否要跳转，这时条件分支可能会招致很大的预测错误处罚
- 不要过分关心可预测分支
- 书写适合用条件传送实现的代码
2.5 确认和消除性能瓶颈
程序剖析运行版本的一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间．再根据Amdahl定律进行优化。
2.6 Amdahl定律
Amdahl定律的主要思想是当我们加快系统的一个部分的速度时，对系统整体性能的影响依赖于这个部分有多重要和速度提高了多少．
公式：S = 1 / ((1 - a) + a / k)
其中a为某部分需要时间的百分比，k为性能提升倍数．
主要观点是要想大幅度提高整个系统的速度，我们必须提高整个系统很大一部分的速度．
3 三、存储器结构及虚拟存储器
3.1 局部性
局部性通常有两种形式：时间局部性(temporal locality)和空间局部性(spatial locality)．
- 在一个具有良好时间局部性的程序中，被引用过一次的存储器位置很可能在不远的将来再被多次引用．
- 在一个具有良好空间局部性的程序中，如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置．
3.2 存储器层级结构
3.2.1 存储器的层级结构
从高层往低层走，存储设备逐渐从小而快变得更大、更慢、更便宜，每层都会缓存来自较低一层的数据对象。被缓存的数据对象一般是处理器近期可能会需要的信息，这样可以有效提高读/写效率。
- 寄存器
- L1高速缓存
- L2高速缓存
- L3高速缓存
- 主存
- 本地二级存储（本地磁盘）
- 远程二级存储（分布式文件系统，WEB服务器）
主要思想：上一层的存储器作为低一层的存储器的高速缓存。利用高速缓存的局部性原理：程序具有访问局部区域里的数据和代码的趋势。
3.3 计算机高速缓存器原理
3.4 高速缓存对性能的影响
3.5 地址空间
地址空间是一个非负整数地址的有序集合．
如果地址空间中的整数是连续的，那么就是一个线性地址空间．
在一个带虚拟存储器的系统中，CPU从一个有2^n个地址的地址空间中生产虚拟地址，这个地址空间称为虚拟地址空间．
物理地址空间与系统中的物理存储器相对应．
3.6 虚拟存储器
虚拟存储器是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的、私有地址空间．
3.7 虚拟内存的管理、翻译和映射
3.8 TLB
TLB(Translation Lookaside Buffer)叫做翻译后备缓冲器．
TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由PTE组成的块．