计组review

第一章计算机抽象及相关技术

七个伟大思想

通过抽象简化设计，硬件与软件之间的接口，指令集体系结构；在更高级别隐藏细节，汇编器将汇编语言翻译为机器可以理解的二进制代码，甚至通过创造硬件中没有的符号指令来“扩展”指令集
加速大概率事件 pc 相对寻址寻址附近的指令，条件分支（2 个设计原则）；大常数操作的立即数寻址；mips 汇编语言的寄存器约定（p77）
通过并行提高性能（多处理器，指令并行；子字并行，数据级并行，为算术操作密集型性能的提高开辟了一条简单的路径）
通过流水线提高性能（提高了吞吐量率，但不能提高指令的固有执行时间）
通过预测提高性能（处理分支）（cache，依赖局部性原理，尽可能在存储器层次结构的更高层中寻找需要的数据，并在预测错误时能够提供从存储器层次的更低一层中获取正确数据的机制）
存储层次（访问局部性）
通过冗余提高可靠性

性能

性能评价的不同方法

响应时间：也叫执行时间，是计算机完成某任务所需的总时间，包括硬盘访问、内存访问、i/o 活动、操作系统开销和 cpu 执行时间
吞吐率：也叫带宽，性能的另一种度量参数，表示单位时间内完成的任务数量
在前几章中性能和执行时间成反比

计算机用户和设计者的角度描述性能的测量的度量标准

都关注 cpu 的执行时间

分析这些度量标准之间的内在联系

提出经典的处理器性能方程式

cpu 时间=指令数cpi时钟周期时间，需要用三种因素去衡量性能，任何一个独立的因子都不可以衡量

程序的性能与算法编程语言编译器指令集体系结构有关时钟频率是 cpu 的

理解程序的性能

一个程序的性能取决于以下各因素的组合：程序所用的算法的有效性。来建立程序并将其翻译成机器指令的软件系统，计算机执行机器指令的有效性。软硬件影响性能。

硬件或软件组成部分	对性能的影响
算法	决定了源码级语句的数量和 i/o 操作的数量
编程语言编译器和体系结构	决定了每条源码级语句对应的计算机指令数量
处理器和存储系统	决定了指令的执行速度
i/o 系统（硬件和操作系统）	决定了 i/o 操作的执行速度

第二章指令：计算机的语言

计算机中指令的表示

alt text 硬件设计原则

mips 中 32 位立即数和地址的寻址

lui or i

Example

* 远距离的分支转移：
* 主要是j指令
假设在寄存器`$ s0`和`$s1`值相等时需要跳转，可以使用如下指令:

```asm
beq $s0,$s1,l1

```
用两条指令替换上面的指令，以获得更远的转移距离：

```
bne $s0,$s1,l2
j l1
l2:

```

立即数寻址：操作数是位于指令自身的常数
寄存器寻址: 操作数是寄存器
基址寻址：或称为偏移寻址，操作数在存储器中，其地址是指令中基址寄存器和常数的和
pc 相对寻址：地址是 pc 与指令中常数的和
伪直接寻址：跳转地址由指令中的 26 位字段和 pc 的高位字段拼接而成

总结

三条设计原则

简单源于规整：所有指令长度统一；算术指令总是需要三个寄存器操作数；寄存器字段在每种指令格式的位置相同；
越小越快。对速度的要求导致 Mips 只有 32 个寄存器而不是更多
优秀的设计需要好的权衡和折中。 mips 在指令中提供更大地址与常数，与保持所有的指令具有相同的长度之间进行折中。

第三章计算机的算术运算

浮点数

Sign 1 位	Exponent8 位	Fraction23 位

双精度

Sign 1 位	Exponent11 位	Fractio52 位

$$(-1)^S * (1+尾数)*2^(指数-偏阶)$$
127，1023

浮点数加法

s1:调整小数点位置，指数较小的数的小数点位置向指数较大的数对齐
s2:将有效数相加
s3:规范化
s4:四舍五入

浮点乘法

将源操作数的指数相加，得到乘积的指数，注意将带偏阶的指数相加时最后需要减去一个 127
计算有效数位的乘法
规格化乘积，指数的大小用来检查上溢和下溢
符号

第四章处理器

计算机的性能由三个因素决定：指令数由编译器和指令集决定；处理器的实现方式决定了时钟周期长度和 cpi;
数据通路 控制单元
一个简单的 Mips 指令实现：
存储器访问指令
算数逻辑指令
分支指令

流水线

