一種高效能可重構(gòu)1 024 位大數(shù)乘法器的設(shè)計(jì)

蘇 成，夏 宏

（華北電力大學(xué)，北京 100096）

0 引言

隨著FPGA 工藝的不斷發(fā)展，在處理冗雜數(shù)據(jù)中使用硬件加速逐漸成為研究熱點(diǎn)。乘法作為加密算法的重要組成部分[1]，其硬件消耗和時(shí)間開銷很大程度上影響著整個(gè)加密算法的性能。我國于2017 年頒布的《SM9標(biāo)識(shí)密碼算法》中，多次使用了1 024 位大數(shù)乘法[2]。

Michael J.Flynnz 等在1982 年建立的快速乘法器模型中，將其分為三個(gè)部分：使用Booth 編碼消減部分積數(shù)量，對(duì)部分積進(jìn)行壓縮，最終部分積相加，這也是現(xiàn)主流的乘法器[3-9]設(shè)計(jì)思路。該種乘法器當(dāng)參與大數(shù)乘法時(shí)，部分積的壓縮電路面積明顯增大，最終部分積相加時(shí)，大數(shù)加法關(guān)鍵電路延時(shí)過大，也會(huì)拖慢整個(gè)系統(tǒng)的速度，而如果使用傳統(tǒng)乘累加的方法，進(jìn)行上百次位移加法運(yùn)算會(huì)帶來巨大的開銷。

本文改進(jìn)了基4-Booth 電路，以此設(shè)計(jì)了64 位乘法單元。采用16 個(gè)64 位乘法單元，2 個(gè)128 位混合進(jìn)位加法器，將1 024 位乘法分為多個(gè)周期流水進(jìn)行，分批次產(chǎn)生部分積，同時(shí)對(duì)已產(chǎn)生的部分積進(jìn)行壓縮和求和。該方法復(fù)用了乘法單元和壓縮電路，極大地減少了硬件資源壓力。同時(shí)，分批次產(chǎn)生結(jié)果，將最終加法拆分在每個(gè)周期中進(jìn)行，避免了大數(shù)加法導(dǎo)致的延時(shí)。本設(shè)計(jì)在SMIC 0.18 μm 工藝庫仿真下，電路面積及能耗均優(yōu)于傳統(tǒng)設(shè)計(jì)方法。

1 64 位乘法單元的設(shè)計(jì)

該乘法器用作64×64 位無符號(hào)的乘法運(yùn)算，主要由部分積產(chǎn)生（基4-Booth 算法編碼/譯碼）、部分積壓縮（Wallace 樹壓縮結(jié)構(gòu)）和超前進(jìn)位加法器組成。乘法器結(jié)構(gòu)如圖1 所示。其中Booth 譯碼采用的是基4 譯碼法則，將二進(jìn)制的64×64 位數(shù)據(jù)輸入到Booth 譯碼模塊中，產(chǎn)生33 個(gè)中間積組成的規(guī)則陣列，并使用全加器為基礎(chǔ)的3-2Wallace 樹，最終壓縮為兩組結(jié)果，使用超前進(jìn)位加法器得到最后的結(jié)果。

圖1 乘法器結(jié)構(gòu)

1.1 改進(jìn)的基4-Booth 算法

Booth 算法由譯碼和部分積產(chǎn)生兩部分組成，通過3位一次譯碼的形式將64 bit 的乘數(shù)編譯33 次，譯碼之后產(chǎn)生編碼為A（被乘數(shù)）、2A、-A、-2A和0 五個(gè)信號(hào)作為部分積的值。

本設(shè)計(jì)使用一種改進(jìn)的部分積產(chǎn)生策略，使用三個(gè)信號(hào)X、Y和Z分別代表A、2A和正負(fù)。用A、B、C分別代表Bi+1、Bi、Bi-1，那么改進(jìn)的部分積生成如表1 所示。

根據(jù)以上真值表，通過卡諾圖，化簡(jiǎn)變形可以得到X、Y、Z的布爾表達(dá)式，如式（1）所示。

