前言

这篇文章是博主复习用的资料，对所教授内容不熟的几乎没有参考价值。如果有需要，可以联系博主，在相应板块详细解释（如果有时间的话）

引言及历史

计算机系统结构和计算机组成的区别：
- 计算机组成：描述对用户透明的结构实现。流水线结构，Cache都是其中的研究对象。
- 计算机结构：从用户的角度描述计算机。指令集，可见的寄存器，内存管理表的结构都是其中的研究对象。

指令集架构关注的问题：寄存器，内存寻址，寻址模式，指令操作，可用操作，控制流指令，指令编码。（指令集 + 架构）

摩尔定律：每18个月，处理器的性能翻番

并行级别：
- 应用层面：数据级并行、任务级并行
- 架构层面：指令级并行（单个周期执行多条指令）、线程级并行、请求级并行、向量架构（GPU）

并行分类：单指令单数据（SISD），单指令多数据（SIMD），如向量架构，GPU，多指令单数据（MISD），多指令多数据（紧耦合MIMD，松耦合MIMD）

ISA：RISC（RISC-V，MIPS，ARM），CISC（x86）

Newmann架构：主存，逻辑计算单元，程序控制单元，IO控制单元

程序：一系列顺序指令

量化研究方法

动态功耗：晶体管极性转换产生的功耗， $动态功耗$ ，其中f是翻转频率
静态功耗：通电不工作产生的功耗， $静态功耗$

性能定义：
- 执行任务所需时间：执行时间，响应时间，已用时间，时延
- 单位时间执行任务：执行率，带宽，吞吐量

计算机设计原理：局部性原理，加速常见时间，阿姆达尔原理（加速某一部分带来的增益是有限的）

CPU Time = CCT * IC * CPI

影响因素：
CCT（Clock Cycle Time）：硬件组织（流水线设计）和硬件技术
IC（instruction count）：Program，Compiler，ISA（只要跟指令有关，就会影响指令数量）
CPI (clock cycles per instruction)：ISA（ISA涉及到流水线架构，所以会影响）和硬件组织

指令

ISA(Instruction Set Architecture)包括：编程寄存器、操作数访问、操作数的类型和大小、指令集、寻址模式、指令编码（是软件和硬件之间的接口，包不包括流水线架构呢？不包括吧。。。不太理解，但是首先肯定的是那一套的Inst是包括的，然后操作数相关，寻址相关也是配套的）

作用：将指令集规范和硬件实现解耦开，高级编程语言和抽象机器解耦开。

ISA的分类：

栈式架构：有一个隐式操作数，在栈顶部
AC（Accumulator）架构：有一个隐式操作数，是累加器
通用寄存器计算机体系结构：只有显式操作数，要么在寄存器要么在内存。可以细分为操作数全来自于寄存器(MIPS)，或者一个来自于寄存器一个来自于内存的架构(80x86)，或者全来自于内存的架构（VAX，已经绝种了）

（思考以上五个架构的优缺点？栈是放在内存的，Accumulator免不了前后数据的强相关使得流水线困难）

对于一条指令来说，最多可含有的内存地址数和最多的操作数也是值得关注的。如x86支持一条内存地址，但MIPS不行。

ISA设计应当关注的问题：寻址模式，操作数种类和大小，指令种类，指令控制流，指令集编码

寻址模式：

立即数寻址：operand = imm
直接寻址：operand = Mem[imm]
间接寻址：operand = Mem[Mem[imm]]
寄存器寻址：operand = R[imm]
寄存器间接寻址：operand = Mem[R[imm]]
相对寻址：operand = PC + imm
堆栈寻址：取栈顶操作数

指令类型：算术&逻辑、浮点数，数据传输、控制、系统

MIPS所拥有的寄存器：32个GPRs，32个浮点数寄存器，PC，HI，LO，AT，GP，SP，FP，RA

大小端问题：大端是数字高位存储在地址小的地方，小端是数字低位存储在地址小的地方。（如何理解记忆？寻址都是由小到大寻址，那么大端是数字高位（大）放在地址小的地方，按顺序来）

流水线

流水线实际要考虑的问题：

流水线每个阶段的开销
流水线寄存器的延迟（寄存器也是有延迟的，见CSAPP，因为这个原因不可能实现无限加速）
时钟歪斜（同一时钟信号到达不同部件的时间不完全相同）

流水线冒险：

结构冒险：所需资源繁忙（如RAM在多个阶段被需要，如I-RAM和D-RAM结合在一起的这种），以及超标量流水线，一个阶段有多条指令要写寄存器堆，但寄存器堆只有一个写端口
数据冒险：RAW，WAR，WAW，五级流水线只有RAW，但超标量都会碰到。关注提交阶段（尤其是从内存读数据）相关的冒险，因为这个时候往往会出现不可前推的冒险，需要停顿。
控制冒险：因为控制流的改变无法提前得知，部分紧跟控制指令后的指令将会被取进流水线执行（但不应执行），需要消除这些指令产生的影响。

