笔记

计算机系统结构的基本概念

引言

系统结构的转折

从单纯依靠指令级并行转向开发线程级并行和数据级并行

计算机系统结构在计算机的发展种有着极其重要的作用

计算机系统结构的概念

计算机系统的层次结构

计算机系统=硬件/固件 + 软件

计算机语言从低级向高级发展

高一级语言的语句相对于低一级语言来说功能更强更便于应用,但以低级语言为基础

从计算机语言的角度,把计算机系统按功能划分成 多级层次结构

每一层以一种语言为特征

虚拟机 由软件实现的机器

语言实现的两种基本技术

翻译 先把N+1 级程序全部转换成N级程序后,再去执行新产生的N级程序,再执行过程中N+1级程序不再被访问

解释 每当一条N+1 级指令被译码后,就直接执行一串等效的N级指令,然后再去取下一条N+1级的指令,以此重复进行

解释执行比编译后执行所花的时间多,但占用的存储空间较少

计算机系统结构的定义

1 计算机系统结构的经典定义

2程序员所看到的计算机属性,即概念性结构与功能特性

按照计算机系统的多级层次结构,不同级程序员所看到的计算机具有不同的属性

3 透明性

在计算机技术中,把这种本来存在的事物或属性,但从某种角度又好像不存在的概念称为透明性

4 Amdahl 提出的系统结构

传统机器语言机程序员所看到的计算机属性

5 广义的系统结构定义 指令集结构,组成,硬件

6 对于通用寄存器型寄存器机器来说,这些属性主要是指

  • 指令系统

包括机器指令的操作类型和格式,指令间的排序和控制机构等

  • 数据表示

硬件能直接识别和处理的数据类型

  • 寻址规则
  • 包括最小寻址单元,寻址方式及其表示
  • 寄存器定义
  • 中断系统
  • 机器工作状态的定义和切换
  • 存储系统
  • 信息保护
  • I/O结构

计算机系统结构概念的实质

确定计算机系统中软硬件的界面,界面之上时软件实现的功能,界面之下时硬件和固件实现的功能

计算机组成和计算机实现

1 计算机系统结构 计算机系统的软,硬件的界面

即机器语言程序员所看到的传统机器级所具有的属性

2计算机组成 计算机系统结构的逻辑实现

包含物理机器级中的数据流和控制流的组成以及逻辑设计等

着眼于: 物理机器级内各事件的排序方式与控制方式,各部件的功能以及各部件之间的联系

3计算机实现 计算机组成的物理实现

包括部件的物理结构,器件的集成度和速度,模块,插件,底板的划分与连接,信号传输,电源,冷却及整机装配技术等

着眼于: 器件技术(主导作用),微组装技术

一种体系结构可以有多种组成

一种组成可以有多种物理实现

4 系列机

计算机系统结构的分类

常见的计算机系统接哦古分类方法有两种

Flynn分类法,冯氏分类法

1 冯氏分类法

用系统的最大并行度对计算机进行分类

最大并行度 计算机系统在单位时间内能够处理的最大的二进制位数

用平面直角坐标系中的一个点表示一个计算机系统,其横坐标表示字宽(n位),纵坐标表示一次能同时处理的字数(m字)。$m \times n$ 表示其最大并行度

2 Flynn 分类法

按照指令流和数据流的多倍型进行分类

指令流 计算机执行的指令序列

数据流 由指令流调用的数据序列

多倍性 在系统受限的部件上,同时处于同一执行阶段的指令或数据的最大数目

Flynn 分类法把计算机系统的结构分为4类

单指令流单数据流(SISD)

单指令流多数据流(SIMD)

多指令流单数据流(MISD)

多指令流多数据流(MIMD)

IS 指令流, DS 数据流 , CS 控制流

CU 控制部件,PU 处理部件, MM,SM 存储器

image-20200223195955756

定量分析技术

1 计算机系统设计的定量原理

4 个定量原理

1 以经常性事件为重点

对经常发生的情况采用优化方法的原则进行选择,以得到更多的总体上的改进

优化是指分配更多的资源,达到更高的性能或者分配更多的资源等

2 Amdahl 定律

加快某部件执行速度所能获得的系统性能加速比,受限于该部件的执行时间占系统总执行时间的百分比

加速比依赖于两个因素

可改进比例 在改进前的系统中,可改进部分的执行在总的执行时间中所占的比例

它总是小于等于1

部件加速比 可改进部分改进以后性能提升的被数

它是改进前所需的执行时间与改进后执行时间的比

一般情况部件加速比是大于1的

系统加速比为改进前与改进后总执行时间之比

Amdahl 定律 一种性能改进的递减规则

如果仅仅对计算任务中的一部分做性能改进,则改进得越多,所得到得总性能得提升就越有限

如果只针对整个任务得一部分进行改进和优化,那么所获得得加速比不超过$\frac{1}{1-可改进比例}$

3 CPU 性能公式

执行一个程序所需得CPU时间

CPU时间=执行程序所需要得时钟周期数$\times$ 时钟周期时间

每条指令执行得平均时钟周期数CPI

CPI = 执行程序所需要得时钟周期数/IC

IC 所执行得指令条数

程序执行的CPU时间可以写成

CPU时间=IC$\times$CPI$\times$时钟周期数

CPU的性能取决于三个参数

时钟周期时间 取决硬件实现技术和计算机组成

CPI 取决于计算机组成和指令集结构

IC 取决于指令集结构和编译技术

局部性原理

时间局部性

空间局部性

部分题目

image-20200224110017184

image-20200224110048138

image-20200224110116017

计算机系统结构的发展

冯 $\cdot$诺伊曼结构

最早的存储程序式计算机于1946年提出来的,它由运算器,控制器,存储器,输入设备,输出设备5部分构成,通常称之为冯$\cdot$ 诺伊曼结构计算机

存储程序原理的基本点时指令驱动,程序预先放在计算机存储器中。

主要特点

  • 计算机以运算器为中心,输入/输出设备与存储器之间的数据传送都经过运算器;存储器,输入/输出设备的操作以及它们之间的联系都由控制器集中控制。
  • 在存储器中,指令和数据同等对待,指令和数据一样可以进行运算
  • 存储器时按地址访问,按顺序先性编址的一维结构,每个单元的位数时固定的
  • 指令的执行是顺序的,分支由转移指令实现
  • 指令由操作码和地址码组成.操作码指明本指令的操作类型,地址码指明操作数地址和存放运算结构的地址。操作数的类型由操作码决定,操作数本身不能判定是何种数据类型
  • 指令和数据均以二进制编码表示,采用二进制运算

后来进行了改进

(1) 对输入/输出方式的改进

冯诺伊曼结构以运算器为中心,所有部件的操作都由控制器集中控制。这使输入/输出云操作运算只能串行进行。人们提供了多种I/O

实际上是把I/O的管理工作从CPU分离出来,给新设置的硬件完成,

出现DMA(Direct Memory Access,直接存储器访问),这是在外设与存储器之间建立数据通路,使它们可以直接传送数据,而不必经过运算器,为了实现这种方式,需要在主存和外设之间增加DMA控制器。

当要进行I/O操作时,CPU将DMA控制器中的寄存器设置号初始参数后,仍可以继续执行后续指令,而外设与主存的信息交换则由DMA控制进行。当DMA完成所指定的一批数据的传送后,才向CPU发结束信号,使CPU进行一些事后处理工作

采用DMA方式,每传送完一批数据就要中断一次,如果进一步使该部件能够控制完成I/O的大部分工作,从而使CPU进一步摆脱用于管理和控制I/O操作和传送信息的所有功能都从CPU那里接管过来,独立出去,I/O处理机方式由管道方式和外围处理机方式两种

(2)采用并行处理技术

(3)存储器组织结构的发展

按内容访问的相联存储器(Content Addressed Memory,CAM) 把查找,比较的操作交由存储器硬件完成。

采用了cache

(4)指令集的发展

越来越多的功能可以由硬件实现

RISC和CISC

软件对系统结构的影响

可移植性是指 一个软件不经过修改或者只需要少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。在这种情况下,称这两台计算机时软件兼容的。实现可移植性性的常用方法3种:采用系列机,模拟与仿真,同意高级语言

  1. 系列机

软件兼容有4种,向下兼容,向下兼容,向下兼容,向下兼容

2.模拟与仿真

模拟 指用软件的方法在一台现有的计算机(宿主机)实现另外一台计算机(虚拟机)的指令集,通常使用解释的方法来实现,虚拟机的每一条指令都用宿主机的一段程序进行解释执行

仿真 由微程序去解释实现另一台计算机的指令集,还需要仿真其存储系统,I/O系统和控制台操作

模拟程序存放在主存中,仿真微程序则是存放在控制存储器中,

