计算机系统结构.pdf

第 1 页 共 10 页 第三次作业 5 7 一条线性流水线由 4 个功能段组成 每个功能段的延迟时间都相等 都为t 开始 5 个t 每间隔一个t 向流水线输入一个任务 然后停顿 2 个t 如此重复 求流水 线的实际吞吐率 加速比和效率 10 分 解 由于题意不清 可做出下面两种时空图 从图中可以看出 除了开始第一个周期外 之后每七个时间段可以完成 5 个任务 则流水线 的吞吐率为 51 0 714 17 k nn TP Tntt 加速比 0 5420 2 86 17 7 k Tnt S Tnt 效率 0 20 0 714 4 17 k Tn t E k Tnt 从图中可以看出 除了开始第一个周期外 之后每七个时间段可以完成 3 个任务 则流水线 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 5t 2t 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 5t 2t 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 6 第 2 页 共 10 页 的吞吐率为 7 3 71 3 tn n T n TP k 加速比 7 12 71 43 0 tn tn T T S k 效率 7 3 71 4 12 0 tn tn Tk T TP k 下面这种时空图是不正确的 有部分同学是这样画的 5 8 用一条5个功能段的浮点加法器流水线计算 10 1i i AF 每个功能段的延迟时间均相等 流水线的输出端与输入端之间有直接数据通路 而且设置有足够的缓冲寄存器 要求用 尽可能短的时间完成计算 画出流水线时空图 计算流水线的实际吞吐率 加速比和效 率 10 分 解 87651094321 10 1 AAAAAAAAAAAF i i 根据以上对计算的划分 可以画出流水线时空图如下 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 9t 2t 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 9 9 9 9 9 第 3 页 共 10 页 其中 任务 1 为 21 AA 任务 2 为 43 AA 任务 3 为 65 AA 任务 4 为 87 AA 任务5为 109 AA 任务6为 4321 AAAA 任务7为 8765 AAAA 任务 8 为 4321109 AAAAAA 任务 9 为 43211098765 AAAAAAAAAA 设每个功能段的延迟时间均为t 则由上图可以得到 流水线完成计算需要的总时间为 tTk 21 不使用流水线 完成计算需要的总时间为 ttT 4559 0 流水线的实际吞吐率为 ttT TP k 1 4286 0 21 99 流水线的加速比为 1429 2 21 45 21 45 0 t t T T S k 流水线的效率为 4286 0 105 45 215 45 0 t t Tk T E k 5 11 一条有 4 个功能段的非线性流水线 每个功能段的延迟时间都相等 都为 20ns 它的 预约表如下 时 间 功能段 1 2 3 4 5 6 7 S1 S2 S3 S4 写出流水线的禁止集合和初始冲突向量 画出调度流水线的状态图 求流水线的最小启动循环和最小平均启动距离 求平均启动距离最小的恒定循环 求流水线的最大吞吐率 按照最小启动循环连续输入 10 个任务 求流水线的实际吞吐量 画出该流水线各功能段之间的连接图 30 分 第 4 页 共 10 页 解 在预约表中 第 1 行的第 1 列与第 7 列之间的距离为 6 第 2 行的第 2 列与第 6 列之间的距离为 4 第 4 行的第 3 列与第 5 列之间的距离为 2 所以流水线的禁止集合为 2 4 6 初始冲突向量为 101010 画出调度流水线的状态图如下 由上图可以找到如下的简单循环 并计算相应的平均启动距离 简单循环 平均启动距离 5 5 7 7 1 7 4 3 5 4 3 7 5 5 7 6 3 5 7 5 5 3 7 5 因此最小启动循环为 1 7 或 3 5 最小平均启动距离为 4 由上表可以看出 平均启动距离最小的恒定循环为 5 已经求得最小平均启动距离为 4 则流水线完成 n 个连续任务需要的总时间最少为 tntntTk 34417 流水线的最大吞吐率为 7 9 max 1025 1 10204 1 4 1 34 n ttn n T n TP k 最小启动循环的平均启动距离为 4 启动循环可以为 1 7 7 1 3 5 和 5 3 四种情况 连续输入 10 个任务 选取不同的启动循环时 前九个任务的 输入输出情况均为 101010 111111 101111 101011 1 3 5 7 7 7 7 5 3 5 第 5 页 共 10 页 0 时刻输入第一个任务 7 时刻输出 32 时刻输入第九个任务 39 时刻输出 启动循环为 1 7 时 33 时刻输入第十个任务 40 时刻输出 流水线的实际吞吐率为 7 9 1025 1 102040 10 40 10 t TP 启动循环为 7 1 时 39 时刻输入第十个任务 46 时刻输出 流水线的实际吞吐率为 7 9 10087 1 102046 10 46 10 t TP 启动循环为 3 5 时 35 时刻输入第十个任务 42 时刻输出 流水线的实际吞吐率为 7 9 101905 1 102042 10 42 10 t TP 启动循环为 5 3 时 37 时刻输入第十个任务 44 时刻输出 流水线的实际吞吐率为 7 9 101364 1 102044 10 44 10 t TP 画出该流水线各功能段之间的连接图如下 5 15 一条由 4 个功能段组成的非线性流水线的预约表如下 每个功能段的延迟时间都为 10ns 时 间 功能段 1 2 3 4 5 6 S1 S2 S3 S4 写出流水线的禁止集合和初始冲突向量 画出调度流水线的状态图 求流水线的最小启动循环和最小平均启动距离 在流水线中插入一个非计算延迟功能段后 求该流水线的最佳启动循环及其最小平 均启动距离 画出插入一个非计算延迟功能段后的流水线预约表 5 行 7 列 画出插入一个非计算延迟功能段后的流水线状态变换图 分别计算在插入一个非计算延迟功能段前 后的最大吞吐率 如果连续输入 10 个任务 分别计算在插入一个非计算延迟功能段前 后的实际吞 输入 输出 S1 S2 S3 S4 第 6 页 共 10 页 吐率 30 分 解 在预约表中 第 1 行的第 1 列与第 6 列之间的距离为 5 第 2 行的第 2 列与第 4 列之间的距离为 2 第 4 行的第 4 列与第 5 列之间的距离为 1 所以流水线的禁止集合为 1 2 5 初始冲突向量为 10011 画出调度流水线的状态图如下 最小启动循环为 3 最小平均启动距离为 3 在预约表中任意一行中 的最大个数为 2 所以在流水线中插入一个非计算延迟 功能段后 该流水线的最佳启动循环为 2 和 1 3 最小平均启动距离为 2 选取最佳启动循环 1 3 画出插入一个非计算延迟功能段后的流水线预约表如 下 时间 1 2 3 4 5 6 7 功能段 S1 S2 S3 S4 延迟 D1 在以上插入一个非计算延迟功能段后的流水线预约表中 第 1 行的第 1 列与第 7 列之间的距离为 6 第 2 行的第 2 列与第 4 列之间的距离为 2 第 4 行的第 4 列与第 6 列之间的距离为 2 所以该流水线的禁止集合为 2 6 初始冲突向量为 100010 画出插入一个非计算延迟功能段后的流水线状态变换图如下 10011 3 4 6 100010 100110 110011 100011 1 3 5 4 7 4 7 4 7 7 4 3 3 1 5 5 第 7 页 共 10 页 在插入一个非计算延迟功能段前 最小平均启动距离为 3 流水线完成 n 个连续任务需要的总时间最少为 tntntTk 33316 流水线的最大吞吐率为 7 9 max 1033 3 10103 1 3 1 33 n ttn n T n TP k 在插入一个非计算延迟功能段后 最小平均启动距离为 2 流水线完成 n 个连续任务需要的总时间最少为 tntntTk 52217 流水线的最大吞吐率为 7 9 max 105 10102 1 2 1 52 n ttn n T n TP k 在插入一个非计算延迟功能段前 最小启动循环的平均启动距离为 3 启动循环为 3 连续输入 10 个任务 输入输 出情况为 0 时刻输入第一个任务 6 时刻输出 3 时刻输入第二个任务 9 时刻输出 27 时刻输入第十个任务 33 时刻输出 流水线的实际吞吐率为 7 9 100303 3 101033 10 33 10 t TP 在插入一个非计算延迟功能段后 最小启动循环的平均启动距离为 2 启动循环可以为 1 3 3 1 两种情况 连续输入 10 个任务 选取不同的启动循环时 前九个任务的输入输出情况均为 0 时刻输入第一个任务 7 时刻输出 16 时刻输入第九个任务 23 时刻输出 启动循环为 1 3 时 17 时刻输入第十个任务 24 时刻输出 流水线的实际吞吐率为 7 9 101667 4 101024 10 24 10 t TP 启动循环为 3 1 时 19 时刻输入第十个任务 26 时刻输出 流水线的实际吞吐率为 7 9 108462 3 101026 10 26 10 t TP 5 17 下面一段程序在一台超标量处理机上运行 每个时钟周期发射两条指令 所有指令都 要经过 取指令 译码 执行 和 写结果 四个阶段 其中 取指令 译码 第 8 页 共 10 页 和 写结果 三个阶段的延迟时间都为一个时钟周期 在 执行 阶段 访问存储器 部件和逻辑操作部件各延迟一个时钟周期 加法操作部件延迟两个时钟周期 乘法操 作部件延迟 3 个时钟周期 4 种操作部件各设置一个 加法部件和乘法部件都采用流 水线结构 每一级流水线的延迟时间都为一个时钟周期 每个操作部件的输出都有直 接数据通路连接到其他操作部件的输入端 k LOAD R0 A R0 Cache 的 A 单元 k 1 ADD R1 R0 R1 R1 R0 k 2 STORE R1 B Cache 的 B 单元 R1 k 3 ADD R2 R3 R2 R2 R3 k 4 MUL R3 R4 R3 R3 R4 k 5 OR R5 R6 R5 R5 R6 k 6 ADD R5 R7 R5 R5 R7 列出程序中可能出现的所有数据相关 采用顺序发射顺序完成调度方法 画出流水线的时空图 并计算执行这个程序所用 的时间 采用顺序发射乱序完成调度方法 画出流水线的时空图和各操作的完成时间 并计 算执行这个程序所用的时间 如果再增加一个能够存放 7 条指令的先行指令窗口 采用乱序发射乱序完成调度 方法 画出流水线的时空图 各操作的发射时间图和完成时间图 并计算执行这个 程序所用的时间 20 分 解 指令 k 和指令 k 1 之间有 先写后读 数据相关 指令 k 1 和指令 k 2 之间有 先写后读 数据相关 指令 k 3 和指令 k 4 之间有 先读后写 数据相关 指令 k 5 和指令 k 6 之间有 先写后读 和 写 写 数据相关 采用顺序发射顺序完成调度方法 画出流水线的时空图如下 IF1 WR2 ID2 EA1 WR1 ID1 EL EA2 WR1 IF1 ES IF1 IF2 WR2 IF2 EA2 EA1 WR1 ID1 IF1 EM2 WR2 ID2 IF2 EO EM1 EM3 WR1 ID1 EA2 EA1 k 5 k 4 k 3 k 2 k 1 k 流水线 1 流水线 2 指令 时钟周期 1 2 4 3 5 6 7 8 9 IF 取指令 ID 译码 EL 执行 LOAD EA 执行 ADD ES 执行 STORE EM 执行 MUL EO 执行 OR WR 写结果 ID1 ID2 k 6 第 9 页 共 10 页 执行这个程序共使用了 9 个时钟周期 采用顺序发射乱序完成调度方法 画出流水线的时空图如下 各操作的完成时间如下 时钟周期 4 5 6 7 8 流水线 1 k k 5 k 2 k 4 流水线 2 k 1 k 3 k 6 执行这个程序共使用了 8 个时钟周期 采用乱序发射乱序完成调度方法 画出流水线的时空图如下 流水线 1 流水线 2 指令 时钟周期 1 2 4 3 5 6 7 8 9 IF 取指令 ID 译码 EL 执行 LOAD EA 执行 ADD ES 执行 STORE EM 执行 MUL EO 执行 OR WR 写结果 WR1 ID1 EL IF1 k WR2 ID2 EA1 EA2 IF2 k 1 WR2 ID2 IF2 EA2 EA1 WR1 ID1 IF1 EM2 EM1 EM3 k 4 k 3 WR1 ID1 IF1 ES k 2 WR2 ID2 IF2 EO WR1 ID1 IF1 EA2 EA1 k 6 k 5 WR2 ID2 EA1 WR1 ID1 EL EA2 WR1 IF1 ES IF1 IF2 WR2 IF2 EA2 EA1 WR1 ID1 IF1 EM2 WR2 ID2 IF2 EO EM1 EM3 WR1 ID1 IF1 EA2 EA1 k 6 k 5