跳转至

ALU

在下学期的组成原理课程中，我们将使用 Verilog 逐步设计实现出一个完整的 CPU ，而 ALU(算术逻辑单元) 正是 CPU 的一个重要部件，它负责执行位运算、加减法、位移等运算操作。本节中，我们将以超前进位加法器为基础，设计一个完整的 ALU，并自主实现加法、减法、比较三类运算，其他运算可以使用 Verilog 自带的运算符实现。

★ 2.1 ALU 原理介绍

一般而言，为了保证 CPU 的运行效率，我们希望 ALU 能够在一个周期内就能得到计算结果，故 ALU 常被设计为一个组合模块。乘除法等运算由于比较耗时，一般被单独设计为一个模块，放在 CPU 的其他位置而非 ALU 中。在我们的设计中，ALU 接受两个操作数 src0 和 src1，以及一个独热码选择信号 sel，用以选择运算类型。ALU 的输出为运算结果 res。其输入输出模型如下图：

Image title

在龙芯架构 32 位精简版指令集中，ALU 需要支持以下运算：

  • 简单算术运算：加法（ADD）、减法（SUB）、小于比较（SLT）、无符号小于比较（SLTU）

  • 逻辑运算：按位或非（NOR），按位与（AND），按位或（OR），按位异或（XOR），左移（SLL）、右移（SRL）、算术右移（SRA）

各种运算对应的选择信号如下表所示：

Image title

一些同学可能会想参考 C 语言等高级语言的编程习惯，根据输入信号 sel 选择调用对应的运算模块，将输入 src0、src1 传递给该模块并获取结果。但是这一想法是不符合硬件设计思想的。这是因为 Verilog 中的模块例化与其他语言的函数调用有较大区别，它通常作为一个单独的代码段，不能放在 if-else 等其它代码段中。从硬件的角度看，设计出结构在上板前必须是确定的。我们不可能根据电路的运行结果动态地生成或删除电路结构，只能引导信号经过不同的路径。

因此，合理的思路是，同时将两个源操作数送到所有运算单元，再通过输入信号 sel 来借助多选器选择哪个运算单元的输出作为最终的结果。即，我们选择的不是使用哪个模块，而是选择使用哪个模块的结果。即使没有选择某个运算，它对应的模块也依然在工作，只是我们没有选择它的结果而已。

ALU.v
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
module ALU (
    input                   [31 : 0]        src0, src1,
    input                   [11 : 0]        sel,
    output                  [31 : 0]        res
);
    // 加法运算示例
    wire [31:0] adder_out;
    wire co;

    Adder #(32) fa1(
        .a(src0),
        .b(src1),
        .ci(0),
        .s(adder_out),
        .co(co)
    );

    // 选择运算结果示例：加法
    assign res = ({32{sel[0]}} & adder_out) | ...;

endmodule

上面是我们给出的 ALU 代码框架以及结果选择的一种实现方式，你也可以选择使用 case 来实现结果的选择。

注意

在大家实现的 ALU 中，请例化自己的加法器来实现加法，不允许使用加法运算符 +。

2.2 减法运算

2.2.1 补码运算

对于 \(n\) 位二进制数，我们一般按照 \(x=\sum_{i=0}^{n-1}a_{i}2^{i}\) 的形式进行表示，其中 \(a_i\in\{0,1\}\)。不难看出，\(n\) 位二进制数的表示范围是 \(0\sim2^n-1\)，即所有小于 \(2^n\) 的非负正整数。那么，我们应当如何表示负数呢？目前有三种主要的表示方法：

  • 原码表示（符号-数值码）：在数的最前面增加一个符号位 s，并约定若 s=0 则该数为正数，若 s=1 则该数为负数。例如 \(15_{10}=001111_2\)，\(-15_{10}=101111_{2SM}\)。对应的数值函数为
\[x=(-1)^s\times\sum_{i=0}^{n-1}a_i2^i\]
x=(-1)^s\times\sum_{i=0}^{n-1}a_i2^i
  • 反码表示：负数由其相反数的原码取反得到。例如 \(15_{10}=001111_2\)，\(-15_{10}=110000_{2OC}\)。对应的数值函数为
\[x=-a_{n-1}(2^{n-1}-1)+\sum_{i=0}^{n-2}a_i2^i\]
x=-a_{n-1}(2^{n-1}-1)+\sum_{i=0}^{n-2}a_i2^i
  • 补码表示：负数由其相反数取反加一得到。例如 \(15_{10}=001111_2\)，\(-15_{10}=110001_2\)。对应的数值函数为
\[x=-a_{n-1}2^{n-1}+\sum_{i=0}^{n-2}a_i2^i\]
x=-a_{n-1}2^{n-1}+\sum_{i=0}^{n-2}a_i2^i