本乘法器設(shè)計(jì)改進(jìn)的基4-Booth 算法譯碼電路可產(chǎn)生不同的中間積結(jié)果，譯碼之前首先將被乘數(shù)擴(kuò)展，然后三位一次譯碼產(chǎn)生33 個(gè)中間積結(jié)果，其中-A、-2A的中間積結(jié)果是反碼，在中間積壓縮時(shí)進(jìn)行補(bǔ)碼的處理。

1.2 Wallace 結(jié)構(gòu)

Wallace 樹壓縮結(jié)構(gòu)完成所有部分積的快速累加，生成求和與進(jìn)位兩個(gè)結(jié)果，核心器件為壓縮器，最基本3-2壓縮器，本文設(shè)計(jì)的64 位乘法器使用8 級(jí)壓縮最終產(chǎn)生兩個(gè)128 位的部分積，如圖2 所示。

圖2 華萊壓縮樹8 級(jí)壓縮

1.3 加法器的設(shè)計(jì)

超前進(jìn)位單元[10-13]的設(shè)計(jì)就是為了解決時(shí)延的問題，超前進(jìn)位單元引入生成信號(hào)g（Generate）和傳播信號(hào)p（Propagate），g和p的表達(dá)式如式（2），進(jìn)位表達(dá)式式（3）所示。

根據(jù)式（2）、式（3）由進(jìn)位信號(hào)ci+1=gi+pici，可以推出四位進(jìn)位位的邏輯表達(dá)式，如式（4）所示。

得出每位的進(jìn)位邏輯表達(dá)式之后就可以通過并行計(jì)算的方式得出每位的“進(jìn)位”以及“和”的結(jié)果，超前進(jìn)位單元CLA 如圖3 所示。可以通過式（5）對(duì)c4的表達(dá)式進(jìn)行變形，從而可以得出進(jìn)位鏈，進(jìn)而用4 位的超前進(jìn)位加法器擴(kuò)展為16 位的超前進(jìn)位加法器。

圖3 超前進(jìn)位單元

用4 個(gè)16 位全加器，根據(jù)進(jìn)位鏈的輸出Gm和Pm可以擴(kuò)展成一個(gè)64 位的全加器，用兩個(gè)64 的超前進(jìn)位加法器可以組成一個(gè)128 位的超前進(jìn)位加法器，以上描述的不同位寬的超前進(jìn)位單元在進(jìn)行128 位加法時(shí)為并行運(yùn)算。

2 1 024 位乘法器的設(shè)計(jì)

處理1 024 位乘法時(shí)，常規(guī)的乘累加硬件結(jié)構(gòu)將會(huì)面臨多次1 024 位加法，即使是改進(jìn)后的Booth 譯碼與壓縮的方法，也會(huì)剩余兩個(gè)2 048 位的大數(shù)相加，其關(guān)鍵路徑延時(shí)和版圖復(fù)雜度都是不可接受的。本文采用流水設(shè)計(jì)思路，將1 024 位的乘數(shù)分為4×256 bit，每個(gè)周期系統(tǒng)吞入一組256 位的乘數(shù)A與B，共需16 次吞吐完成整個(gè)1 024 位乘法。每個(gè)周期內(nèi)的系統(tǒng)路徑如圖4 所示。系統(tǒng)整體流程為，先用64 位乘法單元計(jì)算256 位乘法，再將部分積壓縮至兩行。若之后周期沒有相同位的部分積產(chǎn)生，則置入加法器，否則置入臨時(shí)寄存器，等待下一位部分積繼續(xù)壓縮，直到符合加法條件。

圖4 每個(gè)周期系統(tǒng)路徑

處理256 bit×256 bit 乘法，共需16 個(gè)64 bit 乘法器，該乘法器陣列（64 bit multiplier）負(fù)責(zé)將每個(gè)周期吞入的256 bit 乘數(shù)計(jì)算出部分積，由于關(guān)鍵工藝路徑較長(zhǎng)，此處插入一級(jí)段寄存器。在乘法器繼續(xù)產(chǎn)出的同時(shí)，上一周期的部分積通過華萊士樹陣列壓縮為兩組8×64 位的結(jié)果（C0～7 與D0～7），如圖5 所示。

圖5 部分積的產(chǎn)生與壓縮

