【必威】系统结构复习提纲

计算机的流水处理过程同工厂中的流水装配线类似。为了实现流水,首先必须把输入的任务分割为一系列的子任务,使各子任务能在流水线的各个阶段并发地执行。将任务连续不断地输入流水线,从而实现了子任务的并行。因此流水处理大幅度地改善了计算机的系统性能,是在计算机上实现时间并行性的一种非常经济的方法。

本文导读:

第1章 计算机系统结构基础及并行性的开发

输入输出(I/O)接口

  • I/O系统的工作方式
    • 程序控制:CPU使用I/O指令编程控制,需要不停的查询I/O系统是否完成指令
    • DMA 使用DMA控制器(Direct Memory
      Access)和CPU共享系统总线,在进行DMA时 CPU放弃系统总线控制器
      [处理速度最快,CPU无需介入]
    • 程序中断
      当I/O系统与设备交换数据时,CPU无需等待数据交换,当数据交换完成时I/O系统发送中断信号通知CPU,CPU保存现场后,完成I/O系统后续动作后,返回中断现场
      [对突发时间做处理]
    • 通道
      通过通道程序管理I/O系统和控制器,每当用户请求启动外设时,会构造通道程序和通道状态字

      • 字节多路通道
      • 选择通道
      • 数据多路通道
    • I/O处理机 相比通道方式,指令更丰富,有局部存储器,适用于大型机
  • 总线原理:从两个或两个以上源部件传送信息(指令、数据和地址)到一个或多个部件的一组传输线,
    如一根传输线仅用于连接
    一个源部件(输出)和一个或多个目的部件(输入),则不称为总线
  • 总线分类
    • CPU与其他芯片位置划分
      • 内部总线(适用范围:CPU内部的ALU,寄存器,控制部件之间的数据通信)
      • 外部总线(适用范围:***CPU与其他组件
        ***RAM、ROM和I/O设备的数据通路)
    • 功能划分
      • 数据总线 传输数据
      • 地址总线 传输地址
      • 控制总线 传输控制信号量
      • 工业标准 ISA总线 划分
        98条线,数据线16条,地址线24条,其余是控制线
    • 总线在计算机的位置
      • 机内总线 CPU与其他芯片的连接
      • 机外总线 与外设相连的接口标准
    • 总线扩展
      • 局部总线
        在原有总线规范成为性能瓶颈时,在CPU和ISA之间增加的一级总线或者是管理层
      • 系统总线 插背板之间数据通信一组信号线
      • 通信总线 和外设通信的一组信号线
  • 总线速度 最终会成为 性能的瓶颈
  • 总线接口
    • 串行接口一次发送1
      bit信息,通信连线少,适合长距离传输,传输慢,控制复杂

      • 同步通信
      • 异步通信
    • 并行接口一次发送多
      bit信息(8的倍数),通信连接多,高速数据传输,传输快,控制简单
  • 设备接口
    • SCSI
      • 大容量存储设备设备的标准。SCSI设备彼此独立运行,相互交互数据,数据以分组方式传输,最大可以达到5Gbps(640MB/s)
    • ESDI
    • IDE
    • PCMCIA
    • IEEE-1394
    • USB

                                   一、概要

1、数据的表示:数制及其转换、原码、反码、补码、移码、浮点数、溢出、算术运算、逻辑运算、校验码。

2、计算机系统的组成、体系结构分类及特性:CPU、存储器的组成、性能和基本工作原理、常用I/O设备、通信设备的性能及基本工作原理、I/O接口的功能、类型和特性、CISC/RISC、流水线操作、多处理机、并行处理。

3、存储系统:虚拟存储器基本工作原理、多级存储体系、RAID类型和特性。

4、可靠性与系统性能评测:诊断与容错、系统可靠性分析评价、校验方法、计算机系统性能评测方法。

流水线的原理。流水线的基本原理是把一个重复的过程分解为若干个子过程,前一个子过程为下一个子过程创造执行条件,每一个过程可以与其它子过程同时进行。流水线各段执行时间最长的那段为整个流水线的瓶颈,一般地,将其执行时间称为流水线的周期。加速比
= 采用流水线后的速度/未采用流水线的速度。=
未采用流水线的时间/采用流水线后的时间。流水线的设备利用率,在时空图上表现为n个任务占用的时空区与k个
功能段总的时空区之比。

一、并行技术
1.并行技术分类
2.新技术的设计与实现
3.指令周期

二、流水线技术
1.什么是流水线
2.指令重叠方式
3.流水工作设计
4.流水线的描述方法(时空图)
5.流水线特点

三、流水线的分类(了解)

四、流水线相关及冲突(重点)
1.流水线相关
2.流水线冲突
3.流水线冲突带来问题
4.数据冲突及其解决方案
5.结构冲突及其解决方案
6.控制冲突及其解决方案

五、流水线性能分析(含例题讲解)
1.流水线的基本参数——吞吐率
2.流水线的基本参数——加速比
3.流水线的基本参数——效率
4.结果分析
5.有关流水线性能的若干问题

六、循环展开优化
1.指令调度
2.循环展开

七、多指令流出技术(拓展了解)
1.超标量
2.超长指令字

1.2 计算机系统结构、组成、实现

计算机系统结构、组成、实现三者互不相同,但又相互影响。

各种体系结构

                                二、数据表示

       
数据的表示部分包含了数据转换、原码、反码、补码、移码以及浮点运算知识。其中难点是浮点计算。

1、数制转换

(1)R进制数转换成十进制数

     
R进制数转换成十进制数通常使用按权展开法。具体操作方式为:将R进制数的每一位数值用Rk形式表示,即幂的底数是R,指数为k,k与该位和小数点之间的距离有关。当该位位于小数点左边,k值是该位和小数点之间数码的个数,而当该位位于小数点右边,k值是负值,其绝对值是该位和小时点之间数码的个数加1.

     例如二进制数l0100.01的值可计算如下:

必威 1

按照上面的表示法,即可计算出R进制数十进制的值。

(2)十进制数转换为R进制数

最常用的是“除以R取余法”,如将十进制94转换为二进制数:

必威 2

将所得的余数从低位到高位排列(1011110)2 就是94的二进制数。

(3)二进制数与八进制数、十六进制数之间的转换

二进制转八进制:将每3个二进制数转换为八进制数;

二进制转十六进制:将每4个二进制数转换为十六进制数;

八进制转二进制:将每个八进制数转换为3位二进制数;

十六进制转二进制;将每个十六进制数转换为4位二进制。

       
上面的转换都是以小数点作为计数码个数的起点。八进制数和十六进制数转换,可先转换为二进制数,然后再转换为目标进制。

2、原码、反码、补码、移码

在计算机中,数据编码方式可以有多种,最为常见的有原码、反码、补码、移码。一个正数的原码、反码、补码是相同的,负数则不同。

(1)原码

将最高位用做符号位(0表示正数,1表示负数),其余各位代表数值本身的绝对值的表示形式。这种方式是最容易理解的。

例如,+1 的原码是0000 0001,–1 的原码是1000 0001.

但是直接使用原码在计算时却会有麻烦,比如(1)10 + (-1)10 =
0,如果直接使用原码则:

必威 3

这样计算的结果是-2,也就是说,使用原码直接参与计算可能会出现错误的结果。所以,原码的符号位不能直接参与计算,必须和其他位分开,这样会增加硬件的开销和复杂性。

(2)反码

正数的反码与原码相同。负数的反码符号位为1,其余各位为该数绝对值的原码按位取反。这个取反的过程使得这种编码称为“反码”。

例如,–1的反码:1111 1110 。

 同样对上面的加法,使用反码的结果是:

必威 4

这样的结果是负0,而在人们普遍的观念中,0是不分正负的。反码的符号位可以直接参与计算,而且减法也可以转换为加法计算。

(3)补码

正数的补码与原码相同。负数的补码是该数的反码加1,这个数加1救赎“补”。

例如,–1的补码:1111 1110+1 = 1111 1111。

再次做加法是这样的:

必威 5

直接使用补码进行计算的结果是正确的。

对一个补码表示的数,要计算其原码,只要对它再次求补,可得该数的原码。

由于补码能使符号位与有效值部分一起参加运算,从而简化运算规则,同时它也使减法运算转换为加法运算,进一步简化计算机中运算器的电路,这使得在大部分计算机系统中,数据都使用补码表示。

(3)移码

移码是对补码的符号位取反得到的一种编码。移码只用于表示浮点数的阶码,所以只用于整数。例如,-1的移码为:0111
1111.

3、浮点数计算

在数学中,要表示一个很大的数时,我们常常使用一种称为科学计数法的方式:

                                                     N = M * Re

其中M称为尾数,e是指数,R为基数。

浮点数就是使用这种方法来表示大范围的数,其中指数一般是2,8,16。而且对于特定机器而言,指数是固定不变的,所以在浮点数中指数并不出现。从这个表达式可以看出:浮点数表示的精度取决于尾数的宽度,范围取决于基数的大小和指数的宽度。

浮点数的运算主要有三个步骤:对阶、尾数计数、结果格式化。

(1)对阶

