跳转至

实验2：运算器与寄存器

在本次实验中，我们有以下主要任务：

  • 设计32位ALU，可以实现加法、减法、与、或、异或、取反等运算。
  • 设计32位单周期无符号乘法器，并借助寄存器测试其可接受的最大时钟频率
  • （可选替代）设计32位单周期有符号或可选有无符号乘法器，并借助寄存器测试其可接受的最大时钟频率
  • （可选替代）Booth编码＋华莱士树的流水线乘法器，并借助寄存器测试其可接受的最大时钟频率

1 ALU

ALU（Arithmetic Logic Unit，算术逻辑单元）是计算机中的一种重要组件，它可以实现算术运算和逻辑运算。在龙芯架构32位精简版指令集中，ALU需要支持以下运算：

  • 简单算术运算：加法（ADD）、减法（SUB）、小于比较（SLT）、无符号小于比较（SLTU）
  • 逻辑运算：按位或非（NOR），按位与（AND），按位或（OR），按位异或（XOR），左移（SLL）、右移（SRL）、算术右移（SRA）

ALU的本质并不是执行哪个运算就“调用”哪个运算单元来计算——这并不符合硬件的本质。ALU是同时将两个源操作数送到所有运算单元，每个运算单元都进行计算并输出，再通过op（操作码）来借助多选器选择哪个运算单元的输出作为最终的结果。

image-20231012134205580

在处理独热码的编码时，我们可以有两种选择：

  • RTL级描述方式：使用assign或例化模块等方式分别实现每个运算单元，再使用与或运算来对所有运算单元的输出结果进行多选。设一共有\(n\)个运算单元，设第\(i\)个运算单元对应了操作码的第\(i\)位（例如在本次实验中，加法作为第0个运算单元，对应了独热码的第0位），那么我们可以使用如下的逻辑来实现多选： 

      assign out = ({32{op[0]}} & adder_out) | ({32{op[1]}} & sub_out) | ... | ({32{op[N-1]}} & sra_out);
    注意上述的省略号是简写，真正编写代码需要把所有的运算单元都列出来。 这里涉及到了位拓展和位拼接运算，32{k}表示将k这个数据重复32次，最外层的大括号表示将这重复了32次的数据拼接起来。

  • 行为级描述方式：使用always+case的行为级描述来实现ALU，在case的不同情况下给ALU输出结果赋相应的值，相信编译器可以将代码优化为上述逻辑。

这两种方法都是可以的，但是我们推荐使用第一种方法，因为这样可以让你更加清楚地知道自己的代码是如何工作的。

参考openLA500

openLA500是龙芯杯官方提供的示例代码仓库。你可以参考其中的ALU。杜绝直接抄袭，检查时会有提问。

"资源优化与通路复用

在ALU的设计中，你必然可以使用case和各类运算符来完成这个设计。但是，你是否可以尝试使用资源优化和通路复用的思想来完成这个设计呢？例如，我们可以将加法器的计算结果复用起来计算减法，再使用加减法的计算结果实现小于比较，更可以将左移和右移的计算结果复用起来。如果你能够做到这些，那么你的ALU将会非常紧凑，而且性能也会非常好。openLA500中的alu就实现了这些。

2 寄存器

寄存器是重要的时序电路元件，它可以存储数据，并在时钟上升沿时将数据输出。在本次实验中，我们将实现一个32位寄存器。

寄存器的实现代码我们已经给出，你只需要例化它即可：

module  register
#( parameter WIDTH = 32,
             RST_VAL = 0
)(
    input  clk, rst, en,
    input  [WIDTH-1:0]  d,
    output reg  [WIDTH-1:0] q
);

    always @(posedge clk)
        if (rst) q <= RST_VAL;
        else  if (en) q <= d;

endmodule

这里提供了一个通用的寄存器模板，我们可以根据需要对寄存器进行参数化，用来生成不同位宽的寄存器。例如，如果我们希望生成一个32位，复位值为0的寄存器，那么我们可以使用如下代码：

