基于FPGA的進位存儲大數(shù)乘法器的改進與實現(xiàn)

張曉楠 ，高獻偉 ，，董秀則

1.西安電子科技大學 通信工程學院，西安 710071 2.北京電子科技學院 電子系，北京 100070

基于FPGA的進位存儲大數(shù)乘法器的改進與實現(xiàn)

張曉楠1，高獻偉1，2，董秀則2

1.西安電子科技大學 通信工程學院，西安 710071 2.北京電子科技學院 電子系，北京 100070

提出了一種基于FPGA的進位存儲的大數(shù)乘法器的改進算法，該算法采用串并混合結(jié)構(gòu)可以在一個時鐘內(nèi)完成多次迭代計算，減少了完成一次運算的時鐘數(shù)，因此有效地提高了大數(shù)乘法器的速度。最后硬件結(jié)構(gòu)設計在Altera Stratix II EP2S90F1508C3上實現(xiàn)，給出了192位、256位以及384位的乘法器性能分析，其中，192位可達到0.18 μs，256位達到0.27 μs，384位達到0.59 μs，速度上都提高了3.5倍左右。

大數(shù)乘法；串并混合結(jié)構(gòu)；多次迭代；現(xiàn)場可編程門陣列

1 引言

乘法器是算術單元、數(shù)字信號處理器和其他算術運算的電路的重要功能單元。在很多領域都有重要應用，如密碼體系、科學計算以及工程計算等方面。隨著芯片集成度的不斷提高和數(shù)據(jù)量的加大，特別是現(xiàn)代信息處理中對安全保密的高要求，對于乘法器，特別是大數(shù)乘法器的處理速度方面的要求也日益增大[1]。乘法器的處理過程大致相同，都是先生成部分積再相加。設計的關鍵是在于其運算速度的快慢。

為了加快大整數(shù)乘法，人們對大整數(shù)乘法的算法與實現(xiàn)進行了諸多研究。如參考文獻[2]給出了利用Booth算法和Wallace Tree算法，通過減少部分積，并且把大數(shù)加法拆分為32位的加法來實現(xiàn)對于大數(shù)乘法的高速運算；文獻[3]給出了一種43位浮點乘法器來進行高性能的乘法運算；文獻[4]給出了一種高基（2H進制）的大數(shù)模乘硬件實現(xiàn)方法；文獻[5]提出了一種并行行旁路（PRB）乘法器，通過對乘數(shù)進行重新編碼并行輸出部分積，從而使得乘法中的部分積減少，進而提高乘法速度。文獻[6]和文獻[7]的乘法器都是基于矩陣型乘法器的。本文提出了一種基于FPGA的進位存儲的大數(shù)乘法器的改進算法，主要思路是在一個時鐘完成多步迭代運算，降低完成一次運算的時鐘數(shù)，通過仿真綜合硬件面積和速率的綜合考慮，得到最優(yōu)的步數(shù)和速度。

2 進位存儲乘法器結(jié)構(gòu)

加法器是設計乘法器的的基礎元件，加法器的應用主要是實現(xiàn)對部分積的相加，從而把乘法轉(zhuǎn)換為加法運算。本文主要采用了進位存儲加法器。

2.1 進位存儲加法（CSA）

進位存儲加法器[8]是一種簡單的k個全加器全部并行的結(jié)構(gòu)，沒有任何的串行連接。如果對每位加法的進位保存下來，則兩個或者兩個以上的k位整數(shù)加法可以按位進行并行操作，得到兩個整數(shù)，其中一個表示各個位的進位信息，另一個代表各個位的和信息。

假設要實現(xiàn)三個整數(shù)相加，輸入分別為A,B,C，產(chǎn)生兩個整數(shù)C'、S，得到2C'+S=A+B+C。其中和S的第 i位與進位 C′的第 i+1位可由 Si=Ai⊕Bi⊕Ci,Ci+1'=AiBi+AiCi+BiCi表示。即，一個進位存儲加法器單元就是一個全加器單元。

例如：令 A=35,B=25,C=8，計算S和C′，A=35=（100011）2，B=25=（011001）2，C=8=（001000）2，所以S=（110010）2=50，C′=（001001）2=9，故 A+B+C=2C′+S=2×9+50=68。