首先计算两个数的指数差,把指数小的向指数大的对齐,并将尾数右移指数差的位数,这样两个浮点数就完成了对阶的操作。可以看出,对阶的过程可能使得指数小的浮点数失去一些有效位。如果两个浮点阶数相差很大,大于指数小的浮点数的位数宽度,那么对阶后那个浮点数的位数就变成了0,即当做机器零处理了。

(2)尾数计算

对阶完成后,两个浮点数尾数就如同定点数,计算过程同定点数计算。

(3)结构格式化

尾数计算后,可能会产生溢出,此时将尾数右移,同时指数加1,如果指数加1后发生了溢出,则表示两个浮点数的运算发生了溢出。

如果尾数计算没有溢出,则尾数不断左移,同时指数减1,直道尾数为格式化数。如果这个过程中,指数小于机器能表达的最小数,则将结果置“机器零”,这种情况称为下溢。

 

1.3 计算机系统的软、硬件取舍和性能评测及定量设计原理

指令系统

  • 复杂指令系统计算机(CISC)
    • 指令多
    • 指令使用频率相差悬殊
    • 支持多种寻址方式
    • 指令长度不固定
    • 大量指令对存储器单元中的数据直接处理(读取存储器的效率很低,应该读取寄存器)
  • 精简指令系统计算机(RISC)
    • CPU 寄存器多
    • 选择频率高的简单指令、使用率搞不复杂的指令
    • 指令长度固定、种类少、寻址种类少
    • 较少访问存储器、尽可能的放在寄存器
    • 大多数采用Cache,以及 流水线 组织

                    三、计算机系统的组成与体系结构

       
在计算机系统的组成与体系结构中,计算机体系结构分类、指令系统基数、CISC与RISC、流水线操作等内容是最为重要的。

1、计算机体系结构分类

计算机体系结构分类有多种方式,其中最为常见的是:FLynn分类法与冯氏分类法。

Flynn 分类法是根据指令流、数据流和多倍性三个方面来进行分类的:

必威 6

2、计算机的硬件组成

计算机硬件系统由运算器、控制器、存储器、输入设备和输出设备五大部件组成。其中运算器和控制器组成中央处理器(CPU)。运算器负责完成算术、逻辑运算功能,通常由ALU(算术/逻辑单元)、寄存器、多路转换器、数据总线组成;控制器则负责依次访问程序指令,进行指令译码,并协调其他设备,通常由计数器(PC)、指令寄存器、指令译码器、状态/条件寄存器、时序发生器、微操作信号发生器组成。

3、指令系统基础

在计算机中,CPU都会定义出自己特定的指令系统,不过都遵循着统一的标准格式。指令的基本格式是由操作码和地址码两个部分组成的。操作码指出该指令要完成什么操作,地址码是提供原始的数据。指令系统中定义操作码的方式可以分为规整型(定长编码)和非规整型(变长编码)两种,如表:

必威 7

而在指令系统中用来确定如何提供操作或提供操作数地址的方式称为寻址方式和编址方式。操作数可以存放在CPU中的寄存器(用寄存器名操作)、主存储器(指出存储单元地址)、堆栈(先进后出的存储机制,用栈顶指针SP来标出其当前位置)、外存器或外围设备中。不过在运算时,数据均在主存储器中,操作数可以采用以下几种寻址方式:

(1)隐含寻址方式

在指令中不明显地给出而是隐含着操作数的地址。例如,单地址的指令格式,没有在地址字段中指明第二操作数地址,而是规定累加寄存器AC作为第二操作数地址,AC对单地址指令格式来说是隐含地址。

(2)立即寻址方式

指令的地址字段指出的不是操作数的地址,而是操作数本身。这种方式的特点事指令执行时间很短,不需要访问内存取数。“操作数包含在指令中寻址方式”就是立即寻址。

如,单地址的移位指令格式为

必威 8

这里D不是地址,而是一个操作数。F为标志位,当F = 1
时,操作数进行右移;当F = 0时,操作数进行左移。

(3)直接寻址

特点是:在指令格式的地址字段中直接指出操作数在内存的地址D。

采用直接寻址方式时,指令中的形式地址D就是操作数的有效地址E,即E =
D。因此通常把形式地址D又称为直接地址。此时,由寻址模式给予指示。如果用S表示操作数,那么直接寻址的逻辑表达式为S
= (E) = (D).

(4)间接寻址方式

间接寻址的情况下,指令地址字段中的形式地址D不是操作数的真正地址,而是操作数地址的指示器,D单元的内容才是操作数的有效地址。

如果把直接寻址和间接寻址结合起来,指令有如下形式:

必威 9

寻址特征位 I = 0,表示直接寻址,这时有效地址 E = D; I =
1,表示间接寻址,这时有效地址

E = (D).

间接寻址方式是早期计算机中经常采用的方式,但由于两次访问内存,影响指令执行速度,现在已不大使用。

(5) 寄存器寻址方式和寄存器间接寻址方式

     
 当操作数不放在内存中,而是放在CPU的通用寄存器中时,可采用寄存器寻址方式。此时指令中给出的操作数地址不是内存的地址单元号,而是通用寄存器的编号。这也就是所说的”操作数在寄存器中的寻址方式”.

       
 寄存器间接寻址方式与寄存器寻址方式的区别在于:指令格式中的寄存器内容不是操作数,而是操作数的地址,该地址指明的操作数在内存中。这也就是所说的”操作数的地址在寄存器中的寻址方式”.

(6) 相对寻址方式 

       
相对寻址是把程序计数器PC的内容加上指令格式中的形式地址D而形成操作数的有效地址。程序计数器的内容就是当前指令的地址。”相对”寻址,就是相对于当前的指令地址而言的。 
采用相对寻址方式的好处是程序员无须用指令的绝对地址编程,所编程序可以放在内存任何地方。此时形式地址D通常称为偏移量,其值可正可负,相对于当前指令地址进行浮动。

(7) 基址寻址方式

       
 基址寻址方式是将CPU中基址寄存器的内容加上指令格式中的形式地址而形成操作数的有效地址。它的优点是可以扩大寻址能力。与形式地址相比,基址寄存器的位数可以设置得很长,从而可以在较大的存储空间中寻址。

(8) 变址寻址方式

     
 变址寻址方式与基址寻址方式计算有效地址的方法很相似,它把CPU中某个变址寄存器的内容与偏移量D相加来形成操作数有效地址。但使用变址寻址方式的目的不在于扩大寻址空间,而在于实现程序块的规律性变化。

  1. CISC与RISC

为了提高操作系统的效率,人们最初选择了向指令系统中添加更多、更复杂的指令,而随着不断地升级和向后兼容的需要,指令集也越来越大。这种类型的计算机,我们称之为复杂指令计算机CISC.而后来研究发现,计算机指令系统如果使用少量结构简单的指令会提高计算机的性能,这就是精简指令集计算机RISC.计算机执行程序所需的时间P由三方面因素决定:编译后产生的机器指令数I、执行每条指令所需的平均周期数CPI,以及每个机器周期的时间T.它们的关系是P=I
x CPI x
T.RISC正是通过简化指令的途径使计算机结构更合理,减少指令执行周期数,提高运算速度。虽然RISC编译后产生的机器指令数(I)增多了,但指令所需的周期数(CPI)和每个周期的时间(T)都可以减少。它与CISC可谓各有特色,如表1-5所示。

必威 10

        典型的RISC处理器包括:DEC的Alpha 21164、IBM的Power
PC620、HP的PA-8000、SGIMIPS分部的TS、Sun的Ultra
SPARC.目前RISC处理器技术的发展方向是采用并行处理技术(包括超级流水线、超级标量、超长指令字)大幅度提高运算速度。

  1. 流水线

       
流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的,它们可同时为多条指令的不同部分进行工作,以提高各部件的利用率和指令的平均执行速度。

       
指令流水线是将指令执行分成几个子过程,每一个子过程对应一个工位,我们称为流水级或流水节拍,这个工位在计算机里就是可以重叠工作的功能部件,称为流水部件。

如图1-2所示,IF,ID,EX,WD分别是流水线的流水部件。

必威 11

     
 流水线要求所有的流水级部件必须在相同的时间内完成各自的子过程。在流水线中,指令流动一步便是一个机器周期,机器周期的长度必须由最慢的流水级部件处理子过程所需的时间来决定。

   
 那么我们为什么要提出流水线这个概念,以及流水线是如何提高系统吞吐量的呢?下面我们来看几个图,概念自然就清楚了。

图1-3是一个非流水线结构系统执行指令时空图。

必威 12

显然,采用流水线可以大大提升系统资源的利用率,以及整个系统的吞吐量。

(1)计算流水线执行时间

     
 假定有某种类型的任务,共可分成N个子任务,执行每个子任务需要时间t,则完成该任务所需的时间即为Nt.若以传统的方式,则完成k个任务所需的时间是kNt;而使用流水线技术执行,花费的时间是Nt+(k-1)t.也就是说,除了第一个任务需要完整的时间外,其他都通过并行,节省下了大量的时间,只需一个子任务的单位时间就够了。

   
 另外要注意的是,如果每个子任务所需的时间不同,则其速度取决于其执行顺序中最慢的那个(也就是流水线周期值等于最慢的那个指令周期),要根据实际情况进行调整。

     