绝大多数数字系统都选择补码进行运算，这是因为它简化了加法和减法的形式。考虑某 \(n\) 位二进制数 \(x\)，我们对其按位求反得到 \(\bar{x}=2^n-1-x\)，对应的补码即为 \(x'=2^n-x\)。由于 n 位二进制数加减法是在模 \(2^n\) 的意义下进行的，而 \(x'\equiv 2^n-x\equiv-x(\text{mod }2^n)\)，所以，在补码运算下，有\(a-b=a+b'\)。

补码最大的意义就是能够将二进制整数的加减法转化为加法与求补码两种运算，让我们可以不再关注符号对运算结果产生的影响（且求补码足够简单）。这一事实启发了我们如何复用加法器来实现减法器。

★ 2.2.2 用加法器实现减法器

下面的电路图展示了如何使用加法器进行加减法运算。将加法器的 \(b\) 端输入设置为 \(!b\)，低位进位端输入设置为 1，输出结果即为 \(\text{out}=a+\bar{b}+1=a-b\)，从而完成了减法运算。

Image title

减法器示意图

基于上面的思路，我们可以用下面的 verilog 代码实现减法器：

AddSub.v
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
module AddSub (
    input                   [ 3 : 0]        a, b,
    output                  [ 3 : 0]        out,
    output                  [ 0 : 0]        co
);

Adder #(4) fa1(
    .a(a),
    .b(~b),
    .ci(1'B1),
    .s(out),
    .co(co)
);
endmodule

这里将 \(b\) 取反后输入，并将 1 作为低位进位。这样，我们就通过复用加法器，完成了减法器的设计。

当然，感兴趣的同学也可以试着对超前进位加法器进行修改，直接得到减法器（就像把全加器改成全减器那样）。不过需要指出的是，这两种实现的性能差距很小，这正是求补码操作足够简单带给我们的好处（只需要通过一个非门的延迟，并把 1 作为低位输入）。

2.2.3 溢出检测

溢出是加减法运算时的一个重要问题。当然，在 ALU 的加减法运算中，我们并不考虑溢出的影响（这一问题的影响由程序自身承担）。但是，当我们将加减法复用到其他模块中，比如比较运算中的时候，溢出可能就会成为影响结果判断的重要因素之一了。考虑如下的例子：

例子：加减法溢出

考虑如下的 4 位二进制数运算过程

\[ 0100+0101=1001 \]

对应的十进制表示为

\[ 4+5=-7 \]

这显然是一个不正确的运算结果。但我们如果使用 5 位二进制数进行计算：

\[ 00100 + 00101 = 01001 \]

对应的十进制表示为

\[ 4+5=9 \]

就得到了正确的运算结果。

\(n\) 位补码表示的二进制数表示范围为 \(-2^{n-1}\sim 2^{n-1}-1\)，共计 \(2^n-1\) 个数。因此当运算结果超出了这个范围时，我们就称运算结果发生了溢出。对于上面的例子，4 位二进制数的补码表述范围为 \(-8\sim 7\)，因此正确结果 9 就会发生溢出。而 5 位二进制数的补码表示范围更大，为 \(-16\sim 15\)，因此不会发生溢出。

更精细地说，有两种类型的溢出：如果想要的结果比能表示的最大值还要大，那么就叫做正溢出；想要的结果比能表示的最小值还要小，就叫做负溢出。

如何判断结果是否溢出呢？一个很自然也很基本的观点是：正数 + 正数 = 正数，负数 + 负数 = 负数。我们可以检查输入的 a、b 的符号位（也就是最高位）与结果 out 的符号位进行判断。下表列举了所有可能的结果：

Image title

不难发现，对于加法而言，当且仅当两个原始输入 a、b 的符号相同，但与结果 out 的符号不同时，才会发生溢出。减法可以视作加法来处理。由此，我们便得到了检测溢出的方法。

溢出检测的参考电路图如下：

Image title

加法减法器溢出检测示意图

★ 2.3 比较器

在介绍完加减法运算后，让我们来讨论一下比较运算的实现。我们这里实现的是小于比较 (SLT)，即将两个操作数 a、b 均视为补码，进行补码间的小于比较，当 a < b 时结果为 1。无符号小于比较 (SLTU) 将作为作业的一部分。

那么，如何进行基于补码表示的大小比较呢？我们可以借助先前设计的减法电路。不难发现，在不考虑溢出的前提下，若 \(a-b=0\)，则 \(a=b\)；若 \(s=a-b\) 的符号位为 1，则代表 \(s<0\)，即 \(a<b\)。

然而上面的方法只适用于未发生溢出的情况。经过前面的讨论我们知道，只有当 a、b 异号时，才有可能发生溢出。所以针对 a、b 同号的情况，我们可以放心使用减法器的运算结果。而当 a、b 不同号时，我们可以直接比较它们的符号位：正的那个数必然大于负的那个数。

基于减法器的有符号比较器的电路图如下：

Image title
比较器示意图

最后更新: November 22, 2023

评论

Authors: XhyDds, wintermelon008