register #(.WIDTH(32), .RST_VAL(0)) reg32(
    ......
);
在省略号中，你只需要对寄存器的输入和输出进行连接即可。

不要使用其他信号的上升沿！

在电路中，有且仅有时钟晶振的上升沿是稳定的，其他信号的上升沿都是不稳定的，因此我们不要使用其他信号的上升沿来触发任何操作。如果使用了其他信号的边沿，那么你的电路将会出现很多奇怪的问题，例如电路无法正常工作、电路的时序无法满足等等，最经典的错误就是仿真通过上板不过。

3 加法器的性能测试

在本次实验中，我们将引入时序的概念。相信大家对于时钟频率的概念已经不陌生了，对于一个时钟频率为100MHz的时钟，它的周期为10ns。这意味着，当时钟上升沿到来时，我们的电路需要在10ns内完成所有的计算。如果我们的电路需要在10ns内完成的计算超过了10ns，那么我们的电路就无法正常工作了。

为了测试加法器的性能，我们可以使用寄存器来测试加法器的最大时钟频率。我们可以将加法器的输出接到一个寄存器的输入端，再使用两个寄存器的输出连接到加法器的输入端，这样就可以形成一个数据通路。在这个数据通路中，我们可以使用时钟来控制数据的流动，这样就可以测试加法器的最大时钟频率了。

image-20231012140730836

通过修改限制文件中的时钟频率，你可以不断加大时钟频率，来测试加法器的极限性能。当实现（Implement）的时候，如果Vivado的WNS报告显示负值，那么表示电路已经不能在一个时钟周期内完成运算，你需要降低时钟频率，直到WNS为正值为止。

需要注意的是，由于我们的开发板不存在32位外设，因此大家需要把自己的设计连接入我们提供的测试单元后，再进行实现电路。虽然这样测量的最大时钟频率可能偏低，但如果不使用这样的手段，我们是无法对电路进行实现的。

当\(WNS < 0\)时，我们可以遵循以下公式来计算电路的最大时钟频率：

\[ f_{max} = \frac{1}{T_{clk} - WNS} \]

其中，\(T_{clk}\)为时钟周期，\(WNS\)为Worst Negative Slack，表示最差的负时序。

但是，当WNS为正数时，上述公式并不奏效！这是因为Vivado在发现时序很难满足时，会想尽一切办法优化时序，直到所有办法都无法解决时序问题，因此这样的计算方法将会较为准确的估计电路的最大时钟频率。但是，当WNS为正数时，Vivado可能发现时序很容易满足，于是直接强势开摆，用一个很烂的算法进行线路排布。

需要注意的是，上述公式计算并不准确，因为我们并没有考虑到时序的Setup Time和Hold Time。但是，这个公式可以作为一个估计值，来帮助我们估计电路的最大时钟频率。

4 乘法器的设计

在本次实验中，我们将实现一个32位乘法器。乘法器的实现方法有很多种，我们在这里为大家介绍几种基于加法器的乘法器实现方法。

不允许使用乘号完成乘法器的设计

在本次实验中，我们不允许直接使用乘号完成乘法操作。乘号会占用大量的资源，且不能让大家真正理解乘法器的实现原理。

4.1 简单串行乘法器

  • 将加法器产生的32个部分积串行相加，得到最终的乘积。
  • 这种乘法器的延迟高达32个64位串行加法器的延迟，性能很差。即便可以通过细致的位拼接缩减到33位加法器，性能也不会有太大提升。
  • 改进思想：能不能让更多的部分积并行计算呢？

4.2 二叉树乘法器

  • 使用5层二叉树64位加法器，根据乘数，将被乘数适当移位，不断累加至只剩一个结果

image-20231012142713095

  • 可以通过细致的位拼接，将加法器缩减到33位，性能有所提升，但是仍然不理想。

  • 采用超前进位加法器，可以获得一定的性能提升，但随着超前进位加法器的位数提升，其假超前的问题会越来越严重，导致性能提升不明显：

    image-20231012142911886

    可以看到，这里依然存在依赖关系，即便可以使用MOS管实现多输入与门，但因为电压的物理因素，一般4个输入的与门已经很危险了。所以，超前进位未必是真正的超前，二叉树乘法器的每一个加法器也会引入大量的延迟。

