计算机系统结构

计算机系统结构的基础知识

计算机系统结构的概念

第一台通用电子计算机诞生于1946年
计算机技术的飞速发展受益于两个方面：制造技术的发展、系统结构的创新
经历了四个发展过程
- 引起性能增长速度减缓的主要原因：大功耗问题、可进一步有效开发的指令级并行已经很少、存储器访问速度提高缓慢
- 系统结构的重大转折：从单纯依靠指令级并行转向线程级并行和数据级并行

计算机系统的层次结构

计算机系统 = 硬件 + 软件
计算机语言从低级向高级发展
从计算机语言的角度，把计算机系统按功能划分成多级层次结构
- 每一层以一种语言为特征
- 物理机：用硬件实现的机器
- 虚拟机：用软件实现的机器
- 各机器级的实现主要靠翻译或解释，或两者的结合，解释执行比编译后执行所花的时间多，但占用的存储空间少

计算机系统结构的定义

传统机器程序员所看到的计算机属性，即概念性结构与功能特性
按照计算机系统的多级层次结构，不同级程序员所看到的计算机具有不同的属性
透明性：本来存在的事物或属性，但从某种角度看又好像不存在的概念
功能特性：数据表示、寻址技术、寄存器定义、指令系统、存储系统、中断系统、输入输出系统、机器工作状态

计算机系统结构的实质

确定计算机系统中软硬件的界面，界面之上是软件实现的功能，界面之下是硬件和固件实现的功能
计算机系统结构是计算机系统结构抽象层的设计，使我们能够利用现有的制造技术有效地实现信息处理应用

计算机系统结构的6个伟大思想

层次结构
摩尔定律
局部性原理/存储器层次结构
并行
性能测量&提升
可信性 via 冗余

计算机系统结构的分类

Flynn分类法：按照指令流和数据流的多倍性进行分类
- 指令流：计算机执行的指令序列
- 数据流：由指令流调用的数据序列
- 多倍性：在系统最受限的部件上，同时处于同一执行阶段的指令或数据的最大数目
把计算机系统的结构分为4类
- 单指令流单数据流SISD
- 单指令流多数据流SIMD
- 多指令流单数据流MISD
- 多指令流多数据流MIMD

计算机系统的设计

计算机系统的定量原理

加快经常性事件速度
- 对经常发生的情况采用优化方法的原则进行选择，以得到更多的总体上的改进
- 优化是指分配更多的资源、达到更高的性能或者分配更多的电能等
- 阿姆达尔定律：系统中某一部件由于采用更快的执行方式，整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关
  - 可改进部分的比例：Fe = 可改进部分的执行时间/改进前整个任务的执行时间
  - 改进部分的加速比：Se = 改进前改进部分的执行时间/改进后改进部分的执行时间
  - 改进后整个任务的执行时间为： $T_n=T_0\cdot(1-Fe+\frac{Fe}{Se})$
  - 改进后整个系统的加速比达到： $S_n=\frac{T_0}{T_n}=\frac{1}{1-Fe+\frac{Fe}{Se}}$
- 一种性能改进的递减规则：如果仅仅对计算任务中的一部分做性能改进，则改进越多，所得到的总体性能的提升就越有限，加速比不超过 $\frac{1}{1-Fe}$
CPU性能公式
- 执行一个程序所需的CPU时间=执行程序所需的时钟周期数×时钟周期时间
- 每条指令执行的平均时钟周期数CPI=执行程序所需的时钟周期数/IC（IC：所执行的指令条数）
- 程序执行的CPU时间可以写成CPU时间=IC×CPI×时钟周期时间
- CPU的性能取决于三个参数
  - 时钟周期时间：取决于硬件实现技术和计算机组成
  - CPI：取决于计算机组成和指令系统的结构
  - IC：取决于指令系统的结构和编译技术
- 对CPU性能公式进行进一步细化
  - $CPI_i$ ：第i种指令的处理时间
  - $IC_i$ ：在程序中第i种指令出现的次数
  - CPU平均时钟周期数= $\sum^n_{i=1}(CPI_i \times IC_i)$
  - CPI=时钟周期数/IC= $\frac{\sum\limits^n_{i=1}CPI_i\times IC_i}{IC}=\sum\limits^n_{i=1}(CPI_i\times\frac{IC_i}{IC})$ ，其中 $\frac{IC_i}{IC}$ 反映了第i种指令在程序中所占的比例
程序的局部性原理：程序执行时所访问的存储器地址分布不是随机的，而是相对地簇聚
- 常用的一个经验准则：程序执行时间的90%都是在执行程序中10%的代码
- 时间局部性：程序即将用到的信息很可能就是目前正在使用的信息
- 空间局部性：程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或者临近

计算机系统设计者的主要任务

计算机系统设计者的任务包括：指令系统的设计、数据表示的设计、功能的组织、逻辑设计以及其物理实现等
设计一个计算机系统大致要完成3个方面的工作：
- 确定用户对计算机系统的功能、价格和性能的要求
- 软硬件功能分配
- 设计出生命周期长的系统结构

计算机系统设计的主要方法

“由上往下”设计
- 从层次结构的最上面一级开始，逐层往下设计各层的机器
- 适用于专用机的设计，而不适合通用机的设计
“由下往上”设计
- 从层次结构的最下面一级开始，逐层往上设计各层的机器
- 采用这种方法时，软件技术完全处于被动状态，这会造成软件和硬件的脱节，使整个系统的效率降低
“从中间开始”设计
- 综合考虑软硬件的分工，从中间开始设计

计算机系统的性能评测

执行时间和吞吐率
- 执行时间
  - 计算机完成某一任务所花费的全部时间，包括磁盘访问、存储器访问、输入/输出、操作系统开销等
  - CPU时间：CPU执行所给定的程序所花费的时间，不包含I/O等待时间以及运行其它程序的时间
    - 用户CPU时间：用户程序所耗费的CPU时间
    - 系统CPU时间：用户程序运行期间操作系统耗费的CPU时间
- 吞吐率：单位时间里能够完成的任务数量
基准测试程序
性能比较
- 总执行时间：机器执行所有测试程序的总时间
- 平均执行时间：各测试程序执行时间的算术平均值
- 加权执行时间：各测试程序执行时间的加权平均值
- 调和平均值
- 几何平均值
- 加权几何平均值

计算机系统结构的发展

经典冯诺依曼结构及其改进

存储程序原理的基本点：指令驱动
- 程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作
经典冯诺依曼结构的主要特点
- 计算机以运算器为中心
- 在存储器中，指令和数据同等对待
- 存储器是按地址访问、按顺序线性编址的一堆结构，每个单元的位数是固定的
- 指令的执行是顺序的
- 指令由操作码和地址码组成
- 指令和数据均以二进制编码表示，采用二进制运算
对系统结构进行的改进
- 输入输出方式的改进：程序控制、DMA、I/O处理机
- 采用并行处理技术
- 存储器组织结构的发展
- 指令系统的发展

软件对系统结构的影响

软件的可移植性：一个软件可以不经修改或者只需少量修改就可以由一台机器移植到另一台机器上正确地运行，差别只是执行时间的不同，我们称这两台机器是软件兼容的
实现可移植性的常用方法
1. 统一高级语言
  - 实现软件移植的一种理想方法
  - 较难实现
2. 系列机
  - 由同一厂家生产的具有相同的系统结构，但具有不同组成和实现的一系列不同型号的机器
  - 软件兼容
    - 向上(下)兼容：按某档机器编制的程序，不加修改就能运行于比它高（低）档的机器
    - 向前(后)兼容：按某个时期投入市场的某种型号机器编制的程序，不加修改地就能运行于在它之前（后）投入市场的机器
3. 模拟与仿真
  - 使软件能在具有不同系统结构的机器之间相互移植
  - 模拟：用软件的方法在一台现有的机器(称为宿主机)上实现另一台机器(称为虚拟机)的指令集
  - 仿真：用一台现有机器(宿主机)上的微程序去解释实现另一台机器(目标机)的指令集

器件发展对系统结构的影响

推动计算机系统结构不断发展的最活跃的因素
摩尔定律：集成电路芯片上所集成的晶体管数目每隔18月就翻一番
计算机的分代主要以器件作为划分标准

应用对系统结构的影响

