计算机体系结构突击

性能、加速比、CPI

Amdahl 定律

  • 主要针对传统机器级的体系结构,加快系统中某部件的执行速度活动的性能提升(加速比)受限于该部件的重要性(比例)
  • 不超过 1/(1-可改进比例)
  • 1/(1-可改进比例)+可改进比例/并行数量

CPU 性能指标:CPI计算

  • 时钟周期(Time Per Cycle)、CPI(Cycles Per Instruction,取决于计算机组成和指令系统)、IC(Instruction Count,指令系统的结构和编译技术)。
  • CPI 计算:CPIi表示第i种指令有多少个时钟周期
image-20250521192319868 image-20250521192419723
  • 执行时间和性能成反比

编译优化

  • 局部优化:单个线性程序段(基本块)内进行的优化。复杂度较低、速度快、适用范围广
    • 常量传播、消除公共子表达式(Common Subexpression Elimination)、
    • 消除死代码、削弱强度(位运算)
    • 降低堆栈高度
  • 全局优化:跨越多个基本块或者函数,基于控制流图进行跨分支分析,分析复杂,提升也明显。
    • 若循环内不变则进行代码外提。
    • 常量传播、消除公共子表达式 CSE
    • 函数内联
  • 汇编语言经过汇编器的翻译为机器语言
  • 翻译:源码一次性转成机器码,提前编译、生成独立可运行文件、依赖平台
  • 解释:源码被逐句翻译执行,动态解析
  • 混合:JIT编译,Java C#

Cache

image-20250521211823581
  • 映象规则: 调入块可以放在哪些位置
  • 查找算法: 如何在映象规则规定的候选位置查找
  • 替换算法: 规定的候选位置均被别的块占用怎么办
  • 写策略: 如何处理写操作
image-20250521211957229

平均访问时间 = 命中访问时间T1 + 失效率 × 失效开销

失效开销 = 从向下一级发出请求把整个数据块调入经过的时间

image-20250521212817490

映射规则

全相联:主存中的任一块可以 被放置到Cache中的任意一个 位置。

  • 对比:阅览室位置── 随便坐
  • 特点:空间利用率最高,冲突概率最低,实现最复杂。

直接映射:主存中的每一块只能被放置到 Cache中唯一的一个位置。

  • 对比:阅览室位置── 只有一个位置可以坐
  • 特点:空间利用率最低,冲突概率最高, 实现最简单。
  • 对于主存的第i 块,若它映象到Cache的第j 块,则: j=i mod (M ) (M为Cache的块数,i是块地址)
    • 如果cache有2的m次方块,块j实际上就是地址i的低m位

组相联:折衷

  • 若主存第i 块映象到第k 组,则: k=i mod(G) (G为Cache的组数)

  • 设G=2的g次方,则当表示为二进制数时,k 实际上就是i 的低 g 位。低g位以及直接映象中的低m位通常称为索引

  • n路组相联:每组n个块。绝大多数时候,n ≤ 4

Cache 性能例题

image-20250521222845268

例题 5.1

image-20250521222858450

例题 5.2

image-20250521222936896 image-20250521222944644

例题 5.3

image-20250521222958536 image-20250521223007219 image-20250521223018048

写策略

  • 写直达法(write through) 执行“写”操作时,不仅写入Cache,而且也写入 下一级存储器。
    • 写失效时,直接写入下一级存储器,不调块。(no allocation)
    • 速度快,所使用的存储器带宽较低。
    • 采用写直达法时,若在进行“写”操作的 过程中CPU必须等待,直到“写”操作结 束,则称CPU写停顿。 减少写停顿的一种常用的优化技术是写缓冲器。
    • 写缓冲器合并
  • 写回法(write back) 执行“写”操作时,只写入Cache,标记脏位。仅当Cache中相应的块被置换时,才写回主存。 (设置“脏位”)
    • 写失效时,先把所写单元所在的块调入Cache, 再写cache,标记脏位。(with allocation)
    • 易于实现,一致性好。
image-20250521222057245

查找、替换算法

image-20250521221844613 image-20250521221909067

优化技术总结

“+”号:表示改进了相应指标。 “-”号:表示它使该指标变差。 空格:表示它对该指标无影响。 复杂度:0表示最容易,3表示最复杂。

