張清宇，李 磊

(電子科技大學(xué) 電子科學(xué)技術(shù)研究院，四川 成都 611731)

一種高速模(2n-2p-1)乘法器的設(shè)計(jì)

張清宇，李 磊

(電子科技大學(xué) 電子科學(xué)技術(shù)研究院，四川 成都 611731)

結(jié)合余數(shù)系統(tǒng)以及模乘法器本身的特點(diǎn)，一種高速的模(2n-2p-1)乘法器被提出。得益于剩余范圍的擴(kuò)展和新型的部分積壓縮樹(shù)的采用，該設(shè)計(jì)相較于傳統(tǒng)的模乘法器在關(guān)鍵路徑上減少了一個(gè)長(zhǎng)度為2n的加法器且避免了此類 Booth編碼模乘法器中復(fù)雜的負(fù)數(shù)修正問(wèn)題。在90 nm工藝下的綜合結(jié)果表明，該模乘(2n-2p-1)乘法器相較當(dāng)前的模(2n-2p-1)乘法器有10.4%到49%的延遲性能提升。

余數(shù)系統(tǒng)；剩余范圍擴(kuò)展；部分積壓縮樹(shù)

0 引言

余數(shù)系統(tǒng)作為一種數(shù)值表征系統(tǒng)，憑借其在并行計(jì)算、數(shù)字信號(hào)處理以及大規(guī)模集成電路等領(lǐng)域的潛在應(yīng)用前景，受到了廣泛的研究。近些年來(lái)，隨著冗余余數(shù)系統(tǒng)(Redundant Residue Number System，RRNS)及其相關(guān)算法在糾錯(cuò)領(lǐng)域的不斷應(yīng)用，余數(shù)基的選擇和構(gòu)建變得愈發(fā)重要。模乘單元的性能對(duì)于一種基的選擇和構(gòu)建起到了關(guān)鍵的作用，如何提供更多形式的高速模乘法器成為了余數(shù)系統(tǒng)發(fā)展的關(guān)鍵問(wèn)題之一。

2n-2p±1形式的基可以構(gòu)建出高平衡度的余數(shù)基，是RRNS中最常用的一種基。其對(duì)應(yīng)的乘法器也已經(jīng)被廣泛的研究。在文獻(xiàn)[4]中，一種通用形式的模乘法器被提出，雖然可以用來(lái)構(gòu)造模(2n-2p-1)乘法器，但是效果不佳。在文獻(xiàn)[5]中，我們提出了一種剩余范圍的擴(kuò)展方法，通過(guò)這種方法，在沒(méi)有開(kāi)銷的情況下將剩余范圍從[0，2n-2p-1]擴(kuò)展到[0，2n-1]，為化簡(jiǎn)模(2n-2p-1)乘法器的結(jié)構(gòu)提供了便利。在文獻(xiàn)[6，7]中，基于Booth編碼的模(2n-2p-1)乘法器被提出，但是由于 Booth編碼引入了負(fù)數(shù)，而負(fù)數(shù)在模乘法器中的修正問(wèn)題會(huì)造成較大的性能損失。文獻(xiàn)[8]提出了一種高效且利于 EDA實(shí)現(xiàn)的TDM壓縮樹(shù)(Three Dimensional Minimization，TDM)算法?？紤]到余數(shù)系統(tǒng)中乘法器是無(wú)符號(hào)的且位數(shù)不高(通常小于32)，采用非Booth編碼的TDM壓縮樹(shù)結(jié)構(gòu)反而可以起到很好的效果。本文提出的模(2n-2p-1)乘法器沿用了剩余范圍的擴(kuò)展方法，采用 TDM壓縮樹(shù)解決[6，7]中出現(xiàn)的負(fù)數(shù)修正問(wèn)題，取得了較大的性能提升。

本文首先介紹TDM壓縮樹(shù)及剩余范圍的擴(kuò)展方法，然后提出高速模(2n-2p-1)乘法器的結(jié)構(gòu)并給出結(jié)構(gòu)圖，最后進(jìn)行分析對(duì)比。

1 TDM壓縮樹(shù)算法

在全加器中，不同輸入端到不同輸出端的延遲是不同的。文獻(xiàn)[8]中提出TDM算法可以將壓縮樹(shù)中不同全加器的最長(zhǎng)延遲路徑和最短延遲路徑相連接。這種算法可以很方便地用腳本實(shí)現(xiàn)，具有通用性。為了解決布局布線的不規(guī)整的問(wèn)題，TDM算法支持將全加器替換為4：2或者其他形式的壓縮器，以進(jìn)一步提升速度。最終通過(guò)TDM壓縮樹(shù)可以將部分積(Partial Product，PP)壓縮至兩行。需要注意的是，雖然相較文獻(xiàn)[6，7]中采用的Booth編碼的混合型壓縮結(jié)構(gòu)，TDM壓縮樹(shù)會(huì)產(chǎn)生較大的面積，但是考慮到Booth編碼引入負(fù)數(shù)所帶來(lái)的復(fù)雜修正問(wèn)題，這些面積會(huì)被抵消且總的延遲更小。