例如:若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是取指2ns,分析2ns,执行1ns.那么,最长的是2ns,因此100条指令全部执行完毕需要的时间就是:(2ns+2ns+1ns)
+(100-1)x 2ns=203ns.

     
另外,还应该掌握几个关键的术语:流水线的吞吐率(等于任务数/完成时间),加速比(不采用流水线的执行时间/采用流水线的执行时间)

(2)影响流水性的主要因素

       
如图1-4所示,流水线的关键在于”重叠执行”,因此如果这个条件不能够满足,流水线就会被破坏。这种破坏主要来自两种情况:

转移指令:因为前面的转移指令还没有完成,流水线无法确定下一条指令的地址,因此也就无法向流水线中添加这条指令。从这里的分析可以看出,无条件跳转指令是不会影响流水线的。

共享资源访问的冲突:也就是后一条指令需要使用的数据,与前一条指令发生的冲突,或者相邻的指令使用了相同的寄存器,这也会使得流水线失败。

响应中断:当有中断请求时,流水线也会停止。对于这种情况有两种响应方式,一种是立即停止–精确断点法,能够立即响应中断;另一种是流水线中的指令继续执行,不再新增指令到流水线–不精确断点法。

一、并行技术

1.3.1 软硬件取舍的基本原则

简答、选择、填空

  1. 应考虑在现有硬件、器件条件下,系统要有高的性能价格比。
  2. 要考虑准备采用和可能采用的组成技术,使之尽可能不要过多或不合理地限制各种组成、实现计数的采用。
  3. 把如何为编译和操作系统的实现及如何为高级语言程序的设计提供更多、更好的硬件支持放在首位。

流水线技术

  • 采用并行硬件提高性能,将一个指令拆分成多个指令任务,各指令任务串行执行并且由不同机构执行而不同机构执行时之间可以并行执行
    • 一般一个指令分为 取指、分析、执行 三个任务
    • 如果有100个指令,取指令1ns,分析2ns,执行2ns
    • 由于第一条指令需要拆分串行运行,耗时为 1+2+2=5ns
    • 拆分的指令可以并行执行,任务中耗时最长的是2ns(这就是并行的流水周期),在第一个指令被拆分为3个子任务耗时5ns后,还剩下100-1个指令,在最长的耗时(100-1)*2ns的情况里,其余的子任务都会完成
    • (1)标量流水处理机 耗时为 (1+2+2) + (100-1)*2 = 203ns
    • (1)标量非流水处理机 耗时为 (1+2+2)*100=500ns
    • (4)标量流水处理机 耗时为 (1+2+2) + (100/4-1)*2 = 53ns
    • 流水线计算公式是time=(n*t) + [(k-1)*t]
      n是子任务数,t是每个子任务耗时,k是指令个数
    • 有时候可能会使用 周期时间累加作为第一次取值总耗时
    • 吞吐率TP 单位时间内流水线完成的任务数量
      • 吞吐率 100/203ns
    • 加速比 不使用流水线耗时与使用流水线的耗时比
      • 加速比 500/203=2.46(感兴趣的可以去套下高数公式)
    • 复杂的流水线计算使用画时空图更快

必威 13

1335019680_3761.jpg

必威 14

D7FADF0B-CE9D-4695-9CB5-A0FBE80C6CC4.png

必威 15

5A68C395-6885-4E08-A73B-0758B2B36CC9.png

必威 16

51B741AE-E808-4BAF-B738-E27919018D4B.png

  • 流水线技术被破坏的条件(流水线技术采用的是重叠时间多执行器并行执行)
    • 转移指令 流水线无法确认下一步指令地址
    • 共享资源冲突
      前后数据冲突,导致指令无法继续执行,这种大多数都是局部性的资源冲突,比如前一条指令还在写寄存器,另一条指令已经准备读寄存器了,解决方法如下

      • 推后法 推后相关read操作,等待wait执行完成
      • 通路法 不将结果write into storage
        unit后供read,而是通过专用通路直接读取,可以加快s剫
    • 响应中断
      • 精确中断 立即停止当前流水线,CPU指令变复杂
      • 不精确中断
        封闭流水线指令入口,让当前指令执行完成,执行中断处理程序,实现简单

                                     四、存储系统

   在整个计算机系统中,存储系统的地位非常重要。

1.Cache  

由于在CPU与存储系统间存在着数据传送带宽的限制,因此在其中设置了Cache(高速缓冲存储器,通常速度比内存快),以提高整体效率。但由于其成本更高,因此Cache的容量要比内存小得多。

(1) Cache原理、命中率、失效率

     
使用Cache改善系统性能的主要依据是程序的局部性原理。通俗地说,就是一段时间内,执行的语句常集中于某个局部。而Cache正式将访问集中的内容放在速度更快的Cache上,以提高性能。引入Cache后,CPU在需要数据时,先找Cache,如果没有再找内存。

   
 如果Cache的访问命中率为h(通常1-h就是Cache的失效率),而Cache的访问周期时间是t1,主存储器的访问周期时间是t2,则整个系统的平均访存时间就应该是:

                                                  t3=h*t1+(1-h)* t2

       
 从公式可以看出,系统的平均访存时间与命中率有着很密切的关系。灵活地应用这个公式,可以计算出所有情况下的平均访存时间。

例如:设某流水线计算机主存的读/写时间为100ns,有一个指令和数据合一的Cache,已知该Cache的读/写时间为10ns,取指令的命中率为98%,取数的命中率为95%.在执行某类程序时,约有1/5指令需要存/取一个操作数。假设指令流水线在任何时候都不阻塞,则设置Cache后,每条指令的平均访存时间约为多少?其实这是应用该公式的简单数学题:

                  (2%*100ns + 98%*10ns)+ 1/5 x(5%*100ns +
95%*10ns)=14.7ns

(2)Cache存储器的映射机制

必威 17

     
CPU发生访存请求时,会先让Cache判断是否包括,如果命中(即包括请求的内容)就直接使用。这个判断的过程就是Cache地址映射,这个速度应该尽可能快,常见的映射方法有直接映射、全相联映射和组相联映射三种,其原理如图1-5所示。

 直接映射:是一种多对一的映射关系,但一个主存块只能够复制到Cache的一个特定位置上去。Cache的行号i和主存的块号j有函数关系:i=j%m(其中m为Cache总行数)。例如:某Cache容量为16KB(可用14位表示),每行的大小为16B(可用4位表示),则说明其可分为1024行(可用10位表示)。则主存地址的最低四位为Cache的行内地址,中间10位为Cache行号。如果内存地址为1234E8F8H的话,那么最后四位就是1000(对应16进制数的最后一位),而中间10位,则应从E8F(111010001111)中获取,得到1010001111。

相联映射:将主存中一个块的地址与块的内容一起存于Cache的行中。速度更快,但控制复杂。

组相联映射:是前两种方式的折中方案。它将Cache中的块再分成组。然后通过直接映射方式决定组号,再通过相联映射的方式决定Cache中的块号。

要注意的是,在Cache映射中,主存和Cache存储器将均分成容量相同的块。

例如:容量为64块的Cache采用组相联方式映像,字块大小为128个字,每4块为一组。若主存容量为4096块,且以字编址,那么主存地址应该为多少位?主存区号为多少位?这样的题目,首先根据主存与Cache块的容量需一致,因此内存也是128个字,因此共有12*4096个字,即219(27+212)个字,因此主存地址需要19位;而内存所需要分为4096/64块,即26,因此主存区号需要6位。

(3)Cache淘汰算法

当Cache数据已满,并且出现未命中情况时,就是淘汰一些老的数据,更新一些新的数据。而选择淘汰什么数据的方法就是淘汰算法,常见的方法有三种:随机淘汰、先进先出(FIFO)淘汰(淘汰最早调入Cache的数据)、最近最少使用(LRU)淘汰法。其中平均命中率最高的是LRU算法。

(4)Cache存储器的写操作

在使用Cache时,需要保证其数据与主存一致,因此在写Cache时就需要考虑与主存间的同步问题,通常使用以下三种方法:写直达(写Cache时,同时写主存)、写回(写Cache时不马上写主存,而是等其淘汰时回写)、标记法。

  1. 主存(内存)

(1)主存储器的种类

RAM:随机存储器,可读写,断电后数据无法保存,只能暂存数据。

SRAM:静态随机存储器,在不断电时信息能够一直保持。  

DRAM:动态随机存储器,需要定时刷新以维持信息不丢失。  

ROM:只读存储器,出厂前用掩膜技术写入,常用于存放BIOS和微程序控制。  

PROM:可编程ROM,只能够一次写入,需用特殊电子设备进行写入。

  EPROM:可擦除的PROM,用紫外线照射15~20分钟可擦去所有信息,可写入多次。 

 E2PROM:电可擦除ERPOM,可以写入,但速度慢。  

闪速存储器:现在U盘使用的种类,可以快速写入。  

         
 记忆时,抓住几个关键英文字母。A,即Access,说明读写都行;O,即Only,说明只读;P,即Programmable,说明可通过特殊电子设备写入;E,即Erasable,说明可擦写;E平方说明是两个E,第二个E是电子。

(2)主存储器的组成

         
实际的存储器总是由一片或多片存储器配以控制电路构成的(如图1-6所示)。其容量为WxB,W是存储单元(word,即字)的数量,B表示每个word由多少bit(位)组成。如果某一芯片规格为w?b,则组成W?B的存储器需要用(W/w)x(B/b)个芯片。