不同的应用对计算机系统结构的设计提出了不同的要求
应用需求是促使计算机系统结构发展的最根本的动力
一些特殊领域：需要高性能的系统结构

计算机系统结构中并行性的发展

并行性的概念

并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作
- 同时性：两个或两个以上的事件在同一时刻发生
- 并发性：两个或两个以上的事件在同一时间间隔内发生
从执行程序的角度来看，并行性等级从低到高可分为：
- 指令内部并行：单条指令中各微操作之间的并行
- 指令级并行：并行执行两条或两条以上的指令
- 线程级并行：并行执行两个或两个以上的线程
- 任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段）
- 作业或程序级并行：并行执行两个或两个以上的作业或程序

提高并行性的技术途径

时间重叠：引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度
资源重复：引入空间因素，以数量取胜，通过重复设置硬件资源，大幅度地提高计算机系统的性能
资源共享：这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备

单机系统中并行性的发展

在发展高性能单处理机过程中，起主导作用的是时间重叠原理
- 实现时间重叠的基础：部件功能专用化
在单处理机中，资源重复原理的运用也已经十分普遍
- 多体交叉存储器
- 多操作部件
- 阵列处理机（并行处理机）
在单处理机中，资源共享的概念实质上是用单处理机模拟多处理机的功能，形成所谓虚拟机的概念

多机系统中并行性的发展

多机系统遵循时间重叠、资源重复、资源共享原理，发展为3种不同的多处理机：同构型多处理机、异构型多处理机、分布式系统
耦合度：反映多机系统中各机器之间物理连接的紧密程度和交互作用能力的强弱
功能专用化（实现时间重叠）：专用外围处理机、专用处理机、异构型多处理机系统
机间互连：容错系统、可重构系统、同构型多处理机系统

并行机的发展变化

并行机的萌芽阶段（1964年～1975年）
向量机的发展和鼎盛阶段（1976年～1990年）
MPP出现和蓬勃发展阶段（1990年～1995年）
各种体系结构并存阶段（1995年～2000年）
机群蓬勃发展阶段（2000年以后）

指令集体系结构

指令的组成

操作码
- 操作种类：加、减、乘、除、数据传送、移位、移、输入输出、程序控制、处理机控制等
- 操作数描述
  - 数据的类型：定点数、浮点数、复数、字符、字符串、逻辑数、向量
  - 进位制：2进制、10进制、16进制
  - 数据字长：字、半字、双字、字节
地址码
- 地址：地址码、立即数、寄存器、变址寄存器
- 地址的附加信息：偏移量、块长度、跳距
- 寻址方式：直接寻址、间接寻址、立即数寻址、变址寻址、相对寻址、寄存器寻址

ISA：指令集、指令格式

硬件和软件的接口
设计规范
不是微架构
不仅仅是指令集

指令

信息处理的原子单位
改变机器状态

Architecture

ISA对软件可见
地址空间，寻址技术
操作码，数据类型，寻址方式
权限，优先级
多处理器的支持
多程序设计支持

μArchitecture：根据指令，改变处理器状态

对软件不可见
Cache
分支预测
指令周期
流水线

数据表示

数据表示与数据类型

数据表示：计算机硬件能够直接识别，可以被指令系统直接调用的那些数据类型
数据类型：由软件进行处理和实现的各种数据类型
确定数据表示的原则
- 一是缩短程序的运行时间
- 二是减少CPU与主存储器之间的通信量
- 三是这种数据表示的通用性和利用率
数据表示在不断发展
- 用软件和硬件结合的方法实现新的数据表示
  - 用字节编址支持字符串数据表示
  - 用变址寻址支持向量数据表示

自定义数据表示

一般处理机中的数据表示方法
- 数据存储单元(寄存器、主存储器、外存储器)只存放纯数据，数据的属性通过指令中的操作码来解释
- 在高级语言和应用软件中，数据的属性由数据自己定义，在高级语言与机器语言中间的语义差距，要靠编译器等填补
带标志符的数据表示法

指令系统结构的分类

根据CPU中用来存储操作数的存储单元的类型，将指令系统的结构分为三种类型：
- 堆栈结构
- 累加器结构
- 通用寄存器结构
  - 根据操作数的来源不同，又可进一步分为：
    - 存储器-存储器结构(MM结构)
    - 寄存器-存储器结构(RM结构)
    - 寄存器-寄存器结构(RR结构)
  - 现代指令系统结构的主流
  - 在灵活性和提高性能方面有明显的优势
  - 根据ALU指令的操作数的两个特征对通用寄存器型结构进一步细分
对于不同类型的结构，操作数的位置、个数以及操作数的给出方式也会不同
- 显式给出：用指令字中的操作数字段给出
- 隐式给出：使用事先约定好的单元

寻址技术

寻找操作数及其地址的技术称为寻址技术

编址方式
寻址方式
定位方式

编址方式

对各种存储设备进行编码的方法：

编址单位
- 常用的编址单位：字编址、字节编址、位编址、块编址等
- 编址单位与访问字长
  - 一般：字节编址，字访问
  - 部分：位编址，字访问
  - 辅助存储器：块编址，位访问
- 字节编址字访问的优点：有利于符号处理
- 字节编址字访问的问题：
  - 地址信息浪费：32位机器浪费最低2位地址
  - 存储空间浪费：信息宽度不超过主存宽度的信息必须存放在一个存储字内，不能跨边界
  - 读写逻辑复杂
  - 大端与小端问题
零地址空间个数
- 三个零地址空间：通用寄存器、主存储器、输入输出设备独立编址
- 两个零地址空间：主存储器与输入输出设备统一编址
- 一个零地址空间：最低端是通用寄存器，最高端是输入输出设备，中间为主存储器
- 隐含编址方式：堆栈、Cache等
并行存储器的编址
- 高位交叉编址：主要用来扩大存储器容量
- 低位交叉编址：主要是提高存储器速度
输入输出设备的编址
- 一台设备一个地址：通过指令来区分地址
- 一台设备两个地址：数据寄存器、状态或控制寄存器
- 多个编址寄存器共用一个地址
- 一台设备多个地址

寻址方式

立即数寻址方式和偏移寻址方式的使用频度最高
采用多种寻址方式可以显著地减少程序的指令条数，但可能增加计算机的实现复杂度以及指令的CPI
两种表示寻址方式的方法
- 将寻址方式编码于操作码中，由操作码描述相应操作的寻址方式，适合：处理及采用load-store结构，寻址方式只有很少几种
- 在指令字中设置专门的寻址字段，用以直接指出寻址方式，适合：处理机具有多种寻址方式，且指令有多个操作数

定位方式

程序需要定位的主要原因
- 程序的独立性
- 程序的模块化设计
- 数据结构在程序运行过程中，其大小往往是变化的
- 有些程序本身很大，大于分配给它的主存物理空间(虚存)
主要的定位方式
- 直接定位方式：在程序装入主存储器之前，程序中的指令和数据的主存物理就已经确定了的称为直接定位方式
- 静态定位：在程序装入主存储器的过程中随即进行地址变换，确定指令和数据的主存物理地址的称为静态定位方式
- 动态定位：在程序执行过程中，当访问到相应的指令或数据时才进行地址变换，确定指令和数据的主存物理地址的称为动态定位方式

指令系统的设计与优化

指令系统的设计

指令系统设计的基本原则
1. 指令系统的设计
  - 指令的功能设计
  - 指令格式的设计
2. 在确定哪些基本功能用硬件来实现时，主要考虑3个因素：速度、成本、灵活性
  - 硬件实现的特点：速度快、成本高、灵活性差
  - 软件实现的特点：速度慢、价格便宜、灵活性好
3. 对指令系统的基本要求
  - 完整性：在一个有限可用的存储空间内，对于任何可解的问题，编制计算程序时，指令系统所提供的指令足够使用
  - 规整性：主要包括对称性和均匀性
    - 对称性：所有与指令系统有关的存储单元的使用、操作码的设置等都是对称的
    - 均匀性：指对于各种不同的操作数类型、字长、操作种类和数据存储单元，指令的设置都要同等对待
  - 正交性：
    - 每个指令执行一个特定操作，而不是复制或者重叠其他指令功能
    - 在指令中各个不同含义的字段，如操作类型、数据类型、寻址方式字段等，在编码时应互不相关、相互独立
  - 高效率：指指令的执行速度快、使用频度高
  - 兼容性：主要是要实现向后兼容，指令系统可以增加新指令，但不能删除指令或更改指令的功能