image-20250521213839515 image-20250521213855039 image-20250521213908725

降低失效率

三种失效:冲突失效、强制失效、容量失效。(Conflict、Compulsory、Capacity)

  • 强制:当第一次访问一个块时,该块不在Cache中,需从 下一级存储器中调入Cache,这就是强制性失效。 (冷启动失效,首次访问失效)
    • 解决:增加块大小硬件预取Prefetch.
    • 增加块大小会增加命开销
  • 容量:如果程序执行时所需的块不能全部调入Cache中, 则当某些块被替换后,若又重新被访问,就会发 生失效。这种失效称为容量失效。
    • 解决:增加容量
  • 冲突:在组相联或直接映象Cache中,若太多的块映 象到同一组(块)中,则会出现该组中某个块被别 的块替换(即使别的组或块有空闲位置),然后又 被重新访问的情况。这就是发生了冲突失效。 (碰撞失效,干扰失效)
    • 解决:提高相联度,理想情况是全相联。
    • 增加相连度会增大命中时间
  1. 大小为N的直接映象Cache的失效率约等于 大小为N/2的两路组相联Cache的失效率。
  2. 大小为N的伪相联和两路组相联的失效率相当。在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一 次访问,伪相联Cache先按直接映象Cache的方式去处理。若命中, 则其访问过程与直接映象Cache的情况一样。若失效,则再到另一区 相应的位置去查找。若找到,则发生了伪命中,否则就只好访问下一 级存储器。

**硬件预取**:

预取:假设从预取缓冲器中找到所需指令需多花1个 时钟周期。

image-20250521223203358 image-20250521223228700

编译器预取编译器优化:内外循环交换。

**牺牲Cache**:一种能减少冲突失效次数而又不影响时钟频 率的方法。

基本思想:在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache,称为“牺牲”Cache(Victim Cache)。用于存放被替换出去的块(称为牺牲者),以备重用。 对于减小冲突失效很有效,特别是对于小容 量的直接映象数据Cache,作用尤其明显。

image-20250521223451357

降低失效开销

“子块放置技术”

  1. 两级Cache:第一级小而快,第二级容量更大。

    1. 平均访存时间=命中时间T1+失效率F1 × 失效开M1
    2. 失效开销M1=命中时间T2+失效率F2 × 失效开销M2
    3. 局部失效率:F1, F2 全局失效率 = F1 × F2
    4. 因此,平均访存时间 = T1 + F1 × T2 + F2 × M2

    当第二级Cache比第一级Cache大得多时, 两级Cache的全局失效率与容量和第二级 Cache 相同的单级Cache的失效率非常接近。

例 二级cache

image-20250521215829463 image-20250521215842673 image-20250521215853347 image-20250521215901791
  1. 写缓冲合并提高写缓冲器的效率。写直达Cache:依靠写缓冲来减少对下一级存储器写操作的时间。
    1. 如果写缓冲器为空,就把数据和相应地址写入该缓冲器。 从CPU的角度来看,该写操作就算是完成了。
    2. 如果写缓冲器中已经有了待写入的数据,就要把这次的 写入地址与写缓冲器中已有的所有地址进行比较,看是 否有匹配的项。如果有地址匹配而对应的位置又是空闲 的,就把这次要写入的数据与该项合并。这就叫写缓冲合并。
    3. 如果写缓冲器满且又没有能进行写合并的项,就必须等待。
image-20250521220447088
  1. 读失效优先于写。在读失效时,所读单元的最新值有可能还在Cache的写缓冲器中,尚未写入 主存。
    1. 推迟对读失效的处理 (缺点:读失效的开销增加)
    2. 检查写缓冲器中的内容
  2. 请求字处理
image-20250521220110734
  1. 非阻塞Cache。Cache失效时仍允许CPU 进行其它的命中访问。即允许“失效下命中”。对于整数程序来说,重叠次数对性能提高影响不大,简 单的“一次失效下命中”就几乎可以得到所有的好处。最大的好处就是不影响命中时间
image-20250521220225230

例 一次失效命中和组相联

image-20250521220304904 image-20250521220340533