必威 18

(3)主存储器的地址编码

       
主存储器(内存)采用的是随机存取方式,需对每个数据块进行编码,而在主存储器中数据块是以
     
word来标识的,即每个字一个地址,通常采用的是16进制表示。例如,按字节编址,地址从A4000H到CBFFFH,则表示有(CBFFF-A4000)+1个字节,28000H个,也就是163840个字节,等于160KB.

         
要注意的是,编址的基础可以是字节,也可以是字(字是由1个或多个字节组成的),要算地址位数,首先应计算要编址的字或字节数,然后求2的对数即可得到。

  1. 现流行的并行技术大都可以从三个方面实现:

1.3.2 计算机系统性能评测及定量设计原理

IC:总指令条数

CPI:平均每条指令的时钟周期数

f[c]:主时钟频率

CPU程序执行时间 T[cpu]

T[cpu] = IC × CPI × (1 / f[c])

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

尽可能加速处理高概率事件远比加速处理低概率事件对性能的提高要显著。

性能可改进比 f[new]
:系统性能可改进部分占用时间与改进前系统总执行时间比值,0<=f[new]<=1

部件加速比 r[new]
:系统性能可改进部分,在改进后系能提高的比值,r[new]>1

系统加速比 S[p] :系统改进后的性能与未改进时的性能的比值

S[p] = T[old] / T[new] = 1 / ((1 – f[new]) + f[new] /
r[new])

解释:

  • 性能是时间的倒数,即 S[p] = 改进后性能 / 改进前性能 = (1 /
    T[new]) / (1 / T[old])

选择、填空、简答

程序访问的 局部性定律 :包括时间上和空间上的两个局部性。

并行处理

  • 超标量处理机
  • 超级流水线处理机
  • 超长指令字处理机
  • 向量处理机
  • 多处理机系统(MIMD 中高端机通过高速通信网络进行通信,相比SIMD
    有更高的并行层面)

    • 共享存储器多处理机
    • 分布式存储器多处理机
  • 大规模并行处理机(阵列处理机 MPP 有独立主空间 SIMD)
  • 对称多处理机(SMP 共享主存空间 通过网络)
  • 紧耦合系统 SMP
  • 松耦合系统 MPP

                       五、可靠性与系统性能评测

  1. 可靠性计算

     
可靠性计算主要涉及三种系统,即串联系统、并联系统和冗余系统,其中串联系统和并联系统的可靠性计算都非常简单,只要了解其概念,公式很容易记住。冗余系统要复杂一些。

(1)串联系统

假设一个系统由n个子系统组成,当且仅当所有的子系统都能正常工作时,系统才能正常工作,这种系统称为串联系统,如图1-7所示。

必威 19

设系统各个子系统的可靠性分别用表示,则系统的可靠性:

必威 20

如果系统的各个子系统的失效率分别用来表示,则系统的失效率:

必威 21

(2)并联系统

     
 假如一个系统由n个子系统组成,只要有一个子系统能够正常工作,系统就能正常工作,如图1-8所示。

必威 22

设系统各个子系统的可靠性分别用 R1,R2…Rn表示,则系统的可靠性

R = 1 – (1 – R1) x (1 – R2) x … x (1 – Rn)

假如所有子系统的失效率均为l,则系统的失效率为μ:

必威 23

     
在并联系统中只有一个子系统是真正需要的,其余n-1个子系统都被称为冗余子系统。该系统随着冗余子系统数量的增加,其平均无故障时间也会增加。

(3)模冗余系统

m模冗余系统由m个(m=2n+1为奇数)相同的子系统和一个表决器组成,经过表决器表决后,m个子系统中占多数相同结果的输出可作为系统的输出,如图1-9所示。

必威 24

在m个子系统中,只有n+1个或n+1个以上的子系统能正常工作,系统就能正常工作并输出正确结果。假设表决器是完全可靠的,每个子系统的可靠性为R0,则m模冗余系统的可靠性为:

必威 25

2.系统性能评价

     
无论是生产厂商还是用户,都需要某种方法来衡量计算机系统的性能,但由于系统很复杂、体系结
构和实现的策略多样,因此很难采用统一的标准去评测所有的计算机。

(1)常用方法

时钟频率:即主频(常听到的CPU主频1.8GHz等),通常主频越高,速度越快。但这种比较只能够在相同体系结构的机器上比较,对于异构系统而言,难以保证其有效性。

指令执行速度:在早期,我们经常使用每秒执行的加法指令(由于当时各种指令的速度大致相同或等比例)总数来作为衡量其性能的重要指标,其单位为KIPS(每秒千条指令)、MIPS(每秒百万条指令)。

等效指令法:随着计算机指令系统的发展,使用单种指令的MIPS值的局限性日益暴露,后来就出现了改进的吉普森混合指令速度法。它通过统计各类指令在程序中所占的比例,进行折算。

数据处理速率(PDR)法:它采用固定的比例法来计算数据处理的速度,而且还仅对CPU和主存的速度进行度量,因此有很大的局限性。

核心程序法:把应用程序中用得最频繁的那部分核心程序作为评价计算机性能的标准程序,在不同机器上运行,测其执行时间,作为各类机器性能评价的依据。

(2)基准测试程序  

基准程序法是目前一致承认的测试性能较好的方法,有多种不同的基准程序,用于不同的测试项目。 

 整数测试程序:Dhrystone是一个用来测试编译器和CPU处理整数指令和控制功能有效性的基准测试程序。  

浮点测试程序:在计算机科学和工程应用领域,浮点计算工作量占很大比例,因此有许多此类基准测试程序。  

理论峰值浮点速度:MELOPS,与处理器时钟周期、并行流水线功能部件数相关,是直接计算出来的理论值。

Linpack基准测试程序:主要测试向量性能和高速缓存性能。

Whetstone基准测试程序:综合性测试程序,除测试浮点操作外,还测试整数计算和功能调用等性能。

SPEC基准程序:是由几十家世界知名计算机大厂商支持的非盈利的合作组织,开发共同认可的标准基准程序。

TPC基准程序:是事务处理委员会编写的,共包括TPC-A,TPC-B,TPC-C,TPC-D和TPC-E五种,每一种都有一定的适用范围。

3.校验码

     
 为了实现数据的自动检错与纠错,引入了校验码。而最简单的就是奇偶校验码,它分为奇校验和偶校验两种,均是添加1位校验位,根据信息码中1的个数来决定校验位的取值,使得填入校验位后,使得1的个数为奇数(奇校验)或偶数(偶校验)。这方面知识更深入的考察点主要包括以下几个方面:

(1)海明码距

     
海明的冗余数据位检测和纠正代码差错的理论和方法指出:可以在数据代码上添加若干冗余位组成码字。而将一个码字变成另一个码字时必须改变的最小位数就是码字之间海明距离,简称码距。从这里将得出:没有加冗余校验码的任何编码,它们的码距就是1,即只要改一位,就可以变成另一个码字了;而奇偶校验码则添加了1位校验码,使得要变成另一个码字最少要修改两位,这就使其码距变成2了;根据定义得知,码距是不同码字的海明距离的最小值。判断码距时,可以列出一些码进行判断,找出最小的位数即可。

     另外,还需要记住以下几个关键的关系:

    可查出多少位错误:根据海明的研究发现,可以发现”≤码距-1″位的错误。  

   
可以纠正多少位错误:根据海明的研究发现,可以纠正”<码距/2″位的错误,因此如果要能够纠正n位错误,则所需最小的码距应该是”2n+1″.

(2)海明校验码

要计算海明校验码,首先要知道海明校验码是放置在2的幂次位上的,即”1、2、4、8、16、32……”,而对于信息位为m的原始数据,需加入k位的校验码,它满足m+k+1<2k.计算时总令人感到头痛。而有一种简单的方法,则是从第1位开始写,遇到校验位留下空格。例如:原始信息为101101100,并采用偶校验则:

必威 26

然后根据以下公式填充校验位”1、2、4、8″:

Bit 1=B3 B5 B7 B9 B11 B13 = 1 0 1 0 1 0 =1

Bit 2=B3 B6 B7 B10 B11 = 1 1 1 1 1 =1

Bit 4=B5 B6 B7 B12 B13 = 0 1 1 0 0 =0

Bit 8=B9 B10 B11 B12 B13 = 0 1 1 0 0=0

(注:?指的是异或运算;Bn代表位数)

然后将结果填入,得到:

必威 27

而如果给出一个加入了校验码的信息,并说明有一位错误,要找出,则可以采用基本相同的方

法,假如给出的是:

必威 28

可根据以下公式计算:

Bit 1=B1 B3 B5 B7 B9 B11 B13 = 1 1 0 1 0 0 0 =1

Bit 2=B2 B3 B6 B7 B10 B11 = 1 1 1 1 1 0 =1

Bit 4=B4 B5 B6 B7 B12 B13 = 0 0 1 1 0 0 =0

