跳转到内容

03、文字答案与解析

本文件是对 01、题目版.md 的文字答案补充。PPT 原答案截图仍保留在 02、答案版.md,这里把能从题库文本和清晰截图核对出来的结果写成可直接复习的计算过程。

有些课堂录屏页被底部进度条、弹窗或右侧界面遮住,本文件对这类题优先给出通用求解步骤和能确定的结论;需要看图形细节的题,仍建议配合原截图一起看。

01、定点小数变形补码加法:X+Y,判断溢出

Section titled “01、定点小数变形补码加法:X+Y,判断溢出”

题目:数值位 5 位,X=0.10001X=-0.10001Y=0.11110Y=-0.11110,用变形补码计算 X+YX+Y

答案:

[X]=11.01111,[Y]=11.00010[X]_补=11.01111,\qquad [Y]_补=11.00010 [X]+[Y]=11.01111+11.00010=10.10001[X]_补+[Y]_补=11.01111+11.00010=10.10001

双符号位为 10,表示负溢出,所以:

X+Y 下溢,也叫负溢X+Y\text{ 下溢,也叫负溢}

注意:变形补码用双符号位,00 表示正数无溢出,11 表示负数无溢出,01 表示上溢,10 表示下溢。

02、定点小数变形补码加法:一正一负相加

Section titled “02、定点小数变形补码加法:一正一负相加”

题目:X=0.11111X=-0.11111Y=0.11001Y=-0.11001,用变形补码计算 XYX-Y

答案:

[X]=11.00001,[Y]=00.11001[X]_补=11.00001,\qquad [-Y]_补=00.11001 [XY]=[X]+[Y]=11.00001+00.11001=11.11010[X-Y]_补=[X]_补+[-Y]_补=11.00001+00.11001=11.11010

双符号位为 11,无溢出。结果是负数,求真值:

XY=0.00110X-Y=-0.00110

03、定点小数变形补码:求补码并计算 X+Y、X-Y

Section titled “03、定点小数变形补码:求补码并计算 X+Y、X-Y”

题目:X=+33/64X=+33/64Y=61/64Y=-61/64,数值位 6 位。

先化为二进制:

X=+0.100001,Y=0.111101X=+0.100001,\qquad Y=-0.111101

所以:

[X]=00.100001[X]_补=00.100001 [Y]=11.000011[Y]_补=11.000011 [Y]=00.111101[-Y]_补=00.111101

计算 X+YX+Y

[X]+[Y]=00.100001+11.000011=11.100100[X]_补+[Y]_补=00.100001+11.000011=11.100100

双符号位为 11,无溢出:

X+Y=0.011100X+Y=-0.011100

计算 XYX-Y

[X]+[Y]=00.100001+00.111101=01.011110[X]_补+[-Y]_补=00.100001+00.111101=01.011110

双符号位为 01,表示上溢,也叫正溢。

04、阶码/尾数均用补码的浮点加法

Section titled “04、阶码/尾数均用补码的浮点加法”

这一题的关键步骤固定:对阶、尾数相加、规格化、舍入、溢出判断。

若题面是课堂常见的 X=+17.5X=+17.5Y=9Y=-9,阶码 5 位、尾数 8 位且均用补码,截去法舍入,则:

X=+0.100011×2101X=+0.100011\times 2^{101} Y=0.100100×2100Y=-0.100100\times 2^{100}

浮点表示为:

[X]=00101, 00.100011[X]_浮=00101,\ 00.100011 [Y]=00100, 11.011100[Y]_浮=00100,\ 11.011100

对阶:

ΔE=EXEY=00101+11100=00001\Delta E=E_X-E_Y=00101+11100=00001

所以 YY 的阶码小,尾数右移 1 位,阶码加 1:

[Y]=00101, 11.101110[Y]_浮=00101,\ 11.101110

尾数相加:

00.100011+11.101110=00.01000100.100011+11.101110=00.010001

左规格化:

[X+Y]=00100, 00.100010[X+Y]_浮=00100,\ 00.100010

截去法舍入后不变,真值为:

X+Y=+0.100010×2100=+1000.102=+8.5X+Y=+0.100010\times 2^{100}=+1000.10_2=+8.5

05、浮点数加法:阶码与尾数补码格式

Section titled “05、浮点数加法:阶码与尾数补码格式”

这组题和第 04 题同型。标准答题模板如下:

  1. 先把两个数写成规格化二进制:X=MX×2EXX=M_X\times 2^{E_X}Y=MY×2EYY=M_Y\times 2^{E_Y}
  2. 阶码、尾数分别写成补码。
  3. ΔE=EXEY\Delta E=E_X-E_Y
  4. 小阶向大阶对齐,尾数右移。
  5. 尾数相加。
  6. 若尾数不是规格化形式,则左规或右规。
  7. 按题目要求舍入,最后检查阶码是否溢出。

若仍为 X=+17.5X=+17.5Y=9Y=-9 的版本,最终答案同第 04 题:

[X+Y]=00100, 00.100010[X+Y]_浮=00100,\ 00.100010 X+Y=+1000.12=+8.5X+Y=+1000.1_2=+8.5

题库中同类题:x=13x=-13y=+5y=+5,数值位均为 4 位,用原码一位乘法。

原码:

[x]=1,1101,[y]=0,0101[x]_原=1,1101,\qquad [y]_原=0,0101

符号位:

xfyf=10=1x_f\oplus y_f=1\oplus 0=1

只对数值位相乘:

11012×01012=0100000121101_2\times 0101_2=01000001_2

所以:

[x×y]=1,01000001[x\times y]_原=1,01000001 x×y=10000012=65x\times y=-1000001_2=-65

做这类题时,符号单独处理,数值位按无符号乘法处理。

这类题答案容易被 PPT 底部挡住,考试更可能考“写过程”而不是只填结果。答题步骤如下:

  1. 确定商的符号:
qf=xfyfq_f=x_f\oplus y_f
  1. 对被除数和除数取绝对值,只用数值位做除法。
  2. 每一步做“左移、试减、判断余数符号、上商”。
  3. 若采用恢复余数法:余数为负则恢复,即加回除数。
  4. 若采用不恢复余数法:余数为负则下一步加除数,余数为正则下一步减除数。
  5. 最后把商加上符号位,余数符号一般与被除数相同。

如果题目要求写“阵列除法器”过程,核心就是把每一步的部分余数、加/减除数、上商位写清楚。

08、主存芯片扩展:位扩展、字扩展与容量计算

Section titled “08、主存芯片扩展:位扩展、字扩展与容量计算”

常见题型:CPU 地址线、数据线给定,ROM/RAM 芯片容量给定,求地址范围和芯片数量。

答题模板:

  1. 芯片容量为 2k×b2^k\times b,则片内地址线用 kk 根。
  2. CPU 数据总线宽度为 BB 位,芯片数据宽度为 bb 位,则位扩展片数为:
Bb\frac{B}{b}
  1. 目标容量为 CC,单组扩展后的容量为 2k×B2^k\times B,则字扩展组数为:
C2k×B\frac{C}{2^k\times B}
  1. 总芯片数:
位扩展片数×字扩展组数\text{位扩展片数}\times \text{字扩展组数}
  1. 地址范围:若首地址为 AA,容量为 CC 字节,则末地址为:
A+C1A+C-1

题库中类似答案:ROM 地址范围 000000H~07FFFFH,RAM1 地址范围 280000H~2FFFFFH,RAM2 地址范围 300000H~37FFFFH

09、顺序存储器与交叉存储器带宽计算

Section titled “09、顺序存储器与交叉存储器带宽计算”

设连续读出 nn 个字,每字 ww 位,存储周期 TT,总线传送周期 τ\tau

读出的信息量:

q=nwq=nw

顺序存储器时间:

t=nTt_{顺}=nT

交叉存储器时间:

t=T+(n1)τt_{交}=T+(n-1)\tau

带宽:

W=qtW=\frac{q}{t}

题库例:n=32n=32w=64w=64T=200nsT=200nsτ=25ns\tau=25ns