异常处理：

异常（Exception）：程序执行期间异常引发的内部事件，如页面错误，下溢，除零等。异常处理在五级流水线同一在提交阶段处理。
中断（Interrupt）：程序执行期间的外部事件，如IO中断，通常是异步的形式出现
陷阱（Trap）：由于异常或中断导致控制权移交给管理程序，通常是同步的形式出现

分支预测

分类：

静态分支预测：总是预测跳转或不跳转
动态分支预测：根据历史跳转记录判断跳不跳转

2-bit Predictor：用2bit来记录分支历史状况。可以看成FSM。缺点：在某些特定程序会一直预测不成功。（在FSM的两个状态之间来回抖动）
分支历史记录表（Branch History Table, BHT）：取PC的低几位作为表的Index，每个表项为2-bit Predictor。

局部动态分支预测和全局动态分支预测详见《超标量处理器设计》

Cache设计

存储器基础

随机访问：访问每个位置都是相同时间。DRAM，SRAM，磁盘。底层电路不太了解，略。

局部性原理

空间局部性和时间局部性，例子是矩阵乘法（考虑矩阵在内存里的组织形式，考虑缺失率，kij或ikj的迭代方式才是最快的）

Cache组织

Cache与内存的相连方式

需要讨论的问题：块大小，地址编码格式？addr=tag##index##offset.
相连方式：一一映射，组相联，全相连。组相联是有个组，然后每组有个tag进行比对，比对成功则对应，否则不行。全相连是特殊情况，addr=tag##offset。
归纳一下，一一映射是多个组，一个路，组相联是多组多路，全相联是一组多路。也就是，组是分组个数，路是一组有多少个块。

Cache的读写策略

需要考虑的问题：读or写？命中or缺失？缺失时的块驱逐策略？
块驱逐策略：Random，LRU，PLRU，FIFO
> 写透：写命中时，数据同时写入Cache和内存。（读缺失不会产生写操作）
> 写回：写命中时，只写入Cache。当该块被替换时检查dirty位，如果dirty位为1则写回内存，否则不写。（读缺失会产生写操作）
> 写分配：写缺失时，会发生块驱逐，然后读出相应块到Cache，然后重新写。（比较复杂）
> 写不分配：写缺失时，直接将结果写入内存。

写缓冲：与Cache并行放置，目的是为了让流水线不停顿（尤其是写透）。当缓冲区也爆掉的时候，会停顿CPU。
一般是写回搭配写分配，写透搭配写不分配。原因？
一般L1和L2 cache采用xxx，L3采用xxx。原因？

Cache性能评价

平均访存时间（Average Memory Access Time，AMAT），计算和访存以及命中率有关。注意访存包括指令访存以及数据访存。

降低缺失率：扩大block size，扩大cache size，更高的相连度
降低缺失惩罚：多级cache，读优先
降低命中时间：避免在索引cache时的地址转换（如虚拟地址到物理地址的转换）

多级cache的任务：L1的速度尽量跟cpu对齐，L2尽量够大，防止访问主存。分类有：
> 多级包含：L1的数据全部在L2中，有利于数据的一致性，但因为L1的数据全部在L2中，故L1的缺失率会略高
> 多级排除：L1的数据不一定全部在L2中，优点是防止空间浪费

指令级并行

编译器技术

包含议题：循环展开，软件流水线，超标量处理器
基本块：一个顺序指令序列，单入口单出口
基本块内的指令级并行很小，内部很容易出现数据冒险，需要考虑循环级并行（LLP）
数据依赖：分为真数据依赖和名称依赖（反依赖，可能导致WAR和输出依赖，可能导致WAW）
名称依赖：两条指令引用相同寄存器或内存位置。WAR中出现的依赖往往被称为反依赖。（注意依赖不一定会引发数据冒险，但数据冒险一定是由于数据依赖引发的）。而WAW中出现的依赖往往称为输出依赖。利用寄存器重命名技术可以解决名称依赖。
控制依赖：某部分代码块对某些条件产生的依赖。
可以提高ILP的编译器优化技术：循环展开，软件流水线，基于编译器的分支预测
对于编译器来说，如果发现寄存器相关，可以考虑指令重排，将发生数据冒险的指令，在不改变功能的前提下分隔得尽量远。

循环展开步骤：
①重复：将循环体的内容重复几次
②合并：在逻辑上将某些指令的常量参数予以修改，并合并某些不必要的操作（等效转换）
③寄存器重命名：消除寄存器前后依赖，目的是提高并行性
④调度：进行指令重排，目的是减少流水线停顿