在设计指令系统时，有两种截然不同的设计策略
- CISC(复杂指令系统计算机)：增强指令功能，把越来越多的功能交由硬件来实现，并且指令的数量也是越来越多
- RISC(精简指令系统计算机)：尽可能地把指令系统简化，不仅指令的条数少，而且指令的功能也比较简单

指令系统的优化

指令格式的优化
1. 哈夫曼编码
  - 操作码优化的程度可以用信息熵来衡量： $H=-\sum\limits^n_{i=1}p_ilog_2p_i$
  - 优缺点：可以减少操作码的平均位数，但所获得的编码是变长度的，不规整，不利于硬件处理
  - 扩展操作码：位于定长二进制编码和哈夫曼编码之间的一种编码方案
2. 等长扩展码
  - 为了便于分级译码，一般都采用等长扩展码
  - 15/15/15法和8/64/512法
3. 定长操作码
  - 固定长度的操作码：所有指令的操作码都是同一的长度
  - 保证操作码的译码速度、减少译码的复杂度
  - 以程序的存储空间为代价来换取硬件实现上的好处
  缩短地址码长度的方法：用一个短地址码表示一个大地址空间
4. 用间址寻址方式缩短地址码长度
5. 用变址寻址方式缩短地址码长度
6. 用寄存器间接寻址方式缩短地址码长度
指令字格式的优化
1. 如果指令字的宽度固定，地址码的长度和个数固定，则操作码的缩短并不能带来好处，只是使指令字中出现空白浪费
2. 采用地址个数可变和/或地址码长度可变的方案
  - 利用操作码缩短带来的好处
  - 最常用的操作码最短，其地址字段个数最多
3. 考虑因素
  - 计算机中寄存器个数和寻址方式的数目对机器的指令字长有很大的影响
  - 指令字的平均长度增加了，程序的平均长度也就增加了
  - 在指令系统的设计之中，要在指令字长与寄存器个数以及寻址方式的个数之间进行折中
4. 指令系统的3种编码格式
  - 可变编码格式
  - 固定长度编码格式
  - 混合型编码格式

指令系统的发展和改进

沿CISC方向发展和改进指令系统

CISC指令系统的一大特点：指令数量多、功能多样
增强指令功能主要是从以下3个方面着手：
- 面向目标程序增强指令功能
  - 对大量的目标程序及其执行情况进行统计分析，找出那些使用频度高、执行时间长的指令或指令串。对于使用频度高的指令，用硬件加快其执行；对于使用频度高的指令串，用一条新的指令来替代
  - 既能减少目标程序的执行时间，也能有效地缩短程序的长度
  - 可以从以下几个方面来改进：
    - 增强运算型指令的功能
    - 增强数据传送指令的功能
    - 增强程序控制指令的功能
- 面向高级语言的优化实现来改进指令系统
  - 增强对高级语言和编译器的支持
  - 高级语言计算机
  - 采用“比较简单的系统结构＋软件”的做法能够在较低成本和复杂度的前提下，提供更高的性能和灵活性
- 面向操作系统的优化实现改进指令系统
  - 操作系统和计算机系统结构是紧密联系的，操作系统的实现在很大程度上取决于系统结构的支持
  - 指令系统对操作系统的支持主要有：
    - 处理机工作状态和访问方式的切换
    - 进程的管理和切换
    - 存储管理和信息保护
    - 进程的同步与互斥，信号灯的管理等

沿RISC方向发展和改进指令系统

CISC指令系统结构存在的问题
- 各种指令的使用频度相差悬殊，许多指令很少用
- 指令系统庞大，指令条数很多，许多指令的功能又很复杂，使得控制器硬件非常复杂
- 许多指令由于操作繁杂，其CPI值比较大，执行速度慢，采用这些复杂指令有可能使整个程序的执行时间反而增加
- 由于指令功能复杂，规整性不好，不利于采用流水技术来提高性能
设计RISC机器遵循的原则
- 指令条数少、指令功能简单，只选取使用频度很高的指令，在此基础上补充一些最有用的指令
- 采用简单而又统一的指令格式，并减少寻址方式，指令字长都为32位或64位
- 指令的执行在单个机器周期内完成
- 只有load和store指令才能访问存储器，其它指令的操作都是在寄存器之间进行
- 大多数指令都采用硬连逻辑来实现
- 强调优化编译器的作用，为高级语言程序生成优化的代码
- 充分利用流水技术来提高性能
早期的RISC微处理器
- 1981年，Berkeley分校的Patterson等人的32位微处理器RISC I
- 1981年，Stanford大学Hennessy等人的MIPS
- IBM的801
- 共同特点：
  - 采用load-store结构
  - 指令字长为32位
  - 采用高效的流水技术

MIPS指令系统结构

MIPS的寄存器

32个64位通用寄存器（GPRs）
32个64位浮点数寄存器（FPRs）
一些特殊寄存器

MIPS的数据表示

MIPS的数据表示：整数、浮点数
字节、半字或者字在装入64位寄存器时，用零扩展或者用符号位扩展来填充该寄存器的剩余部分。装入以后，对它们将按照64位整数的方式进行运算

MIPS的数据寻址方式

立即数寻址与偏移量寻址
寄存器间接寻址是通过把0作为偏移量来实现的
16位绝对寻址是通过把R0（其值永远为0）作为基址寄存器来完成的
MIPS的存储器是按字节寻址的，地址为64位
所有存储器访问都必须是边界对齐的

MIPS的指令格式

寻址方式编码到操作码中
所有的指令都是32位的
操作码占6位
3种指令格式：I类指令、R类指令、J类指令

MIPS的操作

MIPS指令可以分为四大类：load和store、ALU操作、分支与跳转、浮点操作
符号的意义
load和store指令
ALU指令

MIPS的控制指令

由一组跳转和一组分支指令来实现控制流的改变
典型的MIPS控制指令
跳转指令
分支指令

MIPS的浮点操作

由操作码指出操作数是单精度（SP）或双精度（DP）
浮点操作
浮点数比较指令

存储系统

存储系统的层次架构

存储系统的层次结构概述

程序访问的局部性原理：程序访问的局部性原理是指，对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的
存储系统的多级层次架构

存储系统的性能参数

存储容量S
存储单位的平均每位价格C
命中率H
平均访存时间： $T=T_1+FT_M$ $T = T^{ 1 } + F T^{ M }$
1. 当命中时，访问时间即为 $T_1$ ，常称为命中时间
2. 当不命中时，访问时间为 $T_1+T_M$ ， $T_M$ 为不命中开销

三级存储系统

Cache-主存层次
主存-辅存层次
两者的比较

存储层次的4个问题

映像规则：当把一个块调入高一层存储器时，可以放到哪些位置上？
查找算法：当所要访问的块在高一级存储器中时，如何找到该块？
替换算法：当发生不命中而且高一层存储器已经满时，应替换哪一块？
写策略：当进行写访问时，应进行哪些操作？

Cache的基本知识

基本结构和原理

映像规则

全相联映像
直接映像
组相联映像

查找方法

替换算法

随机法(Random)
先进先出法(FIFO)
最近最少使用法(LRU)
Not Least Recently Used(NLRU)
Most Recently Used(MRU)

写策略

写命中
1. 写直达(Write Through)：在执行写操作时，不仅把数据写入Cache相应的块，而且也写入下一级存储器
2. 写回法(Write Back)：只把数据写入Cache中相应的块，不写入下一级存储器，只有在修改过的块被替换时，才会写回下一级存储器
写缺失
1. 按写分配法(Write Allocate)：写不命中时，先把所写单元所在的块从主存调入Cache，然后再进行写入
2. 不按写分配法(No-write Allocate)：写不命中时，直接写入下一级存储器而不将相应的块调入Cache

Cache性能分析

平均访存时间 = 命中时间 + 缺失率 × 不命中开销
CPU时间 = (CPU执行周期数 + 存储器停顿周期数) × 时钟周期时间 = IC × (CPI + 访存次数/指令数 × 缺失率 × 不命中开销) × 时钟周期时间

改进Cache性能

降低缺失率
减少不命中开销
减少命中时间

降低Cache的缺失率

三种类型的缺失

