1. 为什么这门课的课后题值得花时间死磕计算机体系结构这门课在计算机专业里有个很特殊的地位。它不像数据结构那样能立刻写出可运行的代码也不像操作系统那样能直观看到进程调度它讲的是一台机器为什么这样设计——指令怎么译码、流水线怎么排、Cache怎么映射、分支预测怎么兜底。这些东西在纸面上看全是框图和公式但真正理解了你后面看任何一款处理器的架构文档、做任何性能优化脑子里都会有一张清晰的图。国科大胡伟武老师这门课的课后题难度是出了名的不低。原因很简单胡老师本人是做处理器设计的他出的题不是让你背概念而是让你算、让你推、让你在具体参数下判断哪种方案更优。很多同学第一次做的时候会觉得课上听懂了题一上手就懵这非常正常。因为体系结构的题本质上是在约束条件下做工程权衡而不是套公式。我写这篇东西的目的很直接把课后题里反复出现的几类核心题型拆开讲清楚每道题背后到底在考什么、为什么这么算、容易在哪里翻车。不是给你一份抄完就忘的答案而是让你下次遇到同类题能自己推出来。适合正在上这门课、准备考试、或者想补体系结构基础的同学。如果你只是想要一份能对答案的清单那这篇可能不太适合你但如果你想真正搞懂这些题往下看。2. 指令系统与性能度量一切计算的起点2.1 CPI、主频、指令数三者的关系不是背出来的课后题里最先出现、也最容易被轻视的就是性能公式相关的计算。很多人觉得CPU时间 指令数 × CPI × 时钟周期这个公式太简单了结果一到综合题就错。问题出在题目往往不会直接给你CPI而是给你各类指令的占比和各自的周期数让你先算平均CPI。平均CPI的计算逻辑是加权平均平均CPI Σ(某类指令占比 × 该类指令的周期数)这里有个坑我必须提醒占比是按指令条数算的不是按执行时间算的。我见过太多人把时间占比代进去结果整道题全错。判断方法很简单看题目给的是某类指令占总指令数的比例还是某类指令占总执行时间的比例前者直接加权后者要先转换。举个典型场景题目给三类指令A、B、C占比分别是50%、30%、20%CPI分别是1、2、3。那平均CPI就是0.5×1 0.3×2 0.2×3 0.5 0.6 0.6 1.7然后如果主频是2GHz指令总数是10^8条CPU时间就是10^8 × 1.7 / (2×10^9) 0.085秒看起来简单但题目经常在这里加一层让你比较两种编译优化方案。比如方案一把某类指令数量减少了20%但导致另一类指令CPI上升。这时候你要重新算指令总数和平均CPI再比CPU时间。千万不要只比CPI也不要只比指令数性能是三者共同决定的。2.2 Amdahl定律被误用最多的一个工具Amdahl定律几乎每套体系结构题里都会出现但它的误用率高得惊人。定律本身很简单加速比 1 / ((1 - 可优化比例) 可优化比例 / 优化倍数)问题在于很多题目会给你一个某部分被加速了的场景然后问你整体加速比这时候你要先判断这个比例是占谁的。是占总执行时间的比例还是占某段代码的比例如果题目说某功能占总执行时间的40%那直接代入如果说某功能占程序指令数的40%那还要结合CPI换算成时间占比。我个人的经验是做Amdahl定律的题第一步永远是把时间占比标出来。如果题目给的不是时间占比先换算。换算的方法就是分别算出优化前后的时间再求比例。这一步多花两分钟能避免后面全盘皆错。还有一个高频陷阱优化倍数趋于无穷时加速比的上限是 1/(1-可优化比例)。题目经常问无论怎么优化这部分整体最多能快多少答案就是这个上限。比如可优化部分占60%那上限就是 1/0.4 2.5倍。这个结论要能条件反射地写出来。2.3 MIPS和MFLOPS为什么它们不能跨机器比较课后题里经常出现MIPS每秒百万条指令和MFLOPS每秒百万次浮点运算的计算。这两个指标的计算本身不难MIPS 主频 / (平均CPI × 10^6) MFLOPS 浮点运算次数 / (执行时间 × 10^6)但题目真正想考的是它们的局限性。MIPS不能跨指令系统比较因为不同机器的一条指令干的活完全不一样。A机器一条指令可能完成B机器三条指令的工作那A的MIPS低不代表A慢。同理MFLOPS只反映浮点性能对整数密集型程序毫无参考价值。所以当题目让你根据MIPS判断哪台机器更快时你要先看两台机器的指令系统是否相同。如果不同MIPS的比较就是无效的必须回到CPU时间这个绝对指标。这个点在选择题和简答题里反复出现属于送分题但前提是你知道它为什么送分。3. 流水线从理想模型到真实冲突3.1 流水线加速比的理论上限和现实折扣流水线是体系结构课后题的重头戏。理想情况下k级流水线的加速比接近k但这是有前提的指令无限多、每级时间完全均衡、没有任何冲突。课后题往往先让你算理想加速比再引入各种现实因素让你修正。理想加速比的公式是加速比 指令数 × k / (k 指令数 - 1)当指令数远大于k时加速比趋近于k。这个公式要会推因为题目可能给你一个具体的指令数让你算实际加速比。比如k5指令数100加速比就是 500/104 ≈ 4.81而不是5。但真正的难点在于流水线冲突。结构冲突、数据冲突、控制冲突这三类冲突的处理方式是课后题的核心考点。我建议做这类题时先在草稿纸上画流水线时空图把每条指令的每个阶段标出来冲突一目了然。不要试图在脑子里空想体系结构的题画图是最快的。3.2 数据冲突的转发与停顿什么时候必须停数据冲突里RAW写后读是最常见的。题目通常给一段指令序列让你判断需要插入几个停顿周期或者问转发能不能解决。判断逻辑是这样的如果前一条指令的结果在后一条指令需要它之前就已经算出来了那转发就能解决不需要停顿。但如果前一条指令是访存指令结果要到MEM阶段才出来而后一条指令紧接着就要用那即使有转发也要停一个周期。我总结了一个快速判断的口诀看生产者和消费者的阶段差。如果生产者在EX阶段出结果消费者在EX阶段要用差0个阶段需要转发如果生产者在MEM阶段出结果消费者在EX阶段要用差-1个阶段转发来不及必须停一拍。这个判断在题目里经常以给出指令序列画出流水线图并标出停顿的形式出现。我的建议是先把每条指令的五个阶段IF、ID、EX、MEM、WB列成表格然后逐条检查依赖关系该停就停。虽然慢但准确率极高。3.3 控制冲突分支预测的代价计算控制冲突来自分支指令。题目通常给一个分支预测准确率让你算因为预测错误带来的额外周期。计算方法是额外周期 分支指令比例 × 预测错误率 × 预测错误惩罚预测错误惩罚取决于流水线设计通常是分支指令在EX或MEM阶段才能确定方向所以惩罚是流水线深度减去已经完成的阶段数。比如5级流水线分支在EX阶段确定那惩罚就是2个周期IF、ID白做了。这里有个容易忽略的点预测错误惩罚和分支延迟槽是两回事。有些题目会同时涉及要分清楚。延迟槽是编译器填的预测错误是硬件猜错了。两者可以叠加但计算时要分开算。我见过一道题给了一个分支预测准确率95%、分支指令占20%、流水线5级、分支在EX阶段解析的条件问平均每条指令的额外周期。答案是0.2 × 0.05 × 2 0.02周期/指令这个数字很小但题目往往接着问如果改成在ID阶段解析分支惩罚变成多少答案是1个周期额外周期变成0.01。这种对比题考的就是你对流水线阶段的理解。4. Cache与存储层次局部性原理的数学化4.1 直接映射、组相联、全相联的地址划分Cache的地址划分是必考题。给定Cache大小、块大小、相联度让你算标记、组索引、块内偏移各占多少位。这个计算有固定套路块内偏移位数 log2(块大小)组数 Cache总大小 / (块大小 × 相联度)组索引位数 log2(组数)标记位数 地址总位数 - 组索引位数 - 块内偏移位数直接映射就是相联度为1的特例全相联就是组数为1的特例。这三个要能互相转换。题目经常给一个地址让你判断它映射到哪一组、标记是什么。这时候把地址写成二进制按位切分就行。我踩过的坑是块大小和块内偏移的单位。题目可能给块大小是64字节那偏移就是6位但如果给的是64个字而每个字4字节那偏移就是8位。一定要看清单位。这个错误在考试里非常致命因为后面全错。4.2 平均访存时间的分解计算AMAT平均访存时间的计算是Cache题的核心AMAT 命中时间 缺失率 × 缺失代价多级Cache的话逐级展开AMAT L1命中时间 L1缺失率 × (L2命中时间 L2缺失率 × 内存访问时间)这个公式看起来简单但题目经常在里面埋坑。比如给你L1和L2的命中率让你算整体命中率。注意L2的命中率通常是针对L1缺失的访问而言的不是针对所有访问。所以整体命中率 L1命中率 L1缺失率 × L2命中率。还有一类题是让你比较不同Cache配置下的AMAT然后判断哪种更好。这时候要注意增加Cache大小可能降低缺失率但可能增加命中时间。题目往往给一组数据让你权衡。我的经验是把每种配置的AMAT都算出来列成表格对比不要凭感觉选。4.3 替换算法与写策略题目里的隐藏考点LRU、FIFO、随机替换这些算法题目通常给一个访问序列让你模拟Cache的命中情况。这类题没有捷径就是老老实实画表记录每次访问后Cache里的内容。我建议用表格行是访问序列列是各组的块命中的打勾缺失的标出替换了谁。写策略方面写直达和写回的区别经常考。写直达每次写都更新内存写回只在替换时更新。题目会问哪种策略产生的内存写次数更少答案通常是写回因为写回把多次写合并成一次。但写回需要脏位硬件更复杂。这种权衡题答题时要两边都说。还有一个高频考点是写分配和非写分配。写缺失时写分配会把块调入Cache非写分配直接写内存。通常写回配写分配写直达配非写分配。这个搭配不是随便定的背后是局部性原理的考量。题目如果问为什么这样搭配你要能从写回希望后续还能命中这个块和写直达反正要写内存调入Cache没意义两个角度解释。5. 指令级并行与动态调度乱序执行的逻辑5.1 Tomasulo算法的核心寄存器重命名与保留站Tomasulo算法是体系结构里最抽象的一块但课后题绕不开它。它的核心思想是用保留站来缓存操作数用寄存器重命名来消除假依赖WAR和WAW从而实现乱序执行。做Tomasulo的题关键是画好三张表指令状态表、保留站状态表、寄存器状态表。然后按周期推进每个周期检查哪些保留站的操作数就绪了就绪的就可以发射到功能部件执行。我个人的经验是先标出所有指令的依赖关系RAW是真依赖必须等WAR和WAW是假依赖Tomasulo通过重命名消除了。题目经常问哪条指令可以提前执行答案就是那些没有RAW依赖的指令。Tomasulo里还有一个容易混淆的点Load和Store的处理。Load可以在地址就绪后直接访存但Store必须等到数据也就绪。而且Store和Load之间可能有地址冲突需要额外判断。题目如果涉及访存指令要特别小心。5.2 记分牌算法与Tomasulo的对比记分牌算法是Tomasulo的前身它也能乱序执行但不能消除WAR和WAW依赖所以会出现停顿。题目经常让你比较两者在同一个指令序列下的表现。对比的关键在于记分牌在写回阶段要检查WAR在发射阶段要检查WAW所以假依赖会导致停顿。Tomasulo通过重命名把结果写到保留站而不是寄存器等所有读者都读完再写回寄存器从而消除了这些停顿。答题时如果题目问哪种算法性能更好答案通常是Tomasulo但要说明前提在存在大量假依赖的代码里Tomasulo优势明显如果代码本身依赖很少两者差别不大。这种有条件回答比单纯说Tomasulo好要得分高。5.3 分支预测与推测执行题目里的边界动态分支预测如两位饱和计数器和推测执行在课后题里通常以给定分支历史画出预测状态机的形式出现。两位饱和计数器的状态转换是强不跳转00→ 弱不跳转01→ 弱跳转10→ 强跳转11每次分支实际跳转就向11移动不跳转就向00移动。题目给一串T跳转和N不跳转让你模拟预测准确率。这个只要按状态机走就行不难但要细心。推测执行的问题是预测错误时要能回滚。题目可能问推测执行需要哪些硬件支持答案包括重排序缓冲ROB、寄存器重命名、检查点恢复等。这些概念要能串起来不能只答一个。6. 存储一致性与多核容易被忽略的章节6.1 Cache一致性协议MESI的状态转换MESI协议是四状态Modified修改、Exclusive独占、Shared共享、Invalid无效。题目通常给一个多核场景让你跟踪某个地址在各核Cache里的状态变化。状态转换的规则是读命中M→ME→ES→SI→缺失写命中M→ME→MS→M要通知其他核失效I→缺失其他核读M→S要写回E→SS→S其他核写M→I要写回E→IS→I做这类题我建议画一个表格行是各核列是操作序列每次操作后更新状态。虽然繁琐但不会错。题目经常问某次写操作后哪些核的Cache块被失效了答案就是所有共享该块的其他核。6.2 内存一致性模型顺序一致性与弱一致性顺序一致性要求所有处理器看到的访存顺序一致弱一致性允许重排序但需要同步操作。题目经常给一段多线程代码问在顺序一致性和弱一致性下分别可能输出什么结果。这类题的核心是顺序一致性下任何重排序都不允许弱一致性下除非有同步点否则读写可以重排。所以同一段代码弱一致性下可能输出更多种结果。答题时要列出所有可能的交错然后判断哪些在顺序一致性下被禁止。我个人的经验是先列出所有可能的执行顺序然后按一致性模型过滤。顺序一致性过滤掉所有违反程序顺序的交错弱一致性只过滤掉违反同步顺序的交错。这个思路清晰不容易乱。7. 做课后题时我踩过的那些坑第一个坑是单位换算。体系结构的题里KB、MB、GHz、ns、ps混在一起稍不注意就错。我的做法是所有时间统一换算成秒所有容量统一换算成字节所有频率统一换算成Hz算完再转回题目要求的单位。多这一步能避免80%的计算错误。第二个坑是平均值的加权方式。CPI、缺失率、加速比这些平均值几乎都是加权平均但权重是什么要看清。CPI的权重是指令占比缺失率的权重是访问占比加速比的权重是时间占比。搞错权重结果全错。第三个坑是流水线图的画法。很多人画流水线图时把停顿周期画成空行但忘了后续指令也要顺延。正确的画法是遇到停顿时后续所有指令都往后推相应的周期数。这个在纸上画的时候容易漏建议用铅笔方便改。第四个坑是Cache模拟的替换顺序。LRU是替换最久未使用的FIFO是替换最早进入的随机替换没有规律。题目如果没明确说默认是LRU。但有些题会故意考FIFO和LRU的区别给一个访问序列让两种算法结果不同。这时候要严格按算法定义走不能凭直觉。第五个坑是Tomasulo的写回时机。Tomasulo里指令在功能部件执行完后结果先写到保留站等所有需要这个结果的指令都读走了才写回寄存器。这个等所有读者读完的条件经常被忽略导致状态表更新错误。记住写回不是执行完就写而是要等CDB广播后确认没有其他保留站在等这个结果。8. 怎么把这些题变成自己的东西课后题做完一遍如果不复盘基本等于白做。我的方法是每做完一道综合题合上答案用一张白纸把解题思路重新写一遍重点写为什么第一步要这么做如果题目改一个条件哪里会变。这个过程很痛苦但效果极好。另外体系结构的题有个特点同一类题会反复出现但参数不同。比如流水线冲突这次是5级下次是7级这次是RAW下次是WAR。如果你能把一类题的通用解法抽象出来后面遇到就只是代数字。我建议每类题整理一个解题模板写清楚步骤和判断条件考前只看模板。最后说一个心态问题。这门课的课后题第一遍做的时候错一半很正常不要慌。胡老师的题本来就难错题恰恰暴露了你的知识盲区。把错题标记出来过一周再做一遍如果还能做对那才是真会了。体系结构这东西急不来但一旦打通后面学什么处理器、什么并行计算都会顺很多。