超标量处理器的分类：
> 静态调度超标量处理器：由编译器实现
> 动态调度超标量处理器：由特殊硬件实现，使用计分板算法或Tomasulo算法

超长指令字（VLIW）处理器：VLIW并行执行多条指令（一条指令完成多个操作）。VLIW架构中，指令级并行的发现与指令执行顺序的调度（硬件中最困难的部分）完全交由编译器完成。

软件流水线：对于每次循环，内部的循环如果是独立的，那么可以通过重排不同循环的指令使不同循环的指令交错，获得ILP。

软件流水线与循环展开的比较：
> 可以一起使用
> 软件流水线占用更少的空间
> 分析复杂，寄存器管理很复杂

动态调度算法

动机：乱序执行，利用重命名技术解决依赖关系
Scoreboard没有重命名，但Tomasulo有。

ScoreBoard

策略：在一系列指令窗口内动态构建依赖关系图。
乱序执行将解码阶段细分为两个阶段：

发射阶段：负责解码指令，检查结构冒险
读操作数阶段：在没有数据冒险的状况下读操作数

顺序发射，乱序执行，乱序提交。
算法经历的四个阶段：

①发射：检查是否有WAW冒险，结构冒险，如果有则发射停顿，否则进行解码操作
②读操作数：没有数据冒险（RAW）后进行读操作
③执行阶段
④写回阶段：该阶段检查WAR（写回的时候，之前的指令还没有读，因为是乱序发射），如果有的话则停止直到没有为止。
留意三种数据冒险在何时处理。

算法相关步骤：

①指令状态：发射（处理WAW），读操作数（处理RAW），执行和写回（处理WAR）。
②功能单元状态：
- 功能单元：指的是加减乘除那些机构。
- 使用九元组来表示功能单元：
- busy：该功能单元是否忙
- op：该功能单元执行的操作
- Fi：该功能单元的目的寄存器
- Fj, Fk: 该功能单元的源操作数寄存器
- Qj, Qk（Query）: 产生Fj，Fk操作数的功能单元
- Rj, Rk（Ready）: Fj，Fk操作数是否产生，产生时为1，产生后进行读，读后将该两位标志置0.
③寄存器结果状态（Result）：指示哪个功能单元要写哪个寄存器（是个映射机构），注意记录的是正在计算的，计算完了的则无需记录。

：Wait Until的意思是所需功能单元空闲并且当前指令的目的寄存器不能是正在执行的某条指令的目的寄存器（保证不会出现WAW），而Bookkeeping的Rj和Rk的限制保证不会出现RAW。
：需要两个操作数Ready了才能读，读后记得清空。
：Wait Until的意思是任何一个功能单元的两个源寄存器（已计算好，因为可能是当前功能单元在算的）不能成为当前单元的目标寄存器（应对WAR冒险，保证WAR的顺序）。这个阶段更新所有其他指令的计分板条目内容，告知操作数已经Ready。并且清除当前指令的Result和Busy位。

PPT上有Scoreboard样例，不再赘述。需要关注的是何时发射（没有WAW），何时读操作数（没有RAW），何时写回（没有WAR），何时更新计分板（发射时更新基本信息，读操作数时更新R，写回时更新计分板上所有的Q，Result和Busy）。

Scoreboard算法的约束条件：可以并行执行的指令条数（即不会发生数据冒险的指令条数最多数目），计分板数据结构的大小（计分板的大小直接决定最多可并行执行的指令条目数，决定了指令窗口的大小），功能单元的数目，指令种存在依赖关系的指令数目多少。

注意Scoreboard仍然是顺序发射不是乱序发射，但是是乱序执行和提交。

关于硬件上的编写细节：组合逻辑？时序逻辑？想清楚。从过程上看，是时序逻辑不是组合逻辑。

Tomasulo

动机：提高浮点数单元的性能
主要特征：拥有一个保留站（reservation stations），通过寄存器重命名技术解决WAR和WAW问题，跟踪每个操作数用于解决RAW问题。

Tomasulo 保留站条目元素：

Op:进行的操作
Vj,Vk:源操作数的值（注意这点跟Tomasulo不同）
Qj,Qk:产生源操作数的寄存器
A:保存读写内存的地址
Busy
寄存器结果状态：和计分板的一样。

Tomasulo和Scoreboard算法的比较：
- 结构性冒险更少，基于Common Data Bus的旁路，对于WAR，WAW冒险无需停顿（通过寄存器重命名技术解决）

Tomasulo算法的缺点：无法实现精确中断（因为乱序提交的缘故）

【课程复习】计算机系统结构复习

前言