您的位置:美高梅集团 > 数理科学 > 系统结构复习提纲

系统结构复习提纲

2019-09-18 18:20

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

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

7.3.1 并行算法

大题?

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

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

5.1.1 重叠原理与一次重叠

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

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

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

     

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

简答

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

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

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

第2章 指令系统

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

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

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

基本思路

横纵结合 寄存器组 写后读

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

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

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

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

填空

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

美高梅集团官网 1

第5章 标量处理机

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

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

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

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

5.1 重叠方式

 

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

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

        反相关:先读后写

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

 

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

计算、选择、填空

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

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

8.1.3 数据流计算机的结构

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

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

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

7

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

选择、简答

设计RISC的基本原则

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

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

  1. 选取其中常用的基本指令,使指令数精简。
  2. 逻辑实现采用硬联和微程序相结合。
  3. 在CPU中设置大量工作寄存器并采用重叠寄存器窗口。

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

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

 

5.3.1 超标量处理机

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

     1. 什么是流水线?

5.2 流水方式

流水的分类

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

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

重点掌握动态流水线

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

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

选择、填空

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

  • 操作方式:同步、异步、同步与异步组合。 阵列处理机根据其SIMD性质均为同步 ,异步与组合多用于多处理机。
  • 控制策略:集中、分布。 多数SIMD采用集中控制部件
  • 交换方法:线路交换、包交换、线路与包交换组合。 SIMD多采用硬连线路交换 ,包交换多用于多处理机和计算机网络中。

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

6.3 SIMD计算机的互连网络

注意:互 网络

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

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

 

8.1.1 数据驱动的概念

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

1.3.1 软硬件取舍的基本原则

简答、选择、填空

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

        输出相关:先写后写

5.3.3 超流水线处理机

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

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

1.5.1 并行性的概念和开发

开发并行性的途径

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

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

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

  • 字串位串 (WSBS)
  • 字串位并 (WSBP)
  • 字并位串 (WPBS)
  • 字并位并 (WPBP)

五、流水线性能分析

8.1 数据流计算机

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

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

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

2.4 指令系统的发展和改进

  • CISC 复杂指令系统计算机
  • RISC 精简指令系统计算机

 

6.2 阵列处理机的原理

       资源份数不够

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])

选择、填空、简答

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

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

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

选择

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

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

计算机系统的设计方法

  • 由上往下
  • 由下往上
  • 由中间开始
  • 有些流水线处理机只有一个存储器,将数据和指令放在一起,访存指令会导致访存冲突

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

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

第7章 多处理机

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

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

选择、填空

美高梅集团官网 2

1-3

  3.指令级并行

7.4 多处理机的操作系统

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

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

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

 

习题1

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

第6章 向量处理机

     XOR   R8,R1,R9

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

本文导读:

7.1.2 多处理机的硬件结构

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

选择、填空、简答

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

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

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

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

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

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

选择、填空

美高梅集团官网 3

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

定义、特点

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

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

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

1-10

  • 名相关:换名技术

5.2.3.4 非线性流水的调度

大题?
直接做题

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

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

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

6.3.4 基本的多级互连网络

选择、填空

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

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

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

大题
直接做题

     DADDIU  R1,R1,#-8

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) × 瓶颈段时间

  Loop:L.D F0,0(R1) 

7.3.3 并行语言与并行编译

大题
直接做题

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

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

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

 

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

   第四周期:空;

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

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

EX

  • 时间—空间图 Ⅱ
     横坐标:表示时间,即各个任务或指令在流水线中 所在该时刻所对应的子过程

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

       注意新的相关性

  • 静态调度

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

美高梅集团官网 4     美高梅集团官网 5

美高梅集团官网 6                            

IF

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

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

       功能部件不是完全流水

  • 工作流程:分装入、流水、排空 三个流程
  • 控制相关
  • 第二种情况:

 

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

6

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

 

  • 单周期处理机模型:一个周期完成一个指令(每个周期是等长的),指令长度可能不一样,会造成很大的浪费
  • 多周期处理机模型:将一个指令的完成划分成若干个周期来实现
  • 流水线模型

     2.按功能分

      F10、F12:第3个循环体

 

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

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

 

       

 

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

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

     3.流水线冲突带来问题

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

二、流水线技术

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

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

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

  • 引入新技术进行优化
  • 出现新问题
  • 解决新问题

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

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

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

  • 结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突,比如说,前面后面指令同时访问存储器
  • 综上所述,综对于数据冲突来说,可以通过定向技术减少数据冲突引起的停顿 (定向技术也称为旁路或短路)。但是并不是所有的数据冲突都可以用定向技术来解决:如下例:

美高梅集团官网 7       美高梅集团官网 8   

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

 

     4.数据冲突

     DADD  R4,R1,R5

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

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

 

美高梅集团官网 9

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

 

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

 

 

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

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

美高梅集团官网 10

美高梅集团官网,     以指令一DADD  R1,R2,R3为例:

???

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

 

 

 

 

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

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

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

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

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

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

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

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

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

 

六、循环展开优化

  1. 指令周期

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

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

 

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

 

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

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

  • 同一个周期数据冲突的情况:以指令四AND   R8,R1,R9为例:在第五周期,第一条指令R2 R3结果正准备写入到R1中,但是此时第四条指令现在就需要使用R1(此时R1的值还不是R1 R2),显然会出现问题
  • 如果猜对了,即已经确定分支失败:将分支指令看作是一条普通指令,流水线正常流动
  • 如果猜错了,即已经确定分支成功,那也不要紧,流水线就把在分支指令之后 取出的所有指令转化为空操作(到最后需要将结果写入到寄存器时,就通过使能信号不让它写入就可以了 ),并按分支目地重新取指令执行。
  •  进一步改进:分支取消机制(取消分支)

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

 

 

     从例题入手理解

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

 

     AND   R6,R1,R7

 

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

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

美高梅集团官网 11

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

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

美高梅集团官网 12

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

     各段执行时间不等时:

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

时钟周期

美高梅集团官网 13

 

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

      F2:保存常数

 

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

 

 

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

美高梅集团官网 14

美高梅集团官网 15

     

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

  • 时间—空间图 **

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

 

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

     2.循环展开:

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

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

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

        或间接使用

        由分支指令引起的相关

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

 

 

( i = i 1)

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

     BNE R1,R2,Loop

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

美高梅集团官网 16

 

WB

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

      标量流水线

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

 

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

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

下面一个是正确画法:

     分析:

 

 

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

        真相关:先写后读

 

WB

     美高梅集团官网 17

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

 

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

 

1

     5.结构冲突

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

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

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

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

指令编号

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

 

  •  动态调度

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

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

美高梅集团官网 18          美高梅集团官网 19

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

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

     同步流水线

  • 主要思想:

     ADD.D F4,F0,F2

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

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

   硬件实现上的困难。

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

 

 

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

          

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

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

     4.流水线的描述方法

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

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

 

 

美高梅集团官网 20     美高梅集团官网 21

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

MEM

(s = s

 

 

  • 循环展开技术

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

一、并行技术

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

EX

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

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

     S.D F4, 0(R1)

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

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

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

5

 

 

 美高梅集团官网 22

 

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

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

 

 

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

    1,速度的提升似乎就此止步了,但是人类的智慧超出你想象,我们有办法让CPI < 1 吗?(即每条指令执行时间连一个周期也用不了)
  • 答案是肯定的,我们可以通过多指令流出技术实现这一点。

 

 

 

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

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

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

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

         操作级流水操作重叠

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

 

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

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

ID

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

  • 第一种情况:

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

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

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

 

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

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

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

 

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

  • i )

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

 

     

IF

 美高梅集团官网 23

 

     4.按处理的数据类型

美高梅集团官网 24

     5.流水线特点

   设置多个功能部件。

      不同之处 :

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

DADD  Rs,  Rs ,Ri

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

 美高梅集团官网 25

 

      在上例中,只有L.D、ADD.D和S.D这3条指令是有效操作 (取、加、存) ,占用3个时钟周期。 而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。可以通过循环展开的方式消除冗余,减少循环控制开销

  • 硬件要求:

 

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

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

     LD    R1,0(R2)

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

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

 

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

    5.按控制方式

  1. 新技术的设计与实现
  • 数据相关

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

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

     解:首先画出时空图

      向量流水线

           采用一些机制可以解决

 

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

美高梅集团官网 26

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

2

 

           权衡

美高梅集团官网 27           美高梅集团官网 28

3

 

美高梅集团官网 29

 

     4.结果分析:

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

     2.指令重叠方式

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

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

 

     2.流水线冲突(hazards)

 

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

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

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

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

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

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

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

 

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

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

 

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

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

Start

 

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

      F14、F16:第4个循环体

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

  •  超标量(Superscalar)

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

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

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

 

MEM

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

美高梅集团官网 30

    

 

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

  • 在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 运算呢?

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

ID

美高梅集团官网 31

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

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

DADD  Ri,  Ri,  1

 

     对上图的解读:

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

美高梅集团官网 32        美高梅集团官网 33      

  • 资源重复:如多核
  • 资源共享:如CPU分时技术
  • 时间重叠:如流水线技术
  • R3)的结果正处在DM后面,这样一来,(R2 R3)的结果会通过我们刚拉的那根线传到ALU前,这时候,我们在进入ALU之前设置一个多路选通器,不选择错误的R1值,而是选择使用传过来的(R2 R3)值,问题就解决了!

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

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

 

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

 

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

美高梅集团官网 34

 

 

  • 第三种情况:

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

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

 

 

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

4

     3.流水线工作设计

 

     1.按处理级别

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

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

本文由美高梅集团发布于数理科学,转载请注明出处:系统结构复习提纲

关键词: