福建农林大学计算机系统结构期末复习资料(更新版).pdf

福建农林大学计算机系统结构 共 18 页第 1 页 计算机系统结构期末复习资料计算机系统结构期末复习资料计算机系统结构期末复习资料计算机系统结构期末复习资料 应用题应用题应用题应用题 题型 1 经统计 某机器 14 条指令的使用频度分别为 0 01 0 15 0 12 0 03 0 02 0 04 0 02 0 04 0 01 0 13 0 15 0 14 0 11 0 03 分别求出用等长码 Huffman 码 只有两种码长的扩展操作码 3 种编码方式 的操作码平均码长 解答 14 条指令的等长操作码的平均码长是 14log2位 即 4 位 哈夫曼编码可先用哈夫曼算法构造哈 夫曼树 本题的哈夫曼树如图 1 所示 在图 1 中 叶子上用圆括号所括起来的数字表示该频度指令所用的 二进位编码的码位数 所以哈夫曼编码的操作码平均码长为 38 3 14 1 i ii lp位 采用只有两种码长的扩展操作码 可根据 14 条指令所给出的使用频度值分成两群 让使用频度较高 的 6 种指令用 3 位操作码编码表示 留下两个 3 位码作为长码的扩展标志 扩展出 2 位 共有 8 条使用低 频的指令的操作码 这样 操作码的平均码长为 14 1 4 320 0580 03 i ii lp 位 题型 2 1 设中断级屏蔽位 1 对应于开放 0 对应于屏蔽 各级中断处理程序的中断级屏蔽位设置 福建农林大学计算机系统结构 共 18 页第 2 页 如表所示 表 1 中断级屏蔽位设置 中断处理程序级别 中断级屏蔽位 第 1 级第 2 级第 3 级第 4 级 第 1 级0000 第 2 级1011 第 3 级1000 第 4 级1010 1 当中断响应应优先次序4321 时 其中断处理次序是什么 2 如果所有的中断处理都各需 3 个单位时间 中断响应和中断返回时间相对中断处理时间少得多 当 机器正在运行用户程序时 同时发生第 2 3 级中断请求 过两个单位时间后 又同时发生第 1 4 级中断 请求 试画出程序运行过程示意图 分析 为了领会中断响应排队器对中断响应的优先次序是用硬件固定的 以及通过由操作系统给各中断 级服务程序现行程序状态字中的中断级屏蔽位设置不同的状态 可以改变中断处理 完 的次序这两个要 点 图 1 给出了一个中断响应硬件部分的简单逻辑原理示意图 图中略去了某些实现上的具体细节 因为这些已不是本课程要讨论的内容 中断级屏蔽位是程序状态字中的一个组成部分 程序状态字是将散布于系统各部分 反映程序工作时 某些关键性硬件的状态 组合在一起所构成的字 有的计算机也称其为处理器状态字或程序换道区 每类 程序均在主存中指定一个区域来放置其程序状态字 运行一个程序或进程时 就会将其程序状态字从主存 指定单元或区域取出送到分散于系统各部分的寄存器或计数器中 建立起运行此程序或进程的环境 一个 程序或进程在退出运行时 也会将反映该程序状态的这些寄存器或计数器内容组拼成程序状态字 存回该 程序或进程在主存中的指定单元或区域里 因此 程序或进程的切换 只需要通过硬件启动的交换新旧程 序状态字的内容即可快速完成 例如在 IBM 370 系列机上 程序状态字为 64 位 等于它的长字 交换程 序状态字只需硬件启动经写长字和读长宇二次访存即可完成 尽管中断请求是随机发出的 为了便于精确保存中断的断点以及在中断处理完后又能返回到原中断 处 中断响应排队器总是在每条指令执行到最后一个机器周期的最后一个时钟周期时 对目前到达中断响 福建农林大学计算机系统结构 共 18 页第 3 页 应排队器入口的所有中断请求排一次队 择优进行响应 在中断响应排队器相应的输出端产生出响应信号 此信号经中断级服务程序入口地址形成硬件 生成该级中断服务程序的程序状态字在内存区中所存放的地 址 同时 经中断响应控制信号启动 进行新旧程序状态字的交换 完成程序的切换 被中断的程序的断 点地址 即程序计数器的内容 由硬件自动压入返回地址堆栈 予以保存 系统切换到新的程序或进程 后 继续运行下去 如果新的程序或进程是一个中断服务程序 在运行结束 执行到中断返回指令时 就 会从堆栈中弹出所保存的返回地址 再次交换程序状态字 系统又重新返回到原先被中断的程序 恢复运 行 当然 低级的中断服务程序在处理过程中又遇到了比其更高级的中断请求时 应允许其被中断 以实 现多级中断的嵌套 利用返回地址堆栈的后进先出工作方式 就可以完成中断嵌套时的正确返回 可以看 出 只要某道程序运行时 由操作系统在现行程序的程序状态字中 根据对各中断级的中断请求是否屏蔽 设置好中断级屏蔽位的状态 就可以控制这些级别的中断请求是否进入中断响应排队器去参加排队 只有 能进入中断响应排队器的中断级请求 才有机会得到响应 从而就可改变中断实际处理完的次序 应当注意的是 用户程序是不能屏蔽任何中断的 因此 用户程序的现行程序状态字中 对各级中断 级的屏蔽位 均应让其处于 开放 状态 根据本题所给出的各级中断处理程序对中断级屏蔽位设置的状况 很容易得出其中断处理 完 的次序 应当是 1 3 4 2 因为正处理 l 级的中断处理程序时 现行程序状态字中的中断级屏蔽位为 0000 在 其执行期间 任何新的同级和低级的中断请求都不可能进入中断响应排队器进行排队 所以 1 级中断处 理程序一定会先处理完 当执行 3 级中断服务程序时 由于现行程序状态字中的中断级屏蔽位为 1000 即 对 l 级中断请求是 开放 的 而对其它各级中断请求则处于 屏蔽 状态 所以 只要此时发生 1 级中 断请求 它就能进入中断响应排队器去排队 从而在中断请求排队的微操作发出时 就可打断 3 级中断服 务程序的执行 交换程序状态字 转去执行 1 级中断处理程序 使之被优先处理完 而在执行 3 级中断服 务程序时 由于现行程序状态字对 2 3 4 级的中断请求处于被 屏蔽 的状态 所以 它们都不能打断 正在执行的 3 级中断处理程序 其它的情况也就可以依此类推得到 解答 1 中断处理 完 的次序为2431 2 CPU 运行程序的过程示意图如下图所示 在该图中 粗短线部分代表进行交换程序状态字的时间 t 为 1 个单位时间 题型 2 2 若机器共有 5 级中断 中断响应优先次序为 l 2 3 4 5 现要求其实际的中断处理次序 为 l 4 5 2 3 1 设计各级中断处理程序的中断级屏蔽位 令 1 对应于屏蔽 0 对应于开放 2 若在运行用户程序时 同时出现第 4 2 级中断请求 而在处理第 2 级中断未完成时 又同时出现第 l 3 5 级中断请求 请画出此程序运行过程示意图 分析 根据题意 中断级屏蔽位 l 对应于屏蔽 0 对应于开放 实际上就是在图 3 1 中 控制各 级中断请求进入中断响应排队器入口端的与门控制端是接在各中断级屏蔽位触发器的 0 输出端而已 并无实质上的不同 此外 正在处理某级中断服务程序时 与其同级的新的中断请求是不能被响应的 应 福建农林大学计算机系统结构 共 18 页第 4 页 K T n TP 当予以屏蔽 这是因为两者既然是属于同一优先级的 则先来的中断请求理所应当先得到响应并被处理完 所以 根据所要求的中断处 理 完 的次序 各级中断处理程序现行状态字中各中断级屏蔽位的状态就很 容易被设置出来 解答 1 各级中断处理程序中的中断级屏蔽位的设置 如表 2 所示 表 2 中断级屏蔽位的设置 中断处理程序级别中断级屏蔽位 5 11111 01 00 0 1 0 01 11 501100 2 由已知条件可得程序运行过程的示意图如图 3 3 所示 图中 粗短线表示交换程序状态宇的时间 题型 3 吞吐率 衡量流水线性能的主要指标有吞吐率 加速比和效率 解决流水线瓶颈问题的常用方法 细分瓶颈段 重复设置瓶颈段 最大吞吐率 Tpmax 指流水线达到稳定状态后可获得的吞吐率 实际吞吐率 Tp 是指单位时间内能处理的任务数或输出结果的数量 它总是小于最大吞吐率 因为流水 线有建立阶段和排空阶段 以及其他因素会影响流水线的连续流动 1 吞吐率 Tp 流水线单位时间里能流出的任务数或结果数 各段时间均相等的流水线 实际吞吐率 tnk n TP 1 福建农林大学计算机系统结构 共 18 页第 5 页 最大吞吐率 各段时间不完全相等的流水线 实际吞吐率 最大吞吐率 2 效率 流水线中的设备实际使用时间与整个运行时间的比值 即流水线设备的利用率 各段时间均相等的流水线 E TP t 各段时间不完全相等的流水线 流水线中经过时间最长的子过程称为瓶颈子过程 例如 有一个 4 段的指令流水线如图 2 所示 其中 1 3 4 段的经过时间均为 0 t 只有 2 段的经过时 间为 0 3t 因此瓶颈在 2 段 使整个流水线最大吞吐率只有 3 1 0 t 其时 空图如图 3 所示 即使流水 线每隔 0 t 流入一条指令 也会因来不及处理被堆积于 2 段 致使流水线仍只能以 0 3t 才流出一条指令 为了提高流水线的最大吞吐率 首先要找出瓶颈 然后设法消除此瓶颈 消除瓶颈的一种办法是将瓶 颈子过程再细分 例如将 2 段再细分成 21 22 23 三个字段 如图 4 所示 让各子段经过时间都减少到 0 t 这样 最大吞吐率就可提高到 0 1t 图 5 是将瓶颈子过程再细分后的时 空图 然而 并不是所有的子过 程都能再细分的 假如 2 段已经不能再细分了 则可以通过重复设置多套 如此例用 3 套 瓶颈段并联 让它们交叉并行 如图 6 所示 每隔 0 t 轮流给其中一个瓶颈段分配任务 使它们仍可每隔 0 t 解释完一 条指令 时 空图见图 7 所示 这种办法需要解决好在各并行子过程之间的任务分配和同步控制 比瓶颈 ttnk n TP n 1 1 lim max k i ki tttnt n TP 1 21 max 1 max 1 21 max k ttt TP k i ki k i i tttntk tn E 1 21 1 max 1 福建农林大学计算机系统结构 共 18 页第 6 页 子过程再细分控制要复杂 设备量要多 以上讲的都是流水线连续流动时能达到的最大吞吐量 由于流水开始时总要有一段建立时间 加上各 种原因使流水线不能连续流动 经常是流一段时间 停一段时间 因此流水线的实际吞吐率 p T总比最大吞 吐率 max p T 要小 例题 为提高流水线效率可采用哪两种主要途径来克服速度瓶颈 现有 3 段流水线 各段经过时间依次 为 t 3 t t 1 分别计算在连续输入 3 条指令时和 30 条指令时的吞吐率和效率 2 按两种途径之一改进 画出你的流水线结构示意图 同时计算连续输入 3 条指令和 30 条指令时的吞吐 率 3 通过对 1 2 两小题的计算比较可得出什么结论 解答 提高流水线效率 消除速度瓶颈主要有将瓶颈段再细分以及重复设置多个瓶颈段并联工作 给其轮 流分配任务的两种途径 1 在 3 段流水线 各段经过时间依次是t t 3 t 的情况下 连续流入 3 条指令时 将 ttttttttmn j 3 3 3 2 321 代入 可得吞吐率 p T和效率 为 t tnt n T m i ji p 11 3 1 1 福建农林大学计算机系统结构 共 18 页第 7 页 而连续流入 30 条指令时 只需将上式之 n 改为 30 其他参数不变 得 2 若采取将 2 段细分成 3 个字段 每个字段均为t 构成的流水线结构如下图所示 连续流入 3 条指令时 将tmn ji 5 3代入 得 连续流入 30 条指令时 将30 n代入 其它参数不变 有 若采取将 3 个 2 段并联构成的流水线 其构成如下图所示 连续流入 3 条指令及流入 30 条指令时的吞吐率 p T和效率 所计算的结果分别与子过程细分的相同 11 5 1 1 1 m i ji m i i tntm tn t tnt n T m i ji p 46 15 1 1 46 25 1 1 1 m i ji m i i tntm tn t tt T i ji p 7 3 13 3 5 1 7 3 75 3 5 1 t t i i t tt T i ji p 17 15 130 30 5 1 17 15 345 530 t t 福建农林大学计算机系统结构 共 18 页第 8 页 3 将 1 题中 n 3 和 n 30 的计算结果进行比较可以看出 只有当连续流入流水线的指令越多时 流 水线的实际吞吐率和效率才会提高 将 1 2 题的计算结果进行比较 同样可以看出 无论采用平瓶颈子过程再细分 还是将多个瓶 颈子过程并联来消除流水线瓶颈 都只有在连续流入流水线的指令数越多时 才能使实际吞吐率和效率得 到显著的提高 若连续流入流水线的指令数太少 消除流水线瓶颈虽可以提高流水线的实际吞吐率 p T 而 效率 却可能下降 题型 4 1 在一个 4 段的流水线处理机上需经 7 拍才能完成一个任务 其预约表如下表所示 分别写出 延迟禁止表 F 冲突向量 C 画出流水线状态转移图 求出最小平均延迟及流水线的最大吞吐率及其调度时 的最佳方案 按此调度方案 输入 6 个任务 求实际的吞吐率 段 时间 1234567 1 S 2 S 3 S 4 S 解答 此例可得延迟禁止表 F 2 4 6 初始冲突向量 C 101010 状态转移图如图所示 各种周期性调度方案及其相应的平均延迟如下表所示 调度方案平均延迟 拍 1 7 4 3 5 4 5 3 4 5 5 由表可知 最小平均延迟为 4 拍 此时流水线的最大吞吐率 Tpmax 1 4 任务 拍 最佳调度方案宜选其中按 1 7 周期性调度的方案 按 1 7 调度方案输入 6 个任务 全部完成的时间为 1 7 1 7 1 7 24 拍 实际吞吐率 Tp 6 24 任务 拍 若按 3 5 调度方案输入 6 个任务 全部完成的时 间为 3 5 3 5 3 7 26 拍 实际吞吐率 Tp 6 26 任务 拍 若按 5 3 调度方案输入 6 个任务 全部完成 的时间为 5 3 5 3 5 7 28 拍 实际吞吐率 Tp 6 28 任务 拍 题型 4 2 在一个 5 段的流水线处理机上需经 9 拍才能完成一个任务 其预约表如表下表所示 表 9 拍才能完成一个任务的预约表 时间时间 段段 t t t t0 0 0 0t t t t1 1 1 1t t t t2 2 2 2t t t t3 3 3 3t t t t4 4 4 4t t t t5 5 5 5t t t t6 6 6 6t t t t7 7 7 7t t t t8 8 8 8 S S S S1 1 1 1 S S S S2 2 2 2 S S S S3 3 3 3 S S S S4 4 4 4 S S S S5 5 5 5 福建农林大学计算机系统结构 共 18 页第 9 页 分别写出延迟禁止表 F 冲突向量 C 画出流水线状态转移图 求出最小平均延迟及流水线的最大吞 吐率及其调用方案 按此流水调度方案输入 6 个任务 求实际吞吐率 解答 对预约表中各个行中打 的拍数求出差值 并将这些差值汇集在一起 就可得到延迟禁止表 F 1 3 4 8 由延迟禁止表 F 可转换得初始冲突向量 C 10001101 根据初始冲突向量可画出状态转 移图如下图所示 流水线状态转移图为 各种周期性调度方案及其相应的平均延迟如下表所示 调度方案平均延迟 拍调度方案平均延迟 拍 2 5 3 5 6 7 6 5 2 7 4 5 7 7 5 5 5 2 3 5 6 5 5 5 6 6 由上表可知 最小平均延迟为 3 5 拍 此时流水线的最大吞吐率 Tpmax 1 3 5 任务 拍 最佳调度方案宜选其中按 2 5 周期性调度的方案 按 2 5 调度方案输入 6 个任务的时空图为 1 11 1 1 1 11 1 1 12 2 2 2 22 22 22 23 33 3 3 3 3 3 33 34 4 4 4 4 4 44 4 4 45 5 5 5 55 55 5 5 56 66 6 66 66 66 6 时 间 空 间 段 号 s1 s2 s3 s4 s5 01 2 3 4 5 6 78 91 01 11 21 31 41 5 1 6 1 7 1 81 9 2 02 12 2 2 3 2 42 5 t 全部完成的时间为 25 拍 实际吞吐率 Tp 6 25 拍 任务 题型 4 2 求向量 CBAD 各向量元素均为 N 参照 CRAY 1 方式分解为 3 条向量指令 1 3 V 存储器 访存取 A 送入3 V 寄存器组 2 2 V 0 V 1 V KCB 3 4 V 2 V 3 V DAK 当采用下列 3 种方式工作时 各需多少拍才能得到全部结果 1 1 2 3 串行执行 2 1 和 2 并行执行完后 再执行 3 3 采用链接技术 解答 1 每条指令所需拍数为 福建农林大学计算机系统结构 共 18 页第 10 页 指令 1 1 启动访存 6 访存 1 存 V3 N 1 第一个分量后每隔 1 拍出一个结果 7 N 拍 指令 2 1 送浮加部件 6 浮加 1 存 V2 N 1 7 N 拍 指令 3 1 送浮乘部件 7 浮乘 1 存 V4 N 1 8 N 拍 串行 7 N 7 N 8 N 22 3N 拍 2 指令 1 和 2 并行执行 1 启动访存 送浮加部件 6 访存 浮加 1 存 V3 存 V2 N 1 7 N 拍 1 2 并行 7 N 8 N 15 2N 拍 3 1 6 1 1 7 1 N 1 16 N 拍 题型 4 3 设向量长度为 64 以 CRAY 1 机上所用浮点功能部件的执行时间分别为 相加 6 拍 相乘 7 拍 求倒数近似值 14 拍 从存储器读数 6 拍 打入寄存器及启动功能部件各 1 拍 问下列各指令组内的哪 些指令可以链接 哪些指令不能链接 不能链接的原因是什么 分别计算出各指令组全部完成所需的拍 数 1 2 3 4 0 V 存储器 1 V 2 V 3 V 4 V 5 V 6 V 2 V 0 V 1 V 3 V 存储器 4 V 2 V 3 V 0 V 存储器 2 V 0 V 1 V 3 V 2 V 0 V 5 V 3 V 4 V 0 V 存储器 1 V 1 0 V 3 V 1 V 2 V 5 V 3 V 4 V 解答 1 3 条向量指令之间既没有发生源 i V冲突 也没有 i V的先写后读相关 又不存在功能部件的使 用冲突 所以这 3 条向量指令可以同时并行流水 max 1 6 访存 1 64 1 1 6 浮加 1 64 1 1 7 浮乘 1 64 1 72 拍 所以向量指令组全部完成需要 72 拍 2 3 条向量指令之间没有功能部件的使用冲突 但是在第 1 2 两条向量指令与第 3 条向量指令之间有 V2 及 V3 的先写后读相关 只要让第 1 条向量指令较第 2 条向量指令提前 1 拍启动 则第 1 2 两条向量指令 的第 1 个结果元素就可以被同时链接到第 3 条向量指令中 max 1 7 浮乘 1 64 1 1 6 访 存 1 64 1 1 6 浮加 1 64 1 80 拍 3 第 1 条向量指令与第 2 条向量指令之间有 V0 的先写后读相关 两者可以链接 第 3 条向量指令与第 2 条向量指令之间有源向量寄存器 V0 的冲突 它们之间只能串行 第 3 条向量指令与第 4 条向量指令之间 有加法功能部件的使用冲突 它们之间也只能串行 1 6 访存 1 1 7 浮乘 1 64 1 1 6 访 存 1 64 1 1 6 浮加 1 64 1 222 拍 4 4 条向量指令均依次有 Vi 的先写后读相关 但无源 Vi 冲突 也无功能部件的使用冲突 所以 这 4 条 向量指令可以全部链接在一直 进行流水 1 6 访存 1 1 14 求倒数 1 1 7 浮乘 1 1 6 浮 加 1 64 1 104 拍 题型 5 并行处理机有 16 个处理单元 要实现相当于先 8 组 2 元交换 然后是 1 组 16 元交换 再次是 4 组 4 元交换的交换函数功能 1 写出实现此交换函数最终等效的功能 各处理器间所实现的互连函数的一般式 2 画出实现此互连函数的四级立方体互连网络拓扑结构图 标出各级交换开关的状态 解答 1 01230123 bbbbbbbbCube 2 拓扑结构及变换开关状态如下图所示 福建农林大学计算机系统结构 共 18 页第 11 页 题型 6 给定算术表达式FDCBAEZ 利用普通的串行编译算法 产生三元指令组为 指令之间都是相关的 需 5 级运算 如用并行编译算法 则可得到能并行执行的三元指令组为 分配给两个处理机 只需 3 级运算 假定 A B 两个88 矩阵相乘 需要在多处理机实现任务一级 即外循环 的并行 用 FORTRAN 语言书写 的程序如下 DO 10 J 0 6 10FORK20 J 7 20DO30I 0 7 C I J 0 DO40K 0 7 40C I J C I J A I K B K J 30CONTINUE JOIN8 设 FORK 语句在处理机上执行 在循环执行 7 次 FORK 20 语句时 派生出 J 0 6 共 7 个以 20 为标号的进程 让它们与 J 7 的进程并行 如果只有 3 台处理机 分配了 J 0 和 J 1 的进程后 其余 J 为 2 6 的 5 个进程 就得排队等待 处理机 1 在结束循环后执行 J 7 的进程 整个程序在先后执行完 8 个进程才结束 资源时 Z F E D C BA 56 45 34 2 3 1 2 1 Z FE DC BA 56 435 4 21 3 2 1 福建农林大学计算机系统结构 共 18 页第 12 页 间图如下图所示 题型 6 2 由霍纳法则给定的表达式如下 ghfedcbaE 利用减少树高的办法来加速运算 要求 1 画出树形流程图 2 确定 PP ESPT P 的值 解答 1 对于原先只能单处理机处理 7 1 T 改成 cdbaghfaceE 其计算的树形流 程图如下图所示 1 P 34 P T 题型 6 3 求 821 AAA 的累计加 有如下程序 1 写出用 FORK JOIN 语句表示其并行任务的派生和汇合关系的程序 以假使此程序能在多处理机上运 行 2 画出该程序在有三台处理机的系统上运行的时间关系示意图 3 画出该程序在有两台处理机的系统上运行的时间关系示意图 解答 1 改写后的程序为 FORK20 FORK30 FORK40 10A1 A1 A2 JOIN4 GOTO80 4 7 1 P P T T S 12 7 P S E P P 511 755 311 877 655 433 211 7 6 5 4 3 2 1 AAAS AAAS AAAS AAAS AAAS AAAS AAAS 福建农林大学计算机系统结构 共 18 页第 13 页 20A3 A3 A4 JOIN4 GOTO80 30A1 A5 A6 JOIN4 GOTO80 40A7 A7 A8 JOIN4 80FORK60 50A1 A1 A3 JOIN2 GOTO70 60A5 A5 A7 JOIN2 70A1 A1 A5 2 在三台处理机的系统上运行的时间关系图如下图所示 设标号 50 和 60 的两个并发进程中 标号为 60 的进程最后完 3 在两台处理机的系统上运行的时间关系图如下图所示 设标号 50 进程最后完 题型 6 4 若有下述程序 YXZ UWY VWX UAW BUV BAU 试用 FORK JOIN 语句将其改写成可在多处理机上并行执行的程序 假设现有两台处理机 且除法速度最 慢 加 减法速度最快 请画出该程序运行时的资源时间图 解答 改写后的程序为 10U A B FORK30 20V U B JOIN2 GOTO40 30W A U JOIN2 40FORK60 50X W V JOIN2 GOTO70 60Y W U JOIN2 70Z X Y 福建农林大学计算机系统结构 共 18 页第 14 页 简答题简答题简答题简答题 1 通过举例来说明什么是计算机系统结构 计算机组成和计算机实现 答 指令系统的确定属于计算机系统结构 指令的实现 如取指令 指令操作码译码 计算操作数地址 取数 运算 送结果等的操作安排和排序属于计算机组成 实现这些指令功能的具体电路 器件的设计及 装配技术属于计算机实现 确定指令系统中是否要设乘法指令属于计算机系统结构 乘法指令是专门的高 速乘法器实现 还是靠用加法器和移位器经一连串时序信号控制其相加和右移来实现属于计算机组成 乘 法器 加法 移位器的物理实现 如器件的类型 集成度 数量 价格 微组装技术的确定和选择属于计 算机实现 主存容量与编址方式的确定属于计算机系统结构 为达到性能价格要求 主存速度应该为多少 逻辑结构是否采用多体交叉属于计算机组成 主存器件的选定 逻辑设计 微组装技术的使用属于计算机 的实现 2 简述并行性开发的途径 答 开发并行性的途径有时间重叠 资源重复和资源共享等 3 计算机系统的 3T 性能目标是什么 答 计算机系统的 3T 性能目标是 1TFLOPS 计算能力 1TBYTE 主存容量 和 1TBYTES 的 I O 带宽 4 什么是数据表示 以及引入数据表示的原则 答 数据表示指的是能由机器硬件直接识别和引用的数据类型 引入数据表示的原则有 1 看系统的 效率是否提高 即是否减少了实现时间和存储时间 2 看引入这种数据表示后 其通用性和利用率是否 提高 5 如何选择尾数基值大小 答 尾数基值取大 会扩大浮点数的表示范围 增加可表示数的个数 减少移位次数 降低右移造成的 精度损失和提高运算速度 这都是好的 但会降低数据的表示精度 数值的分布变稀 这些是不好的 因 此 m r的选取要根据应用需要来综合平衡 一般在巨 大 中型机上 m r宜取大 这样可使数的表示范 围大 个数多 运算速度快 又因浮点数尾数位数相对多得多 所以精度实际比小 微型机的高得多 而 小 微型机由于可表示数范围不要求太大 速度也不要求太高 倒是尾数字长较短 因此更注重于可表示 的精度 宜使 m r值取小些 如 IBM370 取 m r 16 Burroughs 的大部分机器 包括 B6700 7700 取 m r 8 而 PDP 11 CDC6600 CYBER70 等取 m r 2 6 相关处理有哪几类处理 解决重叠方式相应处理的采用什么方案 答 相关处理包括转移指令的处理 指令相关的处理 主存空间数相关的处理 通用寄存器组相关的处 理 包含有操作数的相关和变址值 基址值的相关两种 推后 分析 1 k 和设置 相关专用通路 是解决 重叠方式相关处理的两种基本方法 前者是以降低速度为代价 使设备基本上不增加 后者是以增加设备 为代价 使重叠效率不下降 7 全局性相关的处理常用的处理方法 答 1 猜测法 2 加快和提前形成条件码 3 采取延迟转移 4 加快短循环程序的处理 8 多级互连网络开关的控制方式 答 1 级控制 同一级的所有开关只用一个控制信号控制 同时只能处于同一种状态 2 单元控制 每一个开关都有自己独立的控制信号控制 可各自处于不同的状态 3 部分级控制 第i级的所有开关分别用1 i个信号控制 nni 10 为级数 9 nn 维如何不冲突访问 答 只要并行存储体体数 n 为偶数 对nn 的正方形数组无论怎样存放 都不可能同时实现行 列 主 对角线 次对角线上的所有元素都能无冲突地访问 福建农林大学计算机系统结构 共 18 页第 15 页 10 多 Cache 的一致性问题的解决办法 答 1 解决进程迁移引起的多 Cache 的不一致性 2 以硬件为基础实现多 Cache 的一致性 3 以 软件为基础实现多 Cache 的一致性 11 程序并行性分析中 数据相关的种类 答 1 数据相关 先写后读 相关 2 数据反相关 先读后写 相关 3 数据输出相关 写 写 相关 4 同时具有 先写后读 和 先读后写 相关 5 不存在任何一种数据相关 名词解释名词解释名词解释名词解释 1 计算机系统结构计算机系统结构计算机系统结构计算机系统结构 也称计算机系统的体系结构 ComputerArchitecture 它只是系统结构中的一部分 指的是传统机器级的系统结构 它是软件和硬件 固件的交界面 是机器语言 汇编语言程序设计者 或 编译程序设计者看到的机器物理系统的抽象 2 并行性并行性并行性并行性 并行性是指问题中具有可同时进行运算或操作的特性 并行性包括同时性和并发性 3 数据表示数据表示数据表示数据表示 数据表示指直接可以被硬件识别和处理的数据类型 即 可以直接被计算器指令运算和处理 如整数 浮点数 向量等 4 CISCCISCCISCCISC 即复杂指令系统 Complex Instruction Set Computer CISC 其设计思想是认为计算机性能 的提高主要依靠增加指令复杂性及其功能实现的 即增强指令功能 用新的复杂指令替代原由软件子程序 完成的功能 实现软件功能硬化的计算机系统 5 RISCRISCRISCRISC 精简指令系统 Reduced Instruction Set Computer RISC 其设计思想是简单的指令能执行 得更快以及指令系统只由使用频率高的指令组成 即减少指令数目 简化指令功能 降低硬件复杂度 提 高指令执行速度 1 个节拍内完成 的计算机系统 6 数据宽度数据宽度数据宽度数据宽度 数据宽度是 I O 设备取得 I O 总线后所传输数据的总量 又称数据逻辑宽度 7 数据通路宽度数据通路宽度数据通路宽度数据通路宽度 数据总线的物理宽度 8 存储存储存储存储体系体系体系体系 所谓存储体系 就是让构成存储系统的n种不同的存储器 1n MM 之间 配上辅助软 硬 件或辅助硬件 使之从应用程序员来看 它们在逻辑上是一个整体 让存储层次的等效访问速度是接近于 1 M 的 每位价格的接近于 n M 的 9 全排列网络全排列网络全排列网络全排列网络 同时实现两对或多对入 出端间的连接时 不可能发生争用数据传送路径的冲突 称无这 类性质的互连网络为非阻塞式网络或全排列网络 10 多处理机多处理机多处理机多处理机 指有两台以上的处理机 共享 I O 子系统 机间经共享主存或高速通信网络通信 在操作 系统控制下 协同求解大而复杂问题的计算机系统 11 时间重叠时间重叠时间重叠时间重叠 时间重叠是在并行性概念中引入时间因素 让多个处理过程在时间上相互错开 轮流重叠 地使用同一套硬件设备的各个部分 加快硬件周转来赢得速度 12 资源重复资源重复资源重复资源重复 是在并行概念中引入空间因素 通过重复设置硬件资源来提高可靠性和性能 13 资源共享资源共享资源共享资源共享 是用软件方法让多个用户按一定时间顺序轮流使用同一套资源来提高资源利用率 相应地 也就提高了系统的性能 选择判断选择判断选择判断选择判断 1 计算机系统的软硬件取舍 软件和硬件在逻辑功能上是等效的 1 确定软 硬件功能分配比例的第一 个基本原则 考虑在现有硬 器件 主要是逻辑器件和存储器件 条件下 系统要有高的性能价格比 主要 从实现费用 速度和其他性能要求来综合考虑 2 确定软 硬件功能分配的第二个基本原则 要考虑到 准备采用和可能采用的组成技术 使它尽可能不要过多或不合理地限制各种组成 实现技术的采用 3 确定软 硬件功能分配的第三个基本原则 不能仅从 硬 的角度考虑如何便于应用组成技术的成果和便 于发挥器件技术的进展 还应从 软 的角度把如何为编译和操作系统的实现以及为高级语言程序的设计 福建农林大学计算机系统结构 共 18 页第 16 页 提供更多更好的硬件支持放在首位 2 系统结构中的并行性发展和计算机系统的分类 弗林分类法 1 单指令流单数据流 SISD 2 单 指令流多数据流 SIMD 3 多指令流单数据流 MISD 4 多指令流多数据流 MIMD 冯氏分类法 1 字串位串 WSBS 2 字串位并 WSBP 3 字并位串 WPBS 4 字并位并 WPBP 3 尾数基值大小和下溢处理方法 可表示数的范围 随 rm 的增大 可表示数的范围增大 可表示数的个数 随 rm 的增大 可表示数的个数增多 数在实数轴上的分布 rm 越大 数的密度分布越稀 可表示数的精度 由于 rm 愈大 数在数轴上的分布变稀 已可得出数的表示精度下降的结论 运算中的精度损失 rm 愈大 尾数右移的可能性愈小 精度的损失就越小 下溢处理方法 1 截断法 2 舍入法 3 恒置 1 法 4 查表舍入法 4 数据宽度类型 有单字 单字节 定长块 可变长块 单子加定长块和单子加可变长块等 单字 单字节 宽度适合于输入机 打印机等低速设备 采用定长块适合于磁盘等高速设备 可以充分利 用总线带宽 采用可变长块宽度适合于高优先级的中高速磁带 磁盘等设备 三类通道 分字节多路 选择和数组多路 字节多路通道适用于连接大量的像光电机等字符类低速设备 数组多路通道适合于连接多台像磁盘等高速 设备 选择通道适合于连接优先级高的磁盘等高速设备 5 透明性的判断 选择 例 什么是透明性概念 对计算机系统结构 下列哪些是透明的 哪些是不透明的 存储器的模 m 交叉存取 浮点数据表示 I O 系统是采用通道方式还是外围处理机方式 数据总线宽 度 字符行运算指令 阵列运算部件 通道是采用结合型还是独立型 PDP 11 系列的单总线结构 访 问方式保护 程序性中断 串行 重叠还是流水控制方式 堆栈指令 存储器最小编址单位 Cache 存储器 答 透明指的是客观存在的事物或属性从某个角度看不到 简称透明 Transparent 不同机器级程序员 所看到的计算机属性是不同的 它就是计算机系统不同层次的界面 透明的有 存储器的模 m 交叉存取 数据总线宽度 阵列运算部件 通道是采用结合型还是独立型 PDP 11 系列的单总线结构串行 重叠还是流水控制方式 Cache 存储器 不透明的有 浮点数据表示 I O 系统是采用通道方式还是外围处理机方式 字符行运算指令 访问 方式保护 程序性中断 堆栈指令 存储器最小编址单位 6 流水方式的分类 1 流水按处理的级别可以分为部件级 处理机级和系统级 2 按功能可以分为单 功能流水线和多功能流水线 3 按多功能流水线的各段能否允许同时用于多种不同功能连接流水 可以 分为静态流水线和动态流水线 静态流水线 在某一时间内各段只能按一种功能连接流水 只有等流水线 全部流空后 才能切换成按另一种功能的连接流水 动态流水线 各功能段在同一时间内可按不同运算或 功能连接 4 从机器所具有的数据表示可以分为标量流水机和向量流水机 7 浮点数尾数基值的选择 优 缺 一般在巨 大 中型机上 rm 宜取大 这样可使数表示的范围大 个数多 运算速度快 有因在这些机器上尾数位数多 精度实际比小 微型机的高得多 小 微型机由于 数表示的范围小 速度要求不高 尾数字长较短 更注重数表示的精度 rm 宜取小些 8 局部性相关的处理 指令相关 访存操作数相关和通用寄存器组相关等局部性相关都是由于在机器同时 解释的多条指令之间出现了对同一主存单元或寄存器要求 先写后读 重叠机器处理这些局部性相关的 方法有两种 1 推后后续指令对相关单元的读 直至在先的指令写入完成 2 设置相关直接通路 将 福建农林大学计算机系统结构 共 18 页第 17 页 运算结果经相关直接通路直接送入所需部件 是流水线有多个子过程 多条指令同时处在不同子过程上解 释 任务在流水线中流动顺序的安排和控制可以有两种方式 1 让任务 指令 流出流水线的顺序保持 与流入流水线的顺序一致 称为顺序流动方式或同步流动方式 2 让流出流水线的任务 指令 顺序可 以和流入流水线的顺序不同 称为异步流动方式 当流水线采用异步流动方式后 会出现顺序流动不会发生的其他相关 除 先写后读 外还 先读 后写 写 写 相关 写 写 相关