2 剩余范圍的擴(kuò)展方法

對(duì)于任意整數(shù) X，有〈X〉2n-2p-1=x，x∈[0，2n-2p-1]。也就是說(shuō)，模(2n-2p-1)的剩余范圍是[0，2n-2p-1]。為了化簡(jiǎn)運(yùn)算，可以將剩余范圍擴(kuò)展到[0，2n-1]。因?yàn)橛小?n-2p-1+i〉2n-2p-1=i，i∈[1，2p+1]，這樣就可以使用2n-2p-1+i在乘法器中來(lái)表示 i。圖1所示的 RNS系統(tǒng)中，這種擴(kuò)展并不會(huì)產(chǎn)生計(jì)算錯(cuò)誤，并且很容易在后向轉(zhuǎn)換中進(jìn)行修正。通過(guò)使用這種擴(kuò)展方法，可以化簡(jiǎn)模(2n-2p-1)乘法器的結(jié)構(gòu)，避免了重復(fù)將[2n-2p-1，2n-1]修正到[1，2p]所帶來(lái)的浪費(fèi)。

圖1 RNS系統(tǒng)框圖

3 高速模(2n-2p-1)乘法器的結(jié)構(gòu)

假設(shè)A[n-1:0]是乘數(shù)，B[n-1:0]是被乘數(shù)，A[n-1:0]× B[n-1:0]所產(chǎn)生的 PP被 TDM壓縮樹(shù)壓縮至兩列，分別為 P0[2n-2:0]，P1[2n-2:0]。模(2n-2p-1)乘法器可以被表示為：

其中H0[n-2:0]，L0[n-1:0]分別代表 P0[2n-2:0]的高n-1位和低n位。H1[n-2:0]，L1[n-1:0]分別代表P1[2n-2:0]的高n-1位和低n位。根據(jù)文獻(xiàn)[5]中模(2n-2p-1)乘法器的性質(zhì)，有：

其中符號(hào)#用來(lái)連接各比特位。將式(2)、式(3)帶入式(1)，可以進(jìn)一步得到：

將式(4)中前四項(xiàng)和后四項(xiàng)分別兩個(gè)(n-1)位的 CSA和兩個(gè)n位的CSA進(jìn)行處理，可以得到：

其中 MH[n-1:0]，ML[n-1:0]為兩個(gè)(n-1)位的 CSA的輸出，NH[n:0]，NL[n:0]為兩個(gè)(n-1)位的 CSA的輸出。NH[n:0]和NL[n:0]可以進(jìn)一步折疊：

將四個(gè)n位的部分項(xiàng)MH[n-1:0]，ML[n-1:0]，NH[n-1:0]以及 ML[n-1:0]繼續(xù)用兩個(gè) n位 CSA進(jìn)行處理，得到：

其中RH[n:0]和 RL[n:0]為這兩個(gè)n位CSA產(chǎn)生的輸出且可以繼續(xù)折疊：

令 C[2:0]=NH[n]+NL[n]+RH[n]+RL[n]，式(9)產(chǎn)生的四個(gè)部分項(xiàng)可以進(jìn)一步用一個(gè)n位CSA壓縮：

將得到的SH[n-1:0]修正為：

將 SH[n-2:0]#SH[n-1]和 SL[n-1:0]用一個(gè) n位二進(jìn)制加法器相加得到R[n:0]：

繼續(xù)對(duì)R[n:0]折疊：

最終，得到最后結(jié)果Y[n-1:0]：

其中M=R[n]+SH[n-1]。實(shí)驗(yàn)證明當(dāng)n≥2p時(shí)，結(jié)果不會(huì)溢出。整體結(jié)構(gòu)如圖2所示，在關(guān)鍵路徑上包含1個(gè)TDM壓縮樹(shù)，5個(gè)CSA，以及2個(gè)n位的二進(jìn)制加法器。

圖2 模(2n-2p-1)乘法器的結(jié)構(gòu)

4 分析與比較

我們將本文提出的模(2n-2p-1)乘法器和文獻(xiàn)[4，5，6，7]中的模乘法器進(jìn)行對(duì)比分析。所有的模乘法器都采用Verilog硬件描述語(yǔ)言進(jìn)行建模，并采用Design Complier在90 nm COMS工藝下進(jìn)行綜合。

綜合結(jié)果表明，相較于文獻(xiàn)[4]中的設(shè)計(jì)，本設(shè)計(jì)的平均延遲降低49%，平均面積降低了 5.1%。與文獻(xiàn)[5]中的設(shè)計(jì)相比，本設(shè)計(jì)的平均延遲降低了 10.4%，但是平均面積提升了 4.5%。和文獻(xiàn)[6]相比，本設(shè)計(jì)平均延遲降低了23.2%而平均面積降低了26.1%。與文獻(xiàn)[7]進(jìn)行比較，本設(shè)計(jì)平均延遲降低了 10.3%，平均面積提升了1.3%。

