系统结构答案

第第 一一 章章 1 261 26 假设高速缓存假设高速缓存 CacheCache 工作速度为主存的工作速度为主存的 5 5 倍 且倍 且 CacheCache 被访问命中的概率为被访问命中的概率为 9090 那么 采 那么 采 用用 CacheCache 后能使整个存储系统获得多高的加速比后能使整个存储系统获得多高的加速比 T0 1 解 根据 Amdahl 定理有 Sn 结合题意 Cache 工作速度 为 Tn 1 Fe Fe Se 主存的 5 倍 相当于改进存储器后获得的加速比为 5 即 Se 5 Cache 被访问命中的概率为 90 相当 于访问存储器的时间有 90 化在 Cache 上 即 Fe 0 9 所以 Sn 1 1 0 9 0 9 5 3 57 1 271 27 设计指令存储器有两种不同方案 一种是采用价格较贵的高速存储器芯片 另一种是采用价设计指令存储器有两种不同方案 一种是采用价格较贵的高速存储器芯片 另一种是采用价 格便宜的低速存储器芯片 采用后一方案时 用同样的经费可使存储器总线带宽加倍 从而每隔格便宜的低速存储器芯片 采用后一方案时 用同样的经费可使存储器总线带宽加倍 从而每隔 2 2 个时个时 钟周期可取出钟周期可取出 2 2 条指令条指令 每条指令为单字长每条指令为单字长 3232 位位 而采用前一方案时 每一个时钟周期取出一条单字长 而采用前一方案时 每一个时钟周期取出一条单字长 指令 由于访存局部性原理 当取出指令 由于访存局部性原理 当取出 2 2 个指令字时 通常这个指令字时 通常这 2 2 个指令字都要使用 但仍有个指令字都要使用 但仍有 2525 的时钟周 的时钟周 期中 取出的期中 取出的 2 2 个指令字中仅有个指令字中仅有 1 1 个指令字是有用的 试问采用这两种实现方案所构成的存储器带宽是个指令字是有用的 试问采用这两种实现方案所构成的存储器带宽是 多少 多少 解 带宽是指单位时间内处理的二进制位数 相当于频率 用 f 表示 采用方案 A 时 存取指令的 CPIa 1 时钟周期 指令字 即 fa 1 CPIa 指令字长 1 32 32 位 时钟周期 采用方案 B 时 存取指令的 CPIb 0 75 2 2 0 25 2 1 1 25 时钟周期 指令字 即 fa 1 CPIa 指令字长 0 8 32 25 6 位 时钟周期 1 281 28 某工作站采用时钟频率为某工作站采用时钟频率为 15MHz15MHz 处理速率为 处理速率为 10MIPS10MIPS 的处理机来执行一个测试程序 假定每的处理机来执行一个测试程序 假定每 次存储器存取为次存储器存取为 1 1 个时钟周期 试问 个时钟周期 试问 1 1 此计算机的有效此计算机的有效 CPICPI 是多少是多少 2 2 假定将处理机的时钟频率提高到假定将处理机的时钟频率提高到 30MHz30MHz 但存储器的工作速率不变 这样 每次存储器存取需要 但存储器的工作速率不变 这样 每次存储器存取需要 2 2 个时钟周期 如果个时钟周期 如果 3030 指令每条只需要一次存储器存取操作 另外 指令每条只需要一次存储器存取操作 另外 5 5 指令每条需要二次存储器存取操 指令每条需要二次存储器存取操 作 假定测试程序的指令数不变 并与原工作站兼容 试求改进后的处理机作 假定测试程序的指令数不变 并与原工作站兼容 试求改进后的处理机 CPICPI 和和 MIPSMIPS 解 1 由 MIPS 时钟频率 CPI 106 则有 CPIA 时钟频率 MIPS 106 1 5 2 当时钟频率为 15MHZ 时 假设不进行存储操作指令的 CPI 为 x 则要进行一次存储操作指令的 CPI 为 1 x 要进行二次存储操作指令的 CPI 为 2 x 因此有 1 5 x 65 1 x 30 2 x 5 解得 x 1 1 当时钟频率为 30MHZ 时 不进行存储操作指令的 CPI 不变为 1 1 要进行一次存储操作指令的 CPI 为 2 x 3 1 要进行二次存储操作指令的 CPI 为 4 x 5 1 因此平均 CPI 为 CPIB 1 1 65 3 1 30 5 1 5 1 9 所以 MIPSB 时钟频率 CPIB 106 30 106 1 9 106 15 8MIPS 1 291 29 某计算机某计算机 CacheCache 能存放能存放 20002000 条指令 假设条指令 假设 10 10 的指令承担了的指令承担了 90 90 时间的指令访问 而且这时间的指令访问 而且这 10 10 指令中每条指令的执行时间相同 如果要执行的某程序共指令中每条指令的执行时间相同 如果要执行的某程序共 5000050000 条指令 当计算机执行该程序时 在条指令 当计算机执行该程序时 在 CacheCache 中能访问到的指令的概率是多少 中能访问到的指令的概率是多少 解 由题意可知 45000 条指令承担 10 时间的指令访问 5000 条指令承担 90 时间的指令访问 显 然 5000 条指令被频繁使用 设平均使用次数为 X 另外 45000 条指令仅使用一次 则有 45000 0 1 5000X 0 9 解得 X 81 所以该程序执行指令的条数为 Y 45000 5000 81 假设频繁使用的 5000 条指令均匀分布于程序之中 即每次调入 Cache 的 2000 条指令有 200 条是频 繁使用的 另假设每次调入 Cache 的 2000 条指令中的 1800 条均被使用了一次 所以执行该程序时 Cache 中能访问到的指令的概率为 50000 2000 100 1 301 30 有一台计算机 不同类型指令在理想有一台计算机 不同类型指令在理想 CacheCache 无访问失败 与实际 无访问失败 与实际 CacheCache 有访问失败 两种 有访问失败 两种 情况下的性能如下表 求理想情况下的性能如下表 求理想 CacheCache 相对于实际相对于实际 CacheCache 的加速比 的加速比 指令类型指令类型 出现频率出现频率 理想理想 CacheCPICacheCPI 实际实际 CacheCPICacheCPI 运算指令运算指令 40 40 1 1 3 3 取数指令取数指令 20 20 2 2 8 8 存数指令存数指令 15 15 2 2 8 8 控制指令控制指令 25 25 2 2 4 4 解 理想 Cache 情况下指令的平均时钟周期数 CPI 为 CPI理想 1 40 2 20 2 15 2 25 1 6 n i IcIiCPIi 1 实际 Cache 情况下指令的平均时钟周期数 CPI 为 CPI实际 3 40 8 20 8 15 4 25 5 0 n i IcIiCPIi 1 S 实际 CacheCPU 执行时间 理想 CacheCPU 执行时间 IC 时钟周期 CPI实际 IC 时钟周期 CPI理想 CPI CPIA 5 0 1 6 3 12 1 311 31 假设在一台假设在一台 40MHz40MHz 处理机上运行测试程序共有条指令 由处理机上运行测试程序共有条指令 由 4 4 类指令组成 已知指令的类指令组成 已知指令的 CPICPI 和和 所各占比例如下表 所各占比例如下表 指令类型指令类型 指令比例指令比例 CPICPI 算逻运算算逻运算 60 60 1 1 CacheCache 命中存取命中存取 18 18 2 2 控制指令控制指令 12 12 4 4 CacheCache 末命中访主存末命中访主存 10 10 8 8 1 1 计算处理机运行该程序的平均计算处理机运行该程序的平均 CPICPI 2 2 根据根据 1 1 所得所得 CPICPI 计算相应的 计算相应的 MIPSMIPS 速率 速率 解 1 CPI 1 60 2 18 4 12 8 10 2 2 n i IcIiCPIi 1 2 MIPS 时钟频率 CPI 106 40 106 2 2 106 18 19 1 321 32 已知已知 4 4 个程序在个程序在 A A B B C C 三台计算机上的执行时间三台计算机上的执行时间 秒秒 分别如下表 假设每个程序都有分别如下表 假设每个程序都有 100 10100 106 6条指令要执行 计算这条指令要执行 计算这 3 3 台计算机对每个程序的台计算机对每个程序的 MIPSMIPS 速率 根据这些速率值 你能否得出这速率 根据这些速率值 你能否得出这 3 3 台计算机相对性能的明确结论 你能否找到一种将它们排序的方法 试说明理由 台计算机相对性能的明确结论 你能否找到一种将它们排序的方法 试说明理由 程序程序 计算机计算机 A A 计算机计算机 B B 计算机计算机 C C 程序程序 1 1 1 1 1010 2020 程序程序 2 2 10001000 100100 2020 程序程序 3 3 500500 10001000 5050 程序程序 4 4 100100 800800 100100 解 1 由 MIPS 的定义有 MIPS Ic Tcpu 106 100 106 Tcpu 106 100 Tcpu 根据上表中列出的 Tcpu则可计算出相应的 MIPS 如下表所示 程序 计算机 A 计算机 B 计算机 C 程序 1 100 10 5 程序 2 0 1 1 5 程序 3 0 2 0 1 2 程序 4 1 0 125 1 2 由于 MIPS 与指令值 指令使用的频率等有关 在同一台机器上运行不同的程序 得出不同的 速率 MIPS 因此不能仅用 MIPS 来评价计算机性能的优劣 而应用执行程序的算术平均 Tcpu来评价比较好 TcpuA 1 1000 500 100 4 400 25 TcpuB 10 100 1000 800 4 477 5 TcpuC 20 20 50 100 4 47 5 所以性能排序为 C A B 第第 二二 章章 2 252 25 浮点数系统使用的阶码基值浮点数系统使用的阶码基值 r re e 2 2 阶值位数 阶值位数 q 2q 2 尾数基值 尾数基值 r rm m 10 10 尾数位数 尾数位数 p p 1 1 即按照使 即按照使 用的二进制位数来说 等价于用的二进制位数来说 等价于 p 4p 4 计算在非负阶 正尾数 规格化情况下的最小尾数值 最大尾数值 计算在非负阶 正尾数 规格化情况下的最小尾数值 最大尾数值 最大阶值 可表示的最小值和最大值及可表示数的个数 最大阶值 可表示的最小值和最大值及可表示数的个数 解 最小尾数值 rm 1 10 1 0 1 最大尾数值 1 rm p 1 10 1 0 9 最大阶值 2q 1 3 可表示数的最小值 1 rm 1 10 1 0 1 可表示数的最大值 rm2q 1 1 rm p 103 1 10 1 900 可表示数的个数 2q rmp rm 1 rm 22 101 10 1 10 36 2 262 26 一个处理机有一个处理机有 I1I1 I10I10 共共 1010 条指令 经统计 各指令在程序中出现的概率如下 条指令 经统计 各指令在程序中出现的概率如下 I1I1 0 250 25 I2I2 0 200 20 I3I3 0 150 15 I4I4 0 100 10 I5I5 0 080 08 I6I6 0 080 08 I7I7 0 050 05 I8I8 0 040 04 I9I9 0 030 03 I10I10 0 020 02 1 1 计算这 计算这 1010 条指令的操作码最短平均长度 条指令的操作码最短平均长度 2 2 写出这 写出这 1010 条指令的条指令的 HuffmanHuffman 编码 并计算操作码编码的平均长度和信息冗余量 编码 并计算操作码编码的平均长度和信息冗余量 3 3 采用 采用 3 73 7 扩展编码法和扩展编码法和 2 82 8 扩展编码法编写这扩展编码法编写这 1010 条指令的操作码 并分别计算编码的平均长条指令的操作码 并分别计算编码的平均长 度和信息冗余量 说明哪一种扩展编码较好的理由 度和信息冗余量 说明哪一种扩展编码较好的理由 解 1 操作码编码的最短平均长度为 H log2pi n i i p 1 H 0 25log20 25 0 20log20 20 0 15log20 15 0 10log20 10 0 08log20 08 0 08log20 08 0 05log20 05 0 04log20 04 0 03log20 03 0 02log20 02 2 96 位 2 根据给出的使用频度 在构造 Huffman 树的过程中 有两个结点可供合并 因此可生成不 同的 Huffman 树 其中给出一棵如图所示 相应的 Huffman 编码如表所示 1 0 1 0 1 0 I2 I1 1 0 1 0 1 0 I4 1 0 I3 1 0 I6 1 0 I5 I10 I9 I8 I7 IiPi Huffman 编码 Li 2 5 编码 3 7 Li 2 4 编码 2 8 Li I1 0 25 002002002 I2 0 20 102012012 I3 0 15 010310210004 I4 0 10 110311000510014 I5 0 08 0110411001510104 I6 0 08 1110411010510114 I7 0 05 01110511011511004 I8 0 04 01111511100510014 I9 0 03 11110511101511104 I10 0 02 11111511110511114 Huffman 编码的平均长度为 l li n i i p 1 l 0 25 2 0 20 2 0 15 3 0 10 3 0 08 4 0 08 4 0 05 5 0 04 5 0 03 5 0 02 5 2 99 位 Huffman 编码的信息冗余量为 R 1 H l 1 2 96 2 99 100 1 0 3 3 7 扩展编码和 2 8 扩展编码如表所示 3 7 扩展编码要求短码码点数为 3 长码码点数为 7 所以短码长取 2 位 有码点 22 4 个 用一个作 1 00 0 02 0 05 0 13 0 23 0 43 0 03 0 08 0 10 0 20 0 04 0 09 0 17 0 32 0 57 0 05 0 08 0 15 0 25 扩展标志 长码长取 3 位 有码点 23 8 个 有一个未被利用 即有一个 余码点 编码的平均长度为 l 0 25 0 20 0 15 2 0 10 0 08 0 08 0 05 0 04 0 03 0 02 5 3 2 位 3 7 扩展编码的信息冗余量为 R 1 H l 1 2 96 3 2 100 7 5 2 8 扩展编码要求短码码点数为 2 长码码点数为 8 所以短码长取 2 位 有码点 22 4 个 用二个作 扩展标志 长码长取 2 位 有码点 22 2 8 个 码点全部被利用 即没有多余码点 l 0 25 0 20 2 0 15 0 10 0 08 0 08 0 05 0 04 0 03 0 02 4 3 1 位 2 8 扩展编码的信息冗余量为 R 1 H l 1 2 96 3 1 100 4 5 可见 2 8 扩展编码优于 3 7 扩展编码 2 272 27 经统计 某种处理机经统计 某种处理机 1414 条指令的使用频度分别为 条指令的使用频度分别为 0 010 01 0 150 15 0 120 12 0 03 0 02 0 04 0 02 0 04 0 01 0 13 0 15 0 140 03 0 02 0 04 0 02 0 04 0 01 0 13 0 15 0 14 0 11 0 030 11 0 03 分别给出它们的定 分别给出它们的定 长码 长码 HuffmanHuffman 编码 只能有两种码长且平均长度尽可能短的扩展编码 并分别计算三种编码的平均长度 编码 只能有两种码长且平均长度尽可能短的扩展编码 并分别计算三种编码的平均长度 0 15 0 15 0 14 0 13 0 12 0 11 0 04 0 04 0 03 0 03 0 02 0 02 0 01 0 01 2 282 28 用于文字处理的某专用机 每个文字符用用于文字处理的某专用机 每个文字符用 4 4 位十进制数字 位十进制数字 0 0 9 9 编码表示 空格用 编码表示 空格用 表示 表示 在对传送的文字符和空格进行统计后 得出它们的使用频度如下 在对传送的文字符和空格进行统计后 得出它们的使用频度如下 0 200 20 0 0 170 0 17 1 0 061 0 06 2 0 082 0 08 3 0 113 0 11 4 0 084 0 08 5 5 0 050 05 6 0 086 0 08 7 0 137 0 13 8 0 038 0 03 9 0 019 0 01 1 1 若对数字 若对数字 0 0 9 9 和空格采用二进制编码 试设计编码平均长度最短的编码 和空格采用二进制编码 试设计编码平均长度最短的编码 2 2 若传送 若传送 10106 6个文字符号 且每个文字符号后均自动跟一个空格 按最短的编码 共需传送多少个文字符号 且每个文字符号后均自动跟一个空格 按最短的编码 共需传送多少 个二进制位 若传送波特率为个二进制位 若传送波特率为 9600bPS9600bPS 共需传送多少时间 共需传送多少时间 3 3 若对数字 若对数字 0 0 9 9 和空格采用和空格采用 4 4 位定长码编码 重新计算问题 位定长码编码 重新计算问题 2 2 解 1 操作码编码的平均长度最短为 Huffman 编码 生成的 Huffman 树 如图所示 相应的 Huffman 编码如表所示 l li 3 23 位 n i i p 1 2 根据题意 每个字符的二进制码的平均长度为 3 23 4 1 16 15 位 若要传输 106 个字符 则要传输二进制位数为 106 16 15 1 615 107 位 若波特率为 56Kb s 则传输时间为 1 615 107 56 103 288 s 3 当采用四位定长编码时 则需要传输二进制位数为 106 4 4 1 2 107 位 传输时 间为 2 107 56 103 357 s 1 0 1 0 1 0 1 00 0 01 0 04 0 09 0 20 0 40 0 03 0 05 0 11 0 20 0 080 06 0 14 0 27 0 60 0 16 0 08 0 13 0 33 0 17 0 08 1 0 1 0 1 0 3 3 7 7 0 0 5 5 1 1 6 6 4 4 2 2 9 9 8 8 2 292 29 一台模型机共有一台模型机共有 7 7 条指令 各指令的使用频度分别为 条指令 各指令的使用频度分别为 35 35 25 25 20 20 10 10 5 5 3 3 2 2 有 有 8 8 个通用数据寄存器 个通用数据寄存器 2 2 个变址寄存器 个变址寄存器 1 1 要求操作码的平均长度最短 请设计操作码的编码 并计算操作码编码的平均长度 要求操作码的平均长度最短 请设计操作码的编码 并计算操作码编码的平均长度 2 2 设计 设计 8 8 位字长的寄存器位字长的寄存器 寄存器型指令寄存器型指令 3 3 条 条 1616 位字长的寄存器一存储器型变址寻址方式指位字长的寄存器一存储器型变址寻址方式指 令令 4 4 条 变址范围不小于正 负条 变址范围不小于正 负 127127 请设计指令格式 并给出指令各字段的长度和操作码的编码 请设计指令格式 并给出指令各字段的长度和操作码的编码 2 302 30 一台模型机共有一台模型机共有 7 7 条指令 各指令的使用频度分别为 条指令 各指令的使用频度分别为 35 35 25 25 20 20 10 10 5 5 3 3 2 2 有 有 8 8 个通用数据寄存器 个通用数据寄存器 2 2 个变址寄存器 个变址寄存器 1 1 要求操作码的平均长度最短 请设计操作码的编码 并计算操作码编码的平均长度 要求操作码的平均长度最短 请设计操作码的编码 并计算操作码编码的平均长度 2 2 设计 设计 8 8 位字长的寄存器位字长的寄存器 寄存器型指令寄存器型指令 3 3 条 条 1616 位字长的寄存器一存储器型变址寻址方式指令位字长的寄存器一存储器型变址寻址方式指令 4 4 条 变址范围不小于正 负条 变址范围不小于正 负 127127 请设计指令格式 并给出指令各字段的长度和操作码的编码 请设计指令格式 并给出指令各字段的长度和操作码的编码 解 1 操作码编码的平均长度最短为 Huffman 编码 生成的 Huffman 树如图所示 相应的 Huffman 编码如表所示 l li 2 35 位 n i i p 1 IiPi Huffman 编码 Li 0 20 102 0 0 17 0003 7 0 13 0103 3 0 11 1103 2 0 08 00104 4 0 08 00114 6 0 08 01104 1 0 06 01114 5 0 05 11104 8 0 03 111105 9 0 01 111115 1 00 0 02 0 05 0 10 0 20 0 40 0 03 0 05 0 10 0 20 0 25 0 60 0 35 2 由于通用寄存器有 8 个 则指令中通用寄存器字段应为 3 位 操作码字段 2 位可有 4 个码点 用三个码点表示三条指令 另一个码点则作为扩展标志 所以 3 条 8 位长的寄存器 寄存器型指令格式 如下 由于变址寄存器有 2 个 则指令中变址寄存器字段应为 1 位 变址范围 127 127 则指令中相对 位移字段应为 8 位 操作码字段前 2 位可有 4 个码点 用三个码点表示三条指令 另一个码点则作为扩 展标志 扩展 2 位正好可表示四条指令 操作码字段则为 4 位 所以 4 条 16 位长的寄存器 存储器型指 令格式如下 特别地 当采用 3 4 扩展编码时 使用频度高的用短码表示 使用频度低的用长码表示 其相应的 编码如表所示 2 312 31 某处理机的指令字长为某处理机的指令字长为 1616 位 有二地址指令 一地址指令和零地址指令位 有二地址指令 一地址指令和零地址指令 3 3 类 每个地址字段类 每个地址字段 的长度均为的长度均为 6 6 位 位 1 1 如果二地址指令有 如果二地址指令有 1515 条 一地址指令和零地址指令的条数基本相等 问一地址指令和零地址条 一地址指令和零地址指令的条数基本相等 问一地址指令和零地址 指令各有多少条 并为这指令各有多少条 并为这 3 3 类指令分配操作码 类指令分配操作码 2 2 如果指令系统要求这 如果指令系统要求这 3 3 类指令条数的比例大致为类指令条数的比例大致为 1 1 9 9 9 9 问这 问这 3 3 类指令各有多少条 并为这类指令各有多少条 并为这 3 3 类指令分配操作码 类指令分配操作码 解 1 操作码字段取 4 位可有 24 16 个码点 用 15 个码点 0000 1110 表示 15 条二地址指令 另一个码点 1111 则作为扩展标志 所以 15 条二地址指令格式如下 由于要求一地址指令和零地址指令的条数基本相等 所以地址码 1 字段 6 位扩展有 26 64 个码点 用 63 个码点 表示 63 条一地址指令 另一个码点 则作为扩展标志 而用地址码 2 字段 6 位扩展有 26 64 个码点 64 个码点都用来表示零地址指令 共有 64 条 IiPi Huffman 编码 Li 2 4 编码 3 4 Li I1 0 35 002002 I2 0 25 012012 I3 0 20 102102 I4 0 10 110311004 I5 0 05 1110411014 I6 0 03 11110511104 I7 0 02 11111511114 操作码 2 位 寄存器 1 3 位 寄存器 2 3 位 操作码 4 位 寄存器 3 位 变址寄存器 1 位 相对位移 8 位 操作码 4 位 地址码 1 6 位 地址码 2 6 位 2 在一中指令条数的比例大约 1 4 2 4 2 因此若使一地址指令和零地址指令加大一倍 则三 类指令条数的比例大约 1 9 9 操作码字段取 4 位时的 16 个码点 用 14 个码点 0000 1101 表示 14 条二地址指令 另二个码点 1110 与 1111 则作为扩展标志 扩展标志 1110 扩展地址码 1 字段 6 位的 64 个码点 全部用来表示一地址指令 有 64 条 扩展标志 1111 扩展地址码 1 字段 6 位的 64 个码点 用 62 个码点 表示 62 条一地址指令 另二 个码点 与 则作为扩展标志 这样一地址指令 共有 126 条 扩展标志 与 扩展地址码 2 字段 6 位 各有 64 个码点全部用来表示零地址指令 则有 128 条零地 址指令 2 322 32 某模型机某模型机 9 9 条指令使用频度为 条指令使用频度为 ADDADD 加 加 30 30 SUBSUB 减 减 24 24 JOMJOM 按负转移 按负转移 6 6 STOSTO 存 存 7 7 JMPJMP 转移 转移 7 7 SHRSHR 右移 右移 2 2 CILCIL 循环左移 循环左移 3 3 CLACLA 清除 清除 20 20 STPSTP 停机 停机 1 1 要求有两种指令字长 都按双操作数指令格式编排 采用扩展操作码 并限制只能有两种操作码码长 要求有两种指令字长 都按双操作数指令格式编排 采用扩展操作码 并限制只能有两种操作码码长 设该机有若干通用寄存器 主存为设该机有若干通用寄存器 主存为 1616 位宽 按字节编址 采用按整数边界存储 任何指令都在一个主存位宽 按字节编址 采用按整数边界存储 任何指令都在一个主存 周期中取得 短指令为寄存器周期中取得 短指令为寄存器 寄存器型 长指令为寄存器寄存器型 长指令为寄存器 主存型 主存地址应能变址寻址 主存型 主存地址应能变址寻址 1 1 仅根据使用频度 不考虑其它要求 设计出全 仅根据使用频度 不考虑其它要求 设计出全 HuffmanHuffman 操作码 计算其平均码长 操作码 计算其平均码长 2 2 考虑题目全部要求 设计优化实用的操作码形式 并计算其操作码的平均码长 考虑题目全部要求 设计优化实用的操作码形式 并计算其操作码的平均码长 3 3 该机允许使用多少可编址的通用寄存器 该机允许使用多少可编址的通用寄存器 4 4 画出该机两种指令字格式 标出各字段之位数 画出该机两种指令字格式 标出各字段之位数 5 5 指出访存操作数地址寻址的最大相对位移量为多少个字节 指出访存操作数地址寻址的最大相对位移量为多少个字节 解 1 根据给出的使用频度 在构造 Huffman 树的过程中 有两个结点可供合并 因此可生成不 同的 Huffman 树 其中给出一棵如图所示 相应的 Huffman 编码如表所示 Huffman 编码的平均长度为 l li n i i p 1 l 0 3 2 0 24 2 0 2 2 0 07 4 0 07 4 0 06 4 0 03 5 0 02 6 0 01 6 2 61 位 ADDADD CLACLA SUBSUB J0MJ0M JMPJMP STOSTO CILCIL 0 56 0 01 0 03 0 06 0 12 0 26 0 02 0 03 0 060 07 0 14 1 00 0 20 0 07 0 44 0 240 30 STPSTP SHRSHR 2 任何指令都在一个主存 周期中取得 那么短指令字长为 8 位 长指令字长为 16 位 又指令都是二地址指令 所以短指令寄存器 寄存器型的格式为 长指令为寄存器 主存型的格式为 由题意可知 指令操作码采用扩展编码 且只能有两种码长 从指令使用频度来看 ADD SUB 和 CLA 三条指令的使用频度与其它指令的使用频度相差较大 所以用两位操作码的三个码点来表示三条指令 一个码点作为扩展码点 且扩展三位来表示六条指令 即采用 2 4 扩展编码构成 3 6 编码 2 4 扩展编 码如表所示 2 4 扩展编码 3 6 的平均长度为 l li 2 78 n i i p 1 3 4 由短指令寄存器 寄存器型的格式可知 寄存器号字段长度为 3 位 寄存器个数为 8 个 则各字段长度如图格式所标识 而对于长指令寄存器 主存型 一般变址寄存器是某通用寄存器 则变址寄存器号的字段长度为 3 位 则各字段长度如图格式所标识 5 由于相对位移字段长度为 5 位 因此访存地址寻址的最大相对位移量为 25 32 字节 第第 三三 章章 习习 题题 3 83 8 在一台单流水线多操作部件的处理机上执行下面的程序 每条指令的取指令 指令译码需要一在一台单流水线多操作部件的处理机上执行下面的程序 每条指令的取指令 指令译码需要一 个时钟周期 个时钟周期 MOVEMOVE ADDADD 和和 MULMUL 操作分别需要操作分别需要 2 2 个 个 3 3 个和个和 4 4 个时钟周期 每个操作都在第一个时钟周期个时钟周期 每个操作都在第一个时钟周期 从通用寄存器中读操作数 在最后一个时钟周期把运算结果写到通用寄存器中 从通用寄存器中读操作数 在最后一个时钟周期把运算结果写到通用寄存器中 k k MOVEMOVE R1R1 R0R0 R1 R1 R0 R0 k 1k 1 MULMUL R0R0 R2R2 R1R1 R0 R0 R2 R1 R2 R1 k 2k 2 ADDADD R0R0 R2R2 R3R3 R0 R0 R2 R3 R2 R3 1 1 就程序本身而言 可能有哪几种数据相关就程序本身而言 可能有哪几种数据相关 指令 IiPi Huffman 编码 Li 2 5 编码 3 6 Li ADDI1 0 30 012002 SUBI2 0 24 112012 CLAI3 0 20 102102 STOI4 0 07 00114110015 JMPI5 0 07 00104110105 JOMI6 0 06 00014110115 CILI7 0 03 000015111005 SHRI8 0 02 6111015 STPI9 0 01 6111105 操作码 2 位 寄存器 1 3 位 寄存器 2 3 位 操作码 5 位 寄存器 3 位 变址寄存器 3 位 相对位移 5 位 2 2 在程序实际执行过程中 哪几种数据相关会引起流水线停顿在程序实际执行过程中 哪几种数据相关会引起流水线停顿 3 3 画出指令执行过程的流水线时空图 并计算完成这画出指令执行过程的流水线时空图 并计算完成这 3 3 条指令共需要多少个时钟周期 条指令共需要多少个时钟周期 解 1 就程序本身而言 可能有三种数据相关 若 3 条指令顺序流动 则 k 指令对 R1 寄存器的 写与 k 1 指令对 R1 寄存器的读形成的 先写后读 相关 若 3 条指令异步流动 则 k 指令对 R0 寄存器 的读与 k 1 指令对 R0 寄存器的写形成的 先读后写 相关 k 2 指令对 R0 寄存器的写与 k 1 指令对 R0 寄存器的写形成的 写 写 相关 2 在程序实际执行过程中 二种数据相关会引起流水线停顿 一是 先写后读 相关 k 指令对 R1 的写在程序执行开始后的第四个时钟 k 1 指令对 R1 的读对指令本身是第三个时钟 但 k 1 指令比 k 指令晚一个时钟进入流水线 则在程序执行开始后的第四个时钟要读 R1 不能在同一时钟周期内读写同 一寄存器 因此 k 1 指令应推迟一个时钟进入流水线 产生了流水线停顿 二是 写 写 相关 k 1 指 令对 R0 的写对指令本身是第六个时钟 而要求该指令进入流水线应在程序执行开始后的第三个时钟 所 以对 R0 的写是在程序执行开始后的第八个时钟 k 2 指令对 R0 的写对指令本身是第五个时钟 而 k 2 指 令比 k 1 指令晚一个时钟进入流水线 则在程序执行开始后的第四个时钟 所以对 R0 的写是在程序执行 开始后的第八个时钟 不能在同一时钟周期内写写同一寄存器 因此 k 2 指令应推迟一个时钟进入流水 线 产生了流水线停顿 另外 可分析 先读后写 相关不会产生流水线的停顿 3 由题意可认位该指令流水线由六个功能段取指 译码 取数 运一 运二和存数等组成 则程 序指令执行过程的流水线时空图如下图所示 若 3 条指令顺序流动 共需要 9 个时钟周期 空间 存数 K 存数 K 1 存数 K 2 存数 运二 K 1 运二 运一 K 1 运一 K 2 运一 取数 K 取数 K 1 取数 K 2 取数 译码 K 译码 K 1 译码 K 2 译码 取指 K 取指 K 1 取指 K 2 取指 时间 0 1 2 3 4 5 6 7 8 9 3 93 9 某流水线由某流水线由 4 4 个功能部件组成 每个功能部件的执行时间都为个功能部件组成 每个功能部件的执行时间都为 t t 当输入 当输入 1010 个数据后 停顿个数据后 停顿 5t5t 又输入 又输入 1010 个数据 如此重复 计算流水线的实际吞吐率 加速比和效率 并画出时空图 个数据 如此重复 计算流水线的实际吞吐率 加速比和效率 并画出时空图 解 该题中的流水线的任务是非连续流入的 因此不能直接应用公式直接计算 要利用时空图 题 意的流水线时空图如下图所示 空间 S4 1 2 3 4 5 6 7 8 9 10 1 2 S3 1 2 3 4 5 6 7 8 9 10 1 2 S2 1 2 3 4 5 6 7 8 9 10 1 2 S1 1 2 3 4 5 6 7 8 9 10 1 2 时间 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 TP 10 15 t 0 67 t S T0 TK 10 4 t 15 t 2 67 E 4 10 t 4 15 t 0 67 3 11 有一个四段指令流水线为取指 IF 译码 ID 执行 EX 写回 WB 分支指令在第二个时 钟周期未决定是不是条件失败分支 在第三个时钟周期未决定是不是成功分支 还假定第一个时 钟周期的操作和条件分支无关 并略去其它流水线停顿 要求 1 分别画出无条件分支 发生的条件分支 不发生的条件分支时指令执行的时空图 2 假设条件分支指令占所有指令的 20 且其中 60 指令可能执行 无条件分支占 5 问实际的 流水线加速比是多少 解 1 根据题意 分支指令采用的是流水线停顿的方法来处理 而判断条件分支指令让流水线停 顿 应在取指功能段后设计一个 指令分析器 来判断流水线是否停顿 显然 无条件分支指令与条件 成功 发生条件 分支是一样的 需要在第三个时钟周期未决定下一条指令的地址 因此流水线要停顿 二个时钟周期 对于条件失败 条件不成功 分支 需要在第二个时钟周期未决定下一条指令的地址 因此流水线要停顿一个时钟周期 2 串行执行 N 条指令的时间为 T1 N k t 流水线方式执行 N 条指令的时间为 Tn k 1 t N N 5 2 N 20 60 1 5 t Sn T1 Tn k 1 28 3 13 用一条 5 个功能段的浮点加法器流水线计算 F 每个功能段的延迟时间 每个功能段的延 10 1 i Ai 迟时间均相等 流水线的输出端与输入端之间有直接数据通路 而且设置有足够的缓冲寄存器 要求用尽可能短的时间完成计算 画出流水线时空图 计算流水线的实际吞吐率 加速比和效率 解 为使计算过程充分利用流水线的性能 避免 先写后读 相关 需要将计算的算法改为 A1 A2 A3 A4 A9 A10 A5 A6 A7 A9 且按括号的优先次序计算九次加法 相应的流水线时空图如下图所示 空间 S5 1 2 3 4 5 6 7 8 9 S4 1 2 3 4 5 6 7 8 9 S3 1 2 3 4 5 6 7 8 9 S2 1 2 3 4 5 6 7 8 9 S1 1 2 3 4 5 6 7 8 9 时间 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 TP 9 21 t 0 429 t S T0 TK 9 5 t 21 t 2 143 E 5 9 t 5 21 t 0 429 3 15 有一条 3 个功能段的流水线如下图所示 每个功能段的延迟时间均为 t 但是 功能段 S2的输出 要返回到它自己的输入端循环执行一次 输入 输出 t t t 1 如果每隔一个 t 向流水线连续输入任务 这条流水线会发生什么问题 2 求这条流水线能够正常工作的实际吞吐率 加速比和效率 3 可用什么办法来提高流水线的吞吐率 画出改进后的流水线结构 S1S2S3 解 1 每个任务在段 S2要反馈循环一次 执行时间为 2 t 其它各段的执行时间为 t 因此应 按瓶颈段的执行时间 2 t 流入任务 才不会发生冲突现象 否则会发生流水线的阻塞 2 若连续输入 n 个任务 则流水线的实际吞吐率 加速比和效率分别为 TP n 4 t 2 n 1 t n 2 n 1 t S 4n t 4 t 2 n 1 t 2n n 1 E 4n t 3 4 t 2 n 1 t 2n 3 n 1 3 为提高流水线的吞吐率 可重复设置段 S2 并使两个段 S2串连在一起 从而消除瓶颈段 S2 而且各段执行时间相等为 t 流水线的段数为 4 流水线的结构如下图所示 输入 输出 t t t t 3 16 在一个 5 段的流水线处理机上需经 9 t 才能完成一个任务 其预约表为 1 写出流水线的初始冲突向量 2 画出流水线任务调度的状态有向图 3 求出流水线的最优调度策略及最小平均延迟时间和流水线的最大吞吐率 4 按最优调度策略连续输入 8 个任务时 流水线的实际吞吐率是多少 解 1 根据初始冲突向量的构成方法 对预约表各行中打 的拍数求出差值 除去重复的后汇集 在一起 即得到延迟禁止表为 F 1 5 6 8 由 F 可得到初始冲突向量为 C 2 根据后继冲突向量的递推规则 Cj SHR k Ci C0则可得出所有的后继状态 具体有 C0四个后继状态 C1 SHR 2 C0 C0 7 C2 SHR 3 C0 C0 C3 SHR 4 C0 C0 3 2 C4 SHR 7 C0 C0 C0 7 4 7 C1二个后继状态 C5 SHR 2 C1 C0 C6 SHR 7 C1 C0 C0 7 C2二个后继状态 C7 SHR 4 C2 C0 C3 3 4 7 2 C8 SHR 7 C2 C0 C0 C3二个后继状态 C9 SHR 3 C3 C0 C2 时间 1 2 3 4 5 6 7 8 9 流水段 S1 S2 S3 S4 S5 延迟 D2 S1S2 S3S2 C0 C2 C1 C3 C5 C10 SHR 7 C3 C0 C0 C5一个后继状态 C11 SHR 7 C5 C0 C0 由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示 3 由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间 如下表所示 调度策略 平均延迟时间 特别地 从 C0出发的 3 4 3 也是一个 2 2 7 2 2 7 t 3 3 67 t 任务调度策略 除第一条有向弧外 第二 三条 2 7 2 7 t 2 4 5 t 有向组成一个环路 该调度策略为 4 3 从 表 3 4 7 3 4 7 t 3 4 67 t 中可以得到平均延迟时间最小的调度策略为 4 3 7 3 7 t 2 5 t 3 该调度策略则为最优调度策略 相应的最小 4 3 7 4 3 7 t 3 4 67 t 平均延迟时间为 3 5 t 所以流水线的最大吞吐 4 7 4 7 t 2 5 5 t 率为 7 7 t TPmax 1 3 5 t 0 286 t 3 4 3 4 3 t 2 3 5 t 4 按最优调度策略 3 4 3 连续输入 8 个任务时 流水线的实际吞吐率为 TP 8 3 4 3 4 3 4 3 9 t 0 24 t 3 17 有一个 5 段流水线的预约表如下 1 画出流水线调度状态有向图 2 分别求出允许不等间隔调度和等间隔调度的最优调度策略以及这两种调度策略的最大吞吐率 3 若连续输入 10 个任务 求这两种调度策略的实际吞吐率 解 1 根据初始冲突向量的构成方法 对预约表各行中打 的拍数求出差值 除去重复的后汇集 在一起 即得到延迟禁止表为 F 1 3 6 由 F 可得到初始冲突向量为 C0 根据后继冲突向量的递推规则 Cj SHR k Ci C0则可得出所有的后继状态 具体有 C0三个后继状态 C1 SHR 2 C0 C0 5 C2 SHR 4 C0 C0 C3 SHR 5 C0 C0 C0 4 2 5 5 C1二个后继状态 C4 SHR 2 C1 C0 C5 SHR 5 C1 C0 C0 5 C2二个后继状态 C6 SHR 4 C2 C0 C2 4 2 时间 1 2 3 4 5 6 7 流水段 S1 S2 S3 S4 S5 C0 C2 C1 C7 SHR 5 C2 C0 C0 C4一个后继状态 C8 SHR 5 C4 C0 C0 由后继状态和引起状态转移的时间间隔可得到状态有向图如上图所示 2 由状态转移有向图可得到无冲突的任务调度策略及其平均延迟时间 如下表所示 调度策略 平均延迟时间 特别地 从 C0出发的 4 4 也是一个任 务 2 5 2 5 t 2 3 5 t 调度策略 除第一条有向弧外 第二条有向弧是 一 4 5 4 5 t 2 4 5 t 个环路 该调度策略为 4 从表中可以得到平 均 5 5 t 延迟时间最小的等间隔和不等间隔的调度策略为 2 2 5 2 2 5 t 3 3 t 4 4 和 2 2 5 相应的最小平均延迟时 4 4 4 t 间为 4 t 和 3 t 所以流水线的最大吞吐率为 TPAmax 1 4 t 0 25 t TPBmax 1 3 t 0 33 t 3 按等间隔最优调度策略 4 4 连续输入 10 个任务时 流水线的实际吞吐率为 TP 10 4 4 4 4 4 4 4 4 4 7 t 10 43 t 按不等间隔最优调度策略 2 2 5 连续输入 10 个任务时 流水线的实际吞吐率为 TP 10 2 2 5 2 2 5 2 2 5 7 t 5 17 t 第第 四四 章章 习习 题题 4 13 由 3 个访问速度 存储容量和每位价格都不相同的存储器构成一个存储系统 3 个存储器 M1 M2 和 M3 的访问周期分别为 R1 R2 和 R3 存储容量分别为 Sl S2 和 S3 每位价格分别为 C1 C2 和 C3 Ml 靠近 CPU 1 写出这个三级存储系统的等效访问时间 等效存储容量 S 和等效每位价格 C 的表达式 2 在什么条件下 整个存储系统的每位平均价格接近于 C3 解 1 设 Hi为 CPU 访存在 Mi中的概率 则存储系统的等效访问时间 存储容量和每位价格分别 为 T S