减少命中时间

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中,往往是Cache的访问时间限制了处理器的时钟频率

  1. 容量小、结构简单的Cache。会增大失效率

  2. 虚拟Cache:可以直接用虚拟地址进行访问的Cache。tag 存储器中存放的是虚拟地址,进行地址检测用的也是虚拟地址。

    1. 传统:虚拟地址先通过 MMU 转换成物理地址,再访问物理cache,串行。
    2. 在命中时不需要地址转换,省去了地址转换的 时间。即使失效,地址转换和访问Cache也是 并行进行的,其速度比物理Cache快很多。
    image-20250521214559365
  3. Cache访问流水化。提高时钟频率。并不能真正减少cache的命中时间,但可以提高访问Cache的带宽。访问Cache需要多个时钟周期才可以完成

  4. 踪迹 Cache。存放CPU所执行的动态指令序列,能够提高指令Cache的空间利用率, 地址映象机制复杂,相同的指令序列有可能被当作条件分支的不同选择而 重复存放


体系结构基本概念

冯诺依曼、存储程序计算机

  • 冯诺依曼:存储程序计算机 (运算器、存储器、IO、控制器)
    • 以运算器为中心
    • 控制流由指令流产生,分解程序指令,形成控制上述部件的控制流。
    • 存储程序的原理。程序和数据在同一存储器
      • 局部性原理,时间/空间局部性。
      • 信息按照边界存储:访存速度快
    • 存储器是按照地址访问,线性编址的空间。
      • 字节编址可以支持非数值型计算
    • 操作码+地址码 = 指令
    • 数据使用二进制编码表示,采用二进制运算
    • 加工运算数据,形成了数据流
    • 取指、译码、取数、运算、写回

计算机体系结构的概念

  • 计算机体系结构是程序员所看到的计算机的属性,即概念性结构功能特性

  • 计算机系统分层、程序员分层,所以体系结构也分层

  • 体系结构概念的实质:计算机系统中软硬件界面的确定,其界面之上的是软件的功能,界面之下的是硬件和固件的功能。中间向两边,体系结构就是中间,“中间”:层次结构中的软硬件的交界面,目前一 般是在传统机器语言机器级与操作系统机器级之间

  • 计算机组成包括机器级内部的(数据流)和(控制流)的组成以及逻辑设计等。

  • 系统结构、组成、实现

    • 计算机系统/体系结构是系统的软硬件的界面
    • 计算机组成是系统结构的逻辑实现。
    • 计算机实现是组成的物理实现
  • 同一系统结构可以有不同的组成,同一组成可以有多种实现方式,指令集架构相同。只要是同一系统结构就是系列机,前提是一个厂家生产的。向后兼容必须做到,力争向上兼容

  • 软件实现的机器是虚拟机

透明

  • 低层次的机器属性对于高层次机器的程序员是 透明的
    • 机器语言程序员看到的是编程的硬件组织。
    • 浮点数据表示、乘法指令对于高级语言是透明的,对汇编人员不透明
    • 数据总线宽度、微程序对机器、汇编语言透明,但是对硬件设计人员不透明
    • 指令缓冲器对于系统结构透明
  • 应用、高级、汇编、OS、机器、微程序(逻辑程序员)、硬布线逻辑(硬件设计员) OS 和机器之间就是系统结构

软件移植

  • 一个软件可以不经过修改或者少量修改就能在另一台机器上运行,结果相同,时间区别
  • 使软件能在具有不同系统结构的机器之间 相互移植。 在一种系统结构上实现另一种系统结构。 从指令集的角度来看,就是要在一种机器上 实现另一种机器的指令集。
  • 三种方式:
    • 统一高级语言。缺点:需要争取汇编和机器语言的统一
    • 模拟与仿真:用于不同系统结构的机器
      • 模拟:用软件的方法在一台现有的机器( 称为宿主机)上实现另一台机器(称为虚 拟机)的指令集。 机器模拟机器
      • 仿真:用一台现有机器(宿主机)上的微 程序去解释实现另一台机器(目标机)的 指令集。微程序解释机器,更快,要求系统结构差距不大。
      • 缺点:结构差异比较大,效率低下
    • 系列机:用于相同系统结构的机器
      • 缺点 汇编语言兼容的情况下系统结构发展有限

并行分类

并行概念:同一时刻/时间间隔内,完成两种或者两种以上的工作。(性质相同或者不相同)

  • 指令级并行
  • 线程级并行
  • 任务级/过程级并行:基本单元:进程、子程序