Bit 8=B8 B9 B10 B11 B12 B13 =0 0 1 0 0 0=1

     
然后从高位往下写,得到1101,即十进制的11,因此出错的位数为第11位。而剩下的问题就是这个公
式如何来的?首先计算校验码时,1、2、4、8位都是空的,因此在公式的左边;当进行校验时,1、2、4、8位都已经有值,因此要参与计算。而这些值是根据右表得到的,也就是生成B1、B2、B4、B8四个公式,而公式中要参与计算的位,是在表格中出现”1″的那个位。要说明的是,右边的表格,就是对数据位的二进制描述。

     
由于海明码距在计算和纠错过程中,计算都过于复杂,无法很容易地使用硬件实现,因此在实际的应用中并不是应用得很广泛。

(3)CRC校验码

由于CRC的实现原理十分易于用硬件实现,因此被广泛地应用于计算机网络上的差错控制。而CRC的考察点主要有两个:计算CRC校验码;验算一个加了CRC校验的码是否有错误。

计算CRC校验码

   
要计算CRC校验码,需根据CRC生成多项式进行。例如:原始报文为”11001010101″,其生成多项式为:”x4+x3+x+1″.在计算时,是在原始报文的后面若干个0(等于校验码的位数,而生成多项式的最高幂次就是校验位的位数,即使用该生成多项式产生的校验码为4位)作为被除数,除以生成多项式所对应的二进制数(根据其幂次的值决定,得到11011,因为生成多项式中除了没有x2之外,其他位都有)。然后使用模2除,得到的商就是校验码。

必威 29

然后将0011添加到原始报文的后面就是结果:110010101010011。

检查信息码是否有CRC错误

要想检查信息码是否出现了CRC错误的计算很简单,只需用待检查的信息码做被除数,除以生成多项式,如果能够整除就说明没有错误,否则就是出错了。另外要注意的是,当CRC检查出现错误时,它是不会进行纠错的,通常是让信息的发送方重发一遍。

  • 资源重复:如多核
  • 资源共享:如CPU分时技术
  • 时间重叠:如流水线技术

1.3.3 计算机系统设计的主要任务和方法

计算机系统的设计方法

  • 由上往下
  • 由下往上
  • 由中间开始

互联网络

  • ICN 连接计算机中各个处理单元、存储模块以及I/O设备,一般结构有
    • 总线
    • 交叉开关
    • 多级互联网
  • 并行处理机互联方法
    • 恒等置换 I 相同编号的输入输出地址一致
    • 交换置换 E 二进制地址编号 第0位位值不同 的是输入/输出
    • 方体置换 Cube 二进制地址编号 第k位位值不同 的是输入/输出
    • 均匀洗牌置换 Shuffle 输入端二进制地址编号
      左移一位得到输出端二进制地址
    • 蝶式置换 B 输入端二进制地址编号
      最高位和最低位互换得到输出端二进制地址
    • 位置颠倒置换 P 输入端二进制地址编号
      位置顺序颠倒得到输出端二进制地址

必威 30

AF21EACB-C449-4FEA-AC55-A38E26979575.png


  • 计算机系统由 硬件软件组成,软件 又区分为 系统软件
    应用软件
  • 计算机只能读懂二进制指令,需要通过编译程序转码,然后由指令系统执行
  • 总线控制线路包括 总线判优或仲裁逻辑、驱动器和中断逻辑

 

1.5 系统结构中的并行行开发及计算机系统的分类

并行性同一时刻同一间隔 完成 两种及以上 性质
相同或不同 的工作

  1. 新技术的设计与实现

1.5.1 并行性的概念和开发

开发并行性的途径

  • 时间重叠(流水线)
  • 资源重复(阵列)
  • 资源共享(多处理机)

多机系统包含 多处理机系统多计算机系统

冯氏分类法 字W 位B 串S 并P

  • 字串位串 (WSBS)
  • 字串位并 (WSBP)
  • 字并位串 (WPBS)
  • 字并位并 (WPBP)
  • 引入新技术进行优化
  • 出现新问题
  • 解决新问题

习题1

           采用一些机制可以解决

1-3

           权衡

1-10

  • 整体评估、反馈、再改进

第2章 指令系统

 

2.4 指令系统的发展和改进

  • CISC 复杂指令系统计算机
  • RISC 精简指令系统计算机
  1. 指令周期

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

选择、简答

设计RISC的基本原则

  1. 确定指令系统时,只选择使用频度很高的那些指令(一般不超100条)。
  2. 减少指令系统所用寻址方式种类,一般不超过两种。精简指令格式限制在两种之内,并使全部指令等长。
  3. 所有指令都在一个机器周期内完成。
  4. 扩大通用寄存器数,一般不少于32个,尽量减少访存,仅STORE和LOAD可访存,其他指令一律只操作寄存器。
  5. 大多数指令用硬联控制实现,提高指令执行速度,少数指令才用微程序。
  6. 通过精简指令和优化设计编译程序,简单有效地支持高级语言实现。

设计RISC结构采用的基本技术

  1. 选取其中常用的基本指令,使指令数精简。
  2. 逻辑实现采用硬联和微程序相结合。
  3. 在CPU中设置大量工作寄存器并采用重叠寄存器窗口。
  • 单周期处理机模型:一个周期完成一个指令(每个周期是等长的),指令长度可能不一样,会造成很大的浪费
  • 多周期处理机模型:将一个指令的完成划分成若干个周期来实现
  • 流水线模型

第5章 标量处理机

必威 31

5.1 重叠方式

 

5.1.1 重叠原理与一次重叠

实现指令的重叠解释必须在计算机组成上满足:

  1. 要解决访主存的冲突。
  2. 要解决“分析”与“执行”操作的并行。
  3. 要解决“分析”与“执行“操作控制上的同步。
  4. 要解决指令间各种相关的处理。

一次重叠:取值和分析重叠,同时有 两个
工作进行。N次重叠同时有N+1个工作。

二、流水线技术

5.2 流水方式

流水的分类

依据 向下扩展向上扩展 的思路。

按多功能流水线的各段能否允许同时用于多种不同功能连接流水,可把流水线分为
静态流水线动态流水线

重点掌握动态流水线

     1. 什么是流水线?

5.2.2 标量流水线的主要性能 需要扩展

直接做题

标量流水线的主要性能

  • 吞吐率: T[p]
  • 加速比: S[p]
  • 效率: η

最大吞吐率: T[p[max]]

各个子过程时间长度不一时,最大吞吐率由最长的字过程时间决定

T[p[max]] = 1 / max{Δt}

实际吞吐率 T[p] 总小于最大吞吐率

T[p] = 实际任务数 / 实际时间

加速比 S[p] 总大于1

S[p] = 流水线方式性能 / 非流水线性能 = (1 / 流水线方式总时间) / (1 /
非流水线总时间)

S[p] = 非流水线总时间 / 流水线方式总时间

效率 μ

μ = 实际使用时间 / 整个运行时间

可以按阴影区面积与整个时空区面积的比求

具体公式看 P175

设m段流水线,各段经过时间相同,完成n个任务,则

T[p] = n / (m × Δt[0] + (n – 1) × Δt[0]) 或

T[p] = 1 / Δt[0] × (1 + (m – 1) / n) 或

T[p] = T[p[max]] / (1 + (m – 1) / n)

S[p] = m / (1 + (m – 1) / n)

若m段每段经过时间Δt[i]不等,其中瓶颈段时间为Δt[j],完成n个任务,则

T[p] = n / (Σ(i=1, m)Δt[i] + (n – 1)Δt[j]) 或

T[p] = 任务数 / (第一个任务时间 + 其余任务额外花费的时间)

S[p] = n个任务线性处理花费的时间 / (第一个任务时间 +
其余任务额外花费的时间)

其余任务额外花费的时间受瓶颈段时间影响,即 (n – 1) × 瓶颈段时间

  •  计算机中的流水线是把一个重复的过程分解为若干个子过程,每个子过程与其他子过程并行进行。由于这种工作方式与工厂中的生产流水线十分相似,
    因此称为流水线技术
  • 从本质上讲,流水线技术是一种时间并行技术。

5.2.3 标量流水机的处理和控制机构

 

5.2.3.4 非线性流水的调度

大题?
直接做题

     2.指令重叠方式

5.3 指令集高度并行的超级处理机

  • 顺序执行:控制简单,节省设备;但是速度慢,功能部件的利用率低
  • 重叠执行方式 :指令的执行时间缩短 ,功能部件的利用率明显提高
    ;但是需要增加一些硬件;控制过程稍复杂

5.3.1 超标量处理机

采用多指令流水线,每个Δt同时流出m条指令

 

5.3.3 超流水线处理机

每个Δt’仍旧只流出一条指令,但Δt’值小

     3.流水线工作设计

第6章 向量处理机

  • 基本思想:延伸重叠方式,使指令解释过程进一步细化,
    提高各部件的利用率,以提高指令执行速度
  • 理想目标:完成任务的时间与操作处理过程无关,只与提供操作的速度有关(假设一个任务有n个指令,将完成一个指令分为m个段,每段执行时间为△t
    ,则理想目标是完成任务的时间是T=m△t+(n-1)△t;当n >>
    m时,T=(n-1)△t。 指令执行频率为  1 / △t: 即
    与m无关,只和提供操作的速度△t有关)。