q=32×64=2048bq=32\times 64=2048b t=32×200=6400nst_{顺}=32\times 200=6400ns t=200+31×25=975nst_{交}=200+31\times 25=975ns W=320Mb/sW_{顺}=320Mb/s W2100.5Mb/sW_{交}\approx 2100.5Mb/s

命中率:

h=NcNc+Nmh=\frac{N_c}{N_c+N_m}

平均访问时间常用:

ta=htc+(1h)tmt_a=h\,t_c+(1-h)t_m

若题目把主存访问看成“不命中时先访问 Cache 再访问主存”,也可能写成:

ta=tc+(1h)tmt_a=t_c+(1-h)t_m

按题库例:主存从 0 到 199 号单元读 200 个字,重复 5 次,块长 8 字。第一次访问有 25 个块第一次不命中,其余命中:

Nhit,1=20025=175N_{hit,1}=200-25=175

后 4 轮全部命中:

Nhit,2=4×200=800N_{hit,2}=4\times 200=800

总访问次数为 10001000,所以:

h=175+8001000=97.5%h=\frac{175+800}{1000}=97.5\%

11、Cache 直接映射:块号、标记和字块内地址

Section titled “11、Cache 直接映射:块号、标记和字块内地址”

直接映射地址格式:

主存地址 = 标记 tag + Cache 行号 + 块内地址

计算步骤:

  1. 块大小为 2w2^w 字节或字,则块内地址 ww 位。
  2. Cache 共有 2r2^r 行,则行号 rr 位。
  3. 主存地址总位数为 mm,则 tag 位数:
t=mrwt=m-r-w

若主存容量为 16MB16MB,Cache 为 64KB64KB,块大小 1616 字,每字 3232 位,按字节编址:

16×4B=64B=26B16\text{字}\times 4B=64B=2^6B

块内地址 66 位。Cache 行数:

64KB64B=1024=210\frac{64KB}{64B}=1024=2^{10}

行号 1010 位。主存 16MB=224B16MB=2^{24}B,所以 tag 为:

24106=824-10-6=8\text{位}

做命中判断时,用三步:

  1. 把主存地址拆成 tag + 行号 + 块内地址
  2. 用行号找到 Cache 行。
  3. 比较该行保存的 tag 是否等于当前地址 tag;相等命中,不等不命中。

若是直接映射:

Cache行号=主存块号modCache行数Cache行号=主存块号 \bmod Cache行数

若是组相联:

Cache组号=主存块号modCache组数Cache组号=主存块号 \bmod Cache组数

13、直接相联 Cache:主存地址划分、映射与命中率

Section titled “13、直接相联 Cache:主存地址划分、映射与命中率”

题库常考版本:机器字长 32 位,主存 4MB,Cache 数据容量 8KB,块长 16 字,直接相联,按字节编址。

主存地址位数:

4MB=222B4MB=2^{22}B

块大小:

16×4B=64B=26B16\text{字}\times 4B=64B=2^6B

块内偏移 66 位。

Cache 行数:

8KB64B=128=27\frac{8KB}{64B}=128=2^7

行号 77 位。

tag 位数:

2276=922-7-6=9

所以地址格式为:

tag 9位 | 行号 7位 | 块内偏移 6位

若 CPU 顺序访问 0,1,2,,1990,1,2,\ldots,199 号字并重复 5 次,块长 16 字。第一次访问 200 字涉及:

20016=13\left\lceil \frac{200}{16}\right\rceil=13\text{块}

第一次命中:

20013=187200-13=187

后 4 次全命中 800800 次,总命中:

187+800=987187+800=987

命中率:

h=9871000=98.7%h=\frac{987}{1000}=98.7\%

tc=10nst_c=10nstm=50nst_m=50ns,按常用并行式:

ta=htc+(1h)tm=0.987×10+0.013×50=10.52nst_a=h t_c+(1-h)t_m=0.987\times 10+0.013\times 50=10.52ns

14、Cache 映射表:tag/cache 行/字块字段判断

Section titled “14、Cache 映射表:tag/cache 行/字块字段判断”

这一组是第 13 题的延伸。直接映射时抓住一句话:

同一个 Cache 行可能对应多个主存块,靠 tag 区分当前装的是哪一块。

地址拆分后:

主存块号=主存地址块大小主存块号=\left\lfloor \frac{主存地址}{块大小}\right\rfloor Cache行号=主存块号modCache行数Cache行号=主存块号\bmod Cache行数 tag=主存块号Cache行数tag=\left\lfloor \frac{主存块号}{Cache行数}\right\rfloor

如果题目给出 Cache 行表,判断命中时只需要比较行号对应项里的 tag。

15、CPU、Cache、SRAM/DRAM 与访问次数判断

Section titled “15、CPU、Cache、SRAM/DRAM 与访问次数判断”

概念答案:

  1. CPU 访问 Cache,命中时不访问主存。
  2. Cache 未命中时,需要访问主存,把主存块调入 Cache。
  3. SRAM 常用于 Cache,速度快、成本高、集成度低。
  4. DRAM 常用于主存,容量大、成本低,但需要刷新。
  5. Cache 容量通常远小于主存,但速度接近 CPU。

如果题目问“CPU 访问一个字是否一定访问主存”,答案是否定的:Cache 命中时只访问 Cache。

16、指令格式:二地址、一地址、零地址指令容量

Section titled “16、指令格式:二地址、一地址、零地址指令容量”

题库例:机器字长 16 位,地址码 6 位;二地址指令 14 条,一地址指令 125 条。

二地址指令格式:

OP 4位 | A1 6位 | A2 6位

4 位 OP 共 1616 种,已用 1414 种,剩余 22 种可扩展为一地址指令。

一地址指令最多编码空间:

2×26=1282\times 2^6=128

已用 125 条,剩余:

128125=3128-125=3

这 3 个一地址扩展码还可扩展成零地址指令:

3×26=1923\times 2^6=192

所以:

零地址指令最多192零地址指令最多192条

整个指令系统最多:

14+125+192=33114+125+192=331条

若一地址指令要求 248 条,需要二地址剩余扩展码:

24826=4\left\lceil \frac{248}{2^6}\right\rceil=4

二地址指令最多:

164=1216-4=12条

17、扩展操作码:二地址/一地址/零地址格式设计

Section titled “17、扩展操作码:二地址/一地址/零地址格式设计”

答题方法和第 16 题一样。口诀:

短格式没用完的操作码,拿去作为长格式的前缀。

若地址字段每个 4 位,三地址/二地址/一地址/零地址操作码长度分别为:

4 - 8 - 12 - 16

例如二地址 45 条,零地址 7 条:

二地址需要扩展标志:

4524=3\left\lceil \frac{45}{2^4}\right\rceil=3

三地址最多:

243=132^4-3=13条

二地址留给一地址的空间:

3×2445=33\times 2^4-45=3

零地址需要 1 个一地址扩展码,所以一地址最多:

3×241=473\times 2^4-1=47条

18、变长操作码条件下的指令条数分析

Section titled “18、变长操作码条件下的指令条数分析”

核心是“逐级借位”。如果短操作码剩余 rr 个编码,每向下一类地址数少一个,就会多出一个地址字段作为扩展位。

通用公式:

下一类最大条数=r×2地址字段位数下一类最大条数=r\times 2^{地址字段位数}

若下一类已占用 nn 条,则再下一类可用扩展码数:

r×2地址字段位数nr\times 2^{地址字段位数}-n

再乘一次 2地址字段位数2^{地址字段位数},就是再下一类最多条数。

常见寻址方式答案模板:

寻址方式有效地址/操作数
立即寻址操作数就是指令中的立即数
直接寻址EA=AEA=A
间接寻址EA=(A)EA=(A)
寄存器寻址操作数为 (R)(R)
寄存器间接寻址EA=(R)EA=(R)
变址寻址EA=(RX)+AEA=(RX)+A
基址寻址EA=(RB)+AEA=(RB)+A
相对寻址EA=(PC)+AEA=(PC)+A

题库例:

寄存器 R=4000HR=4000HPC=7000HPC=7000HRX=2500HRX=2500HRB=3500HRB=3500H。若存储器表对应:

  • 寄存器寻址:S=4000HS=4000H
  • 寄存器间接寻址:EA=(R)=4000HEA=(R)=4000HS=(4000H)=6600HS=(4000H)=6600H
  • 直接寻址 A=5000HA=5000HS=(5000H)=2021HS=(5000H)=2021H
  • 基址寻址 A=500HA=500HEA=3500H+500H=3A00HEA=3500H+500H=3A00HS=(3A00H)=9000HS=(3A00H)=9000H
  • 间接寻址 A=1000HA=1000HEA=(1000H)=3000HEA=(1000H)=3000HS=(3000H)=A210HS=(3000H)=A210H

相对寻址:

EA=(PC)+AEA=(PC)+A

注意这里的 PCPC 通常是“取完当前指令之后的 PC”。

题库例:当前 PC=4000HPC=4000H,若指令中寻址字段对应相对寻址,位移 D=60HD=60H

EA=4000H+0060H=4060HEA=4000H+0060H=4060H

若位移字段是补码负数,例如 D=E0HD=E0H,按 8 位补码是 20H-20H

EA=RX+D=2308H+FFE0H=22E8HEA=RX+D=2308H+FFE0H=22E8H

考试里最常见的坑:转移指令取指时 PC 已经自动加到下一条指令地址,不能用旧 PC。

21、微指令字段分配与控制存储器容量

Section titled “21、微指令字段分配与控制存储器容量”

题库例:微指令字长 32 位,下址字段法;A、B、C 三组采用编码表示法,D 组直接表示法;下址字段 7 位,测试字段 5 位。

控制存储器最大容量:

32×27=4096=4K32\times 2^7=4096\text{位}=4K\text{位}

最多微指令条数:

27=1282^7=128条

一条微指令中最多同时出现的微命令数:

1+1+1+8=111+1+1+8=11个

最多表示微命令种数:

31+7+15+8=6131+7+15+8=61种

测试字段 5 位若编码表示,通常保留一个“不测试”状态:

251=31种测试2^5-1=31种测试

22、指令执行流程:微操作与控制信号填写

Section titled “22、指令执行流程:微操作与控制信号填写”

sw rt, imm(rs) 为例:

M[R[rs]+SignExt(imm)]R[rt]M[R[rs]+\text{SignExt}(imm)]\leftarrow R[rt]

取指周期通常为:

PC -> AR; PC -> X
X + 4 -> Z
Z -> PC; M[AR] -> DR
DR -> IR

计算周期:

R[rs] -> X
IR(I) + X -> Z
Z -> AR

执行周期:

R[rt] -> DR
DR -> M[AR]

对应填空常见答案:

① R[rs] -> X
② IR(I)out, ADD
③ Z -> AR
④ Rout, Rs/Rt, DRin
⑤ DR -> M[AR]

23、流水线时空图、吞吐率、加速比与效率

Section titled “23、流水线时空图、吞吐率、加速比与效率”

流水线基本公式:

TP=nTkTP=\frac{n}{T_k} Sp=顺序执行时间流水线执行时间S_p=\frac{顺序执行时间}{流水线执行时间} η=顺序执行时间功能段数×流水线执行时间\eta=\frac{顺序执行时间}{功能段数\times 流水线执行时间}

kk 段流水线,每段时间为 Δt\Delta t,完成 nn 个任务且无冲突:

Tk=(k+n1)ΔtT_k=(k+n-1)\Delta t

则:

TP=n(k+n1)ΔtTP=\frac{n}{(k+n-1)\Delta t} Sp=nkΔt(k+n1)Δt=nkk+n1S_p=\frac{nk\Delta t}{(k+n-1)\Delta t}=\frac{nk}{k+n-1} η=nk+n1\eta=\frac{n}{k+n-1}

24、多功能流水线调度与时间计算

Section titled “24、多功能流水线调度与时间计算”

多功能流水线题先做两件事:

  1. 根据题目画出每个任务经过的功能段序列。
  2. 找出相邻任务之间允许的最小启动间隔。

如果题目给出预约表,则从同一功能段两次使用的时间差得到禁止集合 FF;不在 FF 里的启动间隔才允许。