提升并行性

  • 时间重叠:时间片轮转【流水线处理机】
  • 资源重复:重复设置硬件资源(GPU 阵列处理机 多操作部件)
  • 资源共享:这是一种软件方法,它使多个任务按一定时间顺序轮流使用同 一套硬件设备。分时系统。
  • 单处理机:时间重叠(部件功能专一)、资源重复(多体存储器、多操作部件、阵列处理机)、资源共享(虚拟机、分时系统)

Flynn 数据并行、指令并行

  • SISD:单核CPU

  • MISD:少见

  • SIMD:GPU(阵列处理机)、向量处理机。指令操作级并行

    • 阵列处理机:(分布式)存储器阵列 (集中式共享)存储器阵列
  • MIMD:多处理机。

    • 多机系统耦合度有松、紧耦合两大类。
    • 同构型多处理机、异构型多处理机、分布式系统。
    • 共享内存 SMP:多核CPU、SPARC。共享物理内存(受限于带宽,核心数有限)
    • 分布式内存 MPP:分布式计算、超算。每个处理器都有自己的本地内存,通过消息传递来进行通信(共享开销大、复杂)

指令集结构

CISC/RISC

  • RISC:

    • 指令长度固定,指令格式种类少,寻址方式少;
    • 只使用LOAD STORE访存,通用寄存器较多;
    • 流水线技术,一个时钟周期内完成一条指令;
    • 控制器运用组合逻辑。
    • RISC利用VLSI芯片的面积,便于设计,降低成本,提高可靠性,但是不容易实现指令系统的兼容
  • CISC:

    • 指令庞杂复杂,指令使用频度相差悬殊,长度不固定,种类多。不利于用先进的体系结构技术提高性能,研制成本巨大
    • 很多指令可以访存,CPU有专用寄存器
    • 大部分指令都需要多个时钟周期完成
    • 采用微程序控制。
    • 不利于 VLSI设计和单片集成,但是兼容性很强
  • 值得注意的是,从指令系统兼容性看,CISC大多能实现软件兼容,即高档机包含了低档机的全部指令,并可加以扩充。但RISC简化了指令系统,指令条数少,格式也不同于老机器,因此大多数RISC机不能与老机器兼容。由于 RISC 具有更强的实用性,因此应该是未来处理器的发展方向。

  • 但事实上,当今时代 x86 几乎一统江湖,且早期很多软件都是根据CISC 设计的,单纯的RISC将无法兼容。此外,现代CISC结构的CPU已经融合了很多RISC的成分,其性能差距已经越来越小。CISC可以提供更多的功能,这是程序设计所需要的。

RISC重叠寄存器窗口技术 可以减少 CALL(过程调用) 和 RETURN(返回指令) 的执行时间。通过设置大量寄存器,将其分为多个组和全局区,每个组分为高区、本地区、低区,相邻的高低区重叠,加速参数(对应call)和结果(对应return)的传递。

RISC-V: 寄存器寻址、立即数、偏移寻址、寄存器间接寻址

  • R:寄存器寻址,数存在寄存器里
  • I:立即数寻址,其中一个操作是立即数
  • S:存储指令(将寄存器值存入内存),立即数用于地址偏移。
  • U:将高20位立即数加载到寄存器的高位,用于构造大常数或地址。
    • AUIPC(Add Upper Immediate to PC):用于PC相对寻址(如跳转或全局数据访问)。
  • B:条件分支
  • J:无条件跳转

操作数表示、操作数类型

  • 操作数表示:计算机硬件能够直接识别、指令集可以直接调用的数据类型。一般是所有数据类型中最常用、相对比较简单、用硬件实现比较容易的几种。

    • 引入数据表示的原则:缩短运行时间、减少 CPU和主存的通信量、通用性和利用率如何?
    • 分为定点、逻辑、浮点 三种类型
    • 如何确定数据表示(软硬件取舍折中问题)
  • 操作数类型: 由软件进行处理和实现的各种数据类型。研究的是这些数据类型的逻辑结构和物理结构之间的关系并给出相应算法。

  • 操作数类型的表示:或者寻址类型

    • 由操作码编码制定
      • 好:字段少、简单
      • 坏:指令条数增多,译码复杂
    • 使用带标志符的数据类型(数据附上硬件解释的标记)
      • 好:简化指令系统设计,便于开发,支持数据类型于系统实现无关
      • 坏:增加指令的字段数,操作数字段占用更多的位数。