6.1 向量的流水处理和向量流水处理机

  • 向量横向处理:向量的处理方式,但不是向量的流水处理方式
  • 向量纵向处理、分组纵横处理:向量的处理方式,也是向量的流水处理方式

基本思路

横纵结合 寄存器组 写后读

 

6.2 阵列处理机的原理

     4.流水线的描述方法

6.2.1 阵列处理机的构型和特点 需要扩展

定义、特点

  • 时间—空间图 **

6.2.2 ILLIAC IV的处理单元阵列结构 需要扩展

选择、填空

           横坐标:表示时间,即各个任务在流水线中所经过的时间

6.3 SIMD计算机的互连网络

注意:互 网络

           纵坐标:表示空间,即流水线的各个子过程,也称为级、
段、流水线深度(Stage)

6.3.1 互连网络的设计目标与互连函数

简答

SIMD中,处理单元之间、处理单元与存储分体之间,都要通过互联网络进行信息交换

SIMD系统的互连网络的设计目标

  1. 结构不要过分复杂,以降低成本;
  2. 互连要林或,以满足算法和应用的需要;
  3. 处理单元间信息交换所需传送步数要尽可能少,以提高系统性能
  4. 能用规整单一的基本构件组合而成(模块化)

 必威 32

6.3.2 互连网络应抉择的几个问题

选择、填空

需要对 操作方式控制策略交换方法
网络的拓补结构 作出抉择。

  • 操作方式:同步、异步、同步与异步组合。
    阵列处理机根据其SIMD性质均为同步 ,异步与组合多用于多处理机。
  • 控制策略:集中、分布。 多数SIMD采用集中控制部件
  • 交换方法:线路交换、包交换、线路与包交换组合。
    SIMD多采用硬连线路交换 ,包交换多用于多处理机和计算机网络中。
  • 时间—空间图 Ⅱ
     横坐标:表示时间,即各个任务或指令在流水线中
    所在该时刻所对应的子过程

6.3.3 基本的单级互连网络 需要扩展

计算、选择、填空

  1. 立方体单级网络
  2. PM21 单级网络
  3. 混洗交换单级网络
  4. 蝶形单级网络

     纵坐标:表示某个任务或某条指令,即流水线依次 处理的任务或指令

6.3.4 基本的多级互连网络

选择、填空

不同的多级互连网络,在所用的 交换开关拓补结构
控制方式 上各有不同。

  • 交换开关:两个入端和两个出端的交换单元。
  • 拓补结构:各级间出端与入端互连的模式。
  • 控制方式:各个交换开关进行控制的方式。

利用这三个参量,可以描述各种多级互联网络的结构。

大题
直接做题

必威 33

6.3.4.1 多级立方体互连网络 需要扩展

STARAN网络用作交换网络时,采用级控制,实现的是 交换函数

  • 交换函数:将一组元素首尾对称地进行交换。

填空

STARAN网络用作移数网络时,采用 部分级控制

 

6.3.4.2 多级混洗交换网络 需要扩展

     IF:Instruction
Fetch,取指令,用到部件:指令存储器,Adder(
全加器,full-adder,是用门电路实现两个二进制数相加并求出和的组合线路,称为一位全加器。一位全加器可以处理低位进位,并输出本位加法进位。多个一位全加器进行级联可以得到多位全加器。常用二进制四位全加器74LS283)

6.4 共享主存构形的阵列处理机中并行存储器的无冲突访问 需要扩展

选择

     ID:Instruction
Decode,译码(应该是取数同时译码的过程),用到部件:指令译码器寄存器堆读口(这里面的寄存器堆的读口和写口可以看作两个不同的部件),这块有大量寄存器,WB也是从写口将数据写到这块的寄存器中。

第7章 多处理机

     EX:Exec,执行,计算内存单元地址。用到部件:ALU,扩展器

7.1 多处理机的概念、问题和硬件结构

     MEM:访存,从数据存储器中读。用到部件:数据存储器。

7.1.2 多处理机的硬件结构

  1. 紧耦合和松耦合
  2. 机间互连形式
  3. 存储器的组织

选择、填空、简答

P248 流水、向量或阵列处理机中,主存一般都不采用高位交叉编址的方案。

但在多处理机中会有不同的考虑,当各个处理机上活跃的进程是共享统一集中连续物理地址空间中的数据时,主存采用低位交叉编址是有力的。然而,当它们只是较少或基本不共享集中的数据时,主存采用低位交叉编址反倒会引起不希望的访存冲突,不如采用高位交叉编址为好。

     WB:Write
Back,写回,将数据写到寄存器中。用到部件:寄存器堆写口。

7.2 紧耦合多处理机多 Cache 的一致性问题 可能需要扩展

选择、填空

 

7.2.1 多 Cache 的一致性问题的产生

  • 工作流程:分装入、流水、排空 三个流程

7.2.2 多 Cache 的一致性问题的解决办法

  1. 解决进程迁移引起的多 Cache 不一致性
  2. 以硬件为基础实现多 Cache 的一致性
  3. 以软件为基础实现多 Cache 的一致性

7.3 多处理机的并行性和性能 需要扩展

  • 同步处理:功能部件 + 锁存器

7.3.1 并行算法

大题?

必威 34

7.3.2 程序并行性分析 需要扩展

  • 硬件要求:

7.3.3 并行语言与并行编译

大题
直接做题

          独立工作的各子功能部件;

7.4 多处理机的操作系统

  • 主从型
  • 各自独立型
  • 浮动型

          各部件处理时间尽可能相等,争取最大工作频率;

第8章 数据流计算机和规约机

          解决访存冲突,即允许不同指令的同时读、写功能;

8.1 数据流计算机

基于异步性和函数性的一种计算模型

  • 异步性:一旦操作数到齐就开始操作
  • 函数性:消耗一组输入产生一组输出

          解决同步问题,保证以相同的速度处理

8.1.1 数据驱动的概念

 

8.1.3 数据流计算机的结构

  1. 静态数据流机
  2. 动态数据流机

     5.流水线特点

          在流水线处理器中,连续任务是充分发挥流水线的效率必要条件之一

        
 一个任务的执行过程可以划分成多个有联系的子任务,每个子任务由一个专门的功能部件实现

          每个功能部件后面都有缓冲存储部件,用于缓冲本步骤的执行结果

        
 同时有多个任务在执行;每个子任务的功能部件并行工作,但各个功能部件上正在执行的是不同的任务

          各子任务执行的时间应尽可能相近

          流水线有装入时间和排空时间,只有流水线完全充满时,
流水线的效率能得到充分发挥

 

三、流水线的分类(了解)

     1.按处理级别

         操作级流水操作重叠

         指令级流水指令执行重叠

         处理器级(宏流水线)任务重叠

必威 35

 

     2.按功能分

         单功能流水线:流水线只完成一种固定功能

        
多功能流水线:流水线可以完成多种功能,如 TI公司的ASC机,8段流水线,能够实现:定点加减
法、定点乘法、浮点加法等功能

 

     3.按同一时间内各段之间的连接方式分

         静态多功能流水线
:同一时间内,多功能结构只能按一种功能的连接方式工作。

        
动态多功能流水线:在同一时间内,可以有多种功能的连接方式同时工作

 

     4.按处理的数据类型

      标量流水线

      向量流水线

 

    5.按控制方式

     同步流水线

     异步流水线:当Si功能段要向Si+1段传送数据时,首
先发出就绪信号,Si+1功能段收到信号后,向Si回送 一个回答信号。

 

    6.按任务从输出端的流出顺序

     顺序流水方式:指令流出顺序 = 指令流入顺序

     乱序流水方式:指令流出顺序  !=  指令流入顺序

 

    7. 线性流水线——不带反馈回路的流水线

必威 36

       非线性流水线——带反馈回路的流水线

 必威 37

      线性流水线和非线性流水线对比

      相同之处 : 都有从第一个功能段到最后一个功能段的单向传输线。

      不同之处 :

           非线性流水线一般有前馈线路或反馈线路;

          
非线性流水线的输出端经常不在最后一个功能段,而可能从中间的任意一个功能段输出。

           任务经过流水线时,可能要多次经过同一功能段。

          
仅用功能段之间的连接图并不能清楚地描述一个非线性流水线。一般需要连接图和一张预约表共同描述。

 

四、流水线相关及冲突(重点)

必威 38

 

     1.流水线相关(dependence): 两条指令之间存在某种依赖关系。

  • 数据相关

        先写后读:后面指令用到前面指令的结果

        或间接使用

  • 名相关:换名技术

        使用相同的寄存器或存储器单元名称/地址

        反相关:先读后写

        输出相关:先写后写

        真相关:先写后读

  • 控制相关

        由分支指令引起的相关

 

     2.流水线冲突(hazards)

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

  • 数据冲突:当指令在流水线中重叠执行时,因需要用到前面指令的执行结果而发生的冲突

  • 控制冲突:流水线遇到分支指令和其他会改变PC值的指令所引起的冲突

  • 结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突,比如说,前面后面指令同时访问存储器

 

     3.流水线冲突带来问题

  • 导致错误的执行结果
  • 流水线可能会出现停顿,从而降低流水线的效率和实际的加速比
  • 我们约定当一条指令被暂停时,在该暂停指令之后流出的所有指令都要被暂停,而在该暂停指令之前流出的指令则继续进行(否则就永远无法消除冲突)

 

     4.数据冲突

     举例:  指令一:DADD  R1,R2,R3                 R2 + R3 –> R3

                指令二:DSUB  R4,R1,R5                 R1 – R5 –>