仿真快,但是只能用于系统结构差距不大计算机

3.统一高级语言

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

器件技术,特别时超大规模集成电路(Very Large Scale Integration,VLSI)技术的发展速度很快

5代计算机的典型特征

图片

应用对系统结构的影响

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

并行性的概念

所谓并行性(parallelism),是指计算机系统在同一时刻或同一时间间隔内进行多种运算或操作,只要在时间上互相重叠就存在并行性,它包括同时性与并发性两种含义

同时性(simultaneity)是指两个或两个以上的事件在同一时刻发生。并发性(concurrency)是指两个或两个以上的事件在同一时间间隔内发生

并行性等级从高到低可以分为一下几个等级

按处理数据来看

(1) 字串位串 每次只对一个字的一位进行处理。不存在并行

(2) 字串位并 同时对一个字的全部位进行处理,不懂字之间是穿行的,已经开始出现并行性

(3) 字并位串 同时许多字的同一位(位片)进行处理,这种方式具有较高的并行性

(4) 全并行 同时对许多字的全部位或者部分位进行处理,这是最高一级的并行

从执行程序的角度来看

(1) 指令内部并行,单指令中各微操作之间的并行

(2)指令级并行(Instruction Level Parallelism,ILP): 并行执行两条或两条以上的指令

(3) 线程级并行(TLP): 并行执行两个或两个以上的线程,通常是以一个进程内派生多个线程为调度单位

(4) 任务级或过程级并行,并行执行两个或连个以上的过程或任务,以子系统或进程为调度单元

(5) 作业或程序级并行:并行执行两个或两个以上的作业或程序

提高并行性的技术途径

(1) 时间重叠: 让多个处理过程在时间上互相错开,如流水线技术

(2) 资源重复 : 在并行性概念中引入空间因素,以数量取胜,通过重复设置硬件资源,大幅度地提高计算机系统的性能

(3) 资源共享 软件方法,它使多个任务按一定时间顺序轮流使用同一套硬件设备。多道程序,分时系统就是遵守这一途径而产生的。

单机系统中并行性的发展

主导作用是时间重叠原理,

实现时间重叠的基础是部件功能专用化,然后构成流水线

资源重复原理的应用,用单机处理机模拟多处理机的功能,形成所谓虚拟机的概念

多机系统中并行性的发展

紧密耦合系统又叫直接耦合系统

松耦合系统又叫间接耦合系统

计算机指令集结构

指令集结构的分类

区别不同指令集结构的主要因素

CPU 中用来存储操作数的存储单元的类型

  • 堆栈
  • 累加器
  • 通用寄存器组

将指令集结构分为三种类型

  • 堆栈结构
  • 累加器结构
  • 通用寄存器结构

根据img操作数的来源不同,又可以进一步分为

寄存器-存储器结构(RM)(操作数可以来自寄存器)

寄存器-寄存器结构(RR)(操作数都是来自于通用寄存器),也称为load-store结构,这个名称强调:只有load指令和store指令能够访问存储器。

对于不同类型的指令集结构,操作数的位置,个数,以及操作数给的方式(隐式或显式)也会不同

  • 隐式给出: 使用事先约定好的存储单元
  • 显式给出:使用指令字中的操作数字段给出

4种指令集结构的操作数位置以及结果的去向

通用寄存器结构

现代指令集结构的主流

在灵活性和提高性能方面有明显的优势

跟其他的CPU内部存储单元一样,寄存器的访问速度比存储器块

对于编译器而言,能够更加容易,有效地分配和使用寄存器

寄存器可以用来存放变量

减少对存储器的访问,加快速度

用更少的地址位(相对于储存器地址来说)对寄存器进行寻址

根据ALU指令的操作数的两个特征对通用寄存器型指令集的结构进行进一步细分

ALU指令的操作数个数

3个操作数的指令

两个源操作数,一个目的操作数

2个操作数的指令

其中一个操作数作为源操作数,又作为目的操作数

ALU指令种存储器操作数的个数: 0-3

8 ALU 指令中操作数个数

9通用寄存器型指令集结构进一步细分为三种类型

3种的优缺点

图片

寻址方式

寻址方式(addressing mode) 是指一种指令集结构如何确定所要访问的数据的地址

一些寻址方式

图片

指令集结构的功能设计

在确定哪些功能用硬件来实现时,主要考虑的因素有3个,速度,成本与灵活性。

用硬件实现的特点时速度快,成本高,灵活性差。

用软件来实现的特点时速度慢,价格便宜,灵活性好。

一般出现频度高的基本功能用硬件来实现

对指令集的基本要求是: 完整性,规格性,高效率和兼容性。

分类图片

CISC 指令集结构的功能设计

数量多,功能多样的指令,指令往往达到200 ~ 300 条之多

面向目标程序增强功能

(1) 增强运算型指令的功能

(2) 增强数据传送指令的功能

(3) 增强程序控制指令的功能

面向高级语言的优化来改进指令集

(1) 增强对高级语言和汇编器的支持

(2) 高级语言计算机

面向操作系统的优化实现改进指令集
RISC 指令集的功能设计

CISC 指令集的问题

  1. 各种指令的使用频度相差悬殊
  2. 指令集庞大,指令条数很多,许多指令的功能又很复杂
  3. 许多指令由于操作繁琐,其CPI值比较大
  4. 由于指令功能复杂,规整性不好,不利于采用流水线技术
指令控制

控制指令是用来改变控制流的

条件分支(conditional branch)

跳转(jump)

过程调用(call)

过程返回(return)

主要在于分支

分支条件的主要方法及其缺点

图片

操作数的类型和大小

数据表示(data representation)是指计算机能够直接识别,计算机硬件能够直接识别,指令集可以直接调用的数据类型。

数据结构(data structure)则不同,它是指由软件进行处理和实现的各种数据类型。

表示操作数类型的方法有一下两种

  • 由指令中的操作码指定操作数的类型
  • 给数据加上标识(tag),由数据本身给出操作数类型

指令格式的设计

寻址方式的表示

一种是把它与操作码一起编码,另一种则是设置专门的地址描述符

3种编码格式

  1. 可变长编码格式
  2. 固定长度
  3. 混合型

图片

MIPS指令集结构

流水线技术

把一个重复的过程分解为若干个子过程,每个子过程由专门的功能部件来实现,把多个处理过程在时间上错开,依次通过各功能段,这样每个子过程就可以和其他子过程并行进行

  1. 流水线把一个处理过程分解为若干子过程,每个过程由一个专门的部件来实现,因此,流水线实际上是把一个大的处理部件分解为多个独立的工作部件,并依靠它们的并行工作来缩短程序的执行时间
  2. 流水线中各段的时间应尽可能相等,否则将引起流水线阻塞,断流,因为时间长的段将成为流水线的瓶颈,此时流水线中的其他部功能部件就不能充分发挥作用,因此瓶颈问题是流水线设计中必须解决的
  3. 流水线每一个功能部件的后面都要有一个缓冲寄存器(锁存器), 称为流水线寄存器,其作用是在相邻的两段之间传送数据,以保证提供后面要用到的数据,并把各段的处理工作相互隔离
  4. 流水技术适合于大量重复的时序过程,只有在输入端不断地提供任务,才能充分发挥流水线的效率
  5. 流水线需要有通过时间和排空时间。它们分别指顶一个任务和最后一个任务从进入流水线到流出结构的那个时间段。这两个时间段,流水线都不是满载的。经过”通过时间”后,流水线进入满载工作状态,整体流水线的效率才得到充分发挥

流水线

流水线的分类
单功能流水线和多功能流水线

这是按流水线所完成的功能来分类

  1. 单功能流水线 : 只能完成一种固定功能的流水线
  2. 流水线的各段可以进行不同的连接,以实现不同的功能
静态流水线与动态流水线

这是安装统一时间内各段之间的连接方式来对多功能流水线作进一步的分类

  1. 静态流水线: 在同一时间内,多功能流水线中的各段只能按同一种功能的连接方式工作。
  2. 动态流水线: 在同一时间内,多功能流水线中的各段可以按照不同的方式连接,同时执行多种功能。
部件级,处理机级及处理机间流水线

这是按流水线的级别来进行分类

部件级流水线

处理机级流水线

处理机间流水线

线性流水线与非线性流水线

这是按照流水线中是否由回馈回路进行分类

顺序流水线与乱序流数线

这是根据任务流入和流出的顺序是否相同进行分类

流水线性能指标

吞吐率
加速比
效率
例子

流水线的相关与冲突

一个经典的5段流水线

一个经典的5段RISC流水线‘

一条指令的执行过程分为以下5个周期

取指令周期(IF)

指令译码/读存储器周期(ID)

执行/有效地址计算周期(EX)

