第二十八课:ALU 算完以后,怎样判断零和负数

从程序根据结果作出判断的需求出发,推导 zr 与 ng,并将它们接到 no 处理后的最终输出。

本章目录CONTENTS ↓

假设程序正在倒数:每执行一次任务,就把剩余次数减 1;减完后,如果结果为零,就结束循环。前几课的 ALU 已经能算出新的次数,但 CPU 还需要一个判断:这个结果是不是零?

一种方案是让 CPU 收到 16 位结果后,自己另接电路判断。另一种方案是让 ALU 在输出结果的同时,把常用的判断也一并提供。Hack 采用后者:除了 out[16],ALU 还提供两个单比特的状态输出(status outputs),它们随当前 out 改变:

  • 零标志(zero flag),端口名 zr:最终 out 为零时是 1,否则是 0。
  • 负数标志(negative flag),端口名 ng:最终 out 按 16 位补码解释为负数时是 1,否则是 0。

这样,CPU 可以直接利用这两条信号判断是否需要跳转,而不必在接收端重新搭一套相同的检测电路。代价是 ALU 多了两个输出端口和零检测部件。这是对当前接口的设计分析;并非所有处理器都采用这种接口。官方 ALU 接口与规格

本课只解决这两个判断,不增加新的运算或控制位。

为什么要看最终 out

上一课的 selected 是 f 选出的结果,之后还要由 no 决定是否取反。因此,状态标志必须描述 no 处理之后的 out,不能停在 selected。

用一组完整输入看出区别:x、y 都是 16 位的零,zx=nx=zy=ny=0,f=0。输入不变,按位与得到 selected=0000 0000 0000 0000。

no=0:out = 0000 0000 0000 0000 → zr=1,ng=0
no=1:out = 1111 1111 1111 1111 → zr=0,ng=1

第二种情况下,最终结果是补码 −1。如果仍根据 selected 判断,就会错误地报告“结果为零,而且不是负数”。电路应当从最后一个 Mux16 的输出处分出两条检测通路:官方 Chapter 2,图 2.5

selected → no 选择保留或取反 → 最终结果 ──→ out[16]
├──→ 零检测 → zr
└──→ 取最高位 → ng

zr:怎样确认十六位全是零

只看某一位不够。例如 0000 0001 0000 0000 的最低位是 0,整个数却不是零。

回想 Or8Way:八位中只要有一个 1,它就输出 1。因此可以把最终结果分成低八位和高八位,分别检测是否含有 1,再将两个判断用 Or 合并。

lowAny = OR(最终结果的第 0~7 位)
highAny = OR(最终结果的第 8~15 位)
anyOne = lowAny OR highAny
zr = NOT(anyOne)

为什么最后要取反?当十六位全是 0,两组 OR 都为 0,anyOne=0,而“结果为零”应该报告 1。只要任意一位为 1,它所在组的 OR 就为 1,继而使 anyOne=1,于是 zr=0。这两种情况覆盖全部 16 位模式,所以检测不会遗漏任何位置。

这里是在把十六位归约(reduction)为一个判断,复用了第十二课的思路;它与产生十六位结果的 Or16 不同。

ng:为什么直接接最高位就够了

判断负数需要先说明解释规则:Hack 将最终结果按 16 位补码解释。在这条规则下,最高位 out[15] 的位权是 −32768,其余十五位的总贡献介于 0 和 32767 之间。

  • 最高位为 0:数值介于 0 和 32767 之间,不是负数。
  • 最高位为 1:数值为 −32768 加上其余位的贡献,介于 −32768 和 −1 之间,必然是负数。

因此,ng 就等于最终结果的第 15 位,无需再做一次减法或比较。零的最高位为 0,所以零也会正确得到 ng=0。补码位权与符号位

ng 描述的是保留下来的输出,不是有符号溢出标志。例如 32767+1 的低十六位是 1000 0000 0000 0000,按补码解释为 −32768,所以 ng=1;它不会告诉我们精确数学和 32768 已超出补码范围。Hack ALU 不检测或处理溢出。官方 Chapter 2:ALU 的范围限制

接到现有 ALU 中

保留之前的输入预处理、运算选择和 Not16(in=selected, out=invertedResult)。把最后一行 Mux16 替换为下面的接线,并追加四行零检测;沿用官方接口中的 OUT out[16], zr, ng;。

Mux16(a=selected, b=invertedResult, sel=no,
out=out, out[0..7]=lowResult, out[8..15]=highResult, out[15]=ng);
Or8Way(in=lowResult, out=lowAny);
Or8Way(in=highResult, out=highAny);
Or(a=lowAny, b=highAny, out=anyOne);
Not(in=anyOne, out=zr);

第一条语句中的几个 out 都是这颗 Mux16 的输出端口:整条总线接到 ALU 的 out,低、高八位分别接到内部连线 lowResult、highResult,最高位同时接到 ALU 的 ng。它们都来自同一份最终结果,没有再次计算。

这里有一个与实现有关的 HDL 限制:不能把当前 ALU 自己的输出端口再当作部件输入,也不能直接切片内部总线。因此不写 Or8Way(in=out[0..7], ...);而是在产生结果的部件输出端取出子总线,再传给 Or8Way。同一部件输出可以连接多个去处,这是把信号分出去,不是反复给它赋值。HDL Survival Guide:子总线与多个输出连接、官方 Web IDE:接线检查规则

在模拟中核对什么

补齐后使用完整的 ALU.tst 与 ALU.cmp,检查 out、zr、ng;之前的 ALU-nostat.tst 不检查这两个状态输出。官方 Project 2:分阶段测试

核对下面几种最终结果,会分别检验全零、低位非零、高位非零和输出取反后的负数:

最终 out 补码值 zr ng
0000 0000 0000 0000 0 1 0
0000 0000 0000 0001 1 0 0
1000 0000 0000 0000 −32768 0 1
1111 1111 1111 1111 −1 0 1

后面构造 CPU 时,这些信号会参与跳转判断。例如官方示例中的 D;JGT 要求当前计算结果大于零;按补码解释,既不是零(zr=0),又不是负数(ng=0),才满足这个条件。具体指令格式和跳转接线留到对应课程再学。官方 Max.asm:根据结果跳转

这一步补齐了 ALU 的三个输出:out 给出结果,zr 和 ng 给出关于这个结果的判断。读完并完成模拟后告诉我,我们再按一次一题的方式练习。

这一页,先记到这里。