总时间通常写成:

T=首个任务完成时间+启动间隔+最后排空时间T=首个任务完成时间+\sum 启动间隔+最后排空时间

若 PPT 中给出最终最短调度表,应优先按表中启动间隔计算。

25、非线性流水线:预约表、禁止表、初始冲突向量

Section titled “25、非线性流水线:预约表、禁止表、初始冲突向量”

课堂重点题。已知预约表可推出:

F={2,3,5}F=\{2,3,5\}

初始冲突向量按 C=(c5c4c3c2c1)C=(c_5c_4c_3c_2c_1) 写:

C=10110C=10110

最小启动循环:

(1,6)(1,6)

最小平均间隔:

1+62=3.5\frac{1+6}{2}=3.5

若时钟周期 τ=20ns\tau=20ns,插入非计算延迟单元后最大吞吐率:

TPmax=13τ=160ns1.67×107任务/sTP_{max}=\frac{1}{3\tau}=\frac{1}{60ns}\approx 1.67\times 10^7\text{任务/s}

另一题若禁止表为:

F={1,3,4,8}F=\{1,3,4,8\}

初始冲突向量:

C=10001101C=10001101

最小平均延迟:

3.5时钟周期3.5\text{时钟周期}

最佳调度方案:

(2,5)(2,5)

输入 6 个任务时实际吞吐率:

TP=625时钟周期TP=\frac{6}{25\text{时钟周期}}

26、线性流水线调度表与最短时间

Section titled “26、线性流水线调度表与最短时间”

线性流水线如果每个任务都经过同样的功能段,且没有资源冲突,直接套:

T=(k+n1)ΔtT=(k+n-1)\Delta t

如果题面给出了调度表,要按表中任务实际占用的拍数数格子。实际吞吐率:

TP=完成任务数总拍数TP=\frac{完成任务数}{总拍数}

加速比:

Sp=不用流水线的总拍数流水线调度后的总拍数S_p=\frac{不用流水线的总拍数}{流水线调度后的总拍数}

效率:

η=不用流水线的总拍数功能段数×流水线总拍数\eta=\frac{不用流水线的总拍数}{功能段数\times 流水线总拍数}

27、并行/向量处理基础选择与判断

Section titled “27、并行/向量处理基础选择与判断”

常见互连函数答案:

若有 32 个处理器,编号 0 到 31,第 11 号处理器二进制为:

11=01011211=01011_2

则:

  • Cube3(01011)=00011=3Cube_3(01011)=00011=3
  • PM2+3(11)=11+23=19PM2_{+3}(11)=11+2^3=19
  • PM24(11)=1124mod32=27PM2_{-4}(11)=11-2^4\bmod 32=27
  • Shuffle(01011)=10110=22Shuffle(01011)=10110=22
  • Butterfly(01011)=11010=26Butterfly(01011)=11010=26
  • Shuffle(Shuffle(01011))=01101=13Shuffle(Shuffle(01011))=01101=13
  • Shuffle(Cube0(PM21(11)))=16Shuffle(Cube_0(PM2_{-1}(11)))=16

若 256 个 PE,PE197 执行完全混洗 10 次:

197=110001012197=11000101_2

8 位编号循环左移 10mod8=210\bmod 8=2 次:

1100010100010111=2311000101\rightarrow 00010111=23

答案:数据送往 PE23。

题库例:计算

S=A1B1+A2B2++A64B64S=A_1B_1+A_2B_2+\cdots+A_{64}B_{64}

单处理机串行,乘法 4 拍,加法 2 拍:

T=64×4+63×2=382T_{串}=64\times 4+63\times 2=382

16 个 PE 单向环 SIMD,最小时间为:

TSIMD=45T_{SIMD}=45

这一题考试如果只问结论,写 38245;如果问过程,说明每个 PE 先完成本地 4 组乘加,再通过环形网络归约。

29、串行、SIMD、MIMD 计算表达式的时间比较

Section titled “29、串行、SIMD、MIMD 计算表达式的时间比较”

题库常见版本:

S=A1B1+A2B2++A64B64S=A_1B_1+A_2B_2+\cdots+A_{64}B_{64}