存储器访问指令: ALU把所指定的存储器的内容与偏移量相加,形成用于访问的有效地址

寄存器-寄存器ALU指令: ALU按照操作码指定的操作对从通用寄存器组种读取的数据进行运算

寄存器-立即数ALU指令: ALU按照操作码指定的操作对从通用寄存器组种读取的理机数进行运算

分支指令:ALU把偏移量与PC值相加,形成转移目标的地址,同时,对在前一周期读出的操作数机型判断,确定分支是否能成功。

存储器访问/分支完成周期(MEM)

load和store指令。如果是load指令,就用上一个周期计算出的有效地址从存储器种读出相应的数据;如果是store指令,就把指定的数据写入写入这个有效地址所指定的存储器单元

分支指令。 如果在前一个周期判定该分支”成功”,就把转移目标地址送入PC.分支指令执行完成

写回周期(WB)

把上面的每一个周期作为一个流水段,在各段之间加上锁存器,这些锁存器称为流水线寄存器

采用流水线方式实现时,首先要保证不会再同一时钟周期要求同一个功能段做两件不同的工作

相关与流水线冲突
相关

相关(dependence)是指两跳指令之间存在某种依赖关系。有三种类型: 数据相关(真数据相关),民相关和控制相关

1 数据相关(data dependence)

对于两条指令i(在前)和j(在后),如果下述条件之一成立,则称指令j于指令i数据相关:

  1. 指令j使用i产生的结果
  2. 指令j与指令k数据相关,而指令k又与指令i数据相关

2名相关(name dependence)

这里的名是指指令访问的寄存器或存储器单元的名称,如果两条指令使用相同的名,但是他们之间并没有数据数据流动,则称这两条指令存在名相关,指令j与指令i之间的名相关有两种

  1. 反相关(anti-dependence): 如果指令j与指令i读的名称相同,则称指令i和j发生了反相关。反相关指令之间执行顺序必须严格遵守,以保证i读的值是正确的
  2. 输出相关(output dependence): 如果指令j和指令i写相同的名,则称指令i和j发生了输出相关,输出镶滚指令的顺序是不能颠倒的

与真数据相关不同,名相关的两条指令之间并没有数据的传送,只是使用了相同的名而以。

如果把其中一条指令所用的名换成别的,并不影响另外一条指令的正确执行,因此可以通过改变指令种操作数的名来消除名相关,这就是换名(renaming)技术,对于寄存器操作数进行换名称位寄存器换名(register renaming)

3控制相关(control dependence)

控制相关是指由分支指令引起的相关.它根据分支指令的执行结果来确定后续指令是否执行。

一般来说,为了保证程序应有的执行顺序,必须严格按控制相关确定的顺序执行

控制相关带来的限制

流水线冲突

流水线冲突(pipeline hazards) 是指对于具体的流水线来说,由于相关的存在,使得指令流中的下一条指令不能再指定的时钟周期执行

流水线冲突有以下3种类型

1 结构冲突(strutural hazards): 因硬件资源满足不了指令重叠执行的要求而发生的冲突

2数据冲突(data hazards):当指令再流水线种重叠执行时,因需要用到前面指令的执行结果而发生的冲突

3控制冲突(control hazards): 流水线遇到分支指令和其他会改变PC值得指令所引起得冲突

1) 结构冲突

在流水线中处理机中,为了能够使各种处理都能够顺利的重叠执行,需要对功能部件进行流水,或者重复设置资源,如果某种之力组合因为资源冲突而不能正常执行,则称该处理机有结构冲突

2) 数据冲突

当相关的指令靠的足够近时,

可能发生的数据冲突有以下3种

  • 写后读冲突(Read After Write,RAW): 指令j用指令i的计算结构,而且在i将结果写入寄存器之前就去读该寄存器,因而得到的是旧值,它对于真数据冲突
  • 写后写冲突(Write After Write,WAW): 指令j和指令i的结果单元(寄存器或存储器单元)相同,而且j在i写入之前久对该单元进行了写入操作,从而导致写入顺序错误,这时结果单元中留下的时i写入的值,而不是j写入的。这种冲突对应于输出相关,写后写冲突仅发生在这样的流水线中:流水线不止一个段可以进行写操作,或者当前某条指令停顿时,允许气后续指令继续前进
  • 读后写冲突(Write After Read,WAR):指令j的结果单元和指令i的源操作数单元相同,而且j在i后读取该单元之前前就读之前进行写操作,导致i读取到的值是错误的,这种冲突是由反相关引起的

通过定向技术减少数据冲突引起的停顿

为了减少停顿时间,可以采用一种称为定向(forwarding,也称为旁路或者短路)

  • EX 段和MEM 段之间的流水线寄存器种保存的ALU运算结果总是回到ALU的入口
  • 当定向硬件检测到其哪一个ALU的运算结果写入的结果就是当前ALU操作数的源寄存器时,那么控制逻辑就会选择定向的数据作为ALU的输入,而不采用通用寄存器读出的值

需要停顿的数据冲突

不是所有的指令都可以用定向技术

需要设置一个称为流数线互锁机制(pipeline interlock) 用于检测发现数据冲突,并使流数线停顿,直至冲突消失。

依靠编译器解决数据冲突

可以重新组织指令顺序来消除冲突,这种技术被称为(指令调度)

3) 控制冲突

流水线的实现

*向量处理机

指令级并行

指令级并行

概念

几乎所有的处理机都利用流水线来使指令重叠并行执行,以达到提高性能的目的,这种指令之间存在的潜在并行称为指令级并行(ILP: Instruction-Level Parallelism)。

如何通过各种可能的技术,获得更多的指令级并行性

硬件+软件技术

1.流水线处理机的实际CPI

理想流水线的CPI加上各类停顿的时钟周期数

理想CPI是衡量流水最高性能的一个指标

IPC: Instructions Per Cycle(每个时钟周期完成的指令条数)

2.程序基本块

基本程序块: 一段除了入口和出口外不包含其他分直的线性代码片段。

程序平均每5-7条指令就会有一个分支

3.循环级并行: 使一个循环中的不同循环体并行执行

开发循环体中存在的并行性 最常见,最基本

指令级并行的研究重点之一

考虑下述语句

1
for(i=1;i<=500;i=i+1) a[i]=a[i]+s;

每一次循环都可以与其他的循环重叠并行执行

每一次循环的内部,却没有任何的并行性

4.最基本的开发循环级并行的技术

循环展开(loop unrolling)技术

采用向量指令和向量数据表示

5.相关与流水线冲突

相关有三种类型:

数据相关,名相关,控制相关

相关是程序固有的一种属性,它反映了程序中指令之间的互相依赖关系

具体的一次相关是否导致实际冲突的发生以及该冲突会带来多长的停顿,则是流水线的属性。

6.可以从两个方面来解决相关问题

  • 保持相关,但避免发生冲突
  • 通过代码变换,消除相关

7.程序顺序: 由源程序确定的再完全串行方式下指令执行的指令的执行顺序

只有再可能导致错误的情况下,才保持程序顺序

8.控制相关并不是一个必须严格保持的关键属性

9.对于正确地执行程序来说,必须保持的最关键的两个属性是:数据流和异常行为

保持异常行为是指,无论怎么改变指令的执行顺序,都不能改变程序中异常的发生情况

即原来程序中是怎么发生的,改变执行顺序后还是怎么发生的

弱化为:指令顺序的改变不能导致程序中发生新的异常

如果我们能做到保持程序的数据相关和控制相关就能保持程序的数据流的异常行为

数据流: 指数据值从产生者指令到消费者指令的实际流动

分支指令使得数据流具有动态性,因为它使得给定指令的数据可以有多个来源。

仅仅保持数据相关性是不够饿,只有再加上保持控制的顺序,才能够保持程序顺序

有时,不遵守控制相关既不影响异常行为,也不改变数据流

可以大胆的进行指令调度,把失败分支中的指令调度到分支指令之前

指令的动态调度

静态调度

依靠编译器对代码进行静态调度,以减少相关和冲突

它不是在程序执行的过程中,而是在编译期间进行代码调度和优化

通过把相关的指令拉开距离来减少可能产生的停顿

动态调度

在程序的执行过程中,依靠专门硬件对代码进行调度,减少数据相关导致的停顿。

优点:

  • 能够处理一些在编译时情况不明的相关(比如涉及存储器访问的相关),并简化了编译器;
  • 能够使本来时面向某一流水线优化编译的代码在其他的流水线(动态调度)上也能高效地执行

以硬件复杂性的显著增加为代价

动态调度的基本思想
Tomasulo 算法

核心思想:

  1. 检查数据相关的指令,操作数一旦就绪立刻执行,没就绪则等待;
  2. 通过寄存器换名技术消除读后写和写后写冲突