2.2 進位存儲乘法器設計

由于進位存儲加法器相對于其他的加法器速度快很多，因此進位存儲加法器應用到乘法器上應該會有效提高乘法器速度。進位存儲乘法器的基本原理采用右移-加的乘法設計[9-10]。

算法 進位存儲乘法器設計

輸入 整數(shù)x，y(二者都是k位)。

輸出 z=xy。

步驟1令 ps←0,pc←0,p←0。

步驟2對于i從0到k-1，重復執(zhí)行

步驟3sum←ps+pc；

步驟4z←{sum,p}。

步驟5返回(z)。

算法的核心部分步驟2可表示為電路圖圖1形式。

從圖1可看出該結(jié)構(gòu)表示了進行一次迭代運算的過程，兩個k位的數(shù)相乘需要經(jīng)過k次的迭代運算，結(jié)果應是一個2k位的數(shù)，圖1中的 p表示低k位，ps+pc共同表示了高k位，最終輸出結(jié)果應為mult={ps+pc,p}。

圖1 基于CSA的移位加乘法器的電路結(jié)構(gòu)圖

由于這種乘法器的實現(xiàn)形式屬于每個時鐘只進行了一次迭代運算，雖然在芯片面積上開銷小，但速度欠缺，比如：完成一次192位的兩個大數(shù)相乘運算大概需要浪費192個時鐘，完成一次運算花費0.702 μs，大約1 s可以進行142萬次乘法運算。

3 進位存儲乘法器的改進及其硬件設計

一般來說，按照硬件實現(xiàn)的結(jié)構(gòu)來分，大數(shù)相乘可以分為全串行結(jié)構(gòu)、全并行結(jié)構(gòu)和串并混合結(jié)構(gòu)[11]。全并行結(jié)構(gòu)一般要求在一個時鐘周期內(nèi)完成全部的計算過程，這樣的實現(xiàn)方式雖然在時間上有很大提高，但代價是龐大的硬件開銷，因此，一般只具有理論研究意義。全串行結(jié)構(gòu)是在每個時鐘周期只完成一次迭代計算，故需要很多個時鐘周期，所以這種形式計算大數(shù)乘法雖然在硬件開銷上相對于全并行結(jié)構(gòu)少很多，但在時間上是不如全并行結(jié)構(gòu)的計算速度。

綜合考慮，最好的實現(xiàn)方案應當是：結(jié)合硬件開銷和時間的最優(yōu)匹配下的一種串并混合結(jié)構(gòu)。

具體的實現(xiàn)原理：將進位存儲乘法器算法（圖1）中的一個時鐘進行的一次迭代運算，共需要多個時鐘才能完成一組大數(shù)乘法運算的這個過程，通過合理設計轉(zhuǎn)化為一個時鐘可以執(zhí)行多步迭代運算，簡單來說，就是將m位大數(shù)相乘需要m個時鐘執(zhí)行的m次迭代運，轉(zhuǎn)化成一個時鐘執(zhí)行k步的迭代運算，即位數(shù)和步數(shù)之間的關系可由m=k×n+r表示。圖2以192位，2步結(jié)構(gòu)為例，說明了k步計算的核心結(jié)構(gòu)，其中192-CSA結(jié)構(gòu)代表了圖1中的全加器和寄存器模塊，圖2中 p是由192 bit-CSA的輸出依次從左向右順序移入兩位（此處是兩步運算）。

4 大數(shù)乘法的硬件實現(xiàn)結(jié)果

實驗的軟件平臺是基于QuartusII9.0，硬件平臺選擇ALTERA公司的1.2 v的StratixII系列的器件EP2S90F1508C3，該器件含有72 768個邏輯單元。

圖2 192 bit的兩步運算結(jié)構(gòu)

實驗證明，采用串并混合結(jié)構(gòu)的大數(shù)乘法器，可以有效提高乘法運算的硬件實現(xiàn)速度。本文分別對192位、256位以及384位的大數(shù)乘法器進行了性能分析。表1給出了在不同步長k的條件下，192位的大數(shù)乘法運算的各項指標，即，所需要的時鐘數(shù)（clk）、面積（LUTs）、器件的時鐘頻率 f（MHz）以及所耗費的時間t（μs）（進行一次運算所耗費的時間）。表1表明，隨著步數(shù)k的增大，雖然占用邏輯資源LUTs數(shù)目在逐步增大，但計算一組大數(shù)乘法運算的時間總體上呈下降趨勢。

