180分钟 21列 ·问通的难度并不一样，所以建议先浏觉试卷，预算好时问 ●在每页的最后写上自己的名字(5分) 试题11) Part C (试阔12-试14) 分八 (试题27 试题28 试题29-试瑚32) Part H: 试题33》 10分 Part Part I 39 40 总计 180分
计算机系统结构 6.823 期末考试 姓名_________ 开卷考试（可以带讲义，书） 180 分钟 21 页 注意事项： z 问题的难度并不一样，所以建议先浏览试卷，预算好时间 z 在每页的最后写上自己的名字（5 分） 姓名:________ 5 分 Part A: （试题 1 －试题 5） ________ 10 分 Part B: （试题 6 －试题 11） ________ 12 分 Part C: （试题 12 －试题 14） ________ 12 分 Part D: （试题 15－试题 23） ________ 34 分 Part E: （试题 24－试题 26） ________ 18 分 Part F: （试题 27－试题 28） ________16 分 Part G: （试题 29－试题 32） ________ 25 分 Part H: （ 试题 33） ________ 10 分 Part I: （试题 34－试题 38） ________ 28 分 Part H: （试题 39－试题 40） ________ 10 分 总计:__________ 180 分
PartA。高速缓冲存储器(10分) 选择以下陈述的对储，并耳上国。在所有问题里钱设Che的容量确定。 园器品的大小，序低兴客至不个中车 对 对始 对 可限专经数件能可以减少制不令中车 对 对 PtB流水线的构成 的比DLX5的好，为DL1的一个指令只有4个 对 设经入世个本头后快排个冲笑，后面的#本实化用头染人愁米人类西
Part A。 高速缓冲存储器（10 分） 选择以下陈述的对错，并画上圈。 在所有问题里假设 Cache 的容量确定。 问题 1（2 分） 增加 Cache 行大小，降低其容量不命中率。 对 错 问题 2（2 分） Cache 行大小加倍，最多可使冲突不命中率增加 2 倍。 对 错 问题 3（2 分） 把 Cache 的关联度加倍，最多可使冲突不命中率减半。 对 错 问题 4（2 分） 不改变原软件就可以减少强制不命中率。 对 错 问题 5（2 分） 改变 Cache 从 MRU（most recently used）替换方法到 LRU 替换方法，决不会提高不命中率。 对 错 Part B 流水线的构成 Ben 要建立一个四种状态的 DLX 机（DLX4），不同于标准的 5 段流水线机（DLX5）。他想合并 DLX5 的 X （执行）和 M（储存）阶段，从而得到一个统一的 X/M 阶段。为了减少 X/M 阶 段的延时，他把 ALU 和内存平行放置，从而使 DLX4 只能用寄存器间接寻址。假设两个机器都 是全旁通的，而且有转移延迟槽。判断以下陈述是否正确。 问题 6 （2 分） DLX4 的吞吐率比 DLX5 的好，因为 DLX4 的一个指令只有 4 个阶段 对 错 问题 7（2 分） DLX4 没有装载延迟槽（装入指令和其后续指令冲突，后面的指令要使用其装入结果），是因为 X 和 M 阶段被合并了
对 因要生容代西叶，风X有黄手名司光考车毛的可准比风心的大个 对 对 眼数东孕种小 对婚 对 PaC:内存系统(2分
对 错 问题 8（2 分） 当编译同样的代码时，DLX4 的编译器用完寄存器的可能性比 DLX5 的大。 对 错 问题 9（2 分） DLX4 有另外的数据数据冲突，而该冲突 DLX5 没有。 对 错 问题 10（2 分） DLX4 需要较少的旁通硬件。 对 错 问题 11（2 分） DLX4 在装入/存储时缺少偏移寻址方式，会导致 DLX4 性能损失。 对 错 Part C : 虚拟内存系统（12 分） Ben 在设计一个 32 位字节寻址的虚拟内存系统。它有一个 TLB（Translation Lookaside Buffer， 转换后备缓冲器） 和 2 级的分级 PT（Page Tables，页表），却没有 Cache。每一个 PT 在内存 里占一页。PT 根据硬件来调用。在每次页故障和 TLB 更新，访问 TLB 未命中的指令会重新开 始。虚拟的地址包括 20 位的 VPN（virtual page number 虚拟页码）和 12 位的偏移量。下面的图展现了地址转换流程：
Virtual,Address TLB LoOKuP mis Page Table Walk Protection Check memory ∈memory nie permited page Update TLE Protection Fault SEGFAULT 问期2(2分 Bem觉爹TB区城至少应速128KB。最少的TB项是多少？（国出正确的答案） 》不位德义 怎，用入生风T网限灵归 》个B TB查和一个内夺防
问题 12 （2 分） Ben 觉着 TLB 区域至少应该 128KB。最少的 TLB 项是多少？（圈出正确的答案） 1）64 2）32 3）16 4） 8 5） 不能确定 问题 13 （4 分） 在 TLB 查找，内存访问，和页故障中，用户装入指令最好情况下的时间花费是多少？假设没有 保护故障。（圈出正确的答案） 1）一个 TLB 查找 2）一个 TLB 查找和一个内存访问 3）一个内存访问 4） 一个 TLB 查找和两个内存访问 5） 一个 TLB 查找，一个内存访问，和一个页故障 问题 14 （6 分） 在 TLB 查找，内存访问，和页故障中，用户装入指令最坏情况下的时间花费是多少？假设没有 保护故障。一级页表在内存里。（圈出正确的答案）
PtD:真得流水线 Bn正在设计一个深度流木的单发射。按序ISC女理器，它的流水线的前-半是 PCPC Generation F1 ICache Access tction Decode EX Integer Execute 是公水态后处空器知道它正在头行一个予程序道国指个 足要公只被术充后光程多知道一个于看坪范员城建 吸行朵字花序是国计。看装多少洗本成将瑞： 问题19(3分) 好霜子花被一个D,为了发子花序想国头发楼有，为什么一个标室B四不能夜 。这
1）一个 TLB 查找，三个内存访问，和一个页故障 2）两个 TLB 查找，三个内存访问，和两个内存访问 3）三个 TLB 查找，五个内存访问，和两个内存访问 4） 四个 TLB 查找，六个内存访问，和两个内存访问 5） 四个 TLB 查找，十个内存访问，和三个内存访问 Part D : 取得流水线 Ben 正在设计一个深度流水的单发射、按序 RISC 处理器。它的流水线的前一半是： 所有问题里都假设 ISA 的类型 是 DLX/MIPS。没有转移延迟槽和转移预测硬件（指令顺序取， 除非 PC 被稍后的流水段重定向了）。子程序调用使用 JAL/JALR （跳转和链接）。这些指令将 返回地址（PC+4）写入链接寄存器（R31）。子程序返回用 JR r31 指令，而且栈被用来传递参数。 假设 PC 产生（地址）花费一个完整周期，我们不能旁通任何东西到 PC 产生周期的结尾。 问题 15 （2 分） 在什么流水段状态后处理器知道它正在执行一个子程序返回指令？ 问题 17（2 分） 在什么流水段状态后处理器知道一个子程序返回地址？ 问题 18（3 分） 当执行一个子程序返回时，需要多少流水线停滞？ 问题 19（3 分） Louis Reasoner 建议加一个 BTB，为了使子程序返回速度提高。为什么一个标准的 BTB 不能很 好地预测子程序返回？ 问题 20（6 分） Ben 决定在他处理器的流水线上加一个返回栈，以替代 BTB。这个 堆栈记录了前 N 个最近子程序调用的地址，这种栈不需要访问时间。（总是会出现一个返回地 址）。请解释返回堆栈是怎样加速子程序的返回的。描述什么时候，和在哪一个流水段返回地址 压入或弹出栈
同整个流东食。对位于问题2D里的机票三执行以下药代码： A:JALB B JR131 C品2D在 2 RN RF EX 爽2分 李老件短合亮价产衣兰持班的来风物设使生不药西肉的件气以重于在长后 PartE:异常和寄存器重命名(I8分) ADDRRo(R）→AnTR8
问题 21（6 分） 画一个流水线图，对应于问题 20 里的机器里执行以下的代码： A : JAL B . . B : JR r31 确定给出被执行指令的地址。以下是前两个指令。被划去的阶段说明指令在那些循环中被废除 了。 问题 22（4 分） 如果返回地址的预测是错的，那么这是怎样被发现的？处理器会怎么样处理？有多少周期丢失 了（相对于正确的预测）？ 精确的说明你所用的假设。 问题 23（8 分） 描述 Ben 可能会在流水线上添加的除返回栈外的硬件，以提高返回指令的性能，以至于在执行 子程序返回时，只有一个一周期的流水线停滞（假设这个结构用全部周期访问）。 Part E : 异常和寄存器重命名（18 分） 随着 Bentium 处理器中期的成功，Ben Bitdiddle 决定开公司，公司专攻 高端 x86 处理器来和 Intel 竞争。他最后的方案是 Bentium 4，一个超标量乱序处理器，采用寄 存器重命名和推测执行的方法。 Bentium 4 有 8 个结构寄存器（EAX，EBX，ECX，EDX，ESP，EBP，EDI，and ESI）。而且， 处理器提供 8 个 ISA 不可见的内部寄存器 T0--T7，来存放微操作所用的中间值，微操作由微码 引擎产生。微码引擎是译码单元，用来产生 x86 指令的 uops。例如，以下的寄存器-内存 x86 指 令可能被转化成以下类-RISCuops： 所有的 16 个微操作可见的寄存器被寄存器分配表（RAT）重命名为一组物理寄存器（P0-Pn） （讲义 22 有描述）。有一个单独的影子映射结构，记录 RAT 有关在误预测情况下的推测转移。 以下是 Bentium 4 前端的方块图
Note he deo dneteode od (not show diagra 月题24(6分) 个可执行泉略：用最少数 公器整 射构不香妥记承B阳 PartF:转移预测(16分)
问题 24（6 分） 在 Bentium4，如果一个 x86 指令在提交之前产生一个异常，这个机器状态被重新设定成异常指 令开始执行前的精确状态，在异常处理后这个指令重新运行。当发生异常时，Ben 认为，用于 推测转移的影子映射结构可用来恢复一个精确状态。请详细说明一个可执行的策略：用最少数 量的 RAT 瞬象记录，依然能使 Bentium 4 实现精确的异常处理。 问题 25（6 分） Ben 又指出影子映射结构不需要记录 Bentium 4 里所有寄存器的瞬象 从一个异常恢复。请问 Ben 是对的吗？如果是，请指出哪些寄存器状态不需要储存，解释为什么它们不需要，或者解 释为什么所有的寄存器在瞬象里都是需要的。 问题 26（6 分） 假设 Bentium 4 有和 Pentium 4 一样的寄存器重命名机制，正如讲义 22 所描述的。可以使寄存 器重命名工作的、最小数量的 Bentium 4 物理寄存器是多少。解释你的答案。 Part F : 转移预测（16 分）
B试不的动态特移预测器，月以下的高级代码 B托以上的代码转换成下西的汇遥代码。服设N是一个本答大的泰数，没有转移廷运迟槽 a862878出 器嗣 temp2: wt 动态转移预测2：2.bit BH下s 动态转移预测3：2--bit BHTs+1-bit全局历史位 动态转移预测4：2-bit BHTs+2-bit全局历史位 杂得写。个装楼件萨测华法由下国不入同干动布能修行装器，运龙这个2伦的代修 A2tteantpeiciaustec Predict Take Predict-Take 8屵⊙片982 taken taken
Ben 想测试不同的动态转移预测器，用以下的高级代码： for （i = 0; i < N; i++） { if （i % 4 == 0） // % is modulus operator k = k + 1;if （i % 2 == 0）k = k + 2; } Ben 把以上的代码转换成下面的汇编代码。假设 N 是一个非常大的整数，没有转移延迟槽。 Ben 有四个不同的动态转移预测： 动态转移预测 1: 1-bit BHTs （Branch History Table，转移历史表） 动态转移预测 2: 2-bit BHTs 动态转移预测 3: 2-bit BHTs + 1-bit 全局历史位 动态转移预测 4: 2-bit BHTs + 2-bit 全局历史位 Ben 发明了一个 2 位的转移预测算法（如下图示），用于动态转移预测器。注意这个 2 位的转移 预测算法与第十二节课讲得不一样。 问题 27 （4 分） 是否任何转移的预测精确度依赖于动态预测器 2 的 BHT 的最初状态？如果是，请列出是那个 转移
所有司能 受种终价盘个袖气转能轻酒的新带康。如果玩萄装支条做于家新抗态，高写 DBP 2 PartG:迹调度(Trace Scheduling?)(25分) 中、 考庞下列的语言代码(%代表职会： &“x但a898；0 else ￥=v2*v3 根序的控制流围
问题 28 （12 分） 请在下列表各种填入每个动态转移预测器的预测精度。如果预测精度依赖于最初状态，请写下 所有可能的预测精度数，但不用指定最初状态。 Part G : 迹调度（Trace Scheduling？）（25 分） 迹调度一个编译技术，通过消除控制相关，允许转移指令之后的操作上移并和转移指令之前的 操作并行推测执行，来提高指令级的并行度（ILP）。它最先是为了静态调度的 VLIW 机开发的， 但现在是一个通用技术，可用于不同的计算机了。在此我们把它应用一个按序的超标量处理器 中。 考虑下列的 c 语言代码（%代表取余）： 假设 data 是一个均匀分布式的整型变量，在代码执行前设置。 程序的控制流图 决策树
问题29(5分 亮魔是：用过移的季标出大警事个锅于，系左造的块月我行ΛCDG茅轻的 0分墨出频有可能技执行的路径， 闵L父分（这布装起抽 A: 1d B: ”:,5xwm E: 18,4,5iy<-0* 除法器，和系法留有各 PartH:DAXPY向量化(I0分) DA 级话言代， 一个娱性代数程序中的流行的子序。 经器5益品a
一个控制流图和决策树都可以表明可能的通过那些基本块的执行流程。但是控制流图强调了程 序的静态结构，而决策树强调了程序的动态执行。 问题 29 （5 分） 在决策树里，用穿过路径的概率标出每个途径。举个例子，最左边的块用执行 ABCDEG 路径的 全部概率来标示。（提示，你或许想写出案例） 问题 30 （2 分） 在控制流图里，圈出最有可能被执行的路径。 问题 31 （10 分） 以下是 DLX 代码（没有延迟槽）： 这些代码要被一个无转移推测的、按序超标量机执行。假设内存，除法器，和乘法器都有各自 的长延时，不流水的单元可以并行运行。在下一页，用迹调度重写以上代码。只优化最常用的 路径，其他路径能工作就行。不用浪费时间去做其它的最优化。不考虑异常情况（提示：先写 最常用的路径，再加上合适的代码）。 问题 32 （8 分） 假设装入花费 x 个周期，除法花费 y 个周期，乘法则需要 z 个周期。原代码大约需要多少周期 （忽略小常数），新代码在最好情况下需要多少周期？ Part H : DAXPY 向量化 （10 分） 以下是计算 DAXPY（A X[i]+ Y[i]）的高级语言代码，一个线性代数程序中的流行的子程序。 假设 N 是非常大的整数，而且是 32 的倍数，数组 X，Y，S 在内存中不交叠。 给定一个叫 Vectium 的向量机，它是以 VDLX ISA 为基础的。 Vectium 有大量的向量寄存器， 每个向量寄存器有 32 个元素