Tomasulo的基本结构

COS1

1.保留站

保留站(reservation station) 设置在运算部件的入口,

2.公共数据总线

3.load缓冲器和store缓存器

存放读/写存储器的地址或数据,与保留站类似

load缓冲器的作用

  • 存放用于计算有效地址的分量
  • 记录正在进行的load访存,等待存储器的响应
  • 保存已经完成了的load的结果(即从存储器取来的数据),等待CDB传输。

store缓冲器的作用

  • 存放用于计算有效地址的分量
  • 保存正在进行的store访存的目标地址,该store正在等待存储数据的到达
  • 保存该sotre的地址和数据,直到存储器部件接收

4.浮点寄存器

5.指令队列

6.运算部件

Tomasulo算法的基本执行步骤

流出

(1) 从指令队列得头部取一条指令,送入保留站。

(2)若操作数就绪,讲操作数直接放入保留站。

(3)若操作数未就绪,讲产生该操作数编号写入保留站。一旦操作数就绪,立刻送入。

(4)对目标寄存器进行预约

执行

(1)对ALU指令来说,计算结果。

(2)对load和store指令来说,计算有效地址,并讲有效地址放回缓冲器

写结果

功能部件计算完毕后,就将计算结果放到CDB上,所有等待计算结果得寄存器和保留站(包括store缓冲器)都同时从CDB上活动所需要得数据

一个例子

1
2
3
DIV.D F4, F0, F2
SUB.D F10,F4, F6
ADD.D F6, F12,F14
Tomasulo算法详细解

1.符号含义

r: 分配给当前指令的保留站或者缓冲器单元编号;

RS: 保留站

result: 浮点部件或load缓冲器返回的结果

Regs[]:寄存器组名

rd: 目标寄存器编号

rs,rt: 操作数寄存器编号

imm: 符号扩展后的立即数

以上这三个字段,会出现指令之中,之前说个,rs一般是第一个倍访问的寄存器,rt是第二个被访问的寄存器,rd,是第三个被访问的寄存器

以下会出现在保留站中

Op: 要对源操作数进行的操作

Vj和Vk: 分别为保留站中就绪的操作数字段,这里注意,是就绪的操作数。无论是ALU指令,Load指令还是Store指令,j对应的都是rs,k对应的都是rt.

Qj和Qk: 为保留站中未就绪操作数字段,就是未就绪的操作数,无论是ALU指令,Load指令还是Store指令,j对应的都是rs,k对应的都是rt. 当Qj,Qk为0表示保留站或缓冲器单元中的Vj或Vk字段中的数据就绪。当它们为整数时,这时候保留的时保留号,表示它们正在等待结果

A: 这时个Load和Store的保留站字段,指令流程阶段存的时Imm,执行阶段(算出又地址后)存的时访问的有效地址

Qi: 寄存器状态表,对应的时rd。他时寄存器状态表,不是寄存器,当它为0时,代表对应的寄存器是就绪的;为正整数是,代表被某个保留站中的指令预约了,里面保存的即将写结果的保留站号

2 算法

(1)流出阶段

(a)对于浮点运算指令

进入条件: 有空闲保留站(设为r)

操作和状态表内容修改:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if(Qi[rs] = 0){         //检测第一操作数是否就绪
RS[r].Vj<- Regs[rs];//
RS[r].Qj<- 0; //
}
else{ //
RS[r].Qj<-Qi[rs]; //
} //

if(Qi[rt] = 0){ //
RS[r].Vk<- Regs[rt];//
RS[r].Qk<- 0; //
}
else{ //
RS[r].Qk<-Qi[rt]; //
}
RS[r].Busy<- yes; //
RS[r].Qp<- Op; //
Qi[rd]<- r; //

(b) load和store指令

进入条件: 缓存器有空闲单元(设为r)

操作和状态表内容修改

1
2
3
4
5
6
7
8
if(Qi[rs] = 0){
RS[r].Vj<- Regs[rs];
RS[r].Qj<- 0;
}else{
RS[r].Qj<- Qi[rs];
}
RS[r].Busy<- yes;
RS[r].A<- Imm;

对于load指令:

1
Qi[rt]<- r;

对于store指令:

1
2
3
4
5
6
7
if(Qi[rt] = 0){
RS[r].Vk<- Regs[rt];
RS[r].Qk<- 0;
}
else{
RS[r].Qk<- Qi[rt];
}

多条指令对于同一个目标寄存器进行多次预约得结果,只保留了最后一个预约,因为前面进行寄存器换名得时候,已经消除了读后和写后相关。

(2)执行阶段

(a)浮点运算指令

进入条件: (RS[r].Qj = 0) 且 (RS[r].Qk = 0);

操作和状态表内修改: 进行计算,产生结果。

(b)load/store指令

进入条件:(RS[r].Qj = 0) 且r成为load/store缓冲队列得头部

操作和状态表内容修改

RS[r].A <- Rs[r].Vj + RS[r].A

对于load指令,在完成有效地址计算后,还要进行:

从Mem[RS[r].A]读取数据

(3)写回阶段

(a)浮点运算指令和load指令

进入条件: 保留站r执行结束,且CDB就绪。

操作和状态表内容修改:

任意x

1
2
3
4
5
6
7
8
9
10
11
12
13
if(Qi[x] = r){
Regs[x]<- result;
Qi[x]<- 0;
}
if(RS[x].Qj = r){
RS[x].Vj<- result;
RS[x].Qj<- 0;
}
if(RS[x].Qk = r){
RS[x].Vk<- result;
RS[x].Qk<- 0;
}
RS[r].Busy<- no

(b) store

进入条件: 保留站r执行结束,且RS[r].Qk = 0

操作和状态表内容修改:

1
2
Mem[RS[r].A]<- RS[r].Vk
RS[r].Busy<- no;

动态分支预测技术

所开发的ILP越多,控制相关的制约就越大,分支预测就要有更高的准确度

本节中介绍的方法对于每个实在周期流出多条指令的处理机来所非常重要

因为:

  • 在n-流出的处理机中,遇到分支指令的可能性增加了n倍。要给处理器连续提供指令,就需要预测分支的结果
  • Amdahl定律告诉我们,机器的CPI越小,控制停顿的相对影响就更大

动态分支预测: 在程序运行时,根据分支指令过去的表现来预测其将来的行为

  • 如果分支行为发生了变化,预测结果也跟着改变
  • 有更好的预测准确度和适应性

分支预测的有效性取决于:

预测的准确性

越策争取和不争取两种情况下的分支开销

决定分支开销的因素:

  • 流水线的结构
  • 预测的方法
  • 预测错误时的恢复策略等

采用动态分支预测技术的目的

  • 预测分支是否成功
  • 尽快找到分支目标地址(或指令)

需要解决的关键问题

  • 如何记录分支的历史信息

  • 如何根据这些信息来预测分支的去向(甚至取到指令)

在预测错误时,要作废已经预取和分析的指令,恢复现场,并从另一条分支路径重新取指令

采用分支历史表(BHT)

BHT基本思想:根据历史看未来。记录下来最近几次分支的成功与否,来预测本次分支是否成功

分支历史表BHT(Baranch History Table)或分支预测缓冲器(Branch Predicition Buffer)

  • 最简单的动态分支预测方法
  • 用BHT来记录分支指令最近一次或几次的执行情况,并据此进行预测

只有1个预测位的分支预测缓冲

记录分支指令最近一次的历史,BHT中只需要1位二进制

采用两位二进制来记录历史

  • 提高预测的准确度
  • 研究结果表明:两位分支预测的性能与多于两位分支预测的性能差不多

状态转换:

image-20200417004847846

图片解释

11 和 10 表示预测 分支成功

01 和 00 表示预测 分支不成功

实际上表示只有连续两次预测错误才会更改分支策略

分支预测中的操作有两个步骤:

分支预测:

  • 分支指令到达译码段(ID)时,根据从BHT读出的信息进行分支预测
  • 若预测正确,就继续处理后续的指令,流水线没有断流,否则,就要作废已经预取和分析的指令,恢复现场,并从另一条分支路径重新取指令

状态修改

BHT方法只有在一下情况才有用:

判断分支是否成功所需的时间大于确定分支目标地址所需的空间

采用分支目标缓冲器BTB

BTB 基本思想: 也是根据历史看未来,鉴于只记录下来最近一次或者几次分支的成功与否对某些流水线来说作用不大(因为即使是预测分支成功,也不知道下一条指令是啥),分支目标缓冲器BTB连同分支目标指令地址也记下来,因此,称为分支目标缓冲器。

BTB的原理,BTB缓冲的是”当前指令的地址”和分支目标指令的地址

