系统结构复习提纲

 数理科学     |      2019-12-12 04:07

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

本文导读:

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

流水线的原理。流水线的基本原理是把一个重复的过程分解为若干个子过程,前一个子过程为下一个子过程创造执行条件,每一个过程可以与其它子过程同时进行。流水线各段执行时间最长的那段为整个流水线的瓶颈,一般地,将其执行时间称为流水线的周期。加速比 = 采用流水线后的速度/未采用流水线的速度。= 未采用流水线的时间/采用流水线后的时间。流水线的设备利用率,在时空图上表现为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.3 计算机系统的软、硬件取舍和性能评测及定量设计原理

一、并行技术

1.3.1 软硬件取舍的基本原则

简答、选择、填空

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

选择、填空、简答

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

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

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

计算机系统的设计方法

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

 

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章 标量处理机

图片 1

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. 能用规整单一的基本构件组合而成(模块化)

 图片 2

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

选择、填空

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

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

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

计算、选择、填空

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

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

6.3.4 基本的多级互连网络

选择、填空

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

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

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

大题
直接做题

图片 3

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 并行算法

大题?

图片 4

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

  • 硬件要求:

7.3.3 并行语言与并行编译

大题
直接做题

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

7.4 多处理机的操作系统

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

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

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

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

8.1 数据流计算机

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

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

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

8.1.1 数据驱动的概念

 

8.1.3 数据流计算机的结构

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

     5.流水线特点

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

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

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

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

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

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

 

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

     1.按处理级别

         操作级流水操作重叠

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

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

图片 5

 

     2.按功能分

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

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

 

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

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

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

 

     4.按处理的数据类型

      标量流水线

      向量流水线

 

    5.按控制方式

     同步流水线

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

 

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

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

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

 

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

图片 6

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

 图片 7

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

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

      不同之处 :

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

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

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

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

 

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

图片 8

 

     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

 

     图片 9

 

     对上图的解读:

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

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

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

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