并行性
两个工作在时间上相互重叠,即具备了并行性。
※并行性等级(数据处理角度)
- 字串位串 n=1 m=1
- 字并位串 n>1 m=1
- 字串位并 n=1 m>1
- 字并位并 n>1 m>1
※并行性等级(执行角度)
- 指令内部并行:指令内部的微操作之间的并行
- 指令间并行:并行两条或多条指令
- 任务级或过程级并行:并行执行两个或多个过程或任务
- 作业或程序级并行:多个作业或程序间并行
※提高并行性的三条技术途径
- 时间重叠(流水线处理机):多个处理过程在时间上相互错开,轮流使用。
- 资源重复(多处理级系统):重复设置多个硬件部件。
- 资源共享(分时系统):多个用户或处理机共享某些资源。
时间重叠
时间重叠是单处理机并行性开发的主要途径。
一次重叠:
现行控制:
增加一些硬件实现预取和预处理。使分析和执行部件分别连续不断地运行,使部件空闲状态减至最低。
先行控制相比重叠的区别:
分析和执行部件可同时处理两条不相邻指令
资源重复
资源重复主要是为了提高系统的可靠性,即在关键部件上采用冗余技术。
※多机系统中的并行性
- 时间重叠:多个专用功能部件。
- 资源重复:早期不是为了提高速度,而是为了提高可靠性。
- 资源共享:网络化。
多机系统的比较
- 同构型多处理机:数据并行。
- 异构型多处理机:任务并行。
- 分布处理系统:各处理机尽量完成本地作业。
流水线
流水线分类
- 按功能分类
- 单功能流水线
- 多功能流水线
- 按工作方式分类
- 静态流水线(只能按一种连接方式工作)
- 动态流水线
- 按流水的级别分类
- 部件级流水线(运算器流水线)
- 处理机级流水线(指令流水线)
- 处理机间流水线(宏流水线)
- 按数据表示分类
- 标量流水处理机
- 向量流水处理机
- 按流水线中是否有反馈回路分类
- 线性流水线(每个流水段都流过且仅流过一次)
- 非线性流水线(有反馈回路或前馈回路)
其中:
动态流水线必是多功能流水线
单功能流水线必是静态流水线
※流水线(技术)的5个主要特点
- 可以划分为若干互有联系的子过程
- 流水线每个功能段所需时间应尽可能相等
- 形成流水线需要”装入时间”或称”通过时间”
- 流水线不应常”断流”,否则效率不会很高
- 流水线适用于大量重复的过程,输入端最好能连续地提供服务
流水线性能指标
(1)吞吐率(单位时间完成的任务数):
(2)各段时间相等,输入任务连续时,完成n个任务所需时间:
其中k是流水线的段数,是时钟周期。
(3)加速比:
流水线段数为,从极限的角度易知最大极限加速比就是(当任务数)。
(4)效率:
也即
流水线各段执行时间不相等的解决办法
(1)将[瓶颈]部分再细分成更细的并行流水段。
(2)将[瓶颈]流水段重复设置,即增加能相互并行的[瓶颈]处理硬件。
非线性流水线任务的调度
非线性流水线需要用连接图和预约表共同表示,预约表中的”X”表示该时间该功能段被使用。
目标:找出一个最小的启动循环周期,按照这周期向流水线输入新任务,使各个功能段不会发生冲突,且吞吐率和效率最高(完成最快)。
非线性流水线的冲突
启动距离:连续输入两个任务之间的时间间隔。
流水线冲突:几个任务争用同一功能段。
禁止启动距离:引起非线性流水线功能段冲突的启动距离。
禁止向量:每行任意两个“×”之间的距离,去掉重复,组成数列。
平均启动距离:一个启动循环内的所有启动距离相加,然后除以这个启动循环内的启动距离个数。
[1]无冲突调度方法
如预约表:
时间\功能段 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
S1 | X | X | |||||
S2 | X | X | |||||
S3 | X | X | |||||
S4 | X |
(1)写出流水线的禁止向量和初始冲突向量
禁止向量:
初始冲突向量:
(2)画出调度流水线的状态图
当移出的位为1,表示用这些启动距离像流水线输入任务会发生功能段的冲突,因此在状态图中不做任何处理。
当移出的位为0,表示用这个启动距离向流水线输入任务不发生功能段的冲突,这时做“按位或”产生新的冲突向量。
-
-
- 无可右移
-
-
(3)求最小启动循环和最小平均启动距离
最小启动循环:和,最小平均启动距离,即最小启动循环的平均距离,为。
(4)求平均启动距离最小的恒定循环
恒定循环:只有一个等待时间值的循环,即形如的循环。
图中的恒定循环有和,所以最小的就是。
[2]最优调度算法
最小平均启动距离的下限是预约表里任意一行的最多个数,从上表中可以看到即是,所以不妨尝试构造恒定循环。
那么,在表每一行中与第一个距离为2的位置都要留空,如原来在该位置有则向后移动,表变成(“-“处是原来的位置):
时间\功能段 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
S1 | X | - | X | |||||
S2 | X | - | X | |||||
S3 | X | - | X | |||||
S4 | X |
即相当于在到之间添加了一个延迟:
时间\功能段 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
D1 | X |
现在,优化后的流水线可以以循环工作了。
相关性
分类:
- 数据相关:执行本条指令用到的指令、操作数、变址量是前面执行的结果。
- 控制相关:由条件分支指令、转子程序指令、中断指令引起的相关。
一些相关及解决:
- 指令相关->在程序执行过程中不允许修改指令。
- 通用寄存器数据相关->设置专用数据通路。
- LOAD相关->由硬件自动插入空操作,直到LOAD操作完成。
动态调度技术
- 顺序流动:任务按顺序进入流水线,也按顺序离开流水线。
- 吞吐率和效率低。
- 流水线的控制逻辑比较简单。
- 乱序流动:指令流出流水线的顺序和流入的顺序不同。
- 写读相关
- 读写相关
- 写写相关
- 解决:数据重定向、变量换名、建立专用通路。
单发射和多发射
单发射:每个时钟周期取指、译码、执行、写回各最多一次。
多发射:每个时钟周期取指、译码、执行、写回可以有多次。
超标量处理机(空间并行性)
普通标量处理机希望相同操作连续出现,这样流水线效率才能得到充分发挥。 超标量处理机正好相反,希望相同操作不要连续出现,否则可能发生资源冲突。
有不止一条能同时工作的指令流水线。拥有先行指令窗口,能从指令cache中预取多条指令,并进行相关性分析和功能部件冲突检测。
如:i860、i960、Pentium、MC88110、Power6000、SuperSPARC。
顺序发射和乱序发射
顺序发射:指令按程序中的排列顺序发射。
乱序发射:指令不按程序中的排列顺序发射。
顺序完成和乱序完成
顺序完成:指令按程序中的排列顺序执行完。
乱序完成:指令不按程序中的排列顺序执行完。
多流水线调度主要方法
- 顺序发射顺序完成
- 顺序发射乱序完成
- 乱序发射乱序完成(功能部件得到充分利用)
资源冲突
如果操作部件使用流水线结构,发生资源冲突的可能性小,否则发生资源冲突的可能性大,所以超标量处理机的操作部件一般要采用流水线结构。
超标量处理机性能
N条指令在单流水线每隔1个时钟周期发射一条指令的处理机上的执行时间:
在每个周期发射m条指令的超标量流水机上执行时间:
加速比:
加速比极限为。
超流水线处理机(时间并行性)
- 在一个周期内分时发射多条指令的处理机,每隔个时钟周期发射一条指令。
- 指令流水线的段数大于等于8 的流水线处理机。
如:MIPS R4000。
超流水线处理机性能
N条指令在单流水线每隔1个时钟周期发射一条指令的处理机上的执行时间:
在每隔个时钟周期发射一条指令的超流水线处理机上:
加速比:
加速比极限为。
超标量超流水线处理机
一个时钟周期发射m次,每次发射n条指令。
N条指令在单流水线每隔1个时钟周期发射一条指令的处理机上的执行时间:
在每隔个时钟周期发射m条指令的超标量超流水线处理机上:
加速比:
加速比极限为。