分支指令, 三种情况

  • 上一次分支成功的指令,在BTB表中会有记录,这次仍然预测他是成功的,直接用缓冲的分支目标地址去分支目标指令
  • 以前没有执行过的分支指令,在BTB表中不会有记录,不会去分支目标指令,如果这次分支成功了,要将该指令的地址和对应的分支目标指令地址写入BTB
  • 上次分支不成功的指令,和上处理方法一样

另外一种形式

在分支目标缓冲器中存放一条或则多条分支目标出的指令,有三个潜在的好处

  • 更快的获得分支目标处的指令
  • 可以一次提供分支目标处的多条指令,这对于多流出处理器是很有必要的
  • 我们可以使用称为分支折叠(branch folding) 的优化
基于硬件的前瞻预测

对分支指令的结果进行猜测,并假设这个猜测总是对的,然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器,而是放到一个称为 ROB(ReOrder Buffer,再定序缓存)的缓冲器中。等到相应的指令得到“确认(commit)”(即确实是应该执行的)之后,才将结果写入寄存器或存储器。

  1. 顺序流出指令队列
  2. 猜测路径和乱序执行
  3. 顺序确认(保证顺序写回)
  4. 猜错或则发生异常,没写回的全不算数
算法详述

1.流出阶段

(1)从浮点指令队列的头部取一条指令。如果有空闲的保留站(设为r)且有空闲的ROB项(设为b),就流出该指令;如果保留站或ROB全满,便停止流出指令,直到它们都有空闲的项。

(2)如果所需要的操作数已经在寄存器或者ROB中就绪,就把它们送入保留站r中,修改r和b的控制字段,表示已被占用。

(3)将ROB项b的编号也要放入保留站r,以便将来执行结果放到CDB时当做标志。

(4)使用ROB编号对浮点寄存器进行预约。 //备注:书上步骤中没提这个,实际上有。

2.执行阶段

(1)如果有操作数尚未就绪,就等待,并不断地监测CDB。

(2)当两个操作数都已就绪后,就可以执行该指令的操作。

(3)Load指令的执行包括计算地址和从内存中读取数据。

(4)Store指令的执行只包括计算地址。

3.写结果阶段

(1)当结果产生后,将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上,经CDB写到ROB以及所有等待该结果的保留站。

(2)释放产生该结果的保留站。

(3)store指令的操作为:如果要写入存储器的数据已经就绪,就把该数据写入分配给该store指令的ROB项。否则,就监测CDB,直到那个数据在CDB上播送出来,这时才将之写入分配给该store指令的ROB项。

4.确认阶段

(1)其他指令(除分支指令和store指令):当该指令到达ROB队列的头部而且其结果已经就绪时,就把该结果写入该指令的目标寄存器,并从ROB中删除该指令。

(2)store指令:处理与上面类似,只是它把结果写入存储器。

(3)分支指令:

情况I:当预测错误的分支指令到达ROB队列的头部时,清空ROB,执行过程从分支指令的后续正常处重新开始。

情况II:当预测正确的分支指令到达ROB队列的头部时,和非分支指令一样正常确认。

(4)产生异常的指令:在该指令到达ROB头部前不处理。到达ROB头部时,产生中断,清空ROB。此操作能够完成精确的异常处理。

存储系统

存储系统的层次结构

  • 速度越块,价格越高(每位)
  • 容量越大,价格越低(每位)
  • 容量越大,速度越慢

程序访问的局部性原理

存储系统的多级层次结构

存储系统的性能参数

1.存储容量S

一般来说,整个存储器系统的容量即是第二级存储器$M_2$的容量,即$S=S_2$

2.存储系统的平均每位价格C

3.命中率H

命中率(hit ratio)H的定义为,CPU访问存储系统时,在M1中找到所需信息的概率

$N_i$表示访问$M_i$的次数

4.平均访存时间$T_A$

分两种情况考虑CPU的一次访存

  • 当命中时,访问时间即为$T_1$.$T_1$常常称为命中时间(hit-time)
  • 当不命中时,在大多数二级存储系统中,若访问的字不在$M_1$中,就必须从$M_2$中把包含所要访问的字的快(或页面)传送到$M_1$之后CPU才可以在$M_1$中访问到这个字,设传送一个信息块所需要的时间为$T_n$,则不命中时的访问时间为$T_2+T_B+T_1=T_1+T_M$其中$T_M=T_B+T_2$称为不命中开销(miss penalty),它是指从向$M_2$发出访问请求把整个数据快调入$M_1$所需的时间

考虑到命中和不明中的概率分别是$H$和$1-H$,所以该存储系统的平均访存时间为

三级存储系统

大部分计算机都采用了了有Cache(高速缓冲存储器),主存储器和磁盘存储器(辅存)构成的三级存储系统,

“Cache-主存”层次

“主存-辅存”层次

存储层次的4个问题
  • 当把一个块(页)调入高一层(靠近CPU)存储器时,可以放到哪些位置上(映射规则)
  • 当所要访问的块(页)在高一层存储器中时,如何找到该块(查找算法)
  • 当发生不命中且搞一层存储器已经满时,应该替换哪一块(替换算法)
  • 当进行写访问时,应该进行哪些操作(写策略)

Cache

基本结构和原理

Cache是按块进行管理的,Cache和主存均被分割为大小相同的块,信息以块为单位调入Cache,相应地,CPU的访存地址被分割为两部分;块地址和块内位移

[主存地址]=[块地址:块内位移]

工作示意图

映像规则

1. 全相联映射(fully associative mapping)

主存中的任意一块都可以被放置到Cache的任何一个位置

2. 直接映像(direct mapping)

主存中的每一个块只能被防止到Cache中的唯一一个位置

一般地,如果主存的第i块(即块地址为i)映像到Cache块的第j块,则

M为cache的块数

3. 组相联映像(set associative)

Cache被等分为若干组,每组由若干个块组成。主存中的每一个块可以被防止到Cache中唯一的一个组中的任意一个位置,他是前两种方案的折中

n路组相联是指的每个组有n个块

[主存地址] [标识:索引:块内位移]

块内位移取决于块内多少个字节

索引取决于组数(全相联没有索引)

剩下的为标识

查找算法

1.通过查找目录表来实现

目录表的结构

  • 主存块的块地址的高位部分,称为标识。
  • 每个主存块能够唯一地由其标识来确定

主存地址: [标识:索引:块内位移]

块地址:[标识:索引]

只需要查找候选位置所对应的目录表项

2.并行查找与顺序查找

提高性能的重要思想:主候选位置(MRU块)

3.并行查找的实现方法

相联存储器

  • 目录$2^g$个相联存储区构成,每个相联存储区的大小为$n\times(h+\log_{2}n)$位

  • 更具所查找的组内块地址,从Cache存储体中读出的多个信息字中选一个,发送给CPU

[标识(h位):索引(g位)]

单体多字存储器+比较器

举例: 4路组相联并行标识比较(比较器得个数及位数)

4路组相联Cache的查找过程

直接映像Cache的查找过程

优缺点

  • 不必采用相联存储器,而是按地址访问的存储器来实现

…(wait)

替换算法

要解决的问题: 当新调入一块,而Cache又被占满时,替换哪一块?

  • 直接映像Cache中的替换很简单 (只有一个块)
  • 在组相联和全相联Cache中,则又多个块提供选择

主要的替换算法有三种

  • 随机法
  • 先进先出法(FIFO)
  • 最近最少使用法LRU

LRU

选择近期最少被访问的块作为被替换的块。

实际上选择最久没有被访问过的块作为被替换的块

命中率最高

LRU和随机法分别因其不命中率低和实现简单而被广泛采用

对于容量比较大的Cache,LRU和随机法的命中率差别不大

LRU算法的硬件实现

堆栈法

用一个堆栈来记录组相联Cache的同一组中各块被访问的先后次序

用堆栈元素的物理位置来反应先后次序

栈底记录的时该组最早被访问的块

当需要替换时,从栈底得到应该被替换的块

堆栈中的内容必须动态更新

当Cache访问命中时,通过用块地址进行相联查找,在堆栈找到相应的元素,然后把改元素的上面所有元素下压一个位置,同时把本次访问的块地址抽出来,从上面压入栈顶,而元素下面的所有元素则保持不动

如果Cache访问不命中,则把本次访问的地址从最上面压入栈顶,堆栈中所有原来的元素都下移一个位置。如果Cache中该组已经没有空闲块,就要替换一个块,这时从栈底被挤出去的块地址就是需要被替换的块的块地址

所需要硬件

需要为每一组都设置一个项数与相联读相同的小堆栈,每一项的位数为$\log_2 n$位

硬件堆栈所需的功能

相联比较,能够全部下移,部分下移动,和从中间取出一项的功能

速度较低,成本较高