强制缺失：当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，也称为冷启动缺失
容量缺失：如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中
冲突缺失：在组相联或直接映像Cache中，若太多的块映像到同一组中，则会出现该组中某个块被别的块替换，然后又被重新访问的情况

增加Cache块大小

减少强制缺失
增加冲突缺失和不命中开销

增加Cache的容量

减少了容量缺失
增加成本和命中时间

提高相联度

减少冲突缺失
增加访存时间

伪相联Cache

首先按照与直接映像相同的方式进行访问，如果命中，则从相应的块中取出所访问的数据，如果缺失，检查Cache另一位置，看是否匹配，确定“另一块”的方法是将索引字段的最高位取反，按照新索引去寻找对应块
伪相联具有一快一慢两种命中时间，分别对应正常命中和伪命中的情况，这会使CPU流水线的设计复杂化，因此伪相联技术往往应用于离处理器较远的Cache上

硬件预取

指令和数据都可以在处理器提出访问请求之前进行预取，预取内容可以直接放入Cache中，也可以放在一个访问速度比主存快的外部缓冲器中

编译器控制的预取

按照预取数据所放的位置，可把预取分为以下两种类型：
- 寄存器预取
- Cache预取
按照预取的处理方式不同，可把预取分为以下两种：
- 故障性预取
- 非故障性预取

编译优化

内外循环交换
分块
数组合并

减少Cache的缺失开销

采用两级Cache

平均访存时间 = 命中时间L1 + 缺失率L1 × (命中时间L2 + 不命中率L2 × 不命中开销L2)
多级Cache包含性：包含/互斥

请求字处理技术

尽早重启动：在请求字没有到达时，CPU处于等待状态，一旦请求字到达，就立即发送给CPU，让等待的CPU尽早重启动，继续执行
关键字优先：调块时，让存储器首先提供CPU所要的请求字，请求字一旦到达，就立即发送给CPU，让CPU继续执行，同时从存储器调入该块的其余部分

读缺失优先于写缺失

在读缺失时检查写缓冲器的内容，如果没有冲突而且存储器可访问，就可继续处理读缺失，否则直接从缓冲器中读取数据

写缓冲合并

牺牲Cache

在Cache和其下一级存储器的数据通路上增设一个全相联的小Cache，存放因冲突而被替换出去的那些块，每当发生缺失时，在访问下一级存储器之前，先检查牺牲Cache中是否包含有所需的块，如果有，就将该块与Cache中的某个块交换，把所需的块调入Cache

减少命中时间

小而简单的Cache
避免地址变换
Cache访问流水化
踪迹Cache

并行主存系统

内存的组织

单体单字存储器

字长与CPU的字长相同
每一次只能访问一个存储字，假设该存储器的访问周期是T，字长为W位，则其带宽为B= $\frac{W}{T}$

单体多字存储器

一个单体m字存储器
B=m× $\frac{W}{T}$
并行访问存储器
- 方法：把L字W位的存储器改变成L/n字n×W位的存储器
- 逻辑实现：把地址码分成两个部分，一部分作为存储器的地址，另一部分负责选择数据
- 主要缺点：访问冲突大
  1. 取指令冲突(分支)
  2. 读操作数冲突
  3. 写数据冲突
  4. 读写冲突(读写同一存储字)

多体交叉存储器

多体交叉存储器：由多个单字存储体构成，每个体都有自己的地址寄存器以及地址译码和读/写驱动等电路
高位交叉访问存储器
- 主要目的：扩大存储器容量
- 实现方法：用地址码的高位部分区分存储体号
- 参数计算方法：
  - m：每个存储体的容量
  - n：总共的存储体个数
  - j：存储体的体内地址
  - k：存储体的体号
  - 存储器的地址：A=m×k+j
  - 存储器的体内地址： $A_j=A\ mod\ m$
  - 存储器的体号： $A_k=\lfloor\frac{A}{m}\rfloor$
低位交叉访问存储器
- 主要目的：提高存储器访问速度
- 实现方法：用地址码的低位部分区分存储体号
- 参数计算方法：
  - m：每个存储体的容量
  - n：总共的存储体个数
  - j：存储体的体内地址
  - k：存储体的体号
  - 存储器的地址：A=n×j+k
  - 存储器的体内地址： $A_j=\lfloor\frac{A}{n}\rfloor$
  - 存储器的体号： $A_k=A\ mod\ n$

无冲突访问存储器

一维数组(向量)的无冲突访问存储器
- 具体方法：存储体的个数取质数，且n≥向量长度
- 原因：变址位移量必然与存储体个数互质
二维数组的无冲突访问存储器
- 要求：一个n×n的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问
- 顺序存储：按列访问有冲突
- 错位存储：按对角线访问有冲突
- 并行存储体的个数m≥n，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素

虚拟存储器

虚拟存储器是“主存—辅存”层次进一步发展的结果
虚拟存储器可以分为两类：页式和段式
- 页式虚拟存储器把空间划分为大小相同的块(页面)
- 段式虚拟存储器则把空间划分为可变长的块(段)
快速地址转换技术
1. 地址变换缓冲器TLB
  - TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项
  - TLB中的内容是页表部分内容的一个副本
  - TLB利用了局部性原理
2. TLB中的项由两部分组成：标识和数据
  - 标识中存放的是虚地址的一部分
  - 数据部分存放的是物理页帧号、有效位、存储保护信息、使用位、修改位等
3. 一般TLB比Cache的标识存储器更小、更快

基本流水线技术

流水线工作原理

流水线锁存器

流水线的每一个阶段称为流水段，在每一个流水段的末尾或开头必须设置一个(多个)寄存器，称为流水寄存器，流水寄存器会增加每条指令的执行时间，但采用流水线之后整个程序的执行时间会缩短
流水线的表示方法
- 流水线的连接图表示方法：表示流水线的逻辑关系
- 流水线的时空图表示方法：表示流水线的时间关系
- 流水线的预约表表示方法
流水线的时空图
流水线的主要特点
- 只有连续提供同类任务才能充分发挥流水线的效率
- 在流水线的每一个流水段中都要设置一个流水锁存器
- 各流水段的时间应尽量相等

流水线的分类

线性流水线与非线性流水线
- 线性流水线：每一个流水段都流过一次，而且仅流过一次
- 非线性流水线：在流水线的某些流水段之间有反馈电路或前馈电路
按照流水线的级别来分
- 处理机级流水线，又称为指令流水线
- 部件级流水线(操作流水线)
- 处理机之间的流水线称为宏流水线，每个处理机对同一个数据流的不同部分分别进行处理
单功能流水线与多功能流水线
- 单功能流水线：只能完成一种固定功能的流水线
- 多功能流水线：流水线的各段通过不同的连接实现不同的功能
静态流水线与动态流水线
- 静态流水线：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能，只有连续出现同一种运算时，流水线的效率才能得到充分的发挥
- 动态流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能
流水线的其它分类方法
- 按照数据表示方式：标量流水线和向量流水线
- 按照控制方式：同步流水线和异步流水线

线性流水线的性能分析

吞吐率
- 计算流水线吞吐率的最基本公式： $TP=\frac{n}{T_k}$ ，其中n为任务数， $T_k$ 为完成n个任务所用的时间
- 各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为： $T_k=(k+n-1)\Delta t$ ，其中k为流水线的段数， $\Delta t$ 为时钟周期
  - 吞吐率为： $TP=\frac{n}{(k+n-1)\Delta t}$
  - 最大吞吐率为： $TP_{max}=\lim\limits_{n\rightarrow \infty}\frac{n}{(k+n-1)\Delta t}=\frac{1}{\Delta t}$
- 各段执行时间不等，输入连续任务情况下
  - 吞吐率为： $TP=\frac{n}{\sum\limits^k_{i=1}\Delta t_i+(n-1)max(\Delta t_1,\Delta t_2,..., \Delta t_k)}$
  - 最大吞吐率为： $TP=\frac{1}{max(\Delta t_1,\Delta t_2,...,\Delta t_k)}$
  - 流水线各段执行时间不相等的解决办法
    1. 将流水线的“瓶颈”部分再细分
    2. “瓶颈”流水段重复设置：增加分配器和收集器
