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