流水线：一种实现多条指令重叠执行的技术，与生产流水线类似。
5 个步骤：
从指令存储器中读取指令；
指令译码的同时读取寄存器，mips 的指令格式允许同时进行指令译码和读寄存器
执行操作或计算地址
从数据存储器中读取操作数
将结果写回寄存器
流水线所带来的性能提高是通过增加指令的吞吐率，而不是减少单条指令的执行时间实现的

冒险

在下一个时钟周期中下一条指令不能执行

结构冒险

因缺乏硬件支持而导致指令不能再预定的时钟周期内执行的情况

Example

假设流水线结构中只有一个存储器，而不是两个，那么若有第四条指令，第一条指令在访问存储器的同时，第四条指令将会在同一存储器中预取指令
数据冒险

因无法提供指令所需数据而导致指令不能再预定的时钟周期内完成
- 原因：一条指令依赖于更早的一条还在流水线中的指令造成的
Example

减法指令要用到加法指令的和，加法指令知道第五步才能返回它的结果
- 解决方法：前推（forwarding）或者旁路(bypassing):从内部缓冲器而非程序可见的寄存器或存储器中提前取出数据。
- 前推：将结果从前面的指令直接发送到后面的指令
- 旁路：把寄存器堆中的结果直接传递到需要的单元中
- 取数-使用型数据冒险（load-use data hazard）:一种特殊的数据冒险，指当 load 指令要取得数还没取回来是其他指令就需要使用的情况。
- load 指令，所需得数据需要在流水线得第四级完成后生效；
- 流水线阻塞（pipeline stall）:bubble;
- 如何避免？采用硬件上的检测和阻塞；在软件上重新安排代码顺序，以避免取数=使用型数据冒险。
控制冒险

也称分支冒险。因为取到的指令并不是所需要的（或者说指令地址的变化并不是流水线所预期的）而导致指令不能再预定的时钟周期内执行决策指令依赖于一条指令的结果，而其他指令正在执行中。
- 解决方法：
- 阻塞（stall）:穿行
- 分支预测： > 预测分支结果并立即沿预测方向执行，而不是等真正的分支结果确定后才开始执行。预测一些分支发生而预测另一些分支不发生。

流水线数据结构与通路

更新状态：寄存器堆，存储器 ,pc

加入控制

最后三级需要加
9 个
旁路单元控制 alu 多选器，用相应的流水线寄存器的值代替通用寄存器的值（算术运算）
冒险检测单元控制 pc 和 if/id 流水线寄存器的写入，以及在实际控制信号与全 0 中进行选择的多选器。load-use 为真，会阻塞并清除所有的控制字段（数据传输）

小结

流水线是一种在顺序指令流中开发指令间并行性的技术。与多处理器编程相比，其优势在于它对程序员是不可兼得。

流水线提高了吞吐量，但不能提高指令固有的执行时间
多发射在数据通路中增加了额外的硬件，从而允许每个时钟周期发射多条指令，但是却增加了有效延迟。
多发射关注减少每条指令的 cpi
流水线和多发射都视图开发指令级并行，数据相关和控制相关时开发更高指令级并行的主要限制因素。在软硬件上都使用预测来调度和推测时降低相关带来的影响的主要手段

第五章大容量和高速度：开发存储器层次结构

cache 的基本原理

一些概念：

标记：存储器层次结构使用的表中的一个字段，包含了地址信息，这些地址信息可以用来判断 cache 中的字是否就是所请求的字
有效位：存储器层次结构使用的表中的一个字段，用来标识一个块是否含有有效数据

cache 的访问

地址的划分
标记字段：用来和 cache 中标记字段的值进行比较
cache 索引：用来选择块，有 2^n 个 cache 块，故 n 用来索引
偏移：字节的 2 位以及可能的块中字的偏移
cache 的划分
有效位
标记
数据
较大的 chache 块能更好的利用空间局部性降低缺失率。但块大小在 cache 容量中所占比例增加到一定程度时，缺失率也会增加。只是因为此时 chache 中快的数量变得很少，对于这些快将会有大量的竞争发生，结果就造成一个块中的数据在被多次访问之前就被替换出 cache.另外，对于一个太大的块，块中各个字之间的空间局部性也会降低，缺失率降低所带来的收益也会相应减少
仅仅增加块大小所带来的另一个严重的后果是缺失成本的增加。由较低存储器层次中取出快并存放至 cache 中所花费的时间决定了缺失代价。取出块的时间可以分为两部分：第一个字的延迟时间和块中剩余部分的传输时间，传输时间也就是缺失代价会随着块大小增大而增加。（每次传一整块数据）

cache 缺失处理