加速比
- 计算流水线加速比的基本公式：S = 顺序执行时间T_0/流水线执行时间T_k
- 各段执行时间相等，输入连续任务情况下
  - 加速比为： $S=\frac{k\cdot n\cdot \Delta t}{(k+n-1)\Delta t}=\frac{k\cdot n}{k+n-1}$
  - 最大加速比为： $S_{max}=\lim\limits_{n \rightarrow \infty}\frac{k\cdot n}{k+n-1}=k$
- 各段执行时间不相等，输入连续任务情况下
  - 实际加速比为： $S=\frac{n\cdot\sum\limits^k_{i=1}\Delta t_i}{\sum\limits^k_{i=1}\Delta t_i+(n-1)\cdot max(\Delta t_1,\Delta t_2,...,\Delta t_k)}$
  - 当流水线段数增加时，需要连续输入的任务数也必须增加
效率
- 计算流水线效率的一般公式：E = n个任务占用的时空区/k个流水段的总的时空区 = $\frac{T_0}{k\cdot T_k}$
- 各流水段执行时间相等，输入n个连续任务
  - 流水线的效率为： $E=\frac{k\cdot n\cdot \Delta t}{k\cdot (k+n-1)\cdot\Delta t}=\frac{n}{k+n-1}$
  - 流水线的最高效率为： $E_{max}=\lim\limits_{n\rightarrow \infty}\frac{n}{k+n-1}=1$
- 各段流水线执行时间不等，输入n个连续任务
  - 流水线效率为： $E=\frac{n\cdot\sum\limits^k_{i=1}\Delta t_i}{k\cdot[\sum\limits^k_{i=1}\Delta t_i+(n-1)\cdot max(\Delta t_1,\Delta t_2,...,\Delta t_k)]}$
- 流水线各段的设备量或者各段的价格不相等时
  - 流水线效率为：E = n个任务占用的加权时空区/k个流水段的总的加权时空图
- 流水线的吞吐率、加速比与效率的关系
  - $E=TP\cdot \Delta t,\ S=k\cdot E$
流水线最佳段数的选择
- 流水线的总价格估计为：C=a+bk，其中a为所有功能段本身的总价格，b为每个锁存器的价格
- 使流水线的价格比PCR最大时：k= $\sqrt{\frac{a\cdot t}{b\cdot d}}$ ，其中d为流水线锁存器的延迟时间

非线性流水线的调度技术

非线性流水线调度的任务是要找出一个最小循环周期，按照这周期向流水线输入新任务，流水线各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高

1.非线性流水线的预约表表示方法

非线性流水线的冲突
- 流水线的启动距离：连续两个任务之间的时间间隔
- 流水线的冲突：几个任务争用同一个流水段
无冲突调度方法
- 非线性流水线的禁止启动集合F：预约表中每一行任意两个“×”之间的距离都计算出来，去掉重复的，上例中F={3，4，6}
- 由禁止启动集合得到冲突向量：C=( $C_mC_{m-1}... C_2C_1$ )，其中m是禁止集合中的最大值，如果i在禁止集合F中，则 $C_i=1$ ，否则 $C_i=0$ ，上例中C=(101100)
- 由冲突向量构造状态图：把冲突向量送入一个m位逻辑右移移位器，如果移位器移出0，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；否则不作任何处理；如此重复m次。对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理
- 简单循环：状态图中各种冲突向量只经过一次的启动循环
优化调度方法
- 流水线最小平均启动距离的限制范围
  1. 下限是预约表中任意一行里“×”的最多个数
  2. 小于或等于状态图中任意一个简单循环的平均启动距离
  3. 最小平均启动距离的上限是冲突向量中1的个数再加上1
- 采用预留算法来调度非线性流水线，可以达到最优调度
  1. 确定最小平均启动距离(MAL)：预约表任一行中“×”的最多个数
  2. 确定最小启动循环，一般恒定循环作为最小启动循环
  3. 通过插入非计算延迟段——修改预约表实现最小启动循环

高级流水线

超标量流水线

多条指令流水线
超标量处理机：一个时钟周期能同时发射多条指令的处理机
超标量处理机的指令并行度(ILP)大于1<ILP<m，m为每个周期发射的指令条数

目前的指令调度技术，每个周期发射2至4条指令比较合理
先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突检测
多流水线的调度主要有三种方法
1. 顺序发射顺序完成
2. 顺序发射乱序完成
3. 乱序发射乱序完成
普通标量处理机，希望相同操作连续出现；超标量处理机则正好相反，希望相同操作不要连续出现，这种要求正好符合一般标量程序的特点
超标量处理机性能
- 在每个周期发射m条指令的超标量处理机上执行的时间为： $T(m,1)=(k+\frac{N-m}{m})\Delta t$
- 超标量处理机相对于单流水线标量处理机的加速比为： $S(m,1)=\frac{T(1,1)}{T(m,1)}=\frac{m(k+N+1)}{N+m(k-1)}$
- 超标量处理机的加速比的最大值为： $S(m,1)_{max}=m$

超流水线

超流水线处理机
- 两种定义
  - 在一个周期内能够分时发射多条指令的处理机
  - 指令流水线的功能段数为8段或超过8段的流水线处理机
- 提高处理机性能的不同方法
  - 超标量处理机：通过增加硬件资源来提高处理及性能
  - 超流水线处理机：通过各部分硬件的重叠工作来提高处理机性能
- 两种不同并行性
  - 超标量处理机采用的是空间并行性
  - 超流水线处理机采用的是时间并行性
指令执行时序
- 每隔1/n个时钟周期发射一条指令
- 在超标量处理机中，流水线的有些功能段还可以进一步细分
超流水线处理机性能
- 指令级并行度(1,n)的超流水线处理机，执行N条指令所用的时间为： $T(1,n)=(k+\frac{N-1}{n})\Delta t$
- 超流水线处理机相对于单流水线普通标量处理机的加速比为： $S(1,n)=\frac{T(1,1)}{T(1,n)}=\frac{n(k+N-1)}{nk+N-1}$

超标量超流水线

把超标量与超流水线技术结合在一起，就成为超标量超流水线处理机
超标量超流水线处理机在一个时钟周期内分时发射指令n次，每次同时发射m条
超标量超流水线处理机每个时钟周期总共发射指令mn条

超标量处理机性能
- 指令级并行度为(m,n)的超标量超流水线处理机，连续执行N条指令所需要的时间为： $T(m,n)=(k+\frac{N-m}{m\cdot n})\Delta t$
- 超标量超流水线处理机相对于单流水线标量处理机的加速比为： $S(m,n)=\frac{S(1,1)}{S(m,n)}=\frac{m\cdot n\cdot (k+N-1)}{m\cdot n\cdot k+N-m}$
- 理想情况下，超标量超流水线处理机加速比的最大值为： $S(m,n)_{max}=mn$

指令级并行及其开发——硬件方法

指令级并行的概念

指令级并行：指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令
开发ILP的方法可以分为两大类
- 主要基于硬件的动态开发方法
- 基于软件的静态开发方法
流水线处理机的实际CPI
- 理想流水线的CPI加上各类停顿的时钟周期数：CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿_控制冲突
- IPC：每个时钟周期完成的指令条数
基本程序块：一串连续的代码除了入口和出口以外，没有其它的分支指令和转入点
循环级并行：使一个循环中的不同循环体并行执行，开发循环的不同迭代之间存在的并行性
最基本的开发循环级并行的技术：循环展开技术、采用向量指令和数据向量表示

指令的动态调度

静态调度
- 依靠编译器对代码进行静态调度，以减少相关和冲突
- 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化
- 通过把相关的指令拉开距离来减少可能产生的停顿
动态调度
- 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿
- 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器
- 能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行
- 以硬件复杂性的显著增加为代价

动态调度的基本思想

到目前为止我们所使用流水线的最大的局限性：指令是按序发射和按序执行的
将5段流水线的译码阶段再分为两个阶段：
- 发射：指令译码，检测是否存在结构冲突
- 读操作数：等待数据冲突消失，然后读操作数
动态调度的流水线支持多条指令同时处于执行当中
- 要求：具有多个功能部件、或者功能部件流水化、或者兼而有之
指令乱序完成带来的最大问题：中断处理比较复杂
- 动态调度的处理机要保持正确的中断行为：对于一条会产生中断的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生中断
- 即使保持了正确的中断行为，动态调度处理机仍可能发生不精确中断：当执行指令i导致发生中断时，处理机的现场(状态)与严格按程序顺序执行时指令i的现场不同
- 发生不精确中断的原因：当发生中断(设为指令i)时，流水线可能已经执行完按程序顺序是位于指令i之后的指令，或流水线可能还没完成按程序顺序是指令i之前的指令

