计算机系统结构应用题

宋涛2025年4月7日大约 3 分钟

计算机系统结构应用题考点总结

1.给出映像表和其它条件，问虚页号、位数、主存实地址

页面失效的虚页号
映像表行号从0开始，装入位为0的行
虚地址或实地址对应页号所需的位数
$位数=\log_2 页号数$
根据虚地址计算主存实地址

虚地址	虚页号	页内位移	装入位	实页号	页内位移	实地址
虚地址	(虚地址/页面大小)取整	(虚地址/页面大小)取余	映射表中虚地址对应的装入位	装入位为0，写“页面失效”，否则为映射表中的虚页号对应的实页号	页面失效写“无”，否则与虚页号的段内位移一致	虚地址大于实际主存字数，则取余数，其它情况为虚地址值

2.页面替换算法

主存页数	初始值	地址流
从0开始	是否初始存入值	按照地址流依次填写
...待替换的用*标记
命中率	命中列用H标记

主存页面 = 主存容量/页面大小
虚页地址 = (虚地址/页面大小)取整
命中率 = 命中数/地址流数
先进先出算法（FIFO）：按照先后顺序替换
近期最少使用算法（LRU）：最近没出现的替换
堆栈模拟：最新地址在第1 行，其余地址依次下移

3.页面替换算法-Cache、组相联映像

主存分为区号、组号、组内块号、块内地址，Cache分为组号、组内块号、块内地址
按照组相联映像对应规则，地址流只能由对应Cache组替换

4.Cache和加速比

区号位数 = $\log_2 主存块数/Cache块数$
组号位数 = $\log_2 组数$
块号位数 = $\log_2 容量位数 - (组号 + 块内地址位数)$
块内地址位数 = $\log_2 块大小$
$t_a = H_c \cdot t_c + (1-H_c) \cdot t_m ，其中t_a为缓存等效存取周期，H_c为缓存命中率，t_c为缓存存取周期，t_m为主存存取周期$
$S =\frac {t_m}{t_a}，其中S为加速比，t_m为主存存取周期，t_a为缓存等效存取周期$

5.流水线-延迟禁止表、冲突向量、时空图

延迟禁止表：每条流水线的拍数差去重后，从小到大排列
冲突向量：从右往左（第1位开始），延迟禁止表中的数字是多少，第几位就为1，其余位为0
状态转移图：先对0位右移n位（为0的位号），再与冲突向量进行与运算，得出新向量，若新向量仍存在0位，则仍与冲突向量进行与运算，直至闭环
调度方案：状态转移图中线路能一直循环，则为合理调度
平均延迟：调度方案中的移位数求和/移位次数，对应最小值为最小平均延迟和最佳调度方案
最大吞吐量：1/最小平均延迟
时空图：x轴为时间（ $\Delta t$ ），y轴为流水线数，多个任务的执行开始时间按最佳调度方案依次间隔 $n\Delta t$
时空图吞吐率：任务数/最后完成时间
时空图效率：任务执行时间段/总时间段

6.流水线-时空图、瓶颈改造

瓶颈改造方法：瓶颈段细分法和瓶颈段并联法
瓶颈段细分法：y轴瓶颈段拆分多条流水线，每条流水线依次执行任务
瓶颈段并联法：y轴增加流水线，在瓶颈段的下个任务在后续流水线执行，直至原瓶颈段执行完，下个任务才回归原流水线

7.流水线-向量点击