cache 缺失处理由两部分组成：处理器控制单元以及一个进行初始化主存访问和重新填充 cache 的独立控制器
发生指令 cache 缺失的处理步骤：
把程序计数器 pc 的原始值（当前 pc-4）送到存储器中
通知主存执行以此读操作，并等待主存访问完成
写 cache 项，将从主存取回的数据写入 cache 中存放数据的部分，并将地址的高位写入标记字段，设置有效位
重启指令执行第一步，重新取值，这次该指令在 cache
数据缺失类似

写操作

写直达写操作总是同时更新 cache 和下一存储器层次，以保持二者的一致性
写回：当发生写操作时，新值仅仅被写入 cache 块中，只有当修改过的块被替换时才写道较低层存储结构中

小结

利用空间局部性，cache 中的块大小必须大于一个字，使用较大块可以降低缺失率，减少 cache 中与数据存储量相关的标记存储量，从而提高 cache 效率
但是块容量增大降低缺失率同时会带来缺失代价的增加。
可以通过增加主存的带宽来更高效地传输 cache 块

cache 性能的评估和改进

评估

$$CPU时间=（CPU执行时钟周期数+存储器阻塞的时钟周期数）*时钟周期$$ $$存储器阻塞的时钟周期数=读操作引起阻塞的时钟周期数+写操作引起阻塞的时钟周期数$$

简化读写操作，读写操作缺失代价一样，都是从主存中取回数据块的时间，并使用单一缺失率和缺失代价：时钟周期数： $$存储器阻塞时钟周期数=指令数/程序缺失率缺失代价$$
平均存储器访问时间（average memory access time），综合考虑了命中和缺失
$$AMAT=命中时间+缺失率+缺失代价$$

改进

1 相联度减少缺失率

提高相联度的好处在于它通常会降低缺失率，主要的缺点是增加了命中时间

替换块的选择

最近最少使用：一种替换策略，总是替换很长时间没有使用的块。依照过去的经验。

使用多级 cache 结构减少缺失代价

4Ghz=0.25ns;
两级 cache 结构中一级 cache 致力于减少命中时间以获得较短的时钟周期或较少的流水级；
二级 cache 则侧重于改善缺失率以减少长时间的访存代价

通过分块进行软件优化

于对一个数组进行整行或整列操作不同，分块算法对子矩阵（或称为块）进行操作
目标是在数据被替换出去之前，最大限度地对已装入 cache 地数据进行访问，即通过提升时间的局部性的方法来降低 cache 缺失率

虚拟存储器

Note

虚拟存储器：一种将主存当作辅助存储器高速缓存的技术
物理地址：主存储器的地址
保护：一系列机制确保共享处理器、主存、i/o 设备的多个进程之间不能互相干涉，不能有意地或无意地读写其他进程的数据，这些保护机制可以将操作系统和用户的进程隔离开来。
缺页：访问的页不再主存储器中
虚拟地址：虚拟空间的地址，当需要访问主存时需要通过地址映射转换为物理地址

在虚拟存储器中，地址被划分为虚拟页号和页偏移

页的存放和查找

页表：保存着虚拟地址和物理地址之间转换关系的表。页表保存在主存中，通常使用虚页号来索引，如果这个虚页当前在主存中，页表的对影响将包含虚页对应的物理页号
为了指出页表在主存中的位置，硬件包含一个指向页表首地址的寄存器，称为页表寄存器。
页偏移对应页的大小，一般为 4KiB 即$2^12$字节

缺页故障

交换区：为进程的全部虚拟地址空间所预留的磁盘空间

关于写

写回机制，对存储器中的页进行单独的写操作，并且在该页被替换出存储器时再被复制回磁盘中

加快地址转换：TLB

快表：用于记录最近使用地址的映射信息的高速缓存，从而可以避免每次都要访问页表
TLB 中的引用位是一个硬件维护的状态位，它标记了对应的页表项（即虚拟页）最近是否被 CPU 访问过。

存储器层次结构的一般框架

问题 1：块放在何处
问题 2：如何找到块
问题 3：cache 缺失时替换哪一块
问题 4：写操作如何处理

3c:一种理解存储器层次结构行为的直观模型

compulsory miss:强制缺失，也称冷启动缺失，对从未在 cache 中出现过的块第一次访问时产生的缺失
capacity miss：由于 cache 在全相联时都不可能容纳所有请求的块而导致的缺失。也就是 cache 容纳不了一个程序执行所需要的所有块而引起的缺失，当某些块被替换出去随后被调入时将发生容量缺失。
conflict miss：也称碰撞缺失，在组相联或直接映射 cache 中，很多块为了竞争同一个组而导致的缺失，这种缺失在使用相同大小的全相联 cache 中是不可能存在的

第一章 计算机抽象及相关技术