记分牌动态调度算法

基本思想
- 该机器用一个称为记分牌的硬件实现了对指令的动态调度
- 该硬件中维护着3张表，分别用于记录指令的执行状态、功能部件状态、寄存器状态以及数据相关关系等
- 它把前述5段流水线中的译码段ID分解成了两个段：发射和读操作数，以避免当某条指令在ID段被停顿时挡住后面无关指令的流动
- 没有Cache，没有采用Forwarding技术
记分牌的目标：在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令
每条指令的执行过程分为4段(主要考虑浮点操作)
- 发射：如果当前指令所需的功能部件空闲，并且所有其它正在执行的指令的目的寄存器与该指令的不同，记分牌就向功能部件发射该指令，并修改记分牌内部的记录表(解决WAW冲突)
- 读操作数：记分牌监测源操作数的可用性，如果数据可用，它就通知功能部件从寄存器中读出源操作数并开始执行(解决RAW冲突)
- 执行：取到操作数后，功能部件开始执行，当产生出结果后，就通知记分牌它已经完成执行，在浮点流水线中，这一段可能要占用多个时钟周期
- 写结果：记分牌一旦知道执行部件完成了执行，就检测是否存在WAR冲突，如果不存在，或者原有的WAR冲突已消失，记分牌就通知功能部件把结果写入目的寄存器，并释放该指令使用的所有资源；如果检测到WAR冲突，就不允许该指令将结果写到目的寄存器，记分牌必须等待，直到该冲突消失
记分牌中记录的信息由3部分构成
- 指令状态表：记录正在执行的各条指令已经进入到了哪一段
- 功能部件状态表：记录各个功能部件的状态，每个功能部件有一项，每一项由以下9个字段组成：
  - Busy：忙标志，指出功能部件是否忙，初值为“no”
  - Op：该功能部件正在执行或将要执行的操作
  - Fi：目的寄存器编号
  - Fj，Fk：源寄存器编号
  - Qj，Qk：指出向源寄存器Fj、Fk写数据的功能部件
  - Rj，Rk：标志位，为“yes”表示Fj，Fk中的操作数就绪且还未被取走，否则就被置为“no”
- 结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能部件(编号)将把结果写入该寄存器，如果当前正在运行的指令都不以它为目的寄存器，则其相应项置为“no”，Result各项的初值为“no”(全0)
记分牌的性能受限于以下几个方面
- 程序代码中可开发的并行性，即是否存在可以并行执行的不相关的指令
- 记分牌的容量，记分牌的容量决定了流水线能在多大范围内寻找不相关指令，流水线中可以同时容纳的指令数量称为指令窗口
- 功能部件的数目和种类，功能部件的总数决定了结构冲突的严重程度
- 反相关和输出相关，它们引起计分牌中WAR和WAW冲突

Tomasulo算法

核心思想
- 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小
- 通过寄存器重命名来消除WAR冲突和WAW冲突
保留站
- 每个保留站中保存一条已经发射并等待到本功能部件执行的指令(相关信息)：包括：操作码、操作数以及用于检测和解决冲突的信息
- 在一条指令发射到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中；如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识
- 每个保留站都有一个标识字段，唯一地标识了该保留站
公共数据总线CDB
- 所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到(播送到)各个需要该结果的地方
- 在具有多个执行部件且采用多发射(即每个时钟周期发射多条指令)的流水线中，需要采用多条CDB
load缓冲器和store缓冲器
- 存放读/写存储器的数据或地址
- load缓冲器的作用有3个：
  - 存放用于计算有效地址的分量
  - 记录正在进行的load访存，等待存储器的响应
  - 保存已经完成了的load的结果(即从存储器取来的数据)，等待CDB传输
- store缓冲器的作用有3个：
  - 存放用于计算有效地址的分量
  - 保存正在进行的store访存的目标地址，该store正在等待存储数据的到达
  - 保存该store的地址和数据，直到存储部件接收
浮点寄存器FP
- 共有16个浮点寄存器：F0，F2，F4，…，F30
- 它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器
指令队列
- 指令部件送来的指令放入指令队列
- 指令队列中的指令按先进先出的顺序发射
运算部件
- 浮点加法器完成加法和减法操作
- 浮点乘法器完成乘法和除法操作
在Toamsulo算法中，寄存器重命名是通过保留站和发射逻辑来共同完成的
- 当指令发射时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号重命名为将产生这个操作数的保留站的标识
- 指令发射到保留站后，其操作数寄存器号或者换成了数据本身(如果该数据已经就绪)，或者换成了保留站的标识，不再与寄存器有关系
Tomasulo算法具有以下两个特点
- 冲突检测和指令执行控制是分布的，每个功能部件的保留站中的信息决定了什么时候
- 指令可以在该功能部件开始执行，计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器
指令执行的步骤：使用Tomasulo算法的流水线需3段
- 发射：从指令队列的头部取一条指令
  - 如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站(设为r)
  - 如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站r
  - 如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站r
  - 一旦被记录的保留站完成计算，它将直接把数据送给保留站r(消除WAR冲突)
  - 完成对目标寄存器的预约工作(消除WAW冲突)
  - 如果没有空闲的保留站，指令就不能发射(结构冲突)
- 执行：当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作
- 写结果：功能部件计算完毕后，就将计算结果放到CDB上，所有等待该计算结果的寄存器和保留站(包括store缓冲器)都同时从CDB上获得所需要的数据
每个保留站有以下7个字段
- Qp：要对源操作数进行的操作
- Qj，Qk：将产生源操作数的保留站号，等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数
- Vj，Vk：对于每一个操作数来说，V或Q字段只有一个有效；对于load来说，Vk字段用于保存偏移量
- Busy：为“yes”表示本保留站或缓冲单元“忙”
- A：仅load和store缓冲器有该字段，开始是存放指令中的立即数字段，地址计算后存放有效地址
- Qi：寄存器状态表，每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号，为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪

动态分支预测技术

分支预测技术

软件方法
- 总是taken/not taken
- 基于操作码Opcode
- 基于偏移量(forward not taken，backward taken)
- 编译指导
硬件方法：动态分支预测

分支预测错误代价

在预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令
最大代价：~进入流水线循环长度 × 流水线宽度

减少分支预测错误代价的手段

软件
- 减少分支：循环展开
- 提前形成条件码
- 延迟转移
硬件
- 延迟转移
- 前瞻执行

动态分支预测

动态分支预测：在程序运行时，根据分支指令过去的表现来预测其将来的行为
- 如果分支行为发生了变化，预测结果也跟着改变
- 有更好的预测准确度和适应性
分支预测的有效性取决于
- 预测的准确性
- 预测正确和不正确两种情况下的分支开销
  - 决定分支开销的因素
    - 流水线的结构
    - 预测的方法
    - 预测错误时的恢复策略等
采用动态分支预测技术的目的
- 预测分支是否成功
- 尽快找到分支目标地址(或指令)
需要解决的关键问题
- 如何记录分支的历史信息，要记录哪些信息
- 如何根据这些信息来预测分支的去向，甚至提前取出分支目标处的指令

动态分支预测模型

采用分支历史表BHT
- 分支历史表BHT
  - 最简单的动态分支预测方法
  - 用BHT来记录分支指令最近一次或几次的执行情况(成功还是失败)，并据此进行预测
- 只有1个预测位的分支预测：记录分支指令最近一次的历史，BHT中只需要1位二进制位(最简单)
- 采用2位移位器
- 采用2位饱和计数器
- 两位分支预测中的操作有两个步骤
  - 分支预测
  - 状态修改
- BHT方法只在以下情况下才有用：判定分支是否成功所需的时间＞确定分支目标地址所需的时间
- BHT可以跟分支指令一起存放在指令Cache中，也可以用一块专门的硬件来实现
采用分支目标缓冲器BTB
- 目标：将分支的开销降为0
- 方法：分支目标缓冲
  - 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识
  - 这个缓冲区就是分支目标缓冲器，简记为BTB，或者分支目标Cache
