文章目录
- 第一章 基本原理
-
- 计算机系统层次与体系结构
- 测量及分析性能
- 计算机设计量化原理
- 计算机体系结构分类
- 第二章 指令集体系结构
-
- 指令集分类
- 存储器地址的翻译
- 寻址模式
- 优化指令格式
- 指令集操作
- RISC与CISC
- 第三章 流水线
-
- 流水线
- MIPS基本流水线
- 流水线冒险
- 数据冒险
- 控制冒险
- 流水线多周期操作
- 利用动态调度解决数据冒险
- 减少动态预测分支惩罚
- 利用多发射提高ILP
- 第四章 存储器层次
-
- 简介
- 缓存基础
- 测量并提升Cache性能
- 虚拟存储器
- 储存结构框架
第一章 基本原理
计算机系统层次与体系结构
计算机系统层次:应用语言机、高级语言机、汇编语言机、操作系统机、传统机、微程序机
相同指令集体系结构可以有不同的组织(不同的内存系统、总线、CPU等),相同的指令集体系结构何组织在硬件实现上可以不同。
体系结构属性:指令集、I/O机制、寻址技术、数据类型的位数
体系结构在组织方面对程序员是不可见的(transparent)。
体系结构的设计考虑速度、成本、物理器件大小和功耗(power),如乘法单元(成本高、物理器件较大,但速度快)和加法单元迭代使用(相对速度低,但廉价)用以实现乘法。
摩尔定律:晶体管密度及性能每18-24个月翻一番。(已不再适用)
测量及分析性能
性能(performance)的影响因素:响应时间(response time, elapsed time)(反应快慢)、执行时间(运行快慢,评价性能的主要因素)、吞吐量(throughput)(一次性处理数据多少)
执行时间是性能的倒数。
反应时间的定义:硬盘访问、内存访问、I/O操作、系统开销(operating system overhead)所造成的延迟。
执行时间的定义:
- CPU时间:CPU执行计算所用时间,不包括I/O等待及运行其他程序所用时间。
- CPU时间又可分为:
- 用户CPU时间:程序所占用的CPU时间。
- 系统CPU时间:操作系统响应程序请求所占用的CPU时间(与响应时间不同)。
使用程序评估性能的方法:
- 真实应用进行评估(最精确)
- 核心应用(Kernels)进行评估:使用真实程序中的关键片段进行性能评估。
- 玩具测试基准(Toy benchmarks):小型程序进行评估,结果已知。
- 合成测试基准(Synthetic benchmarks):整合多种应用的benchmark,包括核心程序和真实程序。
比较性能方法:
-
总体执行时间:各测试程序总的执行时间,该方法在计算机执行程序次数相同时可用。
-
平均执行时间:1n∑i=1nTimei\frac{1}{n}\sum^{n}_{i=1}Time_in1∑i=1nTimei
-
加权执行时间:程序执行频率不同时可用。
- 指明程序出现的相对频率或权值设定与执行时间成比例:∑i=1nWeighti×Timei\sum_{i=1}^{n}Weight_i\times Time_i∑i=1nWeighti×Timei
-
归一化执行时间:选定参考机,进行归一化,再利用归一化后的数值进行平均,求平均数可使用算数平均数或几何平均数(∏i=1nExecutiontimeration\sqrt[n]{\prod_{i=1}^{n}Execution\ time\ ratio}n∏i=1nExecution time ratio),最终:
实际性能=归一化数×参考机性能实际性能=归一化数\times 参考机性能 实际性能=归一化数×参考机性能
计算机设计量化原理
阿姆达尔定律(Amdahl’s Law):由某些部分加速所得到的性能提高受加速部分的百分率所限。
- 加速比(Speedup):
加速比=增强后的性能增强前的性能加速比=\frac{增强后的性能}{增强前的性能} 加速比=增强前的性能增强后的性能
- 新的执行时间:
执行时间new=执行时间old×1−未增强部分占比)+增强部分占比加速部分加速比)执行时间_{new}=执行时间_{old}\times1-未增强部分占比)+\frac{增强部分占比}{加速部分加速比}) 执行时间new=执行时间old×1−未增强部分占比)+加速部分加速比增强部分占比)
- 总加速比:
总加速比=执行时间old执行时间new=11−未增强部分占比)+增强部分占比加速部分加速比总加速比=\frac{执行时间_{old}}{执行时间_{new}}=\frac{1}{1-未增强部分占比)+\frac{增强部分占比}{加速部分加速比}} 总加速比=执行时间new执行时间old=1−未增强部分占比)+加速部分加速比增强部分占比1
回报递归法则(the law of diminishing returns):对于一部分性能的提高,总体加速比的提高呈递减状态,即贡献越来越少、有上界。
CPU性能方程:
CPU时间=时钟周期数CPUclockcycles)×时钟周期时间Clockcycletime)CPU时间=时钟周期数CPU\ clock\ cycles)\times时钟周期时间Clock\ cycle\ time) CPU时间=时钟周期数CPU clock cycles)×时钟周期时间Clock cycle time)
CPU时间=CPU时钟周期数时钟频率Clockrate)CPU时间=\frac{CPU时钟周期数}{时钟频率Clock\ rate)} CPU时间=时钟频率Clock rate)CPU时钟周期数
CPI:
CPI=程序所需总CPU时钟周期数指令数Instructioncount,IC)CPI=\frac{程序所需总CPU时钟周期数}{指令数Instruction\ count, IC)} CPI=指令数Instruction count,IC)程序所需总CPU时钟周期数
从而可推出:
CPU时间=指令数×CPI×时钟周期时间CPU时间=指令数\times CPI\times 时钟周期时间 CPU时间=指令数×CPI×时钟周期时间
由于改变时钟周期时间、CPI、指令数其一时,很难不改变其他部分,故有以下计算CPI方法:
CPU周期数=∑i=1nICi×CPIiCPU周期数=\sum_{i=1}^{n}IC_i\times CPI_i CPU周期数=i=1∑nICi×CPIi
测量CPU性能的各组成部分:
- 时钟周期:
- 已完成设计:利用时延评估器(timing estimators)或时延验证器timing verifiers)
- 未完成设计:考察关键路径(critical paths)
- 指令数测量:利用编译器及测试指令集行为的工具
- 指令集模拟器(instruction set simulator):慢,但精确测量指令集行为的几乎所有方面。
- 基于执行的监控(execution-based monitoring):快,通过修改程序(插桩代码)。
- CPI测量困难:现代处理器存在流水线和存储层次,需要考虑流水线和cache结构。
CPIi=PipilineCPIi+MemorysystemCPIiCPI_i=Pipiline\ CPI_i+Memory\ system\ CPI_i CPIi=Pipiline CPIi+Memory system CPIi
引用局部性:程序倾向于重用刚使用过的数据和指令。
计算机体系结构分类
指令数据流类型:
- 单指令流单数据流(single instruction stream over a single data stream)
- 单指令流多数据流
- 多指令流多数据流
- 多指令流单数据流
传统顺序机器为SISD的。
向量计算机(vector computer,流水线结构的计算机)为SIMD的。
并行计算机(parallel computer)为MIMD的。
MISD的计算机仅存在于实验,尚无实际应用。
第二章 指令集体系结构
指令集分类
体系结构分类:
- 寄存器-存储器体系结构(register-memory architecture)
- 优点:数据可以不用被分别装入内存,并且指令格式也会更加简单。
- 缺点:操作数不等长,所用时时钟不同。
- 寄存器-寄存器体系结构
- 优点:指令简单,执行时时钟相似。
- 缺点:指令条数增加。
- 存储器-存储器体系结构(暂无,速度较慢,指令长短不一)
- 优点:不浪费寄存器。
- 缺点:指令长度不一,存储器不能被共享。
通用寄存器计算机(GPR,general-purpose register machine)优势:
- 寄存器速度快;
- 寄存器易于编译器有效使用。
GPR结构:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传img-9kInLVnf-1655391892109)https://s1.ax1x.com/2022/06/14/X5nfSO.png)]
- 三操作数模式(three-operand)
- 二操作数模式:一个操作数既是源操作数也是结果操作数。
存储器地址的翻译
所有指令集都是按字节寻址(byte addressed),可访问字节(8 bits)、半字(16 bits)、字(32 bits),多数计算机也可访问双字(64 bits)。
字节排序:
- 小端序(Little Endian):高对高,低对低。如x86-64。
- 大端序(Big Endian):高对低,低对高。如MIPS。
**对齐(align)**问题:某些存储可能要求对齐,⚠️需要注意
寻址模式
寻址时可使用常数(constant)、寄存器、存储地址(有效的存储地址为有效地址(effective address))。
一个指令集体系结构最少需支持位移寻址(displacement addressing)、立即数寻址(immediate addressing)、寄存器间址(register deferred)。
优化指令格式
指令格式构建主要使用哈夫曼编码(Huffman coding)。
每个字符平均最少所需位:
H=−∑i=1nPi⋅log2PiH=-\sum_{i=1}^{n}P_i\cdot \log_{2}{P_i} H=−i=1∑nPi⋅log2Pi
固定长度编码冗余度(redundancy):
R=1−−∑i=1nPi⋅log2Pi⌈log2n⌉R=1-\frac{-\sum_{i=1}^{n}P_i\cdot \log_{2}{P_i}}{\lceil\log_{2}{n}\rceil} R=1−⌈log2n⌉−∑i=1nPi⋅log2Pi
构造哈夫曼树,从而得到前缀码(prefix )。
由于前缀码结构不整齐,故使用扩展码(extended opcodes)折中。扩展码保证了一定范围内的编码长度相同。
操作数×{\times}×寻址模式的组合最大时,每个操作数用寻址标识符(address specifier)。
指令集编码方式:
- 变长(variable):允许所有操作有任何寻址模式。
- 定长(fixed):将操作和寻址模式结合到操作码域。
- 混合(hybrid):折中。
指令集操作
控制流指令:
- 条件转移(conditional branches):有条件
- 跳转(jump):无条件
- 过程调用(procedure calls,procedure invocation)
- 过程返回(procedure returns)
控制流指令最常用的是PC相对(PC-relative)寻址。
条件转移选项:
条件码(CC)就是汇编里学的CF、OF、ZF,条件寄存器就是使用寄存器判断跳转,比较与分支就是直接将比较和跳转合二为一。
过程调用选项:
- 调用者保存(caller saving):谁调用谁保存
- 被调用者保存(callee saving)
RISC与CISC
RISC(reduced instruction set computer,精简指令集计算机)特点:
- 指令类型少,运行快
- 指令简单
- 使用更少的晶体管,设计制造便宜
- 硬连线控制(hardwired control),即固化在电路中
- 与存储器的寻址关联操作少,只用LOAD和STORE
- 所用寄存器多
CISC(complex instruction set computer,复杂指令集计算机)特点:
- 指令多
- 复杂且高效(efficient)
- 由于指令复杂,故需分步实现,即微命令
- 寻址能力强(extensive)
- 所用寄存器较少
指令执行步骤:取指(instruction fetching)、译码(decoding phase)、取操作数(operand fetching phase)、执行(execution phase)、写回(write-back phase)
MIPS是RISC体系结构的一种:
- load-store 指令集
- 定长编码,32 bits
- 高效
- 拥有32个寄存器,每个32 bits,0号寄存器总是保存0,31号及储存期用来存储一些MIPS指令;此外还有用于存储浮点数的浮点寄存器(FPR,32位或64位)
- 支持字节及半字
⚠️MIPS使用的是大端序,需对齐
MIPS指令格式(32位指令,6位操作码):
⚠️上图中的高低位标号应该相反(31-0)。
第三章 流水线
流水线
平衡流水段长度:
非流水线机器上每条指令的所用时间流水段数量\frac{非流水线机器上每条指令的所用时间}{流水段数量} 流水段数量非流水线机器上每条指令的所用时间
MIPS基本流水线
MIPS流水线的五个步骤:IF、ID、EX、MEM、WB
IF阶段:取指到指令寄存器,PC+1。
ID阶段:对指令进行解码,从寄存器中取值。
EX阶段:ALU指令(ADD之类)进行计算,LOAD-STORE指令计算地址,Branch指令计算地址。
MEM阶段:ALU指令啥也不做,LOAD指令访问数据存入LMD,STORE指令访存存入数据。
WB阶段:ALU指令写回,LOAD指令将数据写入寄存器。
时钟周期与CPI取舍:降低CPI会导致电路复杂,进而时钟周期增加。
流水线结构:
流水线的基本性能问题:
- 流水线增加了吞吐量;
- 由于控制开销,指令运行时间增加;
- 但由于吞吐量的增加,程序运行更快。
影响流水线性能的因素:
- 存在水桶效应,不平衡;
- 流水线存在开销:
- 寄存器启动时间(register setup time):输入需要进行稳定,并且有传播(propagation)时延
- 时钟偏差(clock skew):信号传输时延
流水线冒险
解决冒险(hazards)最简单的方法:阻塞(stall)
加速比=未流水化CPI或流水线段数1+流水线阻塞周期加速比=\frac{未流水化CPI或流水线段数}{1+流水线阻塞周期} 加速比=1+流水线阻塞周期未流水化CPI或流水线段数
结构冒险(structural hazards):
- 不完全流水化造成阻塞
- 一些资源未足够复制
- 写冲突
- 访问冲突(只有一个内存入口时,从内存中,IF段取值,MEM段访问数据)
数据冒险
通过加入硬件结构,可以解决数据冒险:
- 设置指令缓存和数据缓存;
- 设置指令缓存存储指令。
数据冒险:使用前送(forwarding)解决数据冒险。特别需要注意的是,在同一阶段使用同一寄存器,也可能产生前送 。前送可以是相同时间,前送可以先获得数据旧数据,后续比较进行更新。
- 写后读(RAW)
- WAW:该种不会在MIPS中出现,若出现那就stall。
- WAR:上图会造成读假数据。
- RAR:非数据冒险
由于某些冲突过于频繁,故可以通过调度来解决冲突。
发射(instruction issue):ID→EX,对于MIPS整数流水线,所有冒险都能在ID阶段检测出来。
- 早解决:不用将指令悬挂,降低硬件复杂性;
- 在使用操作数的周期才检测冒险或前送。
解决LOAD指令的RAW:
堵塞的实现:ID/EX流水线寄存器的控制部分(control portion)全部置零,做空操作(no-op);IF/ID寄存器内容循环(recirculate),保持停顿。
控制冒险
控制冒险可能比数据冒险造成的性能损失更大(great performance loss)。
最简单的方法:直接阻塞,知道到达MEM计算出新的PC
MIPS中将转移测试移动到了ID阶段(增加了额外的加法器和零测试),并且在IF阶段写PC,ID阶段计算出目标地址。从而转移在ID结束后就完成,未使用EX、MEM、WB。
降低转移造成的惩罚:
- 冻结(freeze)或泄放(flush):保持或删除转移指令后的指令,知道转移目的地址已知。
- 预测不成功,若成功在将已去除的指令变为no-op,并重新取值。
- 预测转移成功。
- 延迟转移:使用延迟槽(branch-delay slots)。延迟槽有三种分支调度方法:
- 指令来自以前,最好。
- 指令来自成功目标。
- 指令来自不成功目标。
流水线多周期操作
浮点操作会占用多个周期,需要充分很多次EX。
潜伏期(latency):从产生结果(假定在EX阶段第一周期产生结果)到使用结果之间的周期数。
初始/重复间隔(initiation/repeat interval):发射两个给定类型操作之间必须经过的周期数。
潜伏期和初始间隔:
其中,除法未完全流水化。其他则在EX中进行流水化。
长延迟流水线(Longer Latency Pipelines)的冒险和前送:
- 除法未完全流水化,可能导致结构冲突。
- 指令运行时间不同,可能导致同一周期有多个寄存器写操作,造成结构冲突。
- 指令不再按序到达WB,可能导致WAW冒险。
- 寄存器读总在ID发生,所以不会有WAR冒险。后续更改与前面无关。
- 长延迟导致RAW冒险更频繁。
EX阶段多种操作单元可以并行进行。
写寄存器冲突:可增加端口,从而解决结构冲突。
解决结构冲突的途径:
- 早解决,在ID阶段跟踪写端口的使用,并在发射前阻塞指令。
- 优点:其可以在ID阶段就完成互锁检测和阻塞插入。
- 成本:要加入移位寄存器和写冲突逻辑。
- 到时候再解决:在冲突指令要进入MEM或WB时再阻塞。
- 优点:直到MEM或WB才检测冲突,更容易。
- 缺点:流水线控制复杂化,可以从两个地方插入阻塞。
解决WAW途径:
- 早解决,延缓load发射,直到ADDD进入MEM。
- 到时候再解决: 检测到冒险,就改变控制,使ADDD不写结果。
检测所有可能的冲突:在ID阶段做三个检测
- 等待,直至功能单元能用。(仅除法)
- 检测RAW冒险。
- 检测WAW冒险。
利用动态调度解决数据冒险
解决冲突的途径:
- 静态调度
- 动态调度(Tomasulo方法):
- 发射(issue):取值。
- 若为FP操作,有空保留站,则发射。若操作数在寄存器中就送保留站。
- 若为L-S操作,有缓冲器空间,则发射。
- 无空保留站或空缓冲器,则结构冒险,指令阻塞等待。
- 执行(execute)
- 若有操作数计算出来,则放入相应保留站(Q置0,数放V)。
- 两个操作数都计算出来,就在功能单元中执行操作。
- 检测RAW冒险
- 写结果(write result):计算出结果,写道CDB上。
- 发射(issue):取值。
具体操作如下图:
减少动态预测分支惩罚
使用基本转移预测(Basic Branch Prediction)和转移预测缓冲器(Branch Prediction Buffers)。
基本转移预测:
- 2位预测方案:错两次才改变预测。
- N位预测方案:计数器可取值0到2n−12^n-12n−1。当 ≥2n–12≥\frac{2^n– 1}{2}≥22n–1时,预测转移; 否则,预测不转移。
转移目标缓冲器(Branch-Target Buffers):存储所预测的转移后的下条地址。
转移预测缓冲器和转移目标缓冲器的区别:
- 转移预测缓冲器:在ID阶段被访问,ID末才知道转移目标地址。
- 转移目标缓冲器:用IF阶段来取指令的地址访问缓冲器,命中就能知道预测地址。
图中,命中但预测错误、未命中但预测正确都要更新缓冲器并且重新取指,需消耗2个周期。
利用多发射提高ILP
超标量处理器(superscalar processors):
- 每个周期发射不同数量的指令,指令间不能互相干扰、互斥
- 可用编译器进行静态调度,或者采用Tomasulo进行动态调度
超长指令字处理器(VLIW processors)
- 发射固定数量的指令,格式化成一个大指令(固定指令包),负担在编译器上而非硬件
- 用调度器进行静态调度
第四章 存储器层次
简介
局部性原理(principle of locality):程序在任意时刻都是访问地址空间的一小部分。
- 时间局部性(temporal locality)
- 空间局部性(spatial locality)
存储器层次理论基础是局部性原理。
存储器:
- SRAM:静态RAM
- DRAM:动态RAM,较SRAM便宜但慢
- magnetic disk:磁盘
当命中率足够大,则访问时间接近最高层,大小接近最底层。
缓存基础
cache中寻找/储存数据的方法:
此处的块位数其实就是块内偏移,由于机器是32位机,有4 Bytes,所以2位。
- 直接映像:
- 低位部分用于索引;
- 剩余高位部分作为tag进行对比确认。
cache缺失问题解决:阻塞CPU,冻结所有寄存器中的内容;从存储器中取出数据放入cache;重新在导致缺失的地方进行执行。
对cache进行写操作时,可能遇见写缺失(write miss),仅需将数据写入cache并更新cache和数据。在写入cache时,可能需要将数据送回到内存:
- 通写(write-through):处理简单但效率不高,每次写cache都会导致数据写入主存。
- 解决写入主存慢的问题,可以使用写缓冲器(write buffer),从而使其进行匹配。
- 写回(write-back):当发生替换时,被修改的块才写入主存。
若要利用局部性原理,则cache可以使用类似组相联的结构,但其区别是该cache中同一行的数据必须同时写入。
测量并提升Cache性能
- 通过组相联、全相联。
- 通过多级cache。
⚠️减小CPI和提高时钟频率是不一样的,减小CPI是减小的指令执行的周期数,提高时钟频率是降低一个周期的时间。
直接映像:一个块对应cache中一个位置;
全相联:一个块对应cache(只有一行)中一行中的任意位置;
组相联:一个块对应cache中某一行中的任意位置。
Cache大小=组数×相连性Cache大小=组数\times 相连性 Cache大小=组数×相连性
多级Cache中初级专注于命中时间,二级专注于命中率
虚拟存储器
虚拟存储器和Cache类似,只不过Cache中存储的是数据,但是虚拟存储器中存储的是部分物理地址。
虚拟页可能在外存中,导致会发生缺页。
页表采用全相联。
页最开始存储在磁盘中,由OS决定所要的页存储在主存储器哪里。然后访问页时,页在内存中。
页表还有对应的TLB(快表)。
TLB采用随机替换策略,全相联。
不可能出现TLB命中,页表中缺失的情况。
每个进程都有自己的虚拟空间。
降低缺失率的技术:
- 采用大的块以利用空间局部性;
- 采用页表,全相联;
- LRU和访问位来选择要替换的页。
储存结构框架
LRU可以采用硬件(移位寄存器)实现,或近似实现,甚至随机替换。
虚拟存储器只有回写是现实的,因为从内存想磁盘写数据用时太长。
3C模型:理解存储层次行为的直觉模型
- 强制缺失(Compulsory misses):第一次,从未进入cache;
- 缓解方法:增加块尺寸,利用局部性原理,但可能对性能有影响。
- 容量缺失(Capacity misses):Cache容量(并非组内)不够容纳运行中的所有模块;
- 缓解方法:增大Cache容量,但也增大访问时间。
- 冲突缺失(Conflict misses):多模块在一个组能竞争;
- 缓解方法:增加相连性,朝着全相联的方向走,但会降低性能。