4.3 华莱士树+2位Booth编码设计有符号乘法器

​ 上述乘法器中延迟最大的问题是加法，如64位加法需要由低到高依次计算64级。本次我们介绍的华莱士树+2位Booth编码设计，将这种高延迟的加法减少为1次。

​ 这种结构的完整过程是，Booth编码缩减部分积、华莱士树用多级CSA将加数缩减为2个、最后用一个全加器来实现对最后两个64位加数的加法。除了最后的全加器，都是位运算，不会因位数高而产生大量延迟。

​ 一般而言，全加器的延迟大致与Booth编码+华莱士树相当，你可以据此分为两级流水，也可以Booth编码一级、华莱士树一级、全加器一级实现三级流水。

4.3.1 2位Booth编码

  • 2位Booth编码可以通过有效的编码来缩减乘法中部分积的个数，由32个部分积转化为16个部分积

  • 原理：

    \[ -y_{31} \times 2^{31} + y_{30} \times 2^{30} + y_{29}\times 2^{29}+ \cdots+y_1\times 2^1 + y_0\times 2^0 \\ =(y_{29}+y_{30}-2\times y_{31}) \times2^{30} + (y_{27}+y_{28}-2\times y_{29}) \times2^{28} + \cdots \\ +(y_{1}+y_{2}-2\times y_{3}) \times2^{2} + (y_{-1}+y_0-2 \times y_1) \times 2^0 \]

    有了这样的表示，我们就可以借助如下编码表来使用乘数\(y\)对输入的被乘数\(x\)进行编码：

    \(y_{i+1}\) \(y_i\) \(y_{i-1}\) 编码
    0 0 0 \(0\)
    0 0 1 \(x\)
    0 1 0 \(x\)
    0 1 1 \(2x\)
    1 0 0 \(-2x\)
    1 0 1 \(-x\)
    1 1 0 \(-x\)
    1 1 1 \(0\)

  • 你可以使用generate语法批量例化Booth模块，来构建Booth编码部分

4.3.2 保留进位加法器

  • 保留进位加法器有3输入，2输出，将三个数的加法转化为其和与每一位的进位。 image-20231012144415354

  • 保留进位加法器的优势：任意位宽的加法器都不再依赖低位进位：

    \(S = A \oplus B \oplus CIN\)

    \(COUT = A \& B \ |\ B \& CIN \ |\ A \& CIN\)

    这基本就是全加器的逻辑。

  • 这里的CIN，在华莱士树中与a、b没有什么差别，也是一个完整的加数。注意COUT是每一位进位的结果，在之后使用时要左移一位。

  • 保留进位加法器可以把三个数的和转化为两个数的和，这也是类似于二叉树的方法进行计算。每过一层保留进位加法器，部分和数量减少⅔，因此也只需要层保留进位加法器就可以完成计算。CSA的计算是位运算，所以延迟显著低于全加器。当然，最后一层两个数相加，应当是一个真正的加法器来计算。

4.3.3 华莱士树

image-20231012145911719

  • 华莱士树就是树型保留进位加法器的硬件结构，通过不停地使用保留进位加法器，来使得每一层部分积减少⅓，最终缩减为2个数的加法，再通过一个全加器获得最后的结果。

  • 保留进位加法器的cout，是进位的值，再输入下一级保留进位加法器前，需要左移一位。

  • 在进入华莱士树之前，我们可以使用2位Booth编码来使部分积的个数缩减到一半。

  • 无符号乘法：实现33位乘法器，乘数拓展一位，最高位0拓展，就可以实现无符号的乘法。

4.4 乘法器的性能测试

在这一部分中，请使用加法器测试性能的数据通路来测量乘法器的性能。你可以使用寄存器来测试乘法器的最大时钟频率，也可以使用Vivado的WNS报告来估计乘法器的最大时钟频率。