计算机系统结构课程总结(流水线)

时间:2024-04-13 14:19:41

并行性

两个工作在时间上相互重叠,即具备了并行性。

=+

※并行性等级(数据处理角度)

  1. 字串位串 n=1 m=1
  2. 字并位串 n>1 m=1
  3. 字串位并 n=1 m>1
  4. 字并位并 n>1 m>1

※并行性等级(执行角度)

  1. 指令内部并行:指令内部的微操作之间的并行
  2. 指令间并行:并行两条或多条指令
  3. 任务级或过程级并行:并行执行两个或多个过程或任务
  4. 作业或程序级并行:多个作业或程序间并行

※提高并行性的三条技术途径

  • 时间重叠(流水线处理机):多个处理过程在时间上相互错开,轮流使用。
  • 资源重复(多处理级系统):重复设置多个硬件部件。
  • 资源共享(分时系统):多个用户或处理机共享某些资源。

时间重叠

时间重叠是单处理机并行性开发的主要途径。

一次重叠:
计算机系统结构课程总结(流水线)
现行控制:
增加一些硬件实现预取和预处理。使分析和执行部件分别连续不断地运行,使部件空闲状态减至最低。
计算机系统结构课程总结(流水线)
先行控制相比重叠的区别:
分析和执行部件可同时处理两条不相邻指令

资源重复

资源重复主要是为了提高系统的可靠性,即在关键部件上采用冗余技术。

※多机系统中的并行性

  • 时间重叠:多个专用功能部件。
  • 资源重复:早期不是为了提高速度,而是为了提高可靠性。
  • 资源共享:网络化。

多机系统的比较

  • 同构型多处理机:数据并行。
  • 异构型多处理机:任务并行。
  • 分布处理系统:各处理机尽量完成本地作业。

流水线

计算机系统结构课程总结(流水线)

流水线分类

  • 按功能分类
    • 单功能流水线
    • 多功能流水线
  • 按工作方式分类
    • 静态流水线(只能按一种连接方式工作)
    • 动态流水线
  • 按流水的级别分类
    • 部件级流水线(运算器流水线)
    • 处理机级流水线(指令流水线)
    • 处理机间流水线(宏流水线)
  • 按数据表示分类
    • 标量流水处理机
    • 向量流水处理机
  • 按流水线中是否有反馈回路分类
    • 线性流水线(每个流水段都流过且仅流过一次)
    • 非线性流水线(有反馈回路或前馈回路)

其中:
动态流水线必是多功能流水线
单功能流水线必是静态流水线

※流水线(技术)的5个主要特点

  1. 可以划分为若干互有联系的子过程
  2. 流水线每个功能段所需时间应尽可能相等
  3. 形成流水线需要”装入时间”或称”通过时间”
  4. 流水线不应常”断流”,否则效率不会很高
  5. 流水线适用于大量重复的过程,输入端最好能连续地提供服务

流水线性能指标

(1)吞吐率(单位时间完成的任务数):

TP=nTk

(2)各段时间相等,输入任务连续时,完成n个任务所需时间:
Tk=(k+n1)t

其中k是流水线的段数,t是时钟周期。

(3)加速比:

S=T0线Tk

流水线段数为k,从极限的角度易知最大极限加速比就是k(当任务数n)。

(4)效率:
E=n/k
也即=T0kTk=Sk

流水线各段执行时间不相等的解决办法

(1)将[瓶颈]部分再细分成更细的并行流水段。
(2)将[瓶颈]流水段重复设置,即增加能相互并行的[瓶颈]处理硬件。

非线性流水线任务的调度

非线性流水线需要用连接图预约表共同表示,预约表中的”X”表示该时间该功能段被使用。

目标:找出一个最小的启动循环周期,按照这周期向流水线输入新任务,使各个功能段不会发生冲突,且吞吐率和效率最高(完成最快)。

非线性流水线的冲突

启动距离:连续输入两个任务之间的时间间隔。
流水线冲突:几个任务争用同一功能段。
禁止启动距离:引起非线性流水线功能段冲突的启动距离。
禁止向量:每行任意两个“×”之间的距离,去掉重复,组成数列。
平均启动距离:一个启动循环内的所有启动距离相加,然后除以这个启动循环内的启动距离个数。

[1]无冲突调度方法

如预约表:

时间\功能段 1 2 3 4 5 6 7
S1 X X
S2 X X
S3 X X
S4 X

(1)写出流水线的禁止向量和初始冲突向量
禁止向量:(2,4,6)
初始冲突向量:C=(1,0,1,0,1,0)

(2)画出调度流水线的状态图