表1 m=192時，不同步長k下的乘法器性能分析

為了更清楚地分析該乘法器的性能，本文采用了一個新的性能指標——頻率-面積比FSR（Frequency-Slices Ratio），其中

該指標不僅很好地詮釋了完成一次乘法運算的次數(shù)、周期（頻率）以及LUTs數(shù)目間的關系，而且通過該性能指標可以得到一個最優(yōu)的占用邏輯資源與時間的折中方式，這有助于更好地衡量乘法器的性能。為了更加直觀，特給出圖3進行說明。從圖3中可看出，F(xiàn)SR剛開始隨著步數(shù)k的增大呈增長趨勢，但當k繼續(xù)增大，由于此時的面積開銷大，故呈急速的下降狀態(tài)，值得注意的是，圖中的最高點應是時間與硬件資源開銷的最優(yōu)匹配，此時 k=5，頻率/s/面積=2 326，頻率 f=216.03 MHz，進行一次乘法運算所花費的時間為0.185 μs，1 s可進行大約5 400 750次運算。

圖3 步長與頻率、LUTs之間的關系

同樣，對位數(shù)m=256和m=384，進行了相同的性能分析，如表2和表3所示。

表2 m=256時，不同步長k下的乘法器性能分析

表3 m=384時，不同步長k下的乘法器性能分析

從表2可以看出，時間與硬件資源開銷的最優(yōu)匹配應為k=5時，此時頻率 f=195.92 MHz，進行一次乘法運算所花費的時間為0.271 μs，1 s可進行大約3 841 568次運算。

通過表3可以得到，時間與硬件資源開銷的最優(yōu)匹配應為k=2時，此時頻率 f=161.81 MHz，進行一次乘法運算所花費的時間為0.605 μs，1 s可進行大約165萬次運算。

為了更好地分析改進的算法相對于未改進算法的優(yōu)勢，特別給出了表4進行了乘法器的性能比較。通過選擇合適的步數(shù)得到了相應的速度，從表4中可以看出，在面積（LUTs）上，普通的CSA乘法器相對于改進后的CSA乘法器占用面積少，但是在速度上卻低很多，為了更好說明改進后的乘法器的優(yōu)勢，表4中指標FSR很好地衡量了速度與面積之間的關系，這表明本文在提高速度的同時也兼顧了面積增大所帶來的開銷，例如：當m=192時，改進前的乘法器速度為1 425 000次/s，LUTs為597，改進后的乘法器速度為5 400 000次/s，LUTs為2 321，雖然改進后的LUTs增大很多，但從速度上看，提高了3.79倍多，指標FSR在改進前后差別不大，說明本文所改進的乘法器保證了速度與面積的合理平衡[12]。除此而外，表4也清楚地展示出這種串并混合結(jié)構(gòu)的進位存儲乘法器在速度上相對普通的提高很多，得到最終結(jié)論：192位乘法器速度提高了3.79倍多（5 400 750/1 425 103=3.79），256位乘法器速度提高了5.41倍多，384位乘法器速度提高了2.79倍多。

表4 全串行結(jié)構(gòu)與串并混合結(jié)構(gòu)的對比

5 總結(jié)

本文利用串并混合結(jié)構(gòu)對進位存儲乘法器做了改進，減少了完成一次運算的時鐘數(shù)，從而有效地提高了乘法器的速度，此外，本文通過一個新的性能指標——FSR，很好地衡量了硬件資源與速率之間的關系，最后分別給出了192位、256位以及384位的硬件實現(xiàn)結(jié)果，通過FSR得到了最優(yōu)的乘法器速度，相比普通的進位存儲乘法器速度有很大改善。今后打算在素數(shù)域的模乘上應用此方法[13-14]，進一步改善模乘的速度，以便更好地應用于密碼算法的硬件實現(xiàn)中[15]。

[1]楊軍，余江，趙征鵬.基于FPGA密碼技術的設計與應用[M].北京：電子工業(yè)出版社，2012.