乘法 4 拍,加法 2 拍,PE 间传送 1 拍。

通用 PE 串行 SISD:

T=64×4+63×2=382T=64\times 4+63\times 2=382拍

具有一个乘法器和一个加法器的多功能并行流水 SISD:

T=64×4+2=258T=64\times 4+2=258拍

16 个 PE 的 SIMD:

T=38T=38拍

16 个处理机的 MIMD:

T=34T=34拍

记忆:并行度越高、通信越少,时间越短;但 SIMD/MIMD 不是只看处理器数,还要加上归约通信时间。

30、SIMD 系统:PE 数量、环传送和表达式计算

Section titled “30、SIMD 系统:PE 数量、环传送和表达式计算”

若题目为 8 个 PE 双向环,计算 32 项点积,乘法 4 拍,加法 2 拍,传送 1 拍:

SISD:

TSISD=32×4+31×2=190T_{SISD}=32\times 4+31\times 2=190

SIMD:

TSIMD=32T_{SIMD}=32

加速比:

Sp=190325.94S_p=\frac{190}{32}\approx 5.94

若题目改为 16 个 PE、64 项点积,答案见第 28 题:

TSISD=382,TSIMD=45T_{SISD}=382,\qquad T_{SIMD}=45

31、互连网络与 SIMD/MIMD 计算复杂度

Section titled “31、互连网络与 SIMD/MIMD 计算复杂度”

Omega 网络常用公式:

若用 k×kk\times k 交换开关构造 NN 输入 Omega 网络:

级数:

logkN\log_k N

每级开关数:

Nk\frac{N}{k}

总开关数:

NklogkN\frac{N}{k}\log_k N

例:8×88\times 8 交叉开关构造 512512 输入 Omega 网络:

log8512=3\log_8 512=3\text{级} 5128×3=192个开关\frac{512}{8}\times 3=192\text{个开关}

若扩展到 40964096 个结点:

40968×log84096=512×4=2048\frac{4096}{8}\times \log_8 4096=512\times 4=2048

需要增加:

2048192=18562048-192=1856

32、SIMD 计算表达式:集中/分布数据下的时间

Section titled “32、SIMD 计算表达式:集中/分布数据下的时间”

这类题按三段算:

  1. 本地乘法时间。
  2. 本地加法归约时间。
  3. PE 间传送与全局归约时间。

如果有 nn 项、NN 个 PE,每个 PE 平均处理 n/Nn/N 项,则每个 PE 本地时间近似为:

nNtmul+(nN1)tadd\frac{n}{N}t_{mul}+\left(\frac{n}{N}-1\right)t_{add}

全局归约如果用树形归约,需要:

log2N\log_2 N

轮,每轮通常包括传送和加法。

33、分布存储 SIMD 系统的通信与计算时间

Section titled “33、分布存储 SIMD 系统的通信与计算时间”

分布存储 SIMD 的答题关键是区分:

本地计算时间 + 数据迁移时间 + 全局归约时间

如果数据已经在对应 PE 本地,则不需要最开始的装载/分发通信;如果数据在某个 PE 或主存集中存放,就要先算数据分发时间。

环形网络传送时,距离为 dd 的数据传送需要 dd 个传送单位;若多个传送可并行,要取最长路径对应的时间,而不是把所有路径简单相加。

34、BSP 与 PRAM 模型下点积计算时间和加速比

Section titled “34、BSP 与 PRAM 模型下点积计算时间和加速比”

PPT 例:16 个处理器,计算

S=i=1256AiBiS=\sum_{i=1}^{256} A_iB_i

每次加法 100ns,每次乘法 200ns,h=1h=1g=500nsg=500nsl=800nsl=800ns

串行时间:

T0256×(200+100)=76800nsT_0\approx 256\times(200+100)=76800ns

BSP 计算采用折叠算法,题库答案:

TBSP=10400nsT_{BSP}=10400ns

加速比:

Sp=256×(200+100)104007.38S_p=\frac{256\times(200+100)}{10400}\approx 7.38