比较对法

让各块两两组合,构成比较对,每一个比较对用一个触发器的状态来表示它所相关的两个块最近一次被访问的远近次序,再经过门电路就可找到LRU块

(wait)

写策略

保证一致性

CASE1 写命中,即CPU要访问的数据在Cache中找到了。这个时候有两种策略

(1) 写直达

(2) 写回法

CASE2 写失效。即CPU要访问的数据在Cache中没有找到。这时候有两种策略

(1)按写分配

(2)不按写分配

工作过程
Cache的性能分析

公式1

公式2

公式3

4 Cache不命中对于一个CPI较小而时钟频率较高CPU来说,影响是双重的

  • $CPI_{execution}$较低,固定周期数的Cache不命中开销的相对影响就越大
  • 在计算CPI时,不命中开销的单位是时钟周期数时钟频率高的CPU不命中开销比较大,其CPI中存储器停顿这部分也就比较大

改进:

减低不命中率

降低不命中开销

减少命中时间

降低Cache不命中率

三种类型的不命中

有三种类型的不命中:

  1. 强制性不命中: 第一次访问一个块的时候,该块不在Cache中,需要重下一级存储器中调入Cache
  2. 容量不命中:程序执行的时候,所需要的块不能全部调入Cache中,随着程序的执行,某些块不得不被替换,若有被重新访问,就发生了不命中
  3. 冲突不命中: 组相联或者直接映像中,太多块映射到同一组(或同一块)上,会发生冲突
  1. 相联度越高,冲突不命中就越少
  2. 强制性不命中和容量不命中不受相联度的影响
  3. 强制性不命中不受Cache容量的影响,单容量不命中却随着容量的增加而减少

从上面看来,可以

  1. 减少强制性不命中 — 增加块大小
  2. 减少容量不命中 — 增加容量
  3. 减少冲突不命中 — 提高相联度

但是使用一种方法提高某一项性能的同时,可能会牺牲其他方面的性能

增加Cache块大小
增加Cache的容量
提高相联度
伪相联Cache

减少Cache不命中开销

采用两级Cache

增加一级Cache

  • 第一级Cache(L1)小而快
  • 第二级Cache(L2)容量大

性能分析

局部命中率与全局不命中率

评价第二级Cache时,应该使用全局不命中率这个指标,它指出了在CPU发出的访存中,究竟有多大比例时穿过各级Cache,最终达到存储器的

采用两级Cache时,每条指令的平均访存停顿时间:

一些结论

\\after

让读不命中优先于写
  1. 读不命中,需要访存时,可能存储器还未更新,要读入的内容尚在写缓冲区中,若推迟读访问,直到写缓冲区的数据都写入主存,会增加读命中时间
  2. 不等写缓冲区清空,读访问不命中的时候,直接在写缓冲区里面找时有需要的数据

Cache中的写缓冲器导致对存储器访问的复杂化,在读不命中时,所读单元的最新值有可能还在写缓冲器中,尚未写入主存

解决方法:

  • 推迟读不命中的处理(读不命中的开销增加)
  • 检查写缓冲器中内容

在写回法Cache中,也可采用写缓冲器

写缓冲合并

提高些缓冲器的效率

写直达Cache

依靠写缓冲来减少对下一级存储器写操作的时间

  • 如果缓冲器为空,就把数据和相应地址写入该缓冲器。(从CPU的角度,写操作完成)
  • 如果写缓冲器中已经有待写入的数据,就要把这次的写入地址与缓冲器已有的所有地址进性比较,看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的,就把这次要写入的数据与该项合并。这就叫写缓冲合并

  • 如果写缓冲器满足又没有能进行写合并的项,就必须等待

提高了写缓冲器的空间利用率,而且还能减少因写缓冲器而要进行的等待时间

请求字处理技术

请求字

  • 从下一级存储器调入Cache的快中,只有一个字是立即需要的,这个字称为请求字

应该尽早把请求字发送给CPU

  • 尽早重启动: 调块时,从块的起始位置开始读起,一旦请求字达到,就立即发送给CPU,让CPU继续执行
  • 请求字优先: 调块时,从请求字所在的位置读起。这样,第一个读出的字便时请求字。将之立即发送个CPU

Cache块小或者下一条指令正好访问同一块Cache

非阻塞Cache技术

非阻塞Cache: Cache 不命中时仍允许CPU进行其他的命中访问。即允许”不命中下命中”。

进一步提高性能:

  • “多重不命中下命中”
  • “不命中下命中”

可以同时处理的不命中次数越多,所能带来的性能上的提高就越大

简单的”一次不命中下命中”就几乎可以得到所有的好处

减少命中时间

Cache的访问时间往往会限制处理器的时钟频率

容量小,结构简单的Cache

硬件越简单,速度就越快

应使Cache足够小(物理空间),以便于可以与CPU一起放在同一块芯片上

折衷方案(?) 把标识放在片内,把Cache的数据存储器放在片外

虚拟Cache

物理Cache

  • 使用物理地址进行访问的传统Cache
  • 标识存储器中存放的时物理地址,进行地址检测也是用物理地址
  • 缺点:地址转xing换和访问Cache串行进行,访问速度慢

虚拟Cache

  • 可以直接用虚拟地址进行访问的Cache。标识存储器存放的时虚拟地址,进行地址检测用的也是虚拟地址。
  • 优点
    • 在命中时不需要地址转换,省去了地址转换的时间。即使不命中地址转换和访问Cache也是并行的,其速度比物理Cache块很多

并非都采用虚拟Cache

  • 虚拟Cache的清空问题
    • 解决方法: 在地址标识中增加PID字段
  • 同义和别名
    • 解决方法: 反别名法,页着色

虚拟索引+物理标识

  • 优点:兼得虚拟Cache和物理Cache的好处
  • 局限性:Cache容量受到限制
    • Cache容量$\leq$ 页大小$\times$ 相联读

硬件散列变换

Cache访问流水化
  1. 对第一级Cache的访问按流水方式组织
  2. 访问Cache需要多个时钟周期才可以完成
踪迹Cache

开发指令级并行所遇到的一个挑战是:

当要每个时钟周期流出超过4条指令时,要提供足够多条彼此互不相关的指令时很困难的

一个解决方法: 采用踪迹 Cache

存放CPU所执行的动态指令序列

  • 包含了由分支预测展开的指令,该分支预测事否正确需要在取到该指令时进行确认

优缺点

  • 地址映像机制复杂
  • 相同的指令序列

并行主存系统

主存的主要性能指标: 延迟和带宽

以往:

Cache主要关系延迟,I/O主要关系带宽

Cache 关心两者

并行主存系统式在一个访存周期内能并行访问多个存储子的存储器

  • 能够有效地提高存储器的带宽
单体多字存储器

能提高带宽

优缺点:

  • 优点: 实现简单
  • 缺点: 访存效率不高

原因:

  • 分支指令使得后面指令无效
  • 不一定都是有用的
  • 写入可能变得复杂
多体交叉存储器

由多个单字存储体构成,每个体由自己的地址寄存器以及地址译码和读/写驱动等电路,如下图式四个体交叉存储器

//图片

高位和低位

避免存储体冲突

体冲突: 两个请求要求访问同一个体

减少体冲突次数的一种方法: 采用许多体

解决体冲突的方法

  • 软件方法(编译器)
    • 循环交换优化
    • 扩展数组的大小,使之不是2的幂
  • 硬件方法
    • 使体数为素数
    • 体内地址=地址 A mod (存储体中的字数)

虚拟存储器

基本概率
快速地址转换技术

地址变换缓冲器TLB

TLB中的项由两部分构成: 标识和数据

标识中存放的式虚地址的一部分

数据部分存放的则是物理页帧号,有效位,存储保护信息,使用位,修改位等

一般保证TLB比Cache的标识存储器更小,更快

保证TLB的读出操作不会使Cache的命中时间延长

输入/输出系统

输入/输出系统的性能

输入/输出系统简称I/O系统

它包括:

  • I/O设备
  • I/O设备与处理机的连接

I/O系统是计算机系统的一个重要组成成分

  • 完成计算机与外界的信息交换
  • 给计算机提供大容量的外部存储器

按照主要完成的工作进行分类

存储I/O系统

通信I/O系统

系统的响应时间

从用户输入命令开始,得到结果所花费的时间

由两部分构成:

I/O 系统相应时间

CPU 处理时间

误区: 使用多进程技术可以忽略I/O性能对系统性能的影响

多进程技术只能够提高系统吞吐率,并不能减少系统相应时间

进程切换时可能需要增加I/O操作

课切换的进程数量有限,当I/O处理较慢时,仍然会导致CPU处于空闲状态

评价I/O系统性能的参数主要有:

连接特性