- 看成是专门的硬件实现的一张表格，表格中的每一项至少有两个字段
  - 执行过的成功分支指令的地址
  - 预测的分支目标地址
- 采用BTB后，在流水线各个阶段所进行的相关操作
- 采用BTB后，各种可能情况下的延迟
- BTB的另一种形式
  - 在分支目标缓冲器中增设一个至少是两位的“分支历史表”字段
  - 更进一步，在表中对于每条分支指令都存放若干条分支指令目标处的指令，就形成了分支目标指令缓冲器
基于硬件的前瞻执行
- 前瞻执行的基本思想：对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、发射和执行后续的指令，只是执行指令的结果不是写回到寄存器或存储器，而是写入一个称为重定位缓冲器ROB中，等到相应的指令得到“确认提交”(即确实是应该执行的)之后，才将结果写入寄存器或存储器
- 基于硬件的前瞻执行结合了3种思想
  - 动态分支预测，用来选择后续执行的指令
  - 在控制相关的结果尚未出来之前，前瞻地执行后续指令
  - 用动态调度对基本块的各种组合进行跨基本块调度
- 对Tomasulo算法加以扩充，就可以支持前瞻执行：把Tomasulo算法的写结果和指令完成加以区分，分成两个不同的段
  - 写结果
    - 把前瞻执行的结果写到ROB中
    - 通过CDB在指令之间传送结果，供需要用到这些结果的指令使用
  - 指令提交：在分支指令的结果出来后，对相应指令的前瞻执行给予确认提交
    - 如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器
    - 如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执行

控制相关的动态解决技术

控制相关：由条件转移或程序中断引起的相关，也称全局相关，控制相关对流水线的吞吐率和效率影响相对于数据相关要大得多
- 条件指令在一般程序中所占的比例相当大
- 中断虽然在程序中所占的比例不大，但中断发生在程序中的哪一条指令，发生在一条指令执行过程中的哪一个功能段都是不确定的
处理好条件转移和中断引起的控制相关是很重要的
关键问题
- 要确保流水线能够正常工作
- 减少因断流引起的吞吐率和效率的下降

硬件支持精确中断/例外与分支预测

Issue：如果RS和ROB有空闲单元就发射指令，如果寄存器或ROB中源操作数可用，就将其发送到RS，目的地址的ROB编号也发送给RS，否则，指令发射停顿
Execution：当操作数就绪后，开始执行，如果没有就绪，监测CDB，检查RAW相关
Write result：将运算结果通过CDB传送给所有等待结果的FU以及ROB单元，标记RS可用
Commit：按ROB表中顺序，如果结果已有，就更新寄存器(或存储器)，并将该指令从ROB表中删除，预测失败或有中断时，刷新ROB

多指令发射技术

在每个时钟周期内发射多条指令，CPI < 1

多发射处理机有两种基本风格
- 超标量
  - 在每个时钟周期发射的指令条数不固定，依代码的具体情况而定(有上限)
  - 设这个上限为n，就称该处理机为n-发射
  - 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度
- 超长指令字VLIW
  - 在每个时钟周期发射的指令条数是固定的，这些指令构成一条长指令或者一个指令包
  - 指令包中，指令之间的并行性是通过指令显式地表示出来的
  - 指令调度是由编译器静态完成的
超标量处理机与VLIW处理机相比有两个优点
- 超标量结构对程序员是透明的，处理机能自己检测下一条指令能否发射，不需要由编译器或专门的变换程序对程序中的指令进行重新排列
- 即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，当然运行的效果不会很好

基于静态调度的多发射技术

在典型的超标量处理器中，每个时钟周期可发射1到8条指令
指令按序发射，在发射时进行冲突检测，由硬件检测当前发射的指令之间是否存在冲突以及当前发射的指令与正在执行的指令是否有冲突

基于动态调度的多发射技术

扩展Tomasulo算法：支持双发射超标量流水线
- 每个时钟周期发射两条指令
- 一条是整数指令，另一条是浮点指令
采用一种比较简单的方法
- 指令按顺序流向保留站，否则会破坏语义
- 将整数所用的表结构与浮点用的表结构分离开，分别进行处理，这样就可以同时地发射一条浮点指令和一条整数指令到各自的保留站
上述双发射动态调度流水线的性能受限于以下3个因素
- 整数部件和浮点部件的工作负载不平衡，没有充分发挥出浮点部件的作用
- 每个循环叠代中的控制开销太大
- 控制相关使得处理机必须等到分支指令的结果出来后才能开始下一条L.D指令的执行

超长指令字技术

把能并行执行的多条指令组装成一条很长的指令
设置多个功能部件
指令字被分割成一些字段，每个字段称为一个操作槽，直接独立地控制一个功能部件
在VLIW处理机中，在指令发射时不需要进行复杂的冲突检测，而是依靠编译器全部安排好了
VLIW存在的一些问题
- 程序代码长度增加了
  - 提高并行性而进行的大量的循环展开
  - 指令字中的操作槽并非总能填满
  - 解决：采用指令共享立即数字段的方法，或者采用指令压缩存储、调入Cache或译码时展开的方法
- 采用了锁步机制：任何一个操作部件出现停顿时，整个处理机都要停顿
- 机器代码兼容性不好

多发射处理器受到的限制

主要受以下3个方面的影响
- 程序所固有的指令级并行性
- 硬件实现上的困难
- 超标量和超长指令字处理器固有的技术限制

指令级并行的开发——软件方法

基本指令调度及循环展开

指令调度的基本方法

指令调度：找出不相关的指令序列，让它们在流水线上重叠并行执行
制约编译器指令调度的因素
- 程序固有的指令级并行
- 流水线功能部件的延迟

循环展开

循环展开
- 把循环体的代码复制多次并按顺序排放，然后相应调整循环的结束条件
- 开发循环级并行的有效方法
循环展开的注意事项
- 保证正确性(循环控制、偏移量)
- 注意有效性(循环体之间无关)
- 使用不同的寄存器
- 删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正
- 注意对存储器数据的相关性分析
- 注意新的相关性

跨越基本块的静态指令调度

全局指令调度

概述
- 目标：在保持原有数据相关和控制相关不变的前提下，尽可能地缩短包含分支结构的代码段的总执行时间
- 基本思想：在循环体内的多个基本块间移动指令，扩大那些执行频率较高的基本块的体积

多指令发射

超标量流水线的静态调度——循环展开

静态多指令发射技术：VLIW技术

VLIW vs. 超标量
- 在动态调度的超标量处理器中，相关检测和指令调度基本都由硬件完成
- 在静态调度的超标量处理器中，部分相关检测和指令调度工作交由编译器完成
- 在VLIW处理器中，相关检测和指令调度工作全部由编译器完成，它需要更“智能”的编译器

显示并行指令计算EPIC

什么是EPIC

指令级并行主要由编译器负责开发，处理器为保证代码正确执行提供必要的硬件支持，只有在这些硬件机制的辅助下这些优化技术才能高效完成
系统结构必须提供某种通信机制，使得流水线硬件能够了解编译器“安排”好的指令执行顺序

EPIC编译器的高级优化技术

非绑定分支
谓词执行
前瞻执行

开发更多的指令级并行

循环携带相关

循环携带相关是指一个循环的某个叠代中的指令与其他叠代中的指令之间的数据相关

软件流水

软流水技术的核心思想是从循环不同的叠代中抽取一部分指令(循环控制指令除外)拼成一个新的循环叠代
目的
- 将同一叠代中的相关指令分布到不同的叠代中
- 将不同叠代中的相关指令封装到同一叠代中

软件流水 vs. 循环展开
- 循环展开主要减少由分支指令和修改循环索引变量的指令所引起的循环控制开销
- 软流水使叠代内的指令级并行达到最大

向量处理机

向量处理概念

向量由一组有序、具有相同类型和位数的元素组成
在流水线处理机中，设置向量数据表示和相应的向量指令，称为向量处理机
不具有向量数据表示和相应的向量指令的流水线处理机，称为标量处理机

向量指令集的优点
- 精简
- 表示能力强，告诉硬件 N 个操作
- 可扩展
向量与标量性能的平衡
- 实际的应用问题中通常既有向量计算又有标量计算，而且两类计算有一定的比例
- 向量平衡点：为了使向量硬件设备和标量硬件设备的利用率相等，一个程序中向量代码所占的百分比
- 向量平衡点必须与用户程序的向量化程度相匹配