理想 PRAM 不计通信开销,只保留并行计算和同步归约,题库答案:

TPRAM=5200nsT_{PRAM}=5200ns

加速比:

Sp=256×(200+100)520014.77S_p=\frac{256\times(200+100)}{5200}\approx 14.77

考试时一定先看题面给的 n,h,g,ln,h,g,l,不要把不同版本的数值混用。

35、Cache 一致性:写无效/写更新协议状态变化

Section titled “35、Cache 一致性:写无效/写更新协议状态变化”

写无效协议:

  • 读缺失:从主存或其他 Cache 取块,状态变共享。
  • 写命中且本块共享:发无效信号,使其他 Cache 副本无效,本地变修改/独占。
  • 写缺失:发读独占或无效请求,取得块后写入,本地变修改。
  • 其他处理器写同一块:本地共享副本被置无效。

写更新协议:

  • 写命中共享块:不让其他副本失效,而是把新值广播给其他 Cache。
  • 其他 Cache 收到更新后,仍保持有效,但数据改成新值。
  • 优点是读共享数据时命中率高;缺点是写频繁时总线流量大。

做题步骤:

  1. 先列每个 Cache 中该块的初始状态。
  2. 遇到读:看本地是否有有效副本。
  3. 遇到写:写无效就让别人无效,写更新就让别人同步新值。
  4. 每一步后更新状态表。

36、CPU 数据通路:指令执行流程与控制信号

Section titled “36、CPU 数据通路:指令执行流程与控制信号”

add rt, rs, imm 为例:

R[rt]R[rs]+SignExt(imm)R[rt]\leftarrow R[rs]+\text{SignExt}(imm)

取指周期:

T1: PC -> AR; PC -> X
T2: X + 4 -> Z
T3: Z -> PC; M[AR] -> DR
T4: DR -> IR

计算/执行周期:

T5: R[rs] -> X
T6: IR(I) + X -> Z
T7: Z -> R[rt]

若是 subi rt, rs, imm

R[rt]R[rs]SignExt(imm)R[rt]\leftarrow R[rs]-\text{SignExt}(imm)

只需要在 ALU 控制信号上把 ADD 改为 SUB

常见控制信号:

R[rs] -> X: Rout, Xin, Rs/Rt=0
IR(I)+X -> Z: IR(I)out, ADD, Zin
Z -> R[rt]: Zout, Rin, RegDst=0

37、指令格式字段与微命令控制字段填写

Section titled “37、指令格式字段与微命令控制字段填写”

微指令格式题先看字段:

操作控制字段 | 判别测试字段 | 下址字段

如果 A、B、C 组是编码字段,每组同一时刻最多选一个微命令;直接控制字段则每一位都可以同时有效。

答题步骤:

  1. 根据微操作列出需要哪些控制信号。
  2. 把控制信号映射到对应字段编码。
  3. 判别测试字段若无条件转移,通常填 00 或“不测试”编码。
  4. 下址字段填下一条微指令地址;最后一条通常返回取指入口。
  5. 把各字段按位拼接,再转十六进制。

题库中 sw 微程序补全的关键答案:

R[rs] -> X
IR(I) + X -> Z
Z -> AR
R[rt] -> DR
DR -> M[AR]

对应微指令编码示例:

0100080BH
0410000CH
0204200DH
00400080H

38、微程序控制:微命令序列与 MUX 控制逻辑

Section titled “38、微程序控制:微命令序列与 MUX 控制逻辑”

微程序入口地址逻辑题的题库答案:

A4 = slt + addi
A3 = sw + beq
A2 = lw + beq + addi
A1 = beq + slt + addi
A0 = sw + slt

多路选择器控制信号:

Mop1 = ~P0 P1 equal
Mop0 = P0 ~P1

解释:

  • 当不需要条件分支时,MUX 选择下址字段。
  • 当测试字段 P0P0 有效时,MUX 选择 P0P0 分支地址。
  • 当测试字段 P1P1 有效且状态条件 equal 满足时,MUX 选择 P1P1 分支地址。

这类题不要死背图,要从“当前微指令的测试字段”和“外部状态信号”推导 MUX 选择端。