北大--计算机体系--历年试卷题目汇总及解答cc

一一 填空填空 第一台通用电子计算机第一台通用电子计算机 ENIAC 第一台可操作的存储程序机器第一台可操作的存储程序机器 Mark I 第一台全面的 可操作的 存储程序计算第一台全面的 可操作的 存储程序计算 EDSAC 第一台流水线计算机第一台流水线计算机 IBM7030 第一台成功的商业化计算机 UNIVAC I 第一台首次使用变址寄存器 使用了控制程序 IBM704 第一台含通用寄存器的 Pegasus 第一台采用逻辑指令来进行非数值计算 IBM7094 第一台堆栈计算机 B5000 第一台商用小型机 PDP 8 第一台超级计算机 CDC 6600 采用了 load store 结构 第一台使用 cache 的商用计算机 IBM360 85 第一台商业话的向量超级计算机 Cray 1 1 0 用用 IEEE 754 表示表示 0 0 10 0 在在 IEEE754 中的表示中的表示 0 0 总线的三种类型总线的三种类型 地址总线 控制总线 数据总线 冒险的三种类型冒险的三种类型结构冒险 控制冒险 数据冒险 流水的三种相关流水的三种相关结构相关 控制相关 数据相关 数据的三种相关数据的三种相关先读后写相关 先写后读相关 写写相关 并行的三种方式并行的三种方式时间重叠 资源重复 资源共享 Cache 的四种失效的四种失效义务失效 冲突失效 容量失效 无效失效 主要的是前三种 计算机性能三要素计算机性能三要素指令数 时钟周期长度 CPI 如何判断如何判断 n 位加法溢出位加法溢出 溢出 最高位进位 XOR 次高位进位 cache 写策略 写命中时采取写策略 写命中时采取 和和 策略 写失效时采取策略 写失效时采取 和和 策略策略 写返回 写穿透 写分配 写不分配 意外的两种类型意外的两种类型 中断 自陷 指出关系 指出关系 指令总数指令总数 CPI 周期时间周期时间 编译器编译器 X X 指令系统指令系统 X X X 计算机组成计算机组成 X X 技术工艺技术工艺 X 二二 辨析辨析 浮点没有结合律浮点没有结合律 是的 当两个绝对值较大的相反数相加再和一个较小的数相加时 如果采用结合律 是不对的 比如 这里用 10 进制演示 假设有效位是 8 位 1 0 10 1 0 10 1 0 1 0 1 0 10 1 0 10 1 0 0 0 两者相差 1 0 1 E7 1 E7 7 E0 9 E0 1 E7 1 E7 7 E0 1 E1 两者相差 0 5 流水线级数的加深总能提高性能流水线级数的加深总能提高性能 错 1 数据冒险 代码中的数据冒险意味着增加流水线的长度会增加每条指令的执行 时间 因为流水线在大量的时钟周期里是阻塞的 2 控制冒险 控制冒险意味着增加流水线的长度会导致更慢的分支 因而增加了 程序执行的时钟周期 3 入不敷出 流水线开销限制了由于增加流水线长度获得的时钟片段减少的收益 实际上 流水线级数在 4 到 8 之间的时候性能相对是最高的 流水线减少了单个指令的执行时间流水线减少了单个指令的执行时间 错 流水线所带来的性能提高是通过增加指令的吞吐量 而不是减小单个指令的执行时间 RISC 就是就是 CISC 里的简单指令里的简单指令 错 RISC 和 CISC 不是从属关系 RISC 是简单指令系统 CISC 是复杂指令系统 指令系统强大的计算机一定有好的性能指令系统强大的计算机一定有好的性能 错 性能涉及到 周期时间 CPI 指令条数 与指令系统的强大无直接关系 指令系统影响不了周期时间 汇编语言和机器指令一一对应汇编语言和机器指令一一对应 如果考虑伪指令 错的 如果不考虑伪指令 对的 具体怎么答看大家吧 ORZ SPEC95 用几何平均值评价机器性能 几何平均值能忽略样机的影响 几何平均值也是和总用几何平均值评价机器性能 几何平均值能忽略样机的影响 几何平均值也是和总 运行时间成正比的运行时间成正比的 错 几何平均值不是和总运行时间成正比的 算术加权的才是 错误预测转移发生的指令数错误预测转移发生的指令数 比比 错误预测转移发生率错误预测转移发生率 对于评价预测转移更有效对于评价预测转移更有效 错 这个显然吧 100 个错 3 个 和 10000 个错 3 个能一样么 增加寻址方式总能有效地减少指令总数增加寻址方式总能有效地减少指令总数 错 比较 MIPS 和 8086 的就知道寄存器 存储器寻址比 L S 的代码少 但是不是把方式都加上就一定能减少就不一定了 Datapath 的控制可以用微程序的方法来设计 然后最后用的控制可以用微程序的方法来设计 然后最后用 PLA 硬连线实现硬连线实现 对 这个是概念 PLA 和 ROM 作为两个最底层的实现方式是可以被任何的路径到达的 三三 简答简答 什么是什么是 MIPS MIPS 是世界上很流行的一种 RISC 处理器 MIPS 的意思是 无内部互锁流水级的微处理 器 其机制是尽量利用软件办法避免流水线中的数据相关问题 什么是指令系统体系结构什么是指令系统体系结构 ISA 程序员所能看到的系统属性 例如概念性结构和功能特性 既区别于数据流和控制的 组织 也区别于物理实现 它是硬件和软件接口的抽象 什么是软件流水什么是软件流水 对循环进行重构 使得每次迭代执行的指令是属于原循环的不同迭代过程的 由此达 到指令的并行 提高运行效率 什么是局部性原理什么是局部性原理 时间局部性 如果一个信息项正在被访问 那么在近期她很可能还会被再次访问 空间局部性 在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上 是临近的 时钟扭斜对时钟周期和保持时间的影响时钟扭斜对时钟周期和保持时间的影响 根据时钟扭斜与时钟周期 保持时间之间的关系 即 时钟周期时钟周期 Clk to Q 建立时间 最长延迟路径时间 时钟扭斜时钟扭斜 保持时间保持时间 Clk to Q 时间 最短延迟路径时间 时钟扭斜时钟扭斜 可以得知 时钟扭斜增大时 时钟周期增大 保持时间减少 精确中断与非精确中断精确中断与非精确中断 精确中断 精确地保留程序执行到产生意外事件的指令时的机器的状态 非精确中断 系统程序不得不判断在哪里出现了中断 并一起卷回 延迟转移延迟转移 为了解决控制冒险 在发生冒险的转移指令后面加入一条不会发生冒险的指令 使得 转移行为在下一条指令之后发生 延迟装入延迟装入 为了解决数据冒险 在发生冒险的装入指令后面加入一条不会发生冒险的指令 使得 转移行为在下一条指令之后发生 延迟槽延迟槽 为了解决转移时的冒险 装入时的冒险等问题 通过编译加入一条不会发生冒险的指 令 使得转移 装入在下一条指令之后发生 微程序设计微程序设计 一种特殊的实现处理器控制部件的策略 它在寄存器传输操作的级别进行 编程 微体系结构微体系结构 微程序编程人员所看到的硬件的逻辑结构和功能特性 延迟时间片延迟时间片 1 以分支前的指令填充 2 以分支目标指令填充 3 以分支不发生时的下一条指令填充 比较比较 DRAM 与与 SRAM DRAM速度虽慢 但是却价廉 高密 向用户提供大存储系统的较好选择 SRAM速度虽快 但是昂贵 密度也不很高 向用户提供快速访问时间的较好选择 比较超标量与超长指令字比较超标量与超长指令字 超标量是一种流水线技术 超长指令字是一种指令格式 超长指令字需要更多的寄存器 超标量 每一周期可能发射不同数量的指令 从1条到6条 超长指令字 固定数量的指令 编译器确定可开发的并行度 比较单周期和多周期比较单周期和多周期 允许指令的执行占不同的周期数和功能部件可在单个指令执行过程中共享是多周期的 优势 单周期周期长 除了装入指令外 其他指令周期时间都超过了实际所需时间 数据通路数据通路上而言 多周期比单周期有如下不同 1 指令和数据用同一寄存器 2 只有一个ALU 而不是一个ALU和两个加法器 3 每个主要的功能单元都加上了一个或多个寄存器存储输出值以便在后面的时钟周 期中使用 比较超标量与超流水比较超标量与超流水 超标量是通过内置多条流水线来同时执行多个指令 而超流水线是通过细化流水 提高主频 使得在一个机器周期内完成一个甚至多个操 作 比较软件流水与循环展开比较软件流水与循环展开 循环展开是一个循环内做多个循环做的事情 使得流水线能充分得到利用 软件流水是对循环进行重构 使得每次迭代执行的指令是属于原循环的不同迭代过程 的 这样子达到指令的并行 从而提高运行效率 软件流水不用多次灌满和清空流水线 循环展开需要多次灌满和清空流水线 多周期可能的指令执行步骤多周期可能的指令执行步骤 1 取指 2 指令解码和读取寄存器 3 执行指令计算存储地址或完成转移分支 4 访问寄存器或完成R型指令 5 读取存储器 冒险及其解决方法冒险及其解决方法 结构冒险定义 试图以两种不同的方式使用同一资源 解决 1 暂停 气泡2 延迟2 增加资源 控制冒险定义 在判断转移条件之前 就试图决策转移方向 解决 1 暂停 气泡2 延迟3 预测 数据冒险定义 在产生数据之前 就试图使用它们 解决 1 暂停 气泡2 延迟3 前递 旁路 发生异常的原因有哪些发生异常的原因有哪些 1 运算错误 2 I O设备请求 3 用户程序调用操作系统服务 4 使用未定义指令 5 硬件错误 每个段可能出现的中断每个段可能出现的中断 IF 取指页失效 未对准存储器访问 存储保护违例 ID 未定义或非法操作码 EX 算术意外事件 MEM 取数据页失效 未对准存储器访问 存储保护违例 存储器错误 微程序设计的利弊微程序设计的利弊 易于设计易于设计 灵活性灵活性 易于适应组织 定时 工艺技术的变化 在设计周期的后期也能够变化 可以实现功能非常强大的指令系统可以实现功能非常强大的指令系统 仅仅需要增加更多的控制存储器仅仅需要增加更多的控制存储器 通用性通用性 可以在同一机器上实现多种不同的指令系统 可以针对具体应用 对指令系统进行剪裁 兼容性兼容性 多种组成 同一指令系统 实现成本高实现成本高 速度慢速度慢 比较多周期处理器多周期延迟路径比较多周期处理器多周期延迟路径 多周期处理器 用多个时钟周期执行每条指令 多周期延迟路径 在两个存储部件之间的 需要一个以上时钟周期完成的组合逻辑路 径 四四 计算计算 通过通过 6 7 说明说明 booth 算法的过程算法的过程 6 0110 2 7 1001 2 操作操作步骤步骤被乘数被乘数乘积乘积 0初始值01100000 1001 0 10 减去被乘数01101010 1001 01 右移01101101 0100 1 01 加上被乘数01100011 0100 12 右移01100001 1010 0 00 无操作01100001 1010 03 右移01100000 1101 0 10 减去被乘数01101010 1101 04 右移01101101 0110 1 5结果值0110 1101 0110 2 42 10 160M HZ 的机器 的机器 int 指令指令 70 fp 指令指令 30 int 的的 CPI 2 FP 的的 CPI 5 问 问 MIPS 改进编译 改进编译 int 多多 10 fp 少少 20 问 问 MIPS 问性能提高了多少问性能提高了多少 int 的的 CPI 下降下降 20 问性能提高多少 问性能提高多少 die area 的面积加了的面积加了 25 yield 和和 die area 的面积的立方成反比 问成本多多少的面积的立方成反比 问成本多多少 给定给定 cache 的大小 及的大小 及 tag 19 cache index 9 index 2 offset 2 计算计算 block 的大小的大小 cache 块的大小块的大小 关联度 关联度 页大小是页大小是 8K 总内存 总内存 64M TLB 用用 128 项的直接映射 项的直接映射 TLB 里只放物理页的页地址 还里只放物理页的页地址 还 有有 dirty 位和位和 valid 位 问位 问 TLB 每项里有多少位每项里有多少位 画图说明画图说明 CACHE 和和 TLB 是如何并行工作的是如何并行工作的 指令指令 数据分离的两级数据分离的两级 cache 大小大小 块块 相连相连 失效率失效率 响应时间响应时间 一级一级 16k 8 直接映射直接映射 5 1 周期周期 二级二级 256k 32 4 路相联路相联 1 19 周期周期 系统寻址空间系统寻址空间 2 32 问问 两级分别的两级分别的 Index tag digital sel 位数位数 X6 load store 的的 cpi 多少 多少 X4 扩充扩充 mips 指令系统 增加指令系统 增加 lws a b c 用处是用处是 a Mem b c 4 图上给你改好了 就是将图上给你改好了 就是将 Aluout 连回连回 SrcA 同时在同时在 SrcB 上增加了一个上增加了一个 4 的输入 用的输入 用 01 可以可以 选上 选上 写出寄存器传输级语言写出寄存器传输级语言 MEM PC A R b B R c 2 S A B M MEM S R a M PC R rt then R r31 PC 4 PC PC sx im16 00 else PC PC 4 2 1 多周期的多周期的 lw 指令的控制信号指令的控制信号 2 将其改成流水线的数据通路将其改成流水线的数据通路 需要改动什么需要改动什么 一个流水线的数据通路 一共十五个空 流水线上在跑上面的四条指令的指令序列 叫在一个流水线的数据通路 一共十五个空 流水线上在跑上面的四条指令的指令序列 叫在 相应的空上填出当前流水线上应该是啥值相应的空上填出当前流水线上应该是啥值 X15 为支持中断 需要对MIPS ISA增加什么 EPC 32位寄存器 用于保存受影响的指令的地址 协处理器0的寄存器14 Cause 用于纪录产生意外事件原因的寄存器 在MIPS体系结构中这个寄存 器32位 但是其中的一些位目前还没有用途 假设这个寄存器的5到2位编码了 上面介绍的两类可能的意外事件来源 未定义指令 0 和算术溢出 1 协处理 器0的寄存器13 BadVAddr 包括发生存储器访问的存储器地址的寄存器 协处理器0的寄存 器8 Status 中断屏蔽和使能位 协处理器0的寄存器12 控制写入EPC Cause BadVAddr和Status的控制信号 为了能够将意外事件地址写入PC 增加多路选择器 以便增加输入 two 8000 0080hex 需要能够撤销PC PC 4 这是因为我们希望EPC指向产生意外事件的指 令 而不是它的后继指令 PC PC 4 其他总结其他总结 1 计算机系统结构 指令系统体系结构 机器组成 2 计算机的五个主要部件 数据通路 控制器 存储器 输出设备 输出设备 前两者 可合并为 处理器 3 指令系统设计中的基本问题 应该提供那些以及多少操作 多少操作数如何被指明 如何将这些指令编码成一致的指令格式 4 基本的指令系统体系结构种类 累加器 堆栈 通用寄存器 装入 存储 5 指令系统测度 设计时测度 静态测度 动态测度 最佳测度是执行程序的时间 6 部件延迟 内在延迟 相关负载延迟 X 输出负载 7 建立时间 在触发时钟边沿之前 输入必须稳定 8 保持时间 在触发时钟边沿之后 输入必须保持 9 Clock to Q time 在触发时钟边沿时 输出不能立即变化 分为两部分 内在 Clock to Q 时间 负载相关 Clock to Q 时间 10 时钟扭斜的影响 时钟时间 Clock to Q 最长延迟路径 建立时间 时钟扭斜 保持时间 Clock to Q 最短延迟路径 时钟扭斜 否则发生 保持时间违例 11 设计 从需求分析开始 功能需求 性能特征 以组装结束 分解部件 组装部件 采用层次式设计 自顶向下 vs 自底向上 vs 逐步求精 设计过程 分治 产生并测试 逐步求精 阐明可供选择的高级方案 12 Booth 算法 1 依赖于当前和以前的位 进行下述步骤之一 00 a 0 串的中部 不进行任何运算操作 01 b 1 串的结束 将被乘数加到乘积的左半部 10 c 1 串的首部 从乘积的左半部减去被乘数 11 d 1 串的中部 不进行任何运算操作 2 象第三种乘法算法一样 将乘积算术右移 1 位 13 规格化数 1 S 1 M 2 E 127 非规格化数 1 S 0 M 2 126 14 存储层次技术 原理 局部性原理 工作方式 由时间局部性 将最近被访问的信息项放在离处理器较近的地方 由 空间局部性 将包括临近存储字的数据块一起移动到较高层存储中 中 在任何指定 时间 数据只能在相邻的两级之间拷贝 术语 命中 命中率 命中时间 RAM 访问时间 确定命中 失效时间 失效 失效率 失效损失 替换高层存储数据块的时间 将该块交给处 理器的时间 命中时间 N 路组相连 全相联 Cache 容量依次减小 16 写入策略比较 写穿透 需要一个写缓冲器 有可能遇到写缓冲器饱和的现象 写返回 控制复杂 17 防取策略的比较 如果只有在却也是才将页面调入 按需调页 预测未来的访问 在实际使用前 预先装入页面 预取调页 后者减少了页面传输的开销 移出了已经再页帧中的页 不利于缺页率 预测未 来访问很困难 绝大多数系统只实现了按需调页 而没有实现预测 18 组相联 Cache 缺点 N 个比较器与 1 个比较器 在输出数据时 增加了额外的多路选择延迟 在判断命中 失效时候 才可以得到数据 在直接映射 Cache 中 Cache 块在命中 失 效之前就可以得到 19 Cache 和 TLB 访问重叠是指 根据虚拟页号访问 TLB 和 根据 Cache 索引访问 Cache 同 时进行 重叠访问的条件是 Cache 索引所在的区域需要在页内偏移的部分当中 即块内偏移位数 Cache 索引位数 页内偏移位数 当重叠访问的条件不满足时 解决方案一 增加页面大小 增加页内偏移的位数 解决方案二 换为多路组的 Cache 减小 Cache 索引的位数 20 论选择页面大小 a 增大页面大小的原因 i 页表大小与页面大小成反比 可以节省存储器 ii 当 Cache 容量 页面大小时 易于加快 Cache 的命中时间 较大的页面使得 单页 Cache 是可行的 iii 在二级存储与存储器之间传输较大的页 iv TLB 中表项的数量受到时钟周期的限制 因此较大的页可以映射更多的存储 空间 b 减小页面大小的原因 i 不浪费存储 页内的数据必须是连续的 ii 对较小的进程可以加快进程的启动 c 混合方案 多页面大小 21 总线的优缺点 a 优点 i 多功能性 1 易于增加新设备 2 外设可在多个使用相同总线标准的计算机系统之间移动 ii 低成本 可以以多种方式共享使用单一一组线路 b 缺点 i 可能导致通信瓶颈 总线的带宽制约了最大 I O 吞吐率 ii 总线最高速度主要受制于 1 总线的长度 2 总线上设备的数目 3 需要支持多种设备的范围 特别是这些设备具有 时延差异很大 数据 传输率差异很大 22 增加总线带宽 c 独立的与多路复用的地址和数据线 d 增加数据总线宽度 e 成块传输 ch12 单周期处理器 看起来就象 个以 PC 为状态的有穷状态自动机 page 10 没有寄存器来保存下列过程之间的结果 从理论上讲 需要用一个寄存器来保存一个信号值 signal value 如果 1 这个信号在一个时钟周期被计算 而在其他时钟周期还要使用 2 并且 在这个信号被写入状态部件 state element 之前 计算这个信号的功能块的 输入能够变化 多周期延迟路径的利弊 就是不用寄存器的那种方法 Pros 1 节省寄存器 2 在多周期中可以共时 如果 ALU 需要多个周期 只要整个路径的完成小于 3 个周期 就能正常工作 Cons 1 在大项目上不好验证 静态定时分析工具只观测两个存储部件之间的延迟 将报告这个问题为 timing violation 你只好忽视静态定时分析工具 static timing analyzer 的警告 但是 也就可能忽视了真正的 timing violations 但是 也就可能忽视了真正的 timing violations 从实际开发的角度 这种做法是不负责任的 好的设计师总是在周期之间放入寄存器以避免 多周期延迟问题 不要混淆 多周期处理器 Multiple Cycle Processor 用多个时钟周期执行每条指令的处理器 多周期延迟路径 Multiple Cycle Dealy Path 在两个存储部件 storage element 之间的 需要一个以上时钟周期完成的组合逻辑路 径 可能 也值得 建造一个没有多周期延迟路径的多周期处理器 只要只要一个信号是在某 个周期产生 而在之后的另一周期要使用 就用一个寄存器来保存这个信号值 ch13 微程序和微指令 水平编码 垂直编码 有 20 类的指令 编码位数为 32 位的话 水平编码的话就是大家都 32 位 固定位置的那几位用来放对应的属性 但是 有的属性根本用不到 因此用垂直编码压缩指令格式 某类指令只要表示出对 应的属性 这样 有的指令就可以不用 32 位这么多了 ch14 ch15 结构冒险 structural hazards 试图同时以两种不同的方式使用同一资源 例如 多次存储器访问 多次寄存器写 解决方案 多个存储器 暂停 数据冒险 data hazards 在产生数据之前 就试图使用它们 例如 add r1 r2 r3 sub r4 r1 r5 lw r6 0 r7 or r8 r6 r9 解决方案 前递 旁路 暂停 气泡 控制冒险 control hazards 在判定转移条件之前 就试图决策转移方向 例如 条件转移 解决方案 预测 延迟转移 延迟转移是神马 使流水容易实现的策略 指令长度相同 只有少量的指令格式 ld st 结构 Risc 很适合这些要求 回写时 存在这样的竞争 回写的目标与回写的值到达的时间不一样 如果回写值来得快 就会写错了 因此 要让 MemWr RegWr Branch 这三个控制信号都同时钟作个与操作 这样 在时钟 的前半周期 回写的目标有足够多的时间到达 后半周期 回写目标开启 回写的值就可 以正确地作写操作了 延迟转移现象 对于转移指令 因为目标地址要四个周期的时间 为了统一 其实 Ex 和 Mem 做的是同 样的事 得到 PC 的值 而在流水线中 这条指令后的三条指令将被延迟 Ifetch 要发生在 Mem 之后 有一定的调度算法可以