I/O系统的容量

响应时间和吞吐率

另外一种衡量I/O系统性能的方法

考虑I/O操作对CPU的打扰情况

即考查某个进程在执行时,由于其他进程的I/O操作,使得该进程的执行时间增加了多少

输入/输出系统的可靠性,可用性和可信性

处理器性能已经很高,人们更加关注系统可靠性

反映外设可靠性能的参数有:

  • 可靠性(Reliability)
  • 可用性(Availability)
  • 可用性(Dependability)

系统的可靠性: 系统从某个初始参考电开始一直连续提供服务的能力

用平均无故障时间MTTF(Mean Time to Failure)来衡量

MTTF 的倒数就是系统的失效率

如果系统种的每个模块的生存期服从指数分布,则系统整体的失效率是各部件的失效率之和

系统的可用性: 系统正常工作的时间在连续连词正常服务间隔时间种所占的比率

$可用性=\frac{MTTF}{MTTF+MTTR}$

MTTF+MTTR: 平均失效间隔时间MTBF(MTBF)

系统的可信性: 服务的质量. 即在大多程度可以合理的认为服务是可靠的(不可以度量)

提高系统组成部件可靠性的方法

有效构建方法(valid construction)

在构造系统的过程种消除故障隐患,这样建立起来的系统就不会出现故障

纠错方法(error correction)

在系统构建种采用容错的方法,这样即使出现故障,也可以通过容错信息保证系统正常工作。

廉价磁盘冗余阵列

总线

在计算机系统种,各子系统之间可以通过总线互相连接

优点: 成本低,多样性

主要缺点: 他是由不同的外设分时共享的,形成了信息交换的瓶颈,从而限制了系统中总的I/O吞吐量

总线的设计

技术难点

一个重要原因: 总线上信息传送的速度极大地受限于各种物理因素

总线的长度,设备的数目,信号的强度等等,这些物理因素限制了总线性能的提高

I/O操作相应快和高吞吐量可能造成设计需求上的冲突

设计总线时需要考虑的一些问题

特性 高性能 低价格
总线宽度 独立的地址和数据总线 数据和地址分时共用一套总线
数据总线宽度 越宽越快 越窄越便宜
传输快大小 块越大总线开销越小 单字传输更简单
总线主设备 多个(需要仲裁) 单个(无需仲裁)
分离事务 采用一一分离的请求包和回答包能够提高总线宽度 不采用一一持续连接成本更低,而且延迟更小
定时方式 同步 异步

分离总线事务

(又称: 流水总线,悬挂总线,包交换总线)

在有多个主设备时,可以通过打包技术来提高总线带宽

基本思想

将总线事务分成请求和应答两部分

在请求和应答之间的空闲时间内,总线可以供其他的I/O使用,这样就不必在整个I/O过程都独占总线

总线同步

包含一个供总线上所有设备使用的时钟,并且这些设备时基于该时钟按照一个固定的协议来发送地址和数据的

优点: 速度快,成本低

缺点: 总线操作都必须以同样的时钟频率进行

异步总线

没有同一的参考时钟,每个设备都有各自的定时方法

采用握手协议

总线标准和实例

和CPU的连接

I/O总线的物理连接方式有两种选择

连接到存储器上,更常见的连接到Cache

I/O总线连接到存储器总线上的方式

一种典型的组织结构

CPU对I/O设备的编制有两种方式

存储器映射I/O(也称为统一编址)

将一部分存储器地址空间分配给I/O设备,用load指令和store指令对这些地址进行读写将引起I/O设备的数据传输

给I/O设备独立编址

需要在CPU种设置专用的I/O指令访问I/O设备

CPU需要发出一个标志信号来表示所访问低地址时I/O设备的地址

CPU与外部设备进行输入输出的方式可分为4种

程序查询

中断

DMA

通道

通道处理机

通道处理机能够负担外围设备的大部分I/O工作.

通道处理机(简称通道): 专门负责整个计算机系统的输入/输出工作。通道处理机只能执行有限的一组输入/输出指令

通道的作用和功能

1 程序控制,中断和DMA方式管理外围设备会引起两个问题

所有外设的输入/输出工作均由CPU承担,CPU的计算工作经常被打断而区处理输入/输出的事务,不能充分发挥CPU的计算能力

大型计算机系统的外设虽然很多,但同时工作的机会不是很多

解决上述问题的方法: 采用通道处理机

一个典型的由CPU,通道,设备控制器,外设构成的4级层次结构的输入/输出系统

通道的功能

接收CPU发来的I/O指令,并根据指令要求选择指定的外设与通道相连接

执行通道程序

从主存中逐条取出通道指令,堆通道指令进行译码,并根据需要相被选中的设备控制器发出各种操作命令。

给出外设中要进行读/写操作的数据所在的地址(如磁盘存储器的柱面号,磁头号,扇区号等)

给出主存缓冲区的首地址

该缓冲区存放从外设输入的数据或者将要输出到外设中区的数据

控制外设与主存缓冲区之间的数据传送的长度

对传送的数据个数进行计数,并判断数据传送是否结束

指定传送工作结束时要进行的操作

例如: 将外设的中断请求及通道的中断请求送往CPU等

检查外设的工作是否正常,并将该状态信息送往主存单元保存。

在数据传输过程中完成必要的格式变换

例如: 吧字拆分为字节,或者把字节装配成字等

通道的主要硬件

寄存器

数据缓冲寄存器

主存地址计数器

传输字节数计数器

通道命令字寄存器

通道状态字寄存器

控制逻辑

分时控制

地址分配

数据传送,装配和拆分等

通道对外设的控制通过输入/输出接口和设备控制器进行

通道与设备控制器之间一般采用标准的输入/输出接口来连接

通道通过接口标准接口把操作命令送到设备控制器

设别控制器解释并执行这些通道命令,完成ming’l

通道的工作过程

1.通道完成一次数据输入/输出的工作过程

在用户程序种使用访管指令进入管理程序,由管理程序生成一个通道程序,并启动通道

用户在目标程序种设置一条广义指令,通过调用擦欧总系统的管理程序来实现。

管理程序根据关于指令提供的参数来编制通道程序。

启动输入/输出指令是一条主要的输入/输出指令,属于特权指令。

工作流程

图片

通道处理机执行通道程序,完成指定的数据输入/输出工作

通道处理机执行通道程序于与CPU执行用户程序是并行的。

通道程序结束后向CPU发中断请求。

CPU执行程序和通道执行程序的时间关系

图片

通道的种类

根据信息传送方式的不同,将通道分为三种类型

字节多路通道

数据通道

数组多路通道

三种类型的通道与CPU,设备控制器和外设的连接关系

1.字节多路通道

为多台低速或中速的外设服务

以字节交叉的方式分时轮流地为它们服务

以字节多路通道可以包含多个子通道,每个子通道连接一台设备控制器

2.选择通道

为多台高速外围设备服务

在一段时间内只为一台高速外设独占使用

选择通道的硬件

5个寄存器

数据缓冲寄存器,设备地址寄存器,主存地址计数器,交换字节计数器,设备状态/控制寄存器

格式变换部件

用于在主存和设备之间进行字与字节的拆分和装配

通道控制部件

3.数组多路通道

设用于高速设备

多次选择一个高速设备后传送一个数据块,轮流为多台设备服务

数组多路通道之所以能够并行地为多台高速设备服务,是因为虽然其所连设备的传输速率很高,但寻址等辅助操作时间很长。

通道种的数据传送过程与流量分析

通道流量

一个通道在数据传送周期,单位时间内能够传送的数据量。所用单位一般为Bps.

又称为通道吞吐率,通道数据传输率等

通道最大流量

一个通道在满负荷工作状态下的流量.

参数的定义

$T_s$: 设备选择时间,从通道响应设备发出的数据传送请求开始,到通道实际为这台设备传送数据所需要的时间。

$T_D$: 传送一个字节所用的时间

p: 在一个通道上连接的设备台数,且这些设备同时都在工作

n: 每台设备传送的字节数,这里设备每台设备传送的字节数都相同

k:数组多路通道传输的一个数据块种包含的字节数。

在一般情况下,k<n.对于磁盘,磁带等磁表面存储器,通常k=512.

T: 通道完成全部数据传送工作所需要的时间。

1.字节多路通道

数据传送过程

通道每连接一台外设,只传送一个字节,然后又与另一台设备连接,并传送一个字节。

p台设备每台传送n个数据总共需要的时间为

$T_{BYTE}=(T_S+T_D)\times p \times n$

最大流量

$f_{MAX-BYTE}=\frac{pn}{(T_S+T_D)pn}=\frac{1}{T_S+T_D}$

实际流量是在连接在这个通道上的所有设备的数据传送率之和

