简介

本项目通过使用booth算法编写了一个32bits的有符号乘法器,其流水线为4级,且带有握手信号,vivado版本为2019.2 (注:最新的版本已经为32bits有无符号乘法器,两级流水,不带握手信号,文档暂时没空写)

1 有符号Radix-4 Booth乘法器原理

https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm

2 有符号Radix-4 Booth乘法器基本流程

假设输入为A,B,将A作为booth编码数据,为了重新编码乘数项，分组从LSB开始，每个块有且仅有一位和前一个块重叠,第一个块只使用乘法器的两位(该块为[1:-1])

然后通过获得这些编码块来对输入数据B进行操作来产生部分积

Block	部分积
000	0
001	B
010	B
011	2*B
100	-2*B
101	-B
110	-B
111	0

假设A=4'b1101(-3),B=4'b0101(5); 故res=8'b1111_0001(-15); 具体计算如下所示

1101
0101	0(辅助位)
11111101	(010)移动0位
11110100	(010)移动2位
11110001	(res)

本例子使用0101作为booth编码数据,可知4位的数据会产生两个编码010和010(负一位为零),对应的部分积为B,即将1101进行符号扩展,然后左移相关位数,如第二个部分积的产生,先将1101扩展到8位,即11111101,再对其进行移位,基4booth编码移动两位,故部分积结果为11110100;
由于我们是32bits乘法器,故通过该算法可得到16个部分积,这些结果不能一次通过组合逻辑加法输出(面积和延迟太大),常见的做法是基于wallace tree 的加法树

3 Wallace tree加法树设计

采用 Wallace树结构对部分积进行进位保留压缩 ，使 16个部分积快速化累加成 2个部分积． 本项目采用42压缩器,其具体电路结构如下图所示

逻辑如下图所示

32位乘法器会生成16个64位的部分积,将16位的部分积分为四组,每组用一个64bit的42压缩器,这样输出数据会减小到8个,下一级会减小到4个,最后会减小到两个,然后经过一个64位的超前进位加法器完成计算。 其中64bit的42压缩器只需16个1bit的42压缩器

4 超前进位加法器

~~

5 仿真验证

仿真有两个测试文件,tb_booth_ctrl文件测试功能正确性,tb_bus测试握手信号正确性

5.1 tb_booth_ctrl

本测试文件采用了difftest的思想,首先生成正确的结果,然后将该结果与计算的结果相比较,如果全部正确,则代表功能通过,之后会打印正确率
本次生成10000个测试用例,可以看到正确率100%,由于未对i复位,故前5个测试用例不能使用(懒得改)

5.1 tb_bus

仿真阶段分为四个部分

1. valid_i=1,ready_i=1
   此时为数据有效,整个流水线是通的,如图所示,由于复位信号影响,第一个时钟周期的数据为无效数据,有效数据为左侧红框数据,由于模块有4级流水线,故输出有效数据,延迟四个周期,如右侧红框所示,此时的valid_o也为高,表示该模块有有效的数据
2. valid_i=0,ready_i=1
   此时流水线断流,上游模块无有效输入,所以流水线输出仍然保持原来数据,如图所示,红框1为断流信号,经过四个周期传到红框2,将2中的valid_o信号拉低,表示输出无效(此时为什么输出还是第一组数据?因为红框1中的第一组数据(06,46)在被采集时流水线已经断流,此输入数据为无效数据)
3. valid_i=1,ready_i=0
   此时进入流水线下游反压阶段,下游反压并不会立刻反馈到第一级的流水，而是由下至上逐级反馈，所以下游反压的时候，空的流水线不会立即停止，而是等数据把流水线灌满之后才停止。下游反压时，流水线进的数据如下图框1所示，由于为四级流水,故流水线进入四组数据即可把流水线灌满,之后，流水线就停滞了（表现为ready_o拉低，告诉上游我吃不进数据了）。
4. valid_i=0,ready_i=1
   此时数据无输入,但流水线中有上图框1的四组数据,把之前吃进来的四周期数据计算后再吐出来，可以看到确实输出时ready_i和valid_o同时保持四个周期高电平，把五级流水线内部数据吐完后，valid_o拉低，流水线清空。

6 综合和STA分析

本次使用的综合器为开源RTL综合器yosys,其对RTL设计进行综合, 并映射到一个45nm的开源工艺库nangate45, 然后将综合得到的网表文件和工艺库中的标准单元信息文件输入到开源静态时序分析工具iSTA中, iSTA将快速评估RTL设计中的时序路径, 并给出时序余量最少的若干条路径, 供RTL设计者参考. 通过上述方式, RTL设计者可快速得知RTL设计的时序情况, 并对RTL设计进行快速迭代. 如上图所示,本次综合的频率为500MHZ,最终选择了三条路径的slack均大于零,最大频率可达到647MHZ