指令集架构类型

  • CPU 存放操作数的地方:堆栈、累加器、通用寄存器
  • 大多数通用型指令寄存器架构可以分为:
image-20250521195708729

指令格式:哈夫曼编码、扩展编码

指令格式的优化:如何用最短的位数来表示 指令的操作信息和地址信息。

  • 哈夫曼编码
image-20250521200908875
  • 信息熵:
image-20250521200757693
  • 信息冗余量 = (平均码长 - 信息熵)/ 平均码长
  • 可以减少操作码的平均位数,但所获得的编码是变长的,不规整,不利于硬件处理。
  • 扩展操作码:位于定长二进制编码和哈夫曼编码之间的一种编码 方案。
  • 采用有限几种固定长度的码长,仍然采用高概率的用短码、低概率用长码的哈夫曼压缩思想,使操作码平均长度缩短。
  • 接近全哈夫曼码的码长,具有定长码的规整性。
image-20250521202254289

图中的 3/3/3 表示,分成三组,那么就可以有三种长度,按照频率从高到低,3*3。

2/7同理,有两种长度,按照频率从高到低2+7。前面频率高的只需要两位就能区分了,因此是00和01

image-20250521201332108 image-20250521201521111 image-20250521201531312 image-20250521201541376

8位寄存器-寄存器型二地址指令3条

  • 指令长度:8位(单字长)。
  • 字段分配:
    • 操作码(OP):2位,用于区分3条指令。
    • 源寄存器(R1):3位,支持8个通用寄存器(23=8)。
    • 目的寄存器(R2):3位,与源寄存器编码方式相同。
1
| OP (2) | R1 (3) | R2 (3) |
  • 指令100 → 如加法指令 ADD R1, R2
  • 指令201 → 如减法指令 SUB R1, R2
  • 指令310 → 如逻辑与指令 AND R1, R2

16位寄存器-寄存器变址寻址指令4条

  • 指令长度:16位(双字长)。
  • 字段分配:有效地址 = 变址寄存器内容 + 指令中给定的偏移量
    • 操作码(OP):4位,用于区分4条指令。
    • 通用寄存器(R):3位,支持8个通用寄存器。
    • 变址寄存器(V):1位,支持2个变址寄存器(21=2)。
    • 偏移地址(Offset):8位,满足变址范围 -127~+127(8位补码表示)。
1
| OP (4) | R (3) | V (1) | Offset (8) |
  • 指令11100 → 如取数指令 LDA R, [V+Offset]
  • 指令21101 → 如存数指令 STA R, [V+Offset]
  • 指令31110 → 如跳转指令 JMP R, [V+Offset]
  • 指令41111 → 如条件跳转指令 JNZ R, [V+Offset]

流水线、指令级并行

数据相关不一定都能用定向技术解决

多条向量指令之间不存在 源向量寄存器冲突功能部件冲突,且只有 向量寄存器 的 写后读相关,那么可以通过链接技术实现这些指令的并行处理。

  1. 数据相关(Data Hazards)前一条指令还未写回结果,后一条指令就尝试使用了该结果。

    • 数据相关(数据冒险):RAW、WAW、WAR。 DLX流水线是RAW
    • 解决方法:前递或旁路(Forwarding,定向技术的原理【RAW】,减少 stall)、插入 NOP、使用 stall 等、。
    • RAW:在流水线中,不同指令同时处于不同阶段,如果一条指令还没将结果写回,下一条指令却已经开始读取这个结果,就会出现错误。前一条指令的结果是后一条的操作数。
    • 定向技术用于解决流水线中的数据冒险问题,尤其是 RAW 类型,通过直接在流水线阶段间传递数据(直接从EX传递给后一条指令),减少或避免插入气泡,提高了性能。
  2. 控制相关(Control Hazards)例如分支指令(如 beq)执行时,下一条指令该不该执行不确定。

    • 解决方法延迟分支分支预测、静态猜测等。
  3. 结构相关(Structural Hazards)硬件资源(如内存)被多个阶段同时访问产生冲突。

    • 解决方法:使用独立的指令/数据 Cache、增加资源。