一種高效能可重構1 024 位大數乘法器的設計

蘇 成，夏 宏

（華北電力大學，北京 100096）

0 引言

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

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

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

1 64 位乘法單元的設計

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

圖1 乘法器結構

1.1 改進的基4-Booth 算法

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

本設計使用一種改進的部分積產生策略，使用三個信號X、Y和Z分別代表A、2A和正負。用A、B、C分別代表Bi+1、Bi、Bi-1，那么改進的部分積生成如表1 所示。

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

本乘法器設計改進的基4-Booth 算法譯碼電路可產生不同的中間積結果，譯碼之前首先將被乘數擴展，然后三位一次譯碼產生33 個中間積結果，其中-A、-2A的中間積結果是反碼，在中間積壓縮時進行補碼的處理。

1.2 Wallace 結構

Wallace 樹壓縮結構完成所有部分積的快速累加，生成求和與進位兩個結果，核心器件為壓縮器，最基本3-2壓縮器，本文設計的64 位乘法器使用8 級壓縮最終產生兩個128 位的部分積，如圖2 所示。

圖2 華萊壓縮樹8 級壓縮

1.3 加法器的設計

超前進位單元[10-13]的設計就是為了解決時延的問題，超前進位單元引入生成信號g（Generate）和傳播信號p（Propagate），g和p的表達式如式（2），進位表達式式（3）所示。

根據式（2）、式（3）由進位信號ci+1=gi+pici，可以推出四位進位位的邏輯表達式，如式（4）所示。

得出每位的進位邏輯表達式之后就可以通過并行計算的方式得出每位的“進位”以及“和”的結果，超前進位單元CLA 如圖3 所示?？梢酝ㄟ^式（5）對c4的表達式進行變形，從而可以得出進位鏈，進而用4 位的超前進位加法器擴展為16 位的超前進位加法器。

圖3 超前進位單元

用4 個16 位全加器，根據進位鏈的輸出Gm和Pm可以擴展成一個64 位的全加器，用兩個64 的超前進位加法器可以組成一個128 位的超前進位加法器，以上描述的不同位寬的超前進位單元在進行128 位加法時為并行運算。

2 1 024 位乘法器的設計

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

圖4 每個周期系統路徑

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

圖5 部分積的產生與壓縮

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

圖6 每個周期部分積流向

完成一個完整的1024 位大數乘只需要6 種壓縮電路：PA1、PA2、PA3、PA5、PA16、PA17，其余周期的情況均包含于這6 種內?；谠摲椒ǖ某朔ㄆ骺梢詫崿F電路復用，大大縮小壓縮部分的電路面積。

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

圖7 加法器陣列設計

3 仿真測試

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

圖8 64 位乘法單元測試

1 024 位大數乘法器測試波形如圖9 所示，實現了計算結果分段逐次產生，且產生周期與上文相符，功能仿真通過。

圖9 1 024 位乘法器波形

本設計的綜合使用SMIC 0.18 μm 標準閾值電壓的數字工藝庫，25℃環境溫度下，使用Synopsys Design Complier 完成，工藝角為SSG，電路面積、功耗與關鍵路徑延遲匯總如表2 所示。

表2 系統參數與對比

4 結論

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