文獻(xiàn)[5，7]中的兩種設(shè)計(jì)是兩種典型的高效模(2n-2p-1)乘法器，下面將著重對(duì)本設(shè)計(jì)以及文獻(xiàn)[5，7]進(jìn)行靜態(tài)分析。設(shè)計(jì)[5，7]都包含一個(gè) Booth編碼的壓縮樹(shù)，而本設(shè)計(jì)包含一個(gè)非 Booth的TDM壓縮樹(shù)，這兩種結(jié)構(gòu)的延遲相差不大。比較重點(diǎn)放在產(chǎn)生兩個(gè)2n-1位PP后的路徑，我們稱之為關(guān)鍵路徑。文獻(xiàn)[5]的關(guān)鍵路徑包含1個(gè)2n位二進(jìn)制加法器，1個(gè)CSA，3個(gè)n位二進(jìn)制加法器。文獻(xiàn)[7]的關(guān)鍵路徑包含 6個(gè) CSA和三個(gè)二進(jìn)制加法器。與文獻(xiàn)[5]相比，本設(shè)計(jì)在關(guān)鍵路徑上使用四個(gè)CSA替代了一個(gè)2n位的大加法器和一個(gè)n位的小加法器。與文獻(xiàn)[7]相比，本設(shè)計(jì)在關(guān)鍵路徑上減少了一個(gè)CSA和一個(gè)2n位加法器。采用文獻(xiàn)[4]中的單位門評(píng)估方法，具體結(jié)果如表1所示。

圖3 p=3時(shí)模(2n-2p-1)乘法器的延遲性能

圖4 p=4時(shí)模(2n-2p-1)乘法器的延遲性能

表1 靜態(tài)時(shí)序分析

5 結(jié)論

得益于剩余范圍的擴(kuò)展和TDM壓縮樹(shù)的使用，本設(shè)計(jì)沒(méi)有使用復(fù)雜的模加法器且避免了負(fù)數(shù)修正問(wèn)題。相較于當(dāng)前的模(2n-2p-1)乘法器有較大的延遲性能提升，是目前已知的延遲性能最佳的模(2n-2p-1)乘法器。

[1]馬上，胡劍浩.余數(shù)系統(tǒng)在 VLSI設(shè)計(jì)中的基本問(wèn)題研究與進(jìn)展[C].中國(guó)通信集成電路技術(shù)與應(yīng)用研討會(huì)，2006.

[2]李磊，胡劍浩，敖思遠(yuǎn).高速Booth編碼模(2^n—1)乘法器的設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī)，2011，28(11)：191-193.

[3]胡劍浩，唐青.面向低電壓供電數(shù)字電路的容錯(cuò)計(jì)算系統(tǒng)結(jié)構(gòu)設(shè)計(jì)[J].電子科技大學(xué)學(xué)報(bào)，2013(6)：831-835.

[4]HIASAT A A.New efficient structure for a modular multiplier for RNS[J].IEEE Transactions on Computers，2000，49 (2)：170-174.

[5]LI L，HU J，CHEN Y.An universal architecture for designing modulo(2n-2p-1)multipliers[J].Ieice Electronics Express，2012，9(3)：193-199.

[6]LI L，LI S，YANG P，et al.Booth encoding modulo(2n-2p-1)multipliers[J].Ieice Electronics Express，2014，11(15).

[7]YAN H，LI L，ZHANG Q.A high speed modulo(2n-2p+1) multiplier design[J].Ieice Electronics Express，2015，12(23).

[8]OKLOBDZIJA V G，VILLEGER D，LIU S S.A method for speed optimized partial product reduction and generation of fast parallel multipliers using an algorithmic approach[J]. IEEE Transactions on Computers，1996，45(3)：294-306.

A high speed modulo(2n-2p-1)multiplier design

Zhang Qingyu，Li Lei
(Research Institute of Electronic Science and Technology，University of Electronic Science and Technology of China，Chengdu 611731，China)

Based on the features of residue number systems(RNS)and modular multipliers,a high speed architecture which is more suitable for design high speed modulo(2n-2p-1)multipliers is proposed.Leveraging the novel partial production reduction tree,we eliminate the complicated correction components which is introduced to correct negative number without performance loss.On the other hand,At the cost of two Carry Save Adders(CSAs)on the critical path,we reduce the delay of a 2n-bit binary adder. Compared with the current modulo(2n-2p-1)multipliers,synthesized results in which based on 90 nm process technology demonstrate that the proposed(2n-2p-1)multipliers can achieve a 10.4%～49%delay saving.

residue number systems(RNS)；residue set extending；partial production reduction tree

TN402

A

10.16157/j.issn.0258-7998.2016.11.037

張清宇，李磊 .一種高速模(2n-2p-1)乘法器的設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2016，42(11)：137-140.

英文引用格式：Zhang Qingyu，Li Lei.A high speed modulo(2n-2p-1)multiplier design[J].Application of Electronic Technique，2016，42(11)：137-140.

2016-08-02)

張清宇(1990-)，男，碩士研究生，主要研究方向：專用集成電路(ASIC)和SOC設(shè)計(jì)。

李磊(1983-)，男，博士，副研究員，主要研究方向：專用集成電路(ASIC)和SOC設(shè)計(jì)。