体系结构复习重点【升级版删减版】

体系机构复习重点体系机构复习重点 注 注 红色红色代表不确定 代表不确定 玫粉色玫粉色是加进去的是加进去的 第一章不考大题 第二章不考概念第一章不考大题 第二章不考概念 一 小题一 小题 1 Amdahl 定律 系统中某一部件由于采用更快的执行方式后 整个系统性能的提高与这种执行 方式的使用频率或占总执行时间的比例有关 2 指令级并行 一种平行计算形式 在一个程式运行中 许多指令操作 能在同时间进行 3 程序的局部性原理 是指程序在执行时呈现出局部性规律 即在一段时间内 整个程序的执行仅限 于程序中的某一部分 相应地 执行所访问的存储空间也局限于某个内存区域 4 透明性概念 定义 本来存在的事物或属性 从某种角度看似乎不存在 5 大概率事件优先原则 对于大概率事件 最常见的事件 赋予它优先的处理权和资源使用权 以 获得全局的最优结果 7 超标量处理机 采取设置 M 条指令流水线同时并行 来实现并行度为 m 的处理机 8 向量流水处理 把要解决的问题转化成向量运算 采用横向 纵向 纵横处理方式 对向量各分量进行独立并行的处理 9 系列机 具有相同的系统结构 但组成和实现技术不同的一系列计算机系统 兼容 软件 硬件 兼容最基本特征 向右兼容 11 并行性 指令内部 指令级 线程级 任务级 作业级 指计算机系统具有可以同时进行运算或操作的特性 在同一时间完成两种或 两种以上工作 它包括同时性与并发性两种含义 同时性指两个或两个以上事 件在同一时刻发生 并发性指两个或两个以上事件在同一时间间隔发生 14 写直达法 写回 写直达法 在执行写操作时 不仅把信息写入 Cache 中相应的块 而且也写 入下一级存储器中相应的块 15 加速比 加速比 speedup 是同一个任务在单处理器系统和并行处理器系统中运行 消耗的时间的比率 用来衡量并行系统或程序并行化的性能和效果 16 数据相关 在执行本条指令的过中 如果用到的指令 操作数 变址偏移量等正好是前 面指令的执行结果 则必须等待前面的指令执行完成 并把结果写到主存或通 用寄存器中之后 本条指令才能开始执行 这种相关称为数据相关 17 控制相关 条件分支指令 转子程序指令 中断等引起的相关 18 存储器系统 计算机中的存储系统是用来保存数据和程序的 对存储器最基本的要求就是 存储容量要大 存取速度快 成本价格低 为了满足这一要求 提出了多级存 储体系结构 一般可分为高速缓冲存储器 主存 外存 3 个层次 有时候还包 括 CPU 内部的寄存器以及控制存储器 20 虚拟机 指通过软件模拟的具有完整硬件系统功能的 运行在一个完全隔离环境中的完 整计算机系统 二 简单问答题二 简单问答题 1 计算机体系结构 计算机系统结构就是计算机的机器语言程序员或编译程序编写者所看到的外特 性 是硬件子系统的概念结构及其功能特性 2 CPI 每条指令所需的平均时钟周期数 3 软件兼容 一个软件可以不经修改或者只需要少量修改就可以由一台计算机移植到另一台 计算机上运行 差别只是执行的时间不同 4 仿真与模拟 仿真是指用微程序的方法在一台计算机上实现另一台计算机的指令系统 模拟是指用软件的方法在一台计算机上 实现另一台计算机的指令系统 5 时间重叠 资源重叠 时间重叠 在并行性概念中引入时间因素 让多个处理过程在时间上相互错开 轮流重叠的使用同一套硬件设备的各个部分 以加快硬件周转而赢得速度 以数量取胜 通过重复设置硬件资源 大幅度的提高计算机系统的 资源重叠 重复 在并行性概念中引入空间因素性能 6 先行控制器 先行控制器处理机结构 包括三个独立的控制器和四个缓冲栈 其中三个控制 器为 存储控制器 指令控制器 运算控制器 四个缓冲栈 先行指令缓冲栈 线性读数缓冲栈 现行操作栈 后行写数栈 7 紧密耦合系统 松散耦合系统 smp mpp 紧密耦合系统 机间物理连接的频带较高 它们往往通过总线或者告诉开关实 现互联 可以共享主存 松散耦合系统 通过通道或者通信线路实现计算机间互联 共享某些外围设备 机器间的相互作用是在文件或者数据集一级进行 8 异构型多处理机系统 同构型多处理机类型 同构型 对称型 多处理机 由多个同类型 至少担负同等功能的处理机组成 同时处理同一作业中能并行执行的多个任务 异构型 非对称型 多处理机 由多个不同类型 至少担负不同功能的处理机 组成 按照作业要求的顺序 利用时间重叠原理 依次对它们的多个任务进行 加工 各自完成规定的功能动作 9 佛林分类 他按照他按照指令流指令流和数据流的多倍性特征对和数据流的多倍性特征对计算机系统计算机系统进行分类 把计算机系统分进行分类 把计算机系统分 4 大类 单大类 单指令流指令流单数据流 单数据流 单指令流多数据流单指令流多数据流 多多指令流指令流单数据流 单数据流 多指令多指令 流多数据流流多数据流 10 并行等级划分 1 指令内部并行 指令内部的微操作之间的并行 2 指令级并行 Instruction Level Parallel ILP 并行执行两条或多条 指令 3 任务级或过程级并行 并行执行两个或多个过程或任务 程序段 4 作业或程序级并行 在多个作业或程序间的并行 11 堆栈型机器 通用计算型 一种计算模型 这种类型的电脑 内存以堆栈 Stack 储存 它的指令集中包 含了零位址指令 0 operand instruction set 硬件在执行运算时 到堆 栈的顶端去取出算子 至运算结束时 再储存到堆栈的顶端 12 RISC 指令系统的设计原则 a 大多数指令在单周期内完成 b 采用 LOAD STORE 结构 c 硬布线控制逻辑 d 减少指令和寻址方式的方案 f 固定的指令格式 g 注重译码的优化 13 静态流水 动态流水 动态流水线在同一时间内允许按多种不同运算的联结方式工作 静态流水线 在同一时间内只能按一种运算的联结方式工作 14 分支指令调度 分支条件由指令确定 提供一组比较指令 用于比较两个寄存器的值 有的分 支指令可以直接判断寄存器内容是否为负 或者比较两个寄存器是否相等 分 支的目标地址由 16 位带符号偏移量左移两位后和 PC 相加的结果来决定一条浮 点条件分支指令 通过测试浮点状态寄存器来决定是否进行分支 15 链接技术 分段开采 当利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度 的技术称为链接技术 向量的长度大于向量寄存器的长度时 必须把长向量分 成长度固定的段 采用循环结构处理这个长向量 这种技术称为向量循环开采 技术 也称为向量分段开采技术 16 半性能向量长度 达到一半最大性能值所需的向量长度 17 超流水 通过细化流水 提高主频 使得机器在一个周期内完成一个甚至多个操作 其实质 是用时间换取空间 18 CISC 复杂指令集 CPU 内部为将较复杂的指令译码 也就是指令较长 分成几个微 指令去执行 正是如此开发程序比较容易 指令多的缘故 但是由于指令复杂 执行工作效率较差 处理数据速度较慢 PC 中 Pentium 的结构都为 CISC CPU 三 计算题三 计算题 1 Amdahl 定律 见书 P10 两个例子 系统中某一部件由于采用更快的执行方式后 整个系统性能的提高与这种执行 方式的使用频率或占总执行时间的比例有关 改进后整个系统的加速比达到 题 假定我们利用增加向量处理模块来提高计算机的运算速度 计算机处理向 量的速度比其通常的运算要快 20 倍 我们将可用向量处理部分所花费的时间占 总时间的百分比称为可向量化百分比 1 求出加速比 S 和可向量化百分比 F 之间的关系式 2 当要得到加速比为 2 时的可向量化百分比 F 为多少 解 1 2 由上式 将 S 2 代入 得 F 10 19 0 53 2 CPI 和等效 CPI P11 平均时钟周期数 CPI 平均每条指令执行所需的时钟周期 越少 程序执行越快 这主要取决于 CPU 的体系结构 包括指 令系统的设计 指令时序过程的安排等 CPI 的含义 以 CPU 为评估的模块 以指令系统中各条指令被执行的概 率 频度 为依据 以平均每条指令所花费的时钟周期数标尺 对 CPU 的速度 进行评估 CPU 时间 CPU 时钟周期数 频率 CPU 时间 CPU 时钟周期数 时钟周期长 CPU 时间 IC CPI 频率 f 平均时钟周期数 CPI CPU 时钟周期数 IC 指令的条数 CPU 1 i n i i ICPI 的时钟周期数 通常用 MIPS 和 MFLOPS 反映系统 CPU 吞吐率 MIPS Million Instructions Per Second MIPS 6 10 执行时间 指令条数 6 10 CPI f MFLOPS Million Floating point Operations Per Second 时间改进后改进部分的执行 时间改进前改进部分的执行 改进部分的加速比 时间改进前整个任务的执行 可改进部分的执行时间 可改进部分的比例 Se Fe S T T F F S n n e e e 01 1 FFF S 1920 20 20 1 1 1 1 IC I CPI IC ICPI CPI i n i i n i ii MFLOPS 6 10 执行时间 程序中的浮点操作次数 题 有效 平均 CPI 计算 假设在一台 40MHZ 处理机上运行 200 000 条指令 的目标代码 程序主要由四种指令组成 根据程序跟踪实验结果 已知指令混 合比和每种指令所需的指令数如下 计算在单处理机上用跟踪数据运行程序的 平均 CPI 并根据所得的 CPI 计算相应的 MIPS 速率 指令类型 CPI 指令混合比 算术和逻辑 1 60 高速缓存命中的加载 存储 2 18 转移 4 12 高速存储缺失的存储器访问 8 10 解 CPI 1 60 2 18 4 12 8 10 2 24 MIPS f CPI 106 40 106 2 24 106 17 86 题 A 机执行的程序中有 20 转移指令 2TC 转移指令都需要一条比较指令 1TC 配合 其他指令 1TC B 机中转移指令包含比较指令 但 TC 比 A 机慢 15 A 机 B 机哪个工作速度快 A 机 TCPUA INA 0 2 2 0 2 1 0 6 1 TCA 1 2 INA TCA B 机 TCPUB 0 8INA 0 2 0 8 2 1 0 2 0 8 1 1 15TCA 1 15 INA TCA 结果 B 机比 A 机工作速度快 注意 不能仅按主频衡量系统性能 等效指令速度等效指令速度 吉普森 Gibson 法 加减法 50 乘法 15 除法 5 程 序控制 15 其他 15 静态指令使用频度 在程序中直接统计 动态指令使用频度 在程序执行过程中统计 题 假设在一般程序中浮点开平方操作 FPSQR 所占的比例为 2 它的 CPI 为 100 其他浮点操作 FP 所占的比例为 23 它的 CPI 4 0 其余 75 指令 的 CPI 1 33 计算该处理机的等效 CPI 如果 FPSQR 操作的 CPI 也为 4 0 重 新计算等效 CPI 等效 CPI1 100 2 4 23 1 33 75 3 92 等效 CPI2 4 25 1 33 75 2 00 改进了在用户程序中仅占 2 的开平方操作 整个机器的等效运算速度提高了 近一倍 n i ii 1 Weight TimeT等效指令执行时间 n i i 1 MIPS Weight 1 MIPS等效指令速度 等效 n i ii 1 WeightCPICPI 题 我国早期研制的一种小型计算机 DJS 130 定点 16 位 加法指令每秒 50 万 次 但没有硬件乘除法指令 用软件实现乘除法 速度低 100 倍左右 求等效 指令速度 解 等效指令速度为 即每秒 2 万次 由于用软件实现乘除法 等效指令速度降低了 25 倍 3 Huffman 编码 见 P92 例 最短平均长度 i n i ippH 1 2 log 其中 Pi表示第 i 种操作码在程序中出现的概率 固定长操作码相对于 Huffman 操作码的信息冗余量为 n pp R n i ii 2 1 2 log log 1 采用 Huffman 编码法操作码的最短平均长度可以通过如下公式计算 n i ii lpH 1 Huffman 操作码的主要缺点 操作码长度很不规整 硬件译码困难 与地址码共同组成固定长的指令比较困难 4 替换策略 FIFO LRU OPT 组相联 命中率 命中率定义 在 M1 存储器中访问到的概率 其中 N1 是对 M1 存储器的访问次数 N2 是对 M2 存储器的访问次数 访问周期与命中率的关系 T HT1 1 H T2 当命中率 H 1 时 T T1 存储系统的访问效率 MIPS0 02 100 0 5 0 20 0 5 0 80 1 MIPS 等效指令速度 H N NN 1 12 e T T T H THTHH f H T T T T 1 1 1 1 1 12 2 1 2 1 访问效率主要与命中率和两级存储器的速度之比有关 提高存储系统速度的两条途径 一是提高命中率 H 二是两个存储器的速度不要相差太大 其中 第二条有时做不到 如虚拟存储器 这时 只能依靠提高命中率 例 3 2 在虚拟存储系统中 两个存储器的速度相差特别悬殊 例如 T2 105 T 如果要使访问效率到达 e 0 9 问需要有多高的命中率 0 9H 90000 1 H 1 89999 1 H 89999 计算得 H 0 999998888877777 0 999999 例 3 3 在一个 Cache 存储系统中 当 Cache 的块大小为一个字时 命中率 H 0 8 假设数据的重复利用率为 5 T2 5T1 计算块大小为 个字时 Cache 存储系统的命中率 并分别计算访问效率 n 4 5 20 采用预取技术之后 命中率提高到 P166 替换算法 替换算法 例 3 9 一个程序共有 5 个页面组成 在程序执行过程中 页面地址流如下 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4 假设分配给这个程序的主存只有 3 个页面 1 给出用 FIFO LRU 和 OPT 三种页面替换算法对这 3 个主存页面的调度情况 表 并统计页面命中次数 2 计算这 LRU 页面替换算法的页面命中率 3 假设每个数据平均被访问 30 次 为了使 LRU 算法的失效率小于 10 5 计算 页面大小至少应该为多少 解 1 FIFO LRU 和 OPT 的页面命中次数分别为 2 次 4 次和 5 次 2 LRU 页面替换算法的页面命中率为 Hp 4 10 0 4 3 09 1 1 10 5 HH 99 0 20 1208 01 2 n nH H 0 558 1 10 8 5 1 0 81e1 0 8H Cache 访问效率为 块大小为一个字时当 0 9604 1 10 99 5 1 0 991e2 0 99H 4Cache2 访问效率为 个字时块大小为当 10 P03 4 01 H 1 5 P n 解得 P 2000 字 页面大小应该为 2K 字 例 a program P1 P2 P1 P5 P5 P1 P3 P4 P3 P4 page frame is 3 pages FIFO LRU OPT 例 有一个 Cache 存贮器 主存共分 8 个块 0 7 Cache 为 4 个块 0 一 3 采用组相联映象 组内块数为 2 块 替换算法为近期最少使用法 LRU 1 画出主存 Cache 地址的各字段对应关系 标出位数 图 2 画出主存 Cache 空间块的映象对应关系示意图 3 对于如下主存块地址流 1 2 4 1 3 7 0 1 2 5 4 6 4 7 2 如主存中内容一开始末装入 Cache 中 请列出 Cache 中各块随时间的使用状况 解 首先应根据题意 求得主存和 Cache 地址中各字段之位数 Cache 4 块 组内 2 块 所以组数为 2 组 即组号可有 0 或 1 之分 组内块号 s 为 1 位 主 存 8 块 Cache 4 块 所以区号 nd 为 1 位 由于组相联采用的映象规则是组间直接 组内相联 所以由主存块地址号 先要判断其是在哪一个组中 然后就只能在该组中装入或替换 0 组和 l 组 每组都有其自己的装入和替换问题 t 1 2 3 4 5 6 7 8 9 10 of hit P1 P2 P1 P5 P4 P1 P3 P4 P2 P4 1 1 1 1 4 4 4 4 2 2 2 2 2 2 1 1 1 1 4 FIFO 5 5 5 3 3 3 3 load l h l rep rep r h r r 2 次 1 1 1 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 4 LRU 5 5 5 3 3 3 3 l l h l r h r h r h 4 次 1 1 1 1 1 1 3 3 3 3 2 2 2 2 2 2 2 2 2 OPT 5 4 4 4 4 4 4 l l h l r h r h h h 5 次 程序运行时 由给出的主存块地址流可得到 Cache 中各个块的使用状况 如表所示 表中标 的是候选替换块的块号 例 一个二级存储层次 采用全相联映象和最久没有使用算法 实存共 5 页 为 2 道程序分享 页地址流分别如下 P1 1 2 3 4 1 3 2 1 P2 1 2 3 4 2 2 3 3 试作 2 个实存分配方案 分别使 2 道程序满足 1 命中率相同 2 命中次数之和最大 解 分别为 2 道程序作 堆栈模拟图 其中 表示命中 将两图结果综合 得到 4 个分配方案的命中率情况表如下 结论如下 1 命中率相同的方案是 n1 3 而 n2 2 2 命中次数之和最大的方案是 n1 4 而 n2 1 题 在一个 Cache 存储系统中 主存储器的访问周期 存储容量和单位价格分 别为 60ns 64MB 和 10 元 MB Cache 的访问周期 存储容量和单位价格分别为 10ns 512KB 和 100 元 MB Cache 的命中率为 0 98 1 计算这个 Cache 存储系统的等效访问周期 存储容量和单位价格 2 计算这个 Cache 存储系统的访问效率 解 1 这个 Cache 存储系统的等效访问周期 T Tc H Tm 1 H 10ns 0 98 60ns 1 0 98 11ns 等效存储容量 S 64MB 等效单位价格 C Cc Sc Cm Sm Sc Sm 100 0 5 10 64 0 5 64 10 7 元 MB 2 这个 Cache 存储系统的访问效率 e Tc T 10 11 0 91 2 三种映射框图 题 假定计算机的主存储器按 64 块组织 块大小为 8 个字 高速缓存有 8 个块 框 试画出采用以下映射方法从主存储器到高速缓存的映射关系 尽可能清楚 地画出所有的映射线 1 1 直接映射 2 2 全相联映射 解 1 直接映射方式 b8 b0 b1 b7 b9 b56 b57 B0 B1 B7 b63 标记3位高速缓存 块框 主存储器 块 3位 标记 3位 字 3位 存储器地址 2 全相联映射方式 b8 b0 b1 b7 b9 b56 b57 B0 B1 B7 b63 标记6位 高速缓存 块框 主存储器 标记 6位 字 3位 存储器地址 5 中断调度 调度图 例 4 2 某处理机共有 4 个中断源 中断优先级从高到低分别是 1 级 2 级 3 级和 4 级 当处理机在执行主程序时 同时有 3 级和 2 级两个中断源向处理 机发出中断服务请求 当处理机为 2 级中断源服务时又有 4 级中断源发出中断 服务请求 当处理机为 级中断源服务时又有 级中断源发出中断服务请求 解 处理机响应各中断源的中断请求和执行中断服务程序的过程如下 例 4 3 有四个中断源 D1 D2 D3 和 D4 它们的中断优先级从高到低分别是 1 级 2 级 3 级和 4 级 这些中断源的正常中断屏蔽码和改变后的中断屏蔽码 见下表 每个中断源一位 共 4 位屏蔽码 中中断断请请求求 主主程程序序 中中断断服服务务程程序序 1 1 级级 2 2 级级 3 3 级级 4 4 级级 2 2 3 3 级级 4 4 级级 1 1 级级 时时间间 t t 按按照照中中断断优优先先级级响响应应中中断断请请求求的的例例子子 解 如果 4 个中断源都使用正常的中断屏蔽码 处理机的中断服务顺序将严格按照 中断源的中断优先级进行 如果改变中断屏蔽码 当 D1 D2 D3 和 D4 这 4 个中断源同时请求中断服务 时 处理机实际为各个中断源服务的先后次序就会改变 处理机响应的顺序是 D1 D2 D3 D4 实际服务的顺序是 D4 D3 D2 D1 方法二 改变处理机优先级 例 4 4 某处理机共有 4 个中断源 D1 D2 D3 和 D4 它们的硬件中断优先级 从低到高分别为 1 级 2 级 3 级和 4 级 处理机本身的优先级最低 为 0 级 在中断源 D1 D2 D3 D4 的中断向量中 程序员为它们设置的优先级分别为 4 级 3 级 2 级 1 级 解 在处理机状态字中设置 3 个中断屏蔽位 000 为处理机本身的优先级 001 100 分别表示 4 个中断源的中断优先级 当 4 个中断源同时请求中断服务时 解 处理机实际完成中断服务的过程是 D3 D2 D4 D1 中中断断请请求求 主主程程序序 中中断断服服务务程程序序 D D1 1 D D2 2 D D3 3 D D4 4 D D1 1 D D2 2 D D3 3 D D4 4 时时间间 t t 中中断断请请求求 主主程程序序 中中断断服服务务程程序序 D D4 4 D D3 3 D D2 2 D D1 1 D D1 1 D D2 2 D D3 3 D D4 4 时时间间 t t 6 通道流量计算 通道的容量 工作周期 三种通道的最大流量计算公式 为保证通道不丢失数据 通道的实际流量应不大于通道最大流量 fBYTE fMAX BYTE fSELETE fMAX SELETE fBLOCK fMAX BLOCK 例 4 5 一个字节多路通道连接 D1 D2 D3 D4 D5 共 5 台设备 这些设备 分别每 10us 30us 30us 50us 和 75us 发出一次数据传送请求 1 计算这个通道的实际流量和工作周期 2 如果这个字节多路通道的最大流量正好等于通道实际流量 并假设数据 传输率高的设备 其优先级也高 5 台设备在 0 时刻同时向通道发出第一次传 送数据的请求 并在以后的时间里按照各自的数据传输率连续工作 画出通道 分时为各台设备服务的时间图 并计算处理完各设备的第一次请求的时刻 3 从时间图中发现什么问题 如何解决 解 1 通道的实际流量为 fBYTE 1 10 1 30 1 30 1 50 1 75 MB S 0 2MB S 通道的工作周期为 t 1 fBYTE 5us 通道处理完各设备这个第一次请求的时间 2 处理完各设备这个第一次请求的时间 D1 5us D2 10us D3 20us D4 30us 秒字节 秒字节 秒字节 1 1 1 DSDS BLOCKMAX DSDS SELETEMAX DSDS BYTEMAX TkTnpTkT np f TnTnpTnT np f TTnpTT np f 0 10 20 30 40 50 60 70 80 D1 t D2 t D3 t D4 t D5 t D5 的第一次请求没有响应 数据丢失 3 D5 的第一次请求没有得到响应的原因分析 对所有设备的请求时间间隔取最小公倍数 在这一段时间内通道的流量是 平衡的 可以采取下列方法 方法一 增加通道的最大工作流量 例如 把通道的工作流量增加到 0 25MB S 工作周期为 4us 方法二 动态改变设备的优先级 例如 在 30us 至 70us 之间临时提高设 备 D5 的优先级 方法三 增加缓冲存储器 例如 只要为设备 D5 增加一个数据缓冲寄存 器 它的第一次请求可以在第 85us 处得到响应 第二次请求可以在第 145us 处 得到响应 7 流水 静 动 时空图 非线性流水有返回 吞吐率 效率 相关性问题处 理不过不知道是不是大题 例 5 2 用一条 4 段浮点加法器流水线求 8 个浮点数的和 Z A B C D E F G H 解 Z A B C D E F G H 7 个个浮浮点点加加法法共共用用了了 15 个个时时钟钟周周期期 流流水水线线的的吞吞吐吐率率为为 TP n Tttk 7 15 0 47 1 流流水水线线的的加加速速比比为为 S T T t tk 047 15 1 87 流流水水线线的的效效率率为为 E T k T t tk 047 415 0 47 题 一动态多功能流水线由 个功能段组成 如下图 2 S1 S2 S3 S4 S5 S6 1 其中 s1 S4 S5 S6 组成乘法流水线 S1 S2 S3 S6 组成加法流水线 各个功能段时间均为 50ns 假定该流水线的输出结果可以直接返回流水线输入 端 而且设置有足够的缓冲寄存器 若按照最快的方式用该流水线计算 5 1i iii zyxf 1 请画出其处理过程的时空图 2 计算其实际吞吐率 加速比和效率 解 1 乘法操作用到的流水段有 S1 S4 S5 S6