向量数据表示

向量处理机是解决数值计算问题的一种高性能计算机结构
向量处理机一般都采用流水线结构，有多条流水线并行工作
向量处理机通常属大型或巨型机，也可以用微机加一台向量协处理器组成
一般向量计算机中包括有一台高性能标量处理机
必须把问题转化为向量运算，向量处理机才能发挥作用

等间距向量表示法

三个参数表示一个等间距向量
- 向量起始地址：A
- 向量长度：L
- 向量间距：f

带位移量的向量表示法

用三个参数表示一个向量
- 向量基地址：A
- 向量长度：L
- 向量位移量：f
向量有效长度：L－f ，向量起始地址：A＋f
优点：每个向量可以带有位移，通过控制向量实现可变增量，能够表示稀疏向量

稀疏向量表示法

定义：0元素很多，非0元素很少的向量称为稀疏向量
采用压缩方法存储稀疏向量可以节省存储空间
可以还原之后进行运算，也可以用压缩方法直接进行运算

向量处理方式

横向(水平)处理方式

向量计算是按行的方式从左到右横向地进行
不适合于向量处理机的并行处理

纵向(垂直)处理方式

向量计算是按列的方式从上到下纵向地进行

纵横处理方式

又称为分组处理方式
把向量分成若干组，组内按纵向方式处理，依次处理各组

向量处理机结构

向量处理机的结构因具体机器不同而不同，由所采用的向量处理方式决定
有两种典型的结构
- 存储器-存储器型结构：纵向处理方式采用，向量长度不受限制
- 寄存器-寄存器型结构：分组处理方式采用，速度快

“存储器-存储器”结构

采用纵向处理方式的向量处理机对处理机结构的要求
- 向量指令的源向量和目的向量都是存放在存储器中，运算的中间结果需要送回存储器
- 流水线运算部件的输入和输出端都直接(或经过缓冲器)与存储器相联，从而构成存储器-存储器型操作的运算流水线
要充分发挥这种结构的流水线效率，存储器要不断地提供源操作数，并不断地从运算部件接收结果(每拍从存储器读取两个数据，并向存储器写回一个结果)
- 对存储器的带宽以及存储器与处理部件的通信带宽提出了非常高的要求
- 解决方法：一般是通过采用多体交叉并行存储器和缓冲器技术

“寄存器-寄存器”结构

在向量的分组处理方式中，对向量长度N没有限制，但组的长度n却是固定不变的
设置能快速访问的向量寄存器，用于存放源向量、目的向量及中间结果，让运算部件的输入、输出端都与向量寄存器相联，就构成了“寄存器－寄存器”型操作的运算流水线

只要不出现Vi冲突和功能部件冲突，各Vi之间和各功能部件之间都能并行工作，大大加快了向量指令的处理
- Vi冲突：并行工作的各向量指令的源向量或结果向量使用了相同的Vi
- 功能部件冲突：并行工作的各向量指令要使用同一个功能部件

提高向量处理机性能的常用技术

设置多个功能部件

设置多个独立的功能部件，这些部件能并行工作，并各自按流水方式工作，从而形成了多条并行工作的运算操作流水线

向量链接技术

两条向量指令占用功能流水线和向量寄存器的4种情况
- 指令不相关
- 功能部件冲突
- 源寄存器冲突
- 结果寄存器冲突
当前一条指令的结果寄存器是后一条指令的源寄存器、且不存在任何其他冲突时，就可以用链接技术来提高性能
向量流水线链接：具有先写后读相关的两条指令，在不出现功能部件冲突和源向量冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的

进行向量链接的要求：保证无向量寄存器冲突和无功能部件冲突
- 只有在前一条指令的第一个结果元素送入结果向量寄存器的那一个时钟周期才可以进行链接
- 当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时，要求先行的两条指令产生运算结果的时间必须相等，即要求有关功能部件的通过时间相等
- 要进行链接执行的向量指令的向量长度必须相等，否则无法进行链接

分段开采技术

当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段
由系统硬件和软件控制完成，对程序员是透明的

采用多处理机系统

许多新型向量处理机系统采用了多处理机系统结构

向量处理机的性能评价

向量指令的处理时间

执行一条向量长度为n的向量指令所需的时间为： $T_{vp}=T_s+T_e+(n-1)T_c$
- Ts：向量处理部件流水线的建立时间(向量启动时间)
  - 为了使处理部件流水线能开始工作(即开始流入数据)所需要的准备时间
  - 向量的启动延迟
    - 功能部件延迟
    - Dead Time
- Te：向量流水线的通过时间
  - 第一对向量元素通过流水线并产生第一个结果所获的时间
- Tc：流水线的时钟周期时间
把上式中的参数都折算成时钟周期个数： $T_{vp}=[s+e+(n-1)]T_c$ $T^{ v p } = [s + e + (n - 1)] T^{ c }$
- s：Ts所对应的时钟周期数
- e：Te所对应的时钟周期数
不考虑Ts，并令 $T_{start}$ $T^{ s t a r t }$ =e-1，则 $T_{vp}=(T_{start}+n)T_c$ $T^{ v p } = (T^{ s t a r t } + n) T^{ c }$
- $T_{start}$ ：从一条向量指令开始执行到还差一个时钟周期就产生第一个结果所需的时钟周期数，可称之为该向量指令的启动时间，此后，便是每个时钟周期流出一个结果，共有n个结果
一组向量指令的处理时间
- 对于一组向量指令而言，其执行时间主要取决于三个因素：
  - 向量的长度
  - 向量操作之间是否存在流水功能部件的使用冲突
  - 数据的相关性
- 把能在同一个时钟周期内一起开始执行的几条向量指令称为一个编队
- 可以看出：同一个编队中的向量指令之间一定不存在流水向量功能部件的冲突和数据的冲突
- 编队后，这个向量指令序列的总的执行时间为各编队的执行时间的和： $T_{all}=\sum\limits^m_{i=1}T_{vp}^{(i)}$ $T^{ a l l } = i = 1 \sum m T^{ v p (i) }$
  - $T_{vp}^{(i)}$ ：第i个编队的执行时间
  - m：编队的个数
- 当一个编队是由若干条指令组成时，其执行时间就应该由该编队中各指令的执行时间的最大值来确定
- $T_{all}=\sum\limits^m_{i=1}T_{vp}^{(i)}=\sum\limits_{i=1}^m(T_{start}^{(i)}+n)T_c=(T_{start}+mn)T_c$ $T^{ a l l } = i = 1 \sum m T^{ v p (i) } = i = 1 \sum m (T^{ s t a r t (i) } + n) T^{ c } = (T^{ s t a r t } + m n) T^{ c }$
  - $T_{start}^{(i)}$ ：第i编队中各指令的启动时间的最大值
  - $T_{start}=\sum\limits^m_{i=1}T_{start}^{(i)}$ ：该组指令总的启动时间(时钟周期个数)
- 表示成时钟周期个数： $T_{all}=T_{start}+mn$ (拍)

最大性能 $R_{\infty}$ 和半性能向量长度 $n_{\frac12}$

向量处理机的峰值性能 $R_{\infty}$ $R^{ \infty }$
- $R_{\infty}$ 表示当向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能
- $R_{\infty}=\lim\limits_{n\rightarrow\infty}$ 向量指令序列中浮点运算次数 × 时钟频率 / 向量指令序列执行所需的时钟周期数
半性能向量长度 $n_{\frac12}$ $n^{ \frac{ 1 }{ 2 } }$
- 半性能向量长度 $n_{\frac12}$ 是指向量处理机的性能为其最大性能的一半时所需的向量长度
- 评价向量流水线的建立时间对性能影响的重要参数
向量长度临界值 $n_v$ $n^{ v }$
- 向量长度临界值 $n_v$ 是指：对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度

向量处理机的发展

向量计算机系统结构的发展趋势是
1. 提供多种向量运算指令
2. 除具有向量处理功能外还有其它功能
3. 采用多层次的存储器系统
4. 流水线技术与并行技术相结合
向量计算机系统结构要解决的六个技术问题
1. 处理机带宽
2. 存储器带宽
3. 输入输出带宽
4. 通信带宽
5. 同步系统
6. 多用途