$f_{BYTE}=\sum\limits_{i=1}^{p}f_i$

$f_i$:第i台设备的实际数据传输率

选择通道

在一段时间内只能单独为一台高速外设服务,当这台设备的数据传送工作全部完成后,通道才能为另一台设备服务

p台设备每台传送n个数据总共所需的时间

$T_{SELECT}=(\frac{T_S}{n}+T_D)\times p\times n$

最大流量

$f_{MAX-SELECT}=\frac{pn}{(\frac{T_S}{n}+T_D)pn}=\frac{1}{\frac{T_s}{n}+T_D}$

多组数据通道

工作过程

p台设备每天传送n个数据总共所需的时间为

$T_{BLOCK}=(\frac{T_s}{k}+T_D)\times p\times n$

$f_{MAX-BLOCK}=\frac{pn}{(\frac{T_S}{n}+T_D)pn}=\frac{1}{\frac{T_s}{n}+T_D}$

选择通道和数组多路通道的实际流量就是连接在这个通道上的所有设备种数据流量最大的那一个。

$f_{BLOCK}\leq \max\limits_{i=1}^{p} f_i$

$f_{SELECT}\leq \max\limits_{i=1}^{p} f_i$

各种通道的实际流量应该不大于通道的最大流量

$f_{BYTE}\leq f_{MAX-BYTE}$

$f_{BLOCK}\leq f_{MAX-BYTE}$

$f_{SELECT}\leq f_{MAX-BYTE}$

两边的差值越小,通道的利用率就越高。

等两边相等时,通道处于满负荷工作状态。

题目

img

例题 假设一台计算机的I/O处理时间占相应时间的10%,当I/O性能保持不变,而对CPU的性能分别提高10倍和100倍时,该计算机的性能会发生什么样的变化

设改进前程序的执行时间为1个单位时间

如果

习题

总线仲裁

  • 要解决的问题
  • 方法和特点

解决的是多个设备竞争使用总线的管理问题

集中仲裁和分布仲裁

集中式多采用CPU为仲裁器,可以实现计数器式查询,链式查询,独立查询三种方式

分布式仲裁的仲裁器为各个参与的主设备,实现所谓”比大小”的仲裁方式,最终获胜的主设备获得总线的使用权

总线的通信控制解决的问题是什么,大致方式

目的 解决主设备和从设备的协调调度配合问题

同步数据输入/输出

异步数据输入/输出

半同步通信方式

请自行查阅资料,说明程序查询方式的工作过程。

CPU启动外设工作后,不断地读取外设的状态信息进行测试,查询外设是否准备就绪,如果准备号,则可以进行数据传送;否则,CPU继续读取外设的状态信息进行查询准备,直到外设准备好

请自行查阅资料,说明程序中断方式的工作过程。

当主机启动外设后,无需等待查询,而是继续执行原来的程序,外设在做好输入输出准备时,向主机发出中断请求,主机接到请求后就暂时中止原来执行的程序,转去执行中断服务程序对外部请求进行处理,在中断处理完毕后返回原来的程序继续执行

请自行查阅资料,说明DMA的工作过程。

1外设可通过DMA控制器向CPU发出DMA请求;

2CPU响应DMA请求,系统转变为DMA工作方式,并把总线控制权交给DMA控制器;

3由DMA控制器faculty存储器地址,并决定传送数据块的长度

4 执行DMA传送

5DMA操作结束,并把总线控制权交还CPU

请自行查阅资料,试比较程序查询、程序中断、DMA三种I/O方式的区别。

CPU需要根据外设的工作状态来决定何时进行数据传送,它要求CPU随时对结构状态进行查询,如果接口尚未准备好,CPU需要等待,并进行查询,只有接口准备好,CPU才进行数据的输入输出。它的的特点是简单,只需少量硬件,主要编制程序执行为主

程序中断方式: CPU在执行的程序的过程中,出现某些突然时间待处理,CPU

img

指令 流出 执行 写结果
DIV.D F4,F2,F0 1 2-21 22
SD.D F4,0x05(R1) 2 3-4 23
ADD.D F10,F8,F0 3 4-7 8
LD.D F6,0x08(R2) 4 24-25 26
SUB.D F0,F2,F6 5 27-30 31

最终状态

索引 R1 R2 F0 F2 F4 F6 F8 F10 #0xC3 #0xC8
数值 oxC3 oxC0 0B-(0B/05) 0x0B OB/05 0B/05 05+03 05+03 0x04 0B/05

4.18

备注:标识用二进制,不命中率用分数。

img

主存11位, cache 5位 指令2位

每块3位

标识 索引 位移
6 2 3

OK 00000 1 00000

1
2
3
4
5
6
7
8
9
10
Tag      
000001 00 000
000001 00 100
000001 01 000
000001 01 100
000001 10 000
000001 10 100
000001 11 000
000001 11 100
000010 00 000

复习

简答题

  1. 简述计算机系统的层次结构(从计算机语言的角度)。
  2. 什么是虚拟机?为什么要使用虚拟机?
  3. 什么是翻译?什么是解释?
  4. 计算机系统结构、计算机组成和计算机实现三者之间的关系,并举例说明。
  5. 什么是软件的可移植性?实现软件可移植性的常用方法有哪三种?
  6. 什么是模拟?什么是仿真?
  7. Flynn分类法将计算机系统结构分成哪四类?请简述。
  8. 请简述程序局部性原理。
  9. 简述Amdahl定律。
  10. 影响CPU时间的因素包括什么?(提示:从CPU公式入手,考虑3个参数的影响因素)
  11. 冯诺依曼体系结构的特点。
  12. 简述现代计算机对比冯诺依曼体系结构,在哪几个方面进行了改进。
  13. 什么是系列机?什么是兼容机?
  14. 什么是软件兼容?软件兼容有几种?其中哪一种是软件兼容的根本特征?
  15. 什么是并行性?
  16. 简要说明提高计算机系统并行性的3种技术途径,并分别从单机和多机系统的角度举例。
  17. 增强CISC机器的指令功能主要从哪几方面着手?
  18. 简述CISC存在的主要问题。
  19. 简述RISC的优缺点及设计RISC机器的一般原则。
  20. 根据CPU内部存储单元类型,可将指令集结构分为哪几类?
  21. 常见的三种通用寄存器型指令集结构是什么?
  22. 计算机指令集结构设计所涉及的内容有哪些?
  23. 流水技术有哪些特点?
  24. 什么是静态流水线?什么是动态流水线?
  25. 什么是单功能流水线?什么是多功能流水线?
  26. 什么是线性流水线?什么是非线性流水线?
  27. 列举3种相关。
  28. 流水线中有哪三种冲突?各是什么原因造成的?
  29. 选择至少2种解决流水线结构冲突的方法简述。
  30. 选择至少2种解决流水线数据冲突的方法简述。
  31. 选择至少2种解决流水线控制冲突的静态方法简述。
  32. 简述流水寄存器的作用。
  33. 简述分支延迟槽的主要思想。
  34. 简述分支延迟槽的三种调度策略。
  35. 简述流水线冻结/排空策略。
  36. 什么是静态调度?什么是动态调度?动态调度的优点是什么?
  37. 简述Tomasulo算法的基本思想。
  38. 什么是动态分支预测?有何优点?
  39. 简述分支历史表BHT的基本思想。
  40. 简述分支目标缓冲器BTB的基本思想。
  41. 简述基于硬件的前瞻算法基本思想。
  42. 单级存储器的主要矛盾是什么?通常采取什么方法来解决?
  43. “Cache-主存”和“主存-辅存”层次的主要区别是什么?
  44. 在存储层次中应解决哪四个问题?
  45. 简述Cache的基本工作原理。
  46. 在Cache-主存层中,地址映像方法有哪几种?它们各有什么优缺点?
  47. 简单使用比较器进行4路组相联Cache并行查找的过程。
  48. Cache-主存层常用的替换算法有哪些?
  49. 简述Cache写命中时的两种写策略。
  50. 简述Cache写失效的两种处理方法。
  51. 影响平均访存时间的因素有哪些?针对每个因素,各举出1种改进方法。
  52. Cache的3C失效是哪三种失效?针对每种失效给出一种降低失效率的方法。
  53. 多体交叉存储器有哪两种编址方式?各有什么特点。
  54. 反映输入/输出系统可靠性能的参数有哪些?
  55. 总线仲裁要解决的是什么问题,总线仲裁的方法有哪些,各有什么特点。
  56. 总线的通信控制解决的是什么问题?大致有哪些方式。
  57. 试比较程序查询、程序中断、DMA三种I/O方式的区别。
  58. 简述通道的主要功能。
  59. 简述通道完成一次数据传输的主要过程。
  60. 简述三种通道传输方式及其传输过程。