[2]丁順全，楊永福.一種快速大數(shù)乘法器的設計方法[J].紅河學院校報，2009，7（2）：51-55.

[3]谷理想.一種高性能乘法器的設計與研究[D].江蘇無錫：江南大學，2009.

[4]王金波，張文科.大數(shù)模乘硬件設計與FPGA高速實現(xiàn)[J].信息安全與通信保密，2005（7）：349-353.

[5]商麗衛(wèi)，劉耀軍.并行行旁路乘法器的設計與實現(xiàn)[J].微電子學與計算機，2012，29（8）：134-137.

[6]沈俊忠，肖濤，喬寓然，等.一種支持優(yōu)化分塊策略的矩陣乘加速器設計[J].計算機工程與科學，2016，38（9）：1748-1754.

[7]周磊濤，陶耀東，劉生，等.基于FPGA的Systolic乘法技術研究[J].計算機工程與科學，2015，37（9）：1632-1636.

[8]張榮花.素域上乘法器的FPGA設計與實現(xiàn)[D].西安：西安電子科技大學，2012.

[9]Deschamps J P，Imana J L，Sutter G D.Hardware implementation of finite-field arithmetic[M].[S.l.]：McGraw-Hill Inc，2009：66-74.

[10]Bessalah H，Messaoudi K，Issad M，et al.Left to right serial multiplier for large numbers on FPGA[C]//IEEE International Conference on Mechatronics，2009：288-293.

[11]高向強，馮春陽，閆鑫，等.一種面向64位 DSP處理器的可重構(gòu) ALU研究及設計[J].微電子學與計算機，2015（10）：1-6.

[12]Kang J Y，Gaudiot J L，Kang J Y，et al.A simple high-speed multiplier design[J].IEEE Transactions on Computers，2006，55（10）：1253-1258.

[13]廖望，萬美琳.可擴展雙域模乘器設計與研究[J].華中科技大學學報：自然科學版，2015，43（9）：51-54.

[14]Morales-Sandoval M，Diaz-Perez A.Scalable GF（p）montgomery multiplier based on a digit-digit computation approach[J].IET Computersamp;Digital Techniques，2016，10（3）：102-109.

[15]謝天藝，黃凱.素數(shù)域橢圓曲線密碼加速器的VLSI實現(xiàn)[J].計算機工程與應用，2016，52（1）：89-94.

ZHANG Xiaonan1,GAO Xianwei1，2,DONG Xiuze2

1.School of Telecommunication Engineering,Xidian University,Xi’an 710071,China 2.Department of Electronics,Beijing Electronics Scienceamp;Technology Institute,Beijing 100070,China

Improvement and implementation of carry-save large numbers multiplication on FPGA.Computer Engineering and Applications,2017,53（21）：58-61.

This paper proposes an improved algorithm of carry-save large numbers multiplication on FPGA,which can complete multiple iterations of operation in a clock with a serial-parallel hybrid structure.To some extent,reducing clocks to complete a operation,the structure improves the speed of the large numbers multiplication effectively.Finally,the results of the implementation of this multiplier for several operands sizes（192 bit,256 bit,384 bit）on Altera Stratix II EP2S90F1508C3 show that the time of 192 bit is 0.185 microsecond,256 bit is 0.271 microsecond,and 384 bit is 0.595 microsecond.As a result,the paper’s design is about 3.5 times than the previous design in speed.

large numbers multiplication;serial-parallel hybrid structure;multiple iterations;Field Programmable Gate Array（FPGA）

A

TP312

10.3778/j.issn.1002-8331.1606-0358

北京市自然科學基金（No.4163076）；北京電子科技學院校內(nèi)科研基金（No.2014TD1-DXZ）。

張曉楠（1992—），女，碩士，主要研究方向為各種密碼算法的FPGA實現(xiàn)，E-mail：zhangxiaonan1010@163.com；高獻偉（1974—），男，教授，主要研究領域為SOC與FPGA技術在通信中的應用等；董秀則（1975—），男，工程師，主要研究領域為SOC技術與信息安全技術。

2016-06-27

2016-09-05

1002-8331（2017）21-0058-04

CNKI網(wǎng)絡優(yōu)先出版：2016-12-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161221.0841.010.html