R4

                指令三:XOR   R6,R1,R7                  R1 xor R7
–>R6 

                指令四:AND   R8,R1,R9                  R1 and R9
–>R8 

                指令五:OR    R10,R1,R11               R1 or R11
–> R10

 

     必威 39

 

     对上图的解读:

     以指令一DADD  R1,R2,R3为例:

   第一周期:首先在IM中取出加法指令;

   第二周期:在Reg中取出R2, R3寄存器中的值;

   第三周期:在ALU中做R2 + R3加法运算;

   第四周期:空;

   第五周期:将R2 + R3的结果写回到R1寄存器中;

 

   
 很显然,寄存器R1的正确数据是在第一条指令执行到第五周期才产生的,而后面四条指令都用到了直到第五周期才产生的R1数据,但是有些指令(指令二、三、四)不到第五周期就需要使用R1的数据(如指令二的减法指令在第二周期就需要使用R1的数据),这显然是不合理的,会产生数据冲突。下面逐个情况讨论数据冲突及其解决办法:

 

  • 同一个周期数据冲突的情况:以指令四AND 
     R8,R1,R9为例:在第五周期,第一条指令R2 +
    R3结果正准备写入到R1中,但是此时第四条指令现在就需要使用R1(此时R1的值还不是R1 +
    R2),显然会出现问题

        解决办法:利用寄存器读写数据非常快的特点,无论是从存储器中读还是写入存储器往往都用不了一个完整周期(事实上半个周期就足够完成寄存器的读写操作),所以可以设计规定:上升沿写数据,下降沿读(取)数据。这样一来,在第五周期的上升沿(即第五周期初时刻)将R2
+
R3的结果写到R1寄存器中,在第五周期下降沿(第五周期末)从R1寄存器中取出数据的方法解决此类数据冲突的问题。

  • 在R1写入寄存器的前一个周期(第四周期)就需要使用R1数据的情况:如指令三
    XOR 
     R6,R1,R7:这种情况显然不适合利用上述解决办法解决。但是可以换一个角度:虽然这个时候没有任何办法在Reg中取出正确的R1值,但是可以从ALU部件下手,因为从Reg取出R1数据最终目的就是计算R1
    XOR R7,实际上就是计算(R2 + R3) XOR
    R7,所以只要保证输入到的ALU中的数据是(R2
    +R3)就可以了,那如何使(R2 + R3)的结果输入到ALU参与(R2 + R3) XOR
    R7 运算呢?

        解决办法:采用数据定向路径技术解决!如下图所示(蓝色粗线所示):在第五周期初,对于指令三来说,从Reg读出的错误的R1的值即将进入到ALU中参与XOR运算,此时,我们从DM后拉一根线到ALU之前,因为此时刻(第五周期初,即第四周期末)(R2

  • R3)的结果正处在DM后面,这样一来,(R2 +
    R3)的结果会通过我们刚拉的那根线传到ALU前,这时候,我们在进入ALU之前设置一个多路选通器,不选择错误的R1值,而是选择使用传过来的(R2
    +R3)值,问题就解决了!

  •  同样道理,对于指令二:DSUB  R4,R1,R5,在第四周期初要用到(R2 +
    R3)的值,可以从DM前(或者ALU后)拉一根线到ALU前,如绿色线所示,同样可以解决问题。

必威 40

  • 综上所述,综对于数据冲突来说,可以通过定向技术减少数据冲突引起的停顿
    (定向技术也称为旁路或短路)。但是并不是所有的数据冲突都可以用定向技术来解决:如下例:

     LD    R1,0(R2)

     DADD  R4,R1,R5

     AND   R6,R1,R7

     XOR   R8,R1,R9

必威 41     
  必威 42      

解决上述问题:增加流水线互锁硬件,插入“暂停”(气泡)。

 

 

     5.结构冲突

  • 如果某种指令组合因为资源冲突而不能正常执行,则称该处理机有结构冲突(比如说,两条指令在同一周期同时访问内存,如下图所示)
  • 常见的导致结构相关的原因:

       功能部件不是完全流水

       资源份数不够

必威 43

  • 有些流水线处理机只有一个存储器,将数据和指令放在一起,访存指令会导致访存冲突

     解决办法Ⅰ:插入暂停周期 (“流水线气泡”或“气泡”) ,如下图所示:

必威 44     
 必威 45   

       

   解决方法Ⅱ: 设置相互独立的指令存储器(指令Cache
)和数据存储器(指令Cache )

  • 有时流水线设计者允许结构冲突的存在

          主要原因:减少硬件成本
: 如果把流水线中的所有功能单元完全流水化,或者重复设置足够份数,那么所花费的成本将相当高

 

 

  1. 控制冲突                
      

   
 类似于判断、循环、函数调用、递归等涉及到跳转的会涉及到控制冲突。

 

1               //设s , i 初值都为0;
2                if (i < 10)
3                { 
4 /*指令一:*/       s = s + i;
5 /*指令二:*/       i++;
6                }
7 /*指令三:*/    s = s - 2;

 

 

 

     以此为例,在流水线环境中,首先执行指令一,紧接着执行指令二(当然不是直接执行高级语言,而是该句高级语言对应的机器语言),重点是下一步,按照我们思维,因为此时i
= 1 <
10;所以应该继续执行指令一,但是可惜计算机很“傻”,它此时还真不知道该执行指令一还是指令三,这是为什么?

 

指令编号

时钟周期

1

2

3

4

5

6

7

DADD 
Rs,  Rs ,Ri

(s = s

  • i )

IF

ID

EX

MEM

WB

 

 

DADD 
Ri,  Ri,  1

( i =
i + 1)

 

IF

ID

EX

MEM

WB

 

???

 

 

Start

 

 

 

 

     结合上表所示,前两条指令按照流水线方式依次执行,关于第三条指令,按照正常逻辑:若
i >= 10,则应该执行指令三;若是i <
10,则应该执行指令一。现在重点是落在i
此时到底是多少?请注意,此时正确的i
值取决于指令二:i++,但是在指令二中,i值直到第6周期才被更新(写回到Ri寄存器),就算使用数据定向也不可能实现在第三周期初就能得到正确的i值,所以说,涉及到分支跳转语句时,计算机是不知道是该执行分支语句还是该忽略分支语句继续向下顺序执行。好的,现在先把这个结论放在一边。

 

     对于上述if分支语句而言,执行分支指令的结果就两种:

  • 分支成功(继续执行if中的语句):此时,PC值改变为分支转移的目标地址
    。 在条件判定和转移地址计算都完成后,才改变PC值。
  • 分支失败(执行if函数体外面的语句):PC的值保持正常递增,
    指向顺序的下一条指令。

     在上述的5段流水线中,改变PC值是在MEM段进行的,会给流水线带来了3个时钟周期的延迟(停顿),前面我们说过,流水线出现停顿(暂停)会影响流水线的效率和加速比(尤其是面对上亿条指令时,停顿会经常出现)

  • 可采取两种措施来减少分支延迟

        在流水线中尽早判断出分支转移是否成功; 

        尽早计算出分支目标地址

     关于第一个措施,上面我们已经分析过了,计算机不能正确判断出分支转移是否成功,那该怎么办呢? 

 

     第一种减少延迟时间的方法:猜!(确实是这样的!)

     猜的结果无非就两种:猜对或者猜错了。

   
 这里面我们假设分支失败:则允许分支指令后的指令继续在流水线中流动,就好象什么都没发生似的

  • 如果猜对了,即已经确定分支失败:将分支指令看作是一条普通指令,流水线正常流动
  • 如果猜错了,即已经确定分支成功,那也不要紧,流水线就把在分支指令之后
    取出的所有指令转化为空操作(到最后需要将结果写入到寄存器时,就通过使能信号不让它写入就可以了
    ),并按分支目地重新取指令执行。

     但是这有一个前提:要保证:分支结果出来之前不会改变处理机的状态,以
便一旦猜错时,处理机能够回退到原先的状态

 

     第二种减少延迟时间的方法:延迟分支(指令调度)

  • 主要思想:

    
     从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成,不管分支是否成功,都要按顺序执行延迟槽中的指令

    
     分支延迟槽中的指令“掩盖”了流水线原来必须插入的暂停周期(延迟时间),从而达到减少延迟时间的目的。

  • 分支延迟指令的调度任务:在延迟槽中放入有用的指令
    由编译器完成) 
  • 三种调度方法:  从前调度 
    从目标处调度  从失败处调度

必威 46

  • 分支延迟受到两个方面的限制:

           可以被放入延迟槽中的指令要满足一定的条件。

           编译器预测分支转移方向的能力。

  •  进一步改进:分支取消机制(取消分支)

    
     当分支的实际执行方向和事先所预测的一样时, 执行分支延迟槽中的指令,否则就将分支延迟槽中的
指令转化成一个空操作

 

 

 

