吴焘
(中国科学院自动化研究所广州人工智能与先进计算研究院 广州 510530)
摘 要：本文提出一种基于可编程逻辑专用乘法器实现大数乘法的快速方案。它使用一组并行的乘法、累加器，进位信号发生在乘法、累加结束后的一个时钟周期，而且连续进位，不浪费后续乘法、累加器的计算时间。对于N位乘法、k位字长的架构，该方案平均只需要约2N/k+8个时钟周期。它不涉及复杂的算法，方便应用。在Xilinx Virtex 7系列器件模型中，计算512位乘法需0.184微秒。
关键词：大数乘法；可编程逻辑；快速
中图分类号：TN40 文献标识码：A 文章编号：
DOI：10.11999/JEIT××××××
A Fast Carry-save Multiplier on FPGAs
Tao Wu
(Guangzhou Institute of Artificial Intelligence and Advanced Computing, Institute of Automation of Chinese Academy of Sciences, Guangzhou 510530, China)
Abstract: This paper proposes a fast scheme for long-precision multiplication based on dedicated multipliers on FPGAs. It utilizes a group of multipliers and accumulators, with carry outs occurring at the last clock cycle of the multiplication and accumulation. The carries are generated and passed continuously without any wastes of clock cycles in the following hardware units. For architecture of N-bit multiplication and k-bit words, this scheme takes about 2N/k+8 clock cycles. The proposal does not get involved with any complex algorithms and is simple for applications. On Xilinx Virtex 7 platform, it costs 0.184 μs to compute a 512-bit multiplication.
Key words: Multiprecision multiplication; FPGA; fast
1 引言
乘法器是集成电路中运算电路的核心单元，它可以用在数字信号处理、计算机算术中。常见的乘法器采用例如Wallace Tree等结构压缩部分积 [1-3]。另一种常见的方案是采用波茨编码（Booth encoding）。从可扩展的模乘器出发[4]，可以反过来设计可扩展的乘法器[5,6]和卷积器[7]。对于模乘器而言，既可以从蒙哥马利算法出发，通过交织（interleaving）计算。也可以部分采用蒙哥马利算法[8]或不采用它[9]。此外，可以利用可编程逻辑的专用乘法器搭建大乘法器[10]。
在一般的乘法中，还可以采用Karatsuba-Ofman公式来简化算术[11]，它直接应用在快速傅里叶变换中。余数系统算术便于计算大数运算[12,13]，其中文献[13]基于余数系统乘法提出了一种有效的模乘、模幂算法，它将常系数也作为余数系统表达，进而简化乘法。波茨编码是减少部分积的重要策略，文献[14]中对通常的波茨编码乘法器进行了改进。文献[15]利用Karatsuba算法对大数乘法进行了加速，它应用了Comba算法。
本文提出一种由可编程逻辑（Field Programmable Gate Arrays, FPGA）上的专用乘法器（Dedicated multipliers）计算大数乘法的快速方案。它的基本想法是将乘积分段，每段单独存储进位值。在最后再集体进位N/k次。其中，N是乘数长度，k是分段长度。这种方案借鉴了文献[16]中约简时处理进位的方法。一次N位乘法需要的时间约为2N/k+ 3个时钟周期，其中k视为专用乘法器的大小，通常为16~17。它的速度超过了文献[15] 中基于Karatsuba及Comba算法的硬件乘法器。
2 由可编程逻辑专用乘法器实现大数乘法的架构
从可编程逻辑中的乘法器出发，实现大数乘法的示意图如图1所示。乘数A=(am-1…a1a0), 且0≤ai< 2k. B=(bm-1…b1b0), 0≤bi< 2k. 两个数均有m=N/k个字。可以分m步实施，但每一步需安排m个并行乘法，其部分积可以累加。如图2所示，它是由m个乘法器构成的并行乘法。每个并行乘法器相当于一个处理单元。
.png)
图2：并行乘法
2.1 时间分析
从计算时间来看，输出需要2N/k个时钟周期。直接乘法、累加需要m=N/k个时钟周期。低半部分积可以在运算开始后3个时钟周期即进位，因此多用于进位的时间为N/(2k)+3= m/2+3个时钟周期。因此乘加需要约3m/2+3个时钟周期，它小于输出需要的2m个时钟周期。在寄存器流水的情况下，即使考虑中间延时，1个N位乘法消耗的时间大约是2N/k+8个时钟周期。
3 硬件实现
可以利用移位寄存器、专用乘法器实现上述大整数乘法，如图3所示。其中，A和B分别装载在2个移位寄存器R0, R1中。R0的宽度为2mk=2N位，R1的宽度为N位。输入完成后，A处在寄存器R0的低半部分，高位填0；计算开始后，A向左移动k位，空出的低k位补0。输入完成时，B占满寄存器R1, 计算开始后，每次乘法B向右移动k位，同时高位补k个0. 每个乘积相互独立，相邻累加单元存在进位。
为了防止单元之间串行进位，需要将每个乘法器单元对应的累加值位宽设定得足够大，而在乘积完成后专门完成一次累加值进位。k位乘法器需要将累加值的位宽设计为(k+log2k)位宽。它如同一组调蓄池，等待降雨完成之后再集体调节沿江水位。
.png)
图3：利用移位寄存器输入阵列乘法器的操作数：A左移，B右移。
图4显示了系统计算乘法的处理单元Ui, 它的左边是第i-1个处理单元，右边是第i+1个处理单元，结构相同，没有重复画出。Ui的乘积中高半部分Ti,2k-1..k直接朝第i+1个单元进位，Ui-1的乘积中高半部分Ti-1,2k-1..k直接往第i个单元进位。
.png)
图4：阵列乘法器中的累加单元。它将乘积中的高权字Ti,2k-1..k进位，仅保留低权字Ti,k-1..0.
从垂直箭头以下看，一个处理单元包含3级寄存器。第一级是乘法器逻辑，第二、第三级是加法器、选择器。第1个2:1选择器在乘法计算完成后置0，避免累加值变化。第2个2:1选择器在i个时钟周期内选择低位进位值，然后产生最终结果Ui。考虑到进位已完成，此时它的长度为k位。
.png)
图5：进位的延续时间。横坐标表示空间，相当于乘法器的位置标号。纵坐标表示时间，表示最后一次进位的时间。
图5显示了大数乘法器阵列的进位信号延时。可以见到它从右向左、连续进位。进位与乘法、累加并不矛盾。进位加法紧接在乘法之后，在2m-1个时钟周期类连续进行。
表1列出了本文提出的大数乘法器方案的性能，并与文献中的结果进行了比较。设计方案先由Verilog HDL描述，然后在Modelsim中进行仿真，最后在Xilinx ISE 14.7中布局布线。
.png)
文献[15]使用Karatsuba及Comba算法设计新型硬件乘法器，文献[5]使用可扩展的乘法器计算大整数乘法。文献[15]中，计算256位乘法的速度只有本文的63%，计算512位乘法的速度是本文的81%。但是，此处所耗的面积明显超过它，所用DSP的数量也是它的2倍。因此，本文所提出的方案适合性能优化的场景。而且它整体消耗的资源并不多。
4 结论
乘法器是运算集成电路的核心单元，广泛用于数字信号处理和计算机算术。在椭圆曲线密码算术及RSA密码运算中，都存在大数乘法。本文基于可编程逻辑上的专用乘法器构建大数乘法，性能超过了国际上报道的先进硬件乘法器。此处提出的方案主要应用了并行乘法、并行累加、最后进位的架构，几乎不浪费时钟周期，而且不涉及复杂算法，值得推广应用。
参 考 文 献
[1]Ardekani J F. A M×N Booth Encoded Multiplier Generator Using Optimized Wallace Trees. IEEE Transactions on Very Large Scale Integration (VLSI) systems, 1993, 1(2): 120-125.
[2]Bickerstaff C K, Swartzlander E E. Analysis of Column Compression Multipliers. 15th IEEE Symposium on Computer arithmetic, 2001: 33-39.
[3]Weste N, Harris D. CMOS VLSI design : a circuits and systems perspective. Beijing: China Machine Press, , 2005.
[4]Jiang N, Harris D. Quotient Pipelined Very High Radix Scalable Montgomery Multipliers. Fortieth Asilomar Conference on Signals, Systems and Computers, 2006: 1673-1677.
[5]Wu T, Wang R. Fast unified elliptic curve point multiplication for NIST prime curves on FPGAs. Journal of Cryptographic Engineering, 2019, 9(4): 401-410.
[6]Wu T, Li S, Liu L. Fast RSA decryption through high-radix scalable Montgomery modular multipliers. Science China: Information Sciences, 2015, 58(6): 062401 (16 pp.).
[7]Wu T. High-Speed Fault-Tolerant Finite Impulse Response Digital Filter on Field Programmable Gate Array.?J. Shanghai Jiaotong Univ.?, 2020. https://doi.org/10.1007/s12204-020-2214-z
[8]Jeong Y, Burleson W. VLSI array algorithms and architectures for rsa modular multiplication. IEEE Transactions on Very Large Scale Integration Systems, 1997, 5(2): 211–217.
[9]Meng Q, Chen T, Dai Z, Chen Q. A scalable hybrid modular multiplication algorithm. Journal of Electronics(China), 2008, 25(3): 378–383.
[10]Sentürk A, G?k M. Pipelined Large Multiplier Designs on FPGAs. 15th Euromicro Conference on Digital System Design, 2012: 809-814.
[11]Karatsuba A, Ofman Y. Multiplication of many-digital numbers by automatic computers. Proceedings of the USSR Academy of Sciences, 1962, 145: 293-294.
[12]Mohan A. Residue number systems: algorithms and architectures. Boston, Masse.: Kluwer Academic Publishers, 2002.
[13]Phillips B J, Kong Y, Lim Z. Highly parallel modular multiplication in the residue number system using sum of residues reduction. Applicable Algebra in Engineering, Communication and Computing (AAECC), Springer, 2010, 21: 249-255.
[14]Moss D, Boland D, Leong P. A Two-Speed, Radix-4, Serial–Parallel Multiplier. IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2019, 27(4): 769-777.
[15]Rafferty C, O'Neill M, Hanley N. Evaluation of large integer multiplication methods on hardware. IEEE Transactions on Computers, 2017, 66(8): 1369-1382.
[16]Güneysu T, Paar, C. Ultra high performance ECC over NIST primes on commercial FPGAs. In: Workshop on Cryptographic Hardware and Embedded Systems (CHES). LNCS, 2008, 5154: 62–78.
作者简介：吴焘，1981年12月出生，博士，工程师。研究方向为密码、编码。2003年本科毕业于武汉大学，2006、2013年硕士、博士毕业于清华大学。2018年12月从中山大学深圳研究院博士后出站。
电子邮箱: nstrch@outlook.com