該部分積有兩處數(shù)據(jù)流向，當(dāng)后續(xù)周期內(nèi)沒有與該位相關(guān)的部分積產(chǎn)生時(shí)，直接送入加法器陣列（Adders set），加法器將在下個(gè)周期計(jì)算得到該位的最終結(jié)果，并保存進(jìn)位（Count Chain）。反之，將部分積送入臨時(shí)寄存器，等待下一個(gè)部分積到來后繼續(xù)進(jìn)行壓縮。每個(gè)周期產(chǎn)生的部分積及相關(guān)處理如圖6 所示，其中每個(gè)點(diǎn)代表兩列4×64 位的數(shù)（如C0～C3 和D0～D3）。

圖6 每個(gè)周期部分積流向

完成一個(gè)完整的1024 位大數(shù)乘只需要6 種壓縮電路：PA1、PA2、PA3、PA5、PA16、PA17，其余周期的情況均包含于這6 種內(nèi)。基于該方法的乘法器可以實(shí)現(xiàn)電路復(fù)用，大大縮小壓縮部分的電路面積。

加法電路（Adders set）負(fù)責(zé)將無需再壓縮的部分積相加，通過圖6 可知每次進(jìn)入加法陣列的數(shù)均為4 組64位數(shù)，因此需要256 位加法器。在1.3 節(jié)中已經(jīng)給出128位超前進(jìn)位加法器的設(shè)計(jì)，將128 位繼續(xù)擴(kuò)展為256 位會(huì)帶來布線問題，也會(huì)造成關(guān)鍵路徑過長(zhǎng)，影響主頻。因此采用2 個(gè)128 位加法器并聯(lián)運(yùn)行，其中高128 位加法器采用Challa Ram 等設(shè)計(jì)的進(jìn)位選擇加法器[14]，同時(shí)計(jì)算A+B與A+B+1，再由低128 位加法器進(jìn)位選通得到結(jié)果，如圖7 所示。

圖7 加法器陣列設(shè)計(jì)

3 仿真測(cè)試

本文設(shè)計(jì)的乘法器使用Verilog 語言進(jìn)行描述，邏輯仿真在Modelsim 進(jìn)行。首先基于Pradnya Zode 等[15]提出的遞歸乘法器功能仿真方法，對(duì)64 位乘法單元和128位加法器進(jìn)行了可靠性測(cè)試，使用隨機(jī)數(shù)產(chǎn)生器并驗(yàn)證最終結(jié)果，測(cè)試產(chǎn)生數(shù)據(jù)集大小為9 萬組，如圖8 所示。

圖8 64 位乘法單元測(cè)試

1 024 位大數(shù)乘法器測(cè)試波形如圖9 所示，實(shí)現(xiàn)了計(jì)算結(jié)果分段逐次產(chǎn)生，且產(chǎn)生周期與上文相符，功能仿真通過。

圖9 1 024 位乘法器波形

本設(shè)計(jì)的綜合使用SMIC 0.18 μm 標(biāo)準(zhǔn)閾值電壓的數(shù)字工藝庫，25℃環(huán)境溫度下，使用Synopsys Design Complier 完成，工藝角為SSG，電路面積、功耗與關(guān)鍵路徑延遲匯總?cè)绫? 所示。

表2 系統(tǒng)參數(shù)與對(duì)比

4 結(jié)論

本文設(shè)計(jì)了改良的64 位乘法器，并以此為乘法單元組成了1 024 位大數(shù)乘法，使用流水線策略減小器件的使用，同時(shí)實(shí)現(xiàn)部分器件的復(fù)用。經(jīng)仿真綜合，本文設(shè)計(jì)與傳統(tǒng)乘累加和Booth 譯碼Wallace 壓縮相比，電路面積和功耗明顯降低，關(guān)鍵電路延時(shí)也略有改善，可以適配更高主頻的情況。對(duì)于任意位數(shù)大數(shù)相乘來說，本文的方法均可以起到一定的優(yōu)化效果，但具體使用多少乘法單元與加法器配合才能更好地復(fù)用器件，達(dá)到最優(yōu)化的面積與能耗，仍然是建立大數(shù)乘法設(shè)計(jì)模型的研究重點(diǎn)。