五、流水线性能分析

     1.流水线的基本参数——吞吐率

  • 吞吐率(Through Put)—— 单位时间内流水线完成任务数量或输出的结果数:TP = n / Tk 

     其中:n 为任务数; TK 为完成n个任务所用时间

   
 在K级流水线中,各段执行时间相等,输入任务连续的情况下,时钟周期为△t
,则完成n个任务需要的总时间为   Tk=(k+n-1) △t

     因此吞吐率为TP = n
/ (k+n-1) △t                    当n–>无穷大时,TP MAX = 1
/ △t

 

     各段执行时间不等时:

必威 47         
 必威 48

     2.流水线的基本参数——加速比

  • 加速比——完成一批任务,不使用流水线时间与使用流水线所用的时间之比。

     S = 顺序执行时间T0 /
流水线执行时间Tk

  • 各段执行时间相等,输入任务连续的情况下:S = k*n*△t / (k + n – 1)△t =
    k*n / (k + n -1)      当n—>无穷大时,   S = k

 

     3.流水线的基本参数——效率(数格子)

     效率(Efficiency)——流水线的设备利用率。在时空图上,流水线的效率定义为n个任务时间占用的时空区,与k个功能段总的时空之比

     E =
n个任务占用的时空区(有颜色的格子数) /
k个流水段的总的时空区(所有格子数)
= T0 / k * TK =  k*n*△t
/ k * (k + n – 1)△t = k*n / k * (k + n -1)      当n—>无穷大时,  
E = 1

 必威 49

 

  • 例一:流水线性能分析举例

     每个浮点加法都需要经过4级:求阶差、对阶、尾数加、规格化

     用一条4段浮点加法器流水线求8个浮点数的和:Z =
A+B+C+D+E+G+F+H,求流水线的吞吐率、效率、加速比。

     解:首先画出时空图

必威 50

 

吞吐率:     TP = n / Tk  = 7 / (15 * △t ) = 0.47 / △t

加速比:     S = 4 * 7 / (15)= 1.87 

效   率:     E = 7 * 4 / (15 * 4)= 0.47    —— 数格子

 

 

 

  • 例2:(a1+b1)(a2+b2)*(a3+b3)*(a4+b4)在静态、双功能(加法和乘法)流水线上实现*

必威 51
                           

计算顺序: x1=a1+b1, x2=a2+b2,  x3=a3+b3, x4=a4+b4; y1=x1*x2, 
y2=x3*x4; z=y1*y2

首先画出时空图(第一个是错误画法):

必威 52

 

下面一个是正确画法:

必威 53

          

吞吐率:     TP = n / Tk  = 7 / (17 * △t ) 

加速比:     S = (4*3 + 3*5) / (17)= 1.88 

效   率:     E =(4*3 + 3*5) / (17 * 6)= 0.264    —— 数格子

 

     4.结果分析:

  • 建立、排空时间过多(流水线断流—数据相关和操作变换)
  • 功能切换必须等待排空后进行。(静态通病)
  • 动态流水线结果如何?(减少2个Δt)

 

  • 如何提高流水线效率? 
      尽量细化各功能段,尽量减少功能切换,尽量减少数据相关,尽量增加一次处理的指令数量
  • 流水线适用范围?
      流水线适合于操作相同、操作数间无相关性的多个指令的执行。

     

     5.有关流水线性能的若干问题

  • 流水线并不能减少(而且一般是增加)单条指令的执行时间,但却能提高吞吐率。
  • 适当增加流水线的深度(段数)可以提高流水线的性能。
  • 流水线的深度(级数)受限于流水线的延迟和流水线的额外开销。 
  • 相关问题。如果流水线中的指令相互独立
    ,则可以充分发挥流水线的性能。但在实际中
    ,指令间可能会是相互依赖,这会降低流水线的性能。

 

 

六、循环展开优化

   
 在流水线中,往往因为指令顺序安排不合理而导致CPU等待空转,产生延迟,影响流水线效率。

     解决办法:循环展开和指令调度

     前提假设:假设采用MIPS的5段整数流水线:

                      分支的延迟:1个时钟周期。

                      整数load指令的延迟:1个时钟周期。

                      整数运算部件是全流水或者重复设置了足够的份数。

     从例题入手理解

     例: 对于下面的源代码,转换成MIPS汇编语言,
在不进行指令调度和进行指令调度两种情况下,分析其代码一次循环所需的执行时间。

     

for (i=1024; i>=0; i--)
     x[i] = x[i] + s;

     

  Loop:L.D F0,0(R1) 

     ADD.D F4,F0,F2

     S.D F4, 0(R1)

     DADDIU  R1,R1,#-8

     BNE R1,R2,Loop

 

     其中:  
整数寄存器R1:指向向量中的当前元素(初值为向量中最高端元素的地址)

                 浮点寄存器F2:用于保存常数s

                 第二部浮点加法需要4个周期

 

     分析:

   
 假设一个浮点计算部件需要4周期完成一个计算,若该部件不使用流水线,则延迟为

    

必威 54

 

必威 55

 

     2.循环展开:

      在上例中,只有L.D、ADD.D和S.D这3条指令是有效操作 (取、加、存)
,占用3个时钟周期

而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。可以通过循环展开的方式消除冗余,减少循环控制开销

  • 循环展开技术

       把循环体的代码复制多次并按顺序排列,然后相应调整循环的结束条件

       这给编译器进行指令调度带来了更大的空间

 

     将上述例子中的循环展开3次得到4个循环体,然后对展开
后的指令序列在不调度和调度两种情况下,分析代码的性能。

     分配寄存器(不重复使用寄存器 ):

      F0、F4:用于展开后的第1个循环体

      F2:保存常数

      F6、F8:展开后的第2个循环体

      F10、F12:第3个循环体

      F14、F16:第4个循环体

     下面分三种情况比较循环展开和指令调度节省的时间:

  • 第一种情况:

必威 56   
 必威 57

  • 第二种情况:

      对指令序列进行优化调度,以减少空转周期

      浮点加法部件采用流水指令流出时钟

 

必威 58       
  必威 59

 

  • 第三种情况:

      对指令序列进行优化调度,以减少空转周期

      浮点运算部件不采用流水

 

必威 60   
 必威 61

 

必威 62

  • 循环展开和指令调度时要注意以下几个方面:

       保证正确性。
在循环展开和调度过程中尤其要注意两个地方的正确性:循环控制,操作数偏移量的修改。

       注意有效性。 只有能够找到不同循环体之间的无关性,才能有效
地使用循环展开。

       使用不同的寄存器。
(否则可能导致新的冲突)

      
删除多余的测试指令和分支指令,并对循环结束代码和新的循环体代码进行相应的修正。

       注意对存储器数据的相关性分析     

       注意新的相关性

 

  3.指令级并行

  指令调度可以通过两种形式实现:静态调度和动态调度

  • 静态调度

   依靠编译器(编译器需要做的很复杂,很完善)对代码进行静态调度,以减少相关和冲突。

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

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

 

  •  动态调度

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

  
能够处理一些在编译时情况不明的相关(比如涉及到存储器访问的相关),并简化了编译器;

  
能够使本来是面向某一流水线优化编译的代码在其他的流水线(动态调度)上也能高效地执行。

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

 

七、多指令流出技术(拓展了解)

  • CPI:平均每条指令执行周期数
  • 前面介绍的流水线最理想(实际上达不到)的状态就是每个周期执行一条指令,即CPI

    1,速度的提升似乎就此止步了,但是人类的智慧超出你想象,我们有办法让CPI
    < 1 吗?(即每条指令执行时间连一个周期也用不了)

  • 答案是肯定的,我们可以通过多指令流出技术实现这一点。

必威 63

 

  1.多指令流出处理机有两种实现方式:

  •  超标量(Superscalar)

  在每个时钟周期流出的指令条数不固定,依代码的具体情况而定。(但有上限)

   设这个上限为n,就称该处理机为n流出。

   可以通过编译器进行静态调度,也可以基于 Tomasulo算法进行动态调度。

   动态超标量调度技术的效果更好

 

  • 超长指令字VLIW(Very Long Instruction Word)  

  
在每个时钟周期流出的指令条数是固定的,这些指令构成一条长指令或者一个指令包(就是把能并行执行的多条指令组装成一条很长的指令,通常是100多位到几百位
)。

   指令包中,指令之间的并行性是通过指令显式地表示出来的。

   设置多个功能部件。

   指令字被分割成一些字段,每个字段称为一个操作槽
,直接独立地控制一个功能部件。

   在VLIW处理机中,所有的处理和指令调度都是由编译器静态完成的。

 

  2.指令多流出处理器受哪些因素的限制呢?

  主要受以下三个方面的影响:

   程序所固有的指令级并行性。

   硬件实现上的困难。

   超标量和超长指令字处理器固有的技术限制。

 

  3.由于指令多流出处理机受到多方面的限制,所以又引入了超流水线处理机

   超流水线处理机的特点是将每个流水段进一步细分,这样在一个时钟周期内能够分时流出多条指令。

  
对于一台每个时钟周期能流出n条指令的超流水线计算机来说,这n条指令不是同时流出的,而是每隔1/n
个时钟周期流出一条指令。

   实际上该超流水线计算机的流水线周期为1/n个 时钟周期。

 

  下面是一台每个时钟周期分时流出两条指令的超流水线计算机的时空图

必威 64

 

 

 

 

相关文章