计算机系统结构 概述 & 流水线
第一章 概述
虚拟机
-
虚拟机是一个抽象的计算机
-
由软件实现
-
具有指令集,使用不同的存储区域
计算机系统的层次结构
- 微程序解释指令系统属于仿真
解释与翻译
通常L1L3级是用解释方法,L4L6是用翻译方法
解释执行比编译后再执行所花的时间多,但占用的存储空间较少
共同点:
都是以执行一串L级指令来实现高一级的L+1指令
不同点:
解释是每当一条L+1级指令被译码后马上执行一串等效L级指令
翻译是将L+1级程序全部变换为L级程序后再去执行新产生的L级程序
计算机系统结构定义
定义一:Amdahl定义
对计算机系统而言,是指那些由程序员所看到的系统属性,即概念性结构与功能特性
汇编语言,机器语言,编译程序,操作系统
如数据表示、寻址方式、寄存器组织、指令系统、中断系统、存储系统、处理机工作状态、输入输出系统、信息保护等。
定义二:
计算机系统的软、硬件的界面,即机器语言程序员所看到的传统机器级所具有的属性。
定义三(广义的系统结构定义)
计算机设计的三个方面:指令系统结构、组成、硬件
透明性
在计算机技术中,把这种本来存在的事物或属性,但从某种角度看又好像不存在的概念称为透明性。
计算机组成和计算机实现
计算机系统结构:计算机系统中软、硬件的界面
计算机组成:计算机系统结构的逻辑实现
- 具有相同系统结构的计算机可以采用不同的计算机组成
计算机实现:计算机组成的物理实现
- 同一计算机组成又可以采用多种不同的计算机实现
计算机系统结构的分类
可以按大小、用途、数据类型(定点、浮点、向量、堆栈)、处理机个数(单处理机、并行处理机、超标量处理机)、使用的器件(电子管、晶体管)进行分类。
Flynn佛林分类法
按照指令流和数据流的多倍性特征对计算机系统进行分类
- 指令流(Instruction Stream)计算机执行的指令序列
- 数据流(Data Stream)由指令流调用的数据序列
- 多倍性(Multiplicity)在系统最受限的部件上,同时处于统一执行阶段的指令或数据的最大数目
于是就有以下分类:
-
单指令流单数据流(SISD)
最传统的顺序处理计算机,也有标量流水线处理机
-
单指令流多数据流(SIMD)
阵列处理机(多个处理部件同时处理一条指令),向量流水线处理机
-
多指令流单数据流(MISD)
无实际机器
-
多指令流多数据流(MIMD)
多处理机
看CU个数判断指令I,看PU个数判断数据D
冯氏分类法
用系统的最大并行度对计算机系统进行分类
最大并行度:计算机系统在单位时间内能够处理的最大的二进制位数。
用平面直角坐标系中的一个点代表一个计算机系统
其横坐标表示字宽(n位),纵坐标表示一次能同时处理的字数(m字)。mxn就表示了其最大并
行度。
Handler分类法
Amdahl定律
系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高,与这种执行方式的使用频率或占总执行时间的比例有关。
如果仅仅对计算任务中的一部分做性能改进,则改进得越多,所得到的总体性能的提升就越有限(即Se趋向无限时,Sn=1/(1-Fe))。
如果只针对整个任务的一部分进行改进和优化,那么所获得的加速比不超过1/(1-可改进比例)
CPU性能公式
一个程序所花的系统时间
结论:CPU的性能与3个要素有关:
- 时钟频率f
- CPI (Cycles Per Instruction)
- 指令条数IC
其中时钟频率f取决于硬件技术和组织,CPI取决于计算机组成和指令集,指令数目IC取决于系统结构的指令集和编译技术。
不同指令的CPU性能公式
也就是说,总CPI是(各指令的条数占总指令条数之比) 乘 (各指令的CPI) 之和
性能平衡问题
摩尔定律
集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。换言之,处理器的性能大约每两年翻一倍,同时价格下降为之前的一半
性能平衡问题
动态RAM、IO系统等计算机其他组件发展速度跟不上处理器发展速度,
寻求性能平衡需要:调整组织与结构
性能评测
执行时间(响应时间)
时间从发生到结束的时间
"甲机器比乙机器快n倍” 的含义应该是:
吞吐率
每个时间周期内完成的任务数
MIPS
每秒执行百万指令数
MFLOPS
每秒执行百万浮点运算指令数
冯诺依曼结构
IO、存储器、运算器、控制器
- 以运算器为中心
- 在存储器中,指令和数据同等对待,指令和数据一样可以进行运算,即由指令组成的程序是可以修改的。
- 存储器是按地址访问的按顺序线性编址的一维结构
- 指令的执行是顺序的
- 一般是按照指令在存储器中存放的顺序执行。
- 程序的分支由转移指令实现。
- 由指令计数器PC指明当前正在执行的指令在存储器中的地址。
- 指令由操作码和地址码组成
- 指令和数据均以二进制编码表示,采用二进制运算
改进结构可以以存储器为中心,分散控制
软件对系统结构的影响
可移植性
一个软件不经修改或者只需要少量修改就可以由一台计算机一直到另一台计算机上运行。
实现可移植性的3种常用方法:
采用系列机 (相同系统结构):
由同一厂家生产的具有相同的系统结构,但具有不同组成和实现的一系列不同型号的机器。
系列机的软件兼容:
向上(下)兼容:按某档机器编制的程序,不加修改就能运行于比它高(低)档的机器。
向前(后)兼容:按某个时期投入市场的某种型号机器编制的程序,不加修改地就能运行于在它之前(后)投入市场的机器。
向后兼容是系列机的根本特征。
思想与系列及一致:兼容机:由不同公司厂家生产的具有相同系统结构的计算机 。
模拟和仿真
对于使用频度低和难以用仿真实现的指令使用模拟:用软件的方法在一台现有的机器(称为宿主机)上实现另一台机器(称为虚拟机)的指令集。
对于使用频度较高的指令用仿真:用一台现有机器(宿主机)上的微程序去解释实现另一台机器(目标机)的指令集。
统一高级语言
实现软件移植的一种理想的方法,如JAVA
1.5 计算机系统结构中并行性的发展
并行性的概念
同时性:计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。
包括同时性和并发性两种含义
并行性:两个或两个以上的事件在同一时刻发生。
并发性:两个或两个以上的事件在同一时间间隔内发生。
从处理数据的角度来看,并行性等级从低到高可分为:
字串位串:每次只对一个字的一位进行处理。最基本的串行处理方式,不存在并行性。
字串位并:同时对一个字的全部位进行处理,不同字之间是串行的。
字并位串:同时对许多字的同一位(称为位片)进行处理。
全并行:同时对许多字的全部位或部分位进行处理。
从执行程序的角度来看,并行性等级从低到高可分为:
指令内部(微指令级)并行:单条指令中各微操作之间的并行。
指令级并行(ILP):并行执行两条或两条以上的指令。
线程级并行(TLP):并行执行两个或两个以上的线程。
任务级或进程级并行:并行执行两个或两个以上的过程或任务(程序段)
作业或程序级并行:并行执行两个或两个以上的作业或程序。
提高并行性的技术途径
三种途径:
- 时间重叠
引入时间因素,让多个处理过程在时间上相互错开轮流重叠地使用同一套硬件设备的各个部分,以加快硬件周转而赢得速度。(如流水线技术) - 资源重复
引入空间因素,以数量取胜。通过重复设置硬件资源,大幅度地提高计算机系统的性能。(如超线程、多核、多处理器技术) - 资源共享
这是一种软件方法,它使多个任务按一定时间顺序轮流使用同一套硬件设备。(如分时系统)
单机系统中并行性的发展
- 在发展高性能单处理机过程中,起主导作用的是时间重叠原理。
实现时间重叠的基础:部件功能专用化 - 在单处理机中,资源重复原理的运用也已经十分普遍
- 在单处理机中,资源共享的概念实质上是用单处理机模拟多处理机的功能,形成所谓虚拟机的概念。
多机系统中并行性的发展
多机系统也遵循时间重叠、资源重复、资源共享原理,发展为3种不同的多处理机:异构型多处理机、同构型多处理机、分布式系统
耦合度:
反映多机系统中各机器之间物理连接的紧密程度和交互作用能力的强弱。
紧密耦合系统(直接耦合系统):
在这种系统中,计算机之间的物理连接的频带较高,一般是通过总线或高速开关互连,可以共享主存。
松散耦合系统(间接耦合系统):
一般是通过通道或通信线路实现计算机之间的互连,可以共享外存设备(磁盘、磁带等)。机器之间的相互作用是在文件或数据集一级上进行的。
功能专用化(实现时间重叠 ):
异构型多处理机系统:
由多个不同类型、至少担负不同功能的处理机组成,它们按照作业要求的顺序,利用时间重叠原理,依次对它们的多个任务进行加工,各自完成规定的功能动作。
机间互连:
同构型多处理机系统:
由多个同类型或至少担负同等功能的处理机组成,它们同时处理同一作业中能并行执行的多个任务。
第二章 指令流水线-时间并行
结构
锁存器
流水线每一个功能部件的后面都要有一个缓冲寄存器(锁存器),称为流水寄(锁)存器。
作用:在相邻的两段之间传送数据,以保证提供后面要用到的数据,并把各段的处理工作相互隔离。
特点
- 流水线把一个处理过程分解为若干个子过程(段),每个子过程由一个专门的功能部件来实现。
- 流水线中各段的时间应尽可能相等,否则将引起流水线堵塞、断流,时间长的段将成为流水线的瓶颈。
- 效率
- 连续不断地使用(同一种功能)
- 通过(装入)时间一第一个任务从进入到流出
- 排空时间一最后一个任务从进入到流出
分类
按等级
- 部件级
- 处理机级
- 系统级
按功能的多倍性
- 单功能流水线:只能完成一种固定功能的流水线,如浮点加法器流水线、浮点乘法器流水线
- 多功能流水线:流水线各段可以进行不同的连接,不同连接方式实现不同功能
多功能流水线下的进一步分类
- 静态流水线:在同一时间,多功能流水线的各段按照同一种功能的连接方式工作。通常只有输入是一串相同运算任务时,才能发挥流水线的效率。如同时支持加法和乘法的流水线,不能在同一时间既运行加法任务又运行乘法任务,即使使用流水线中的空闲部件也不行,需要等流水线中加法任务完毕后再执行乘法任务
- 动态流水线:在同一时间,多功能流水线的各段可以按照不同的连接方式,同时执行多种功能
按照连接方式
- 线性流水线:流水线各段串行连接,没有反馈回路,每段最多只流过一次
- 非线性流水线:流水线各段串行连接,但也有反馈回路,使得某些阶段可以重复执行
按照流入流出顺序
-
顺序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每个任务在流水线的各段中是一个跟着一个顺序流动的
-
乱序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同,允许后进入流水线的任务先完成(从输出端流出)。也称为无序流水线、错序流水线、异步流水线
线性流水线又可按照控制方式
- 同步流水线
- 异步流水线
性能指标
吞吐率
单位时间内,流水线完成的任务数量,即输出结果的数量
可见,最大吞吐率与系统一个时钟周期长度有关。
对于各段执行时间不同的,以最长的那一段为准:
解决瓶颈段问题
流水线中这种时间最长的段(S3)称为流水线的瓶颈段
细分瓶颈段
那么时空图就会将原来的S3划分为三小段(图里是S2为瓶颈段)
重复设置瓶颈段
资源重复,控制逻辑比较复杂,所需的硬件增加
例如:对前面的4段流水线重复设置瓶颈段S3:S3a,S3b,S3c
加速比
当n趋于无穷时,S = k
如果各段执行不相等,
所以,k越大,加速比越高;但会带来硬件上的设计问题和延迟时间问题。
效率
对相同执行时间的段,
n趋向无穷时,E=1
对各段执行时间不相同的段
关系
总结一下,
故有以下关系( 相同时):
流水线的相关问题
瓶颈问题
时间最长的那一段为瓶颈段
额外开销
流水寄存器延迟和时钟偏移开销
- 流水线并不能减少(而且一般是增加)单条指令的执行时间,但却能提高吞吐率。
- 增加流水线的深度(段数)可以提高流水线的性能。
- 流水线的深度受限于流水线的额外开销。
- 当时钟周期小到与额外开销相同时,流水己没意义。因为这时在每一个时钟周期中已没有时间来做有用的工作。
冲突问题
流水线设计中要解决的重要问题之一
- 结构冒险
- 数据冒险
- 控制冒险
RISC
- 大多数指令在单周期内完成
- LOAD/STORE结构
- 硬布线控制逻辑(而CISC使用微程序)
- 减少指令和寻址方式的种类
- 固定的指令格式
- 注重编译优化技术
- 单一指令长度 (4bytes)
- 较少的寻址方式(一般≤5)
- 无间接寻址
- 每条指令最多有一个存储器操作数
- LOAD/STORE指令不会与算术运算混在一起
- 整数寄存器有32个以上,浮点寄存器(如果有)有16个以上
MIPS五段流水线
冲突
数据相关
也称真数据相关(写后读 RAW)
对于两条指令i(在前,下同)和j(在后,下同),如果下述条件之一成立,则称指令j与指令i数据相关。
(1)指令j使用指令i产生的结果;
(2)指令j与指令k数据相关,而指令k又与指令i数据相关。
数据相关具有传递性。
数据相关反映了数据的流动关系,即如何从其产生者流动到其消费者。
名相关
两条指令使用相同的名,但是之间没有数据流动,则他们存在名相关
-
反相关(读后写 WAR)
-
输出相关(写后写 WAW)
换名机制:将寄存器换名,消除反相关(读后写)
控制相关
由分支指令引起的相关
-
一条分支指令控制相关的指令不能被移到该分支之前,否则这些指令就不受该分支控制。
then 部分中的指令不能移到i语句之前。 -
如果一条指令与某分支指令不存在控制相关,
就不能把该指令移到该分支之后。
不能把S移到语句的then部分中。
流水线冲突
带来的问题:流水线可能会出现停顿,从而降低流水线的效率和实际的加速比甚至导致错误的执行结果
约定:
当一条指令被暂停时,在该暂停指令之后流出的所有指令都要被暂停,而在该暂停指令之前流出的指令则继续进行 (否则就永远无法消除冲突)
数据冲突
当指令在流水线中重叠执行时,因需要用到前面指令的执行结果而发生的冲突
当相关的指令靠得足够近时,它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序,使之不同于它们非流水实现时的顺序,则发生了数据冲突。
对于五段按序流出的流水线,只会发生写后读(RAW)冲突,即上一条语句要写入寄存器前,下一条语句便已经从寄存器读了。这是因为,按序流出的流水线,上一条语句的读一定发生在下一条语句的读之前,写一定发生在下一条语句写之前,能够发生的只有写后读冲突。
通过定向技术减少数据冲突引起的停顿(定向技术也称为旁路或短路)
关键思想:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令需要它的地方,那么就可以避免停顿。
并不是所有的数据冲突都可以用定向技术来解决。
举例:
LD R1,0(R2)
DADD R4,R1,R5
AND R6,R1,R7
XOR R8,R1,R9
解决方法:增加流水线互锁(pipeline interlock)硬件,插入“暂停stall”。
作用:检测发现数据冲突,并使流水线停顿,直至冲突消失。
静态调度:依靠编译器重新组织指令顺序,以消除冲突,也称指令调度或流水线调度
结构冲突
因硬件资源满足不了指令重叠执行的要求而发生的冲突。
-
资源份数不够
-
功能部件不是完全流水
方法:
-
插入暂停周期
-
将数据与指令分离(分时)存取,如分离cache,双端口RAM,哈佛结构等
-
预取指令技术:在重叠操作中,在前一条指令的执行过程中,就提前取出后面的指令进行相应处理
控制冲突
流水线遇到分支指令和其他会改变pc的指令所引起的冲突。
执行分支指令的结果有两种
- 分支成功:PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后,才改变PC值(MEM段)。
- 不成功或者失败:PC的值保持正常递增,指向顺序的下一条指令。
处理分支指令最简单的方法:“冻结”或者“排空”流水线 。
前述5段流水线中,改变PC值是在MEM段进行的。给流水线带来了三个时钟周期的延迟:
硬件方法
可采取两种措施来减少分支延迟:
- 在流水线中尽早判断出分支转移是否成功;
- 尽早计算出分支目标地址。
两个尽早必须同时采用,缺一不可。
软件方法
3种通过软件(编译器)来减少分支延迟的方法。
共同点:
-
对分支的处理方法在程序的执行过程中始终是不变的,是静态的。
-
要么总是预测分支成功,要么总是预测分支失败
-
预测分支失败
(做的事)允许分支指令后的指令继续在流水线中流动,就好象什么都没发生似的。
(实际上)若确定分支失败,将分支指令看作是一条普通指令,流水线正常流动。
(实际上)若确定分支成功,流水线就把在分支指令之后取出的所有指令转化为空操作,并按分支目地重新取指令执行。需要保证分支结果出来前不会改变处理机的状态,以便猜错时处理机回退到之前的状态
-
预测分支成功
假设分支转移成功,并从分支目标地址处取指令执行。
起作用的场合:先知道分支目标地址,后知道分支是否成功的系统中。在前述 5 段流水线中,由于判断分支是否成功与分支目标地址计算是在同一流水段完成的,所以这种方法对减少该流水线的分支延迟没有任何好处。但在其他的一些流水线处理机中,特别是那此具有隐含设置条件码或分支条件更复杂(因而更慢)的流水线处理机中,在确定分支是否成功之前,就能得到分支的目标地址。这时采用这种方法便可以减少分支延迟
-
延迟分支
在分支指令后面加上m条指令(延迟槽),把它们看成一个整体。不管分支是否成功,都顺序执行这些指令。
分支延迟指令的调度:在延迟槽中放入有用的指令。
分支延迟可以使原来在EX段才能完成的分支计算提前一个周期,到ID段就完成
-
取消分支
当分支的实际执行方向和事先所预测的一样时,执行分支延迟槽中的指令,否则就将分支延迟槽中的指令转化成一个空操作。(动态调度)