当移出的位为1,表示用这些启动距离像流水线输入任务会发生功能段的冲突,因此在状态图中不做任何处理。
当移出的位为0,表示用这个启动距离向流水线输入任务不发生功能段的冲突,这时做“按位或”产生新的冲突向量。

  • C=(1,0,1,0,1,0)
    • D=C1C=(0,1,0,1,0,1)(1,0,1,0,1,0)=(1,1,1,1,1,1)
    • E=C3C=(0,0,0,1,0,1)(1,0,1,0,1,0)=(1,0,1,1,1,1)
    • F=C5C=(0,0,0,0,0,1)(1,0,1,0,1,0)=(1,0,1,0,1,1)
  • D=(1,1,1,1,1,1)
    • 无可右移
  • E=(1,0,1,1,1,1)
    • E5C=(0,0,0,0,0,1)(1,0,1,0,1,0)=F
  • F=(1,0,1,0,1,1)
    • F3C=(0,0,0,1,0,1)(1,0,1,0,1,0)=E
    • F5C=(0,0,0,0,0,1)(1,0,1,0,1,0)=F

计算机系统结构课程总结(流水线)
(3)求最小启动循环和最小平均启动距离
最小启动循环:(1,7)(3,5),最小平均启动距离,即最小启动循环的平均距离,为4

(4)求平均启动距离最小的恒定循环

恒定循环:只有一个等待时间值的循环,即形如(x)的循环。

图中的恒定循环有(5)(7),所以最小的就是(5)

[2]最优调度算法

最小平均启动距离的下限是预约表里任意一行X的最多个数,从上表中可以看到即是2,所以不妨尝试构造恒定循环(2)

那么,在表每一行中与第一个X距离为2的位置都要留空,如原来在该位置有X则向后移动,表变成(“-“处是原来的位置):

时间\功能段 1 2 3 4 5 6 7 8
S1 X - X
S2 X - X
S3 X - X
S4 X

即相当于在S4S3之间添加了一个延迟D1

时间\功能段 1 2 3 4 5 6 7 8
D1 X

现在,优化后的流水线可以以循环(2)工作了。


相关性

分类:

  • 数据相关:执行本条指令用到的指令、操作数、变址量是前面执行的结果。
  • 控制相关:由条件分支指令、转子程序指令、中断指令引起的相关。

一些相关及解决:

  • 指令相关->在程序执行过程中不允许修改指令。
  • 通用寄存器数据相关->设置专用数据通路。
  • LOAD相关->由硬件自动插入空操作,直到LOAD操作完成。

动态调度技术

  • 顺序流动:任务按顺序进入流水线,也按顺序离开流水线。
    • 吞吐率和效率低。
    • 流水线的控制逻辑比较简单。
  • 乱序流动:指令流出流水线的顺序和流入的顺序不同。
    • 写读相关
    • 读写相关
    • 写写相关
    • 解决:数据重定向、变量换名、建立专用通路。

单发射和多发射

单发射:每个时钟周期取指、译码、执行、写回各最多一次。
多发射:每个时钟周期取指、译码、执行、写回可以有多次。

超标量处理机(空间并行性)

普通标量处理机希望相同操作连续出现,这样流水线效率才能得到充分发挥。 超标量处理机正好相反,希望相同操作不要连续出现,否则可能发生资源冲突。

有不止一条能同时工作的指令流水线。拥有先行指令窗口,能从指令cache中预取多条指令,并进行相关性分析和功能部件冲突检测。

如:i860、i960、Pentium、MC88110、Power6000、SuperSPARC。

顺序发射和乱序发射

顺序发射:指令按程序中的排列顺序发射。
乱序发射:指令不按程序中的排列顺序发射。

顺序完成和乱序完成

顺序完成:指令按程序中的排列顺序执行完。
乱序完成:指令不按程序中的排列顺序执行完。

多流水线调度主要方法

  • 顺序发射顺序完成
  • 顺序发射乱序完成
  • 乱序发射乱序完成(功能部件得到充分利用)

资源冲突

如果操作部件使用流水线结构,发生资源冲突的可能性小,否则发生资源冲突的可能性大,所以超标量处理机的操作部件一般要采用流水线结构。

超标量处理机性能

N条指令在单流水线每隔1个时钟周期发射一条指令的处理机上的执行时间:

T(1,1)=(k+N1)t

在每个周期发射m条指令的超标量流水机上执行时间:
T(m,1)=(k+Nmm)t

加速比:
S(m,1)=T(1,1)T(m,1)

加速比极限为m


超流水线处理机(时间并行性)

  • 在一个周期内分时发射多条指令的处理机,每隔1n个时钟周期发射一条指令。
  • 指令流水线的段数大于等于8 的流水线处理机。

如:MIPS R4000。

超流水线处理机性能

N条指令在单流水线每隔1个时钟周期发射一条指令的处理机上的执行时间:

T(1,1)=(k+N1)t

在每隔1n个时钟周期发射一条指令的超流水线处理机上:
T(1,n)=(k+N1n)t

加速比:
S(1,n)=T(1,1)T(1,n)

加速比极限为n


超标量超流水线处理机

一个时钟周期发射m次,每次发射n条指令。

N条指令在单流水线每隔1个时钟周期发射一条指令的处理机上的执行时间:

T(1,1)=(k+N1)t

在每隔1n个时钟周期发射m条指令的超标量超流水线处理机上:
T(m,n)=(k+Nmmn)t

加速比:
S(m,n)=T(1,1)T(m,n)

加速比极限为mn