高基Montgomery模乘陣列結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)*

鄔貴明，謝向輝，吳 東，鄭 方，嚴(yán)忻愷

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室， 江蘇 無錫 214125)

高基Montgomery模乘陣列結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)*

鄔貴明，謝向輝，吳 東，鄭 方，嚴(yán)忻愷

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室， 江蘇 無錫 214125)

提出了兩種高基Montgomery模乘線性陣列結(jié)構(gòu)。兩種線性陣列結(jié)構(gòu)分別利用兩種不同的并行化開發(fā)方法，沿不同的循環(huán)維度進(jìn)行任務(wù)分配和調(diào)度，都能夠充分開發(fā)算法的流水線并行。在Xilinx XC5VLX330 FPGA上實(shí)現(xiàn)了兩種256位寬、基為216的模乘陣列結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，兩種結(jié)構(gòu)具有84個(gè)時(shí)鐘周期的延遲，吞吐率分別為1/17和1/21，與相關(guān)結(jié)構(gòu)相比吞吐率更高。兩種結(jié)構(gòu)在性能和實(shí)現(xiàn)代價(jià)間能夠達(dá)到合理平衡。

模乘；線性陣列結(jié)構(gòu)；現(xiàn)場(chǎng)可編程陣列；流水化

1 引言

最常用的模乘算法是Montgomery模乘算法[1]，在軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)兩方面都非常高效。它使用簡(jiǎn)單的移位操作來代替更費(fèi)時(shí)的除法操作，使用部分結(jié)果加模數(shù)倍數(shù)的方法來代替部分結(jié)果減模數(shù)倍數(shù)的方法，其好處是加法操作在被乘數(shù)的最低位處理后就可以立即開始，不用等到所有位處理完再開始，這一特性有利于開發(fā)并行性。

目前，學(xué)術(shù)界提出了大量Montgomery模乘硬件加速結(jié)構(gòu)，這些結(jié)構(gòu)可分為以下幾類：基2模乘結(jié)構(gòu)、多字基2模乘結(jié)構(gòu)、高基模乘結(jié)構(gòu)和采用大整數(shù)乘法器的模乘結(jié)構(gòu)。1999年Tenca A F和 Ko? ? K[2]首次提出一種多字基2的Montgomery乘法算法和硬件實(shí)現(xiàn)，當(dāng)操作數(shù)為n位時(shí)，一次Montgomery模乘需要2n個(gè)時(shí)鐘周期。為降低計(jì)算延遲，大量研究人員基于Tenca A F和Ko? ? K的工作進(jìn)行改進(jìn)，其中Huang M[3]的工作最為突出，利用最高位的兩種可能性預(yù)先對(duì)部分結(jié)果進(jìn)行計(jì)算，將一次Montgomery模乘運(yùn)行時(shí)間降為n個(gè)時(shí)鐘周期，性能提升了1倍。基于經(jīng)典的多字基2硬件結(jié)構(gòu)，還有研究人員提出了多字基4的結(jié)構(gòu)，但由于這些算法和結(jié)構(gòu)的基比較低，計(jì)算延遲比較長(zhǎng)，無法滿足高性能結(jié)構(gòu)的需求。在高基Montgomery模乘結(jié)構(gòu)方面，McIvor C等[4]提出了高基Montgomery模乘算法和Systolic陣列結(jié)構(gòu)，但該結(jié)構(gòu)不能流水化連續(xù)處理多個(gè)模乘運(yùn)算，仍然存在資源無法充分利用的問題。Zhou L[5]在Huang M[3]所提結(jié)構(gòu)基礎(chǔ)上擴(kuò)展實(shí)現(xiàn)了高基模乘結(jié)構(gòu)，由于關(guān)鍵路徑上多了一個(gè)加法操作和一個(gè)乘法操作，導(dǎo)致運(yùn)行性能較低。

本文提出了兩種高基Montgomery模乘流水化陣列結(jié)構(gòu)，兩種結(jié)構(gòu)分別在吞吐率和實(shí)現(xiàn)代價(jià)方面各有優(yōu)勢(shì)。

2 Montgomery算法

2.1 算法概要

給定兩個(gè)整數(shù)M和R，R>M且R和M互素，R為2n。兩個(gè)整數(shù)X和Y(X

步驟1t=XY；

步驟2m=t(-M-1modR) modR；

步驟3u=(t+mM)/R；

步驟4若u>M，則輸出u-M，否則輸出u。

模R和除R運(yùn)算只需通過簡(jiǎn)單的截取和移位就能實(shí)現(xiàn)，避免了耗時(shí)的除法運(yùn)算。

2.2 基2 Montgomery模乘

上述步驟的可實(shí)現(xiàn)性較差，算法1為實(shí)現(xiàn)性更強(qiáng)的基2 Montgomery模乘，算法中Y為被乘數(shù)，X為乘數(shù)，n為M的位數(shù)，y0為Y的最后一位，z0為Z的最后一位，⊕為邏輯異或操作。文獻(xiàn)[3]給出了該算法的推導(dǎo)過程。

算法1基2 Montgomery模乘

Output:Z=XYR-1modM。

1:Z=0

2:fori=0ton-1do{

3: qi=(xiy0)⊕z0

4: Z=(Z+xiY+qiM)/2}

5:IfZ≥Mthen

6: Z=Z-M

BatinaL和WalterCD等人[6,7]證明，當(dāng)X, Y<2M且R>4M時(shí)，XY2-n(modM) < 2M。算法中最后一步的減法可以避免，乘法結(jié)果可以直接作為下一個(gè)乘法的輸入，注意這時(shí)的R已不再等于2n。這里假設(shè)R=2l，則l ≥ n+2，一般會(huì)選擇l=n+2。算法2[8]給出了R =2n+2時(shí)不需要最后減法的Montgomery模乘算法。算法2中xn+1= 0，其輸入X和Y、輸出Z都在[0, 2M-1]范圍內(nèi)。

算法2不需要減法的基2Montgomery模乘

Output:Z=XYR-1mod2M。

1:Z=0

2:fori=0ton+1do{

3: qi=(xiy0)⊕z0

4: Z=(Z+xiY+qiM)/2}

2.3 多字基2Montgomery模乘

算法2中語句4的大整數(shù)Z、Y和M可以進(jìn)一步切分成多個(gè)字進(jìn)行表示，進(jìn)一步減少實(shí)現(xiàn)代價(jià)。TencaAF和Ko? ?K[2]首次提出了多字基2的Montgomery模乘算法。

算法3中語句8將Z(e)賦為0，是考慮到Z(e)的最低位要賦給Z(e-1)的最高位，不能將i上次迭代的結(jié)果誤傳給這次迭代。可以進(jìn)一步證明進(jìn)位C只需兩位就可以滿足計(jì)算要求。該算法R =2n時(shí)，并不能處理輸入X和Y都在[0, 2M-1]范圍內(nèi)的情況。

算法3多字基2Montgomery模乘

1:Z=0

2:fori=0ton-1do{

5:forj=1toedo{

8: Z(e)=0}

2.4 高基Montgomery模乘

高基Montgomery模乘可以進(jìn)一步降低多字基2的Montgomery模乘的算法復(fù)雜度。算法4給出了高基Montgomery模乘算法，算法中字長(zhǎng)為w，基為2w。由于R=2we> 4M，該算法能夠處理X, Y<2M的輸入。

算法4中的M′需要預(yù)先進(jìn)行計(jì)算。我們將語句3和4定義成任務(wù)A(i)，語句6和7定義成任務(wù)B(i,j)，則該算法的數(shù)據(jù)相關(guān)圖如圖1所示。同一列上的兩任務(wù)數(shù)據(jù)相關(guān)性由C引起，兩列之間的兩任務(wù)數(shù)據(jù)相關(guān)性由Z(j)引起。

算法4高基Montgomery模乘

1:Z=0

2:fori=0toe-1do{

3: qi=(Z(0)+X(i)Y(0))M′mod2w

4: (C,Z(0))=x(i)Y(0)+qiM(0)+Z(0)

5:forj=1toe-1do{

6: (C,Z(j))=C+X(i)Y(j)+qiM(j)+Z(j)

7: Z(j-1)=Z(j)}

8: Z(e-1)=C}

Figure 1 Data dependency graph of high radix Montgomery modular multiplication圖1 高基Montgomery模乘數(shù)據(jù)相關(guān)圖

3 素域高基Montgomery模乘陣列結(jié)構(gòu)設(shè)計(jì)

3.1 并行性開發(fā)

高基Montgomery模乘算法的并行性可通過兩種方法進(jìn)行開發(fā)。如果任務(wù)按照i循環(huán)進(jìn)行劃分，i循環(huán)的迭代將由處理單元PE完成，即圖1中每一列的計(jì)算將由一個(gè)PE完成，并行開發(fā)方法如圖2a所示。在該方法中，每個(gè)PE中用同一個(gè)X(i)參與計(jì)算，不同時(shí)間完成對(duì)Z不同段的計(jì)算。

Figure 2 Two approaches of exploiting parallelism圖2 兩種開發(fā)并行的方法

如果任務(wù)按照j循環(huán)進(jìn)行劃分，j循環(huán)的迭代(即j相同時(shí)i不同的所有迭代)將由PE完成，并行開發(fā)方法如圖2b所示。在這個(gè)方法中，每個(gè)PE中使用同一個(gè)Y(j)、M(j)和Z(j)參與計(jì)算，不同時(shí)間使用不同段的X(i)來參與對(duì)Z的同一段的更新。

3.2 素域高基Montgomery模乘陣列結(jié)構(gòu)

本文提出兩種線性陣列結(jié)構(gòu)分別實(shí)現(xiàn)圖2中兩種并行開發(fā)方法的調(diào)度過程，實(shí)現(xiàn)第一種調(diào)度的結(jié)構(gòu)稱為結(jié)構(gòu)1，實(shí)現(xiàn)第二種調(diào)度的結(jié)構(gòu)稱為結(jié)構(gòu)2，如圖3所示。

結(jié)構(gòu)1中的每個(gè)處理單元結(jié)構(gòu)相同，處理單元結(jié)構(gòu)見圖4。多個(gè)PE組織成流水線結(jié)構(gòu)形式，每個(gè)PE接收前一個(gè)PE傳遞來的數(shù)據(jù)和結(jié)果，并把數(shù)據(jù)和自身的計(jì)算結(jié)果傳遞給下一個(gè)PE。PE間傳遞的是Y(j)、M(j)和Z(j)，其中Y(j)、M(j)是傳遞來的輸入數(shù)據(jù)，而Z(j)是前一個(gè)PE的計(jì)算結(jié)果。

Figure 3 Two linear arrays圖3 兩種線性陣列結(jié)構(gòu)

Figure 4 Processing element of architecture 1圖4 結(jié)構(gòu)1的處理單元

該P(yáng)E結(jié)構(gòu)不同時(shí)刻形成不同的數(shù)據(jù)通路來完成不同任務(wù)。在該結(jié)構(gòu)中，任務(wù)A(i)需要三個(gè)節(jié)拍完成，第一拍完成P=(Z(0)+X(i)Y(0))運(yùn)算，第二拍完成qi= PM′，第三拍才開始執(zhí)行(C, Z(0))=X(i)Y(0)+ qiM(0)+ Z(0)，之后執(zhí)行任務(wù)B(i,j)，需要一拍完成，這樣PE之間的延遲為四拍，這是高基Montgomery模乘的缺點(diǎn)。多字基2Montgomery模乘算法的語句3是簡(jiǎn)單的邏輯運(yùn)算，而高基Montgomery模乘算法的語句3變成了兩個(gè)w字節(jié)的乘法和一個(gè)w字節(jié)的加法，計(jì)算延遲由忽略不計(jì)變成了兩個(gè)時(shí)鐘節(jié)拍。在TencaAF和Ko? ?K的結(jié)構(gòu)中,PE間的延遲為2拍，由于使用了預(yù)先計(jì)算的方法，HuangM的結(jié)構(gòu)變?yōu)?拍。而本文的結(jié)構(gòu)不可能使用預(yù)先計(jì)算的方法，在HuangM的結(jié)構(gòu)中，只有1位需要假設(shè)，而高基算法需要有w位進(jìn)行假設(shè)，代價(jià)很大不可實(shí)現(xiàn)。

結(jié)構(gòu)2中除第一個(gè)PE外，其它每個(gè)處理單元結(jié)構(gòu)相同。PE0完成任務(wù)A(i)，而其它PE完成任務(wù)B(i,j)。PE間組織成流水線結(jié)構(gòu)，PE間由前往后傳遞的是輸入數(shù)據(jù)X(i)和計(jì)算得到的進(jìn)位C，由后往前傳遞的是Z(j-1)。第一個(gè)PE用于計(jì)算qi和Z(0)，可以采用結(jié)構(gòu)1的PE結(jié)構(gòu)，而為了流水化連續(xù)處理多個(gè)模乘，在原來的結(jié)構(gòu)上增加一個(gè)乘法器并修正原來的計(jì)算通路；其它PE僅完成任務(wù)B(i,j)，原來的PE結(jié)構(gòu)用于完成任務(wù)A(i)和B(i,j)，因此結(jié)構(gòu)在原來的基礎(chǔ)上可以得到進(jìn)一步精簡(jiǎn)。

PE0僅完成任務(wù)A(i)，需要三個(gè)節(jié)拍完成。前一個(gè)PE任務(wù)完成，后一個(gè)PE才能開始計(jì)算。第二個(gè)PE僅完成任務(wù)B(i,j)，計(jì)算延遲為一拍，因此第三個(gè)PE在第五個(gè)節(jié)拍才能開始計(jì)算。除第一個(gè)PE外，PEj在第3+j個(gè)節(jié)拍開始計(jì)算。若第一個(gè)PE不能流水化處理多個(gè)模乘，則第一個(gè)PE在第五拍時(shí)才能重新開始計(jì)算，與第一次計(jì)算相隔四拍。這樣會(huì)導(dǎo)致陣列中所有PE每四拍才運(yùn)算一次，計(jì)算效率非常低。實(shí)際上，可充分利用所有PE空閑的三拍進(jìn)行其它三個(gè)模乘的運(yùn)算。另外，對(duì)于最后一個(gè)PE，輸出C直接連接到輸入Z(j-1)上。

下面討論如何在結(jié)構(gòu)2上使其能夠流水化處理四個(gè)模乘。每個(gè)處理單元的結(jié)構(gòu)幾乎不用改動(dòng)，主要需要考慮如何對(duì)來自四個(gè)不同輸入的Y(j)、M(j)和Z(j)以及輸出Z(j-1)進(jìn)行有效的調(diào)度。這里采用循環(huán)移位器來實(shí)現(xiàn)對(duì)四個(gè)不同輸入及中間結(jié)果的調(diào)度。圖5以Y為例說明了四組輸入(A、B、C和D)的調(diào)度情況，Y的每一段在不同時(shí)刻進(jìn)入循環(huán)移位器，四個(gè)移位器中第一個(gè)便連接在各自的PE輸入上。輸出Z(j-1)的調(diào)度更簡(jiǎn)單點(diǎn)，第二個(gè)PE的輸出要送給第一個(gè)PE進(jìn)行計(jì)算，而該計(jì)算在下一拍便開始，因此輸出直接連接在第一個(gè)PE的輸入Z(j-1)上。第三個(gè)及以后的PE的輸出要在三拍之后才能用上，因此只需在輸出和前一個(gè)PE的輸入Z(j-1)間采用兩個(gè)移位寄存器即可。

Figure 5 Scheduling of four Y inputs圖5 四個(gè)Y輸入的調(diào)度

4 實(shí)驗(yàn)結(jié)果

兩種線性陣列結(jié)構(gòu)都采用Verilog HDL進(jìn)行描述，以Xilinx XC5VLX330為目標(biāo)器件進(jìn)行綜合，基于ModelSim 6.5d工具進(jìn)行實(shí)驗(yàn)評(píng)測(cè)，綜合結(jié)果由Xilinx ISE 13.3給出。

對(duì)于結(jié)構(gòu)1，PE的計(jì)算核心是(C,Z(j))=C+X(i)Y(j)+qiM(j)+Z(j)，該計(jì)算的關(guān)鍵路徑在于C的反饋，為降低關(guān)鍵路徑的計(jì)算延遲，可以使X(i)Y(j)+qiM(j)+Z(j)在C產(chǎn)生之前提前計(jì)算，得到A=X(i)Y(j)+qiM(j)+Z(j)，這樣關(guān)鍵路徑上只有一個(gè)加法運(yùn)算(C,Z(j))=C+A。另外，中間結(jié)果Z還可以使用進(jìn)位保留的形式，這樣可以進(jìn)一步加速加法運(yùn)算并節(jié)省資源。這里為了簡(jiǎn)單化實(shí)現(xiàn)，我們沒有采用提前計(jì)算和進(jìn)位保留的方法。對(duì)于結(jié)構(gòu)2，PE(除第一個(gè)PE)的計(jì)算核心仍然是(C,Z(j))=C+X(i)Y(j)+qiM(j)+Z(j)，但關(guān)鍵路徑已不在于C，C不參與反饋，直接傳遞給下一個(gè)PE，關(guān)鍵路徑轉(zhuǎn)移到了X(i)到C和qi到C。

另外，兩種結(jié)構(gòu)中的乘法去處均采用了FPGA中的DSP模塊實(shí)現(xiàn)，若采用進(jìn)位保留的乘法器，將有利于性能的提升。在時(shí)序約束為200 MHz時(shí)，針對(duì)模數(shù)位寬n=256、字長(zhǎng)w=16、字?jǐn)?shù)e=17的情況，所設(shè)計(jì)的兩種結(jié)構(gòu)的綜合結(jié)果如表1所示。

Table 1 Synthesis result when targeting Xilinx XC5VLX330表1 目標(biāo)器件為Xilinx XC5VLX330時(shí)的綜合結(jié)果

表1括號(hào)中的數(shù)據(jù)表示所占FPGA資源的百分比。從表1可以看出,結(jié)構(gòu)1的運(yùn)行頻率低于結(jié)構(gòu)2，實(shí)現(xiàn)代價(jià)高于結(jié)構(gòu)2。兩種結(jié)構(gòu)的延遲雖然一致，結(jié)構(gòu)2的實(shí)現(xiàn)代價(jià)卻低于結(jié)構(gòu)1的1/2，吞吐率僅降低了20%。

表2比較了本文提出的結(jié)構(gòu)與其它兩種典型結(jié)構(gòu)的性能，設(shè)計(jì)參數(shù)基本相同。文獻(xiàn)[4]的結(jié)構(gòu)為高基Montgomery模乘結(jié)構(gòu)，延遲為38拍，優(yōu)于本文的結(jié)構(gòu)，然而吞吐率卻不高；文獻(xiàn)[8]的結(jié)構(gòu)為位級(jí)Systolic結(jié)構(gòu)，需要更多的節(jié)拍數(shù)。這兩種典型結(jié)構(gòu)無法處理輸入X和Y在[0, 2M-1]的情況，而本文的結(jié)構(gòu)可以處理。

Table 2 Performance comparison表2 性能比較

5 結(jié)束語

本文提出了兩種素域高基Montgomery模乘流水化陣列結(jié)構(gòu)，兩種結(jié)構(gòu)分別在吞吐率和硬件實(shí)現(xiàn)代價(jià)方面各有優(yōu)勢(shì)。相對(duì)于長(zhǎng)整數(shù)乘法，所提出的結(jié)構(gòu)延遲太長(zhǎng)，下一步工作將研究采用大整數(shù)乘法部件實(shí)現(xiàn)Montgomery模乘結(jié)構(gòu)。

[1] Montgomery P L. Modular multiplication without trial division[J]. Mathematics of Computation, 1985, 44(170):519-521.

[2] Tenca A F, Ko? ? K. A scalable architecture for Montgomery multiplication[C]∥Proc of Cryptographic Hardware and Embedded Systems, 1999:94-108.

[3] Huang M, Gaj K, El-Ghazawi T. New hardware architectures for Montgomery modular multiplication algorithm[J]. IEEE Transactions on Computers, 2011, 60(7):923-936.

[4] McIvor C, McLoone M, McCanny J V. High-radix systolic modular multiplication on reconfigurable hardware[C]∥Proc of IEEE International Conference on Field-Programmable Technology, 2005:13-18.

[5] Zhou L, Huang M, Smith S C. High-performance and area-efficient hardware design for radix 2k Montgomery multipliers[C]∥Proc of International Conference on Computer Design, 2011:1.

[6] Batina L, Muurling G. Montgomery in practice:How to do it more efficiently in hardware[C]∥Proc of Topics in Cryptology, the Cryptographer’s Track at the RSA Conference, 2002:40-52.

[7] Walter C D. Montgomery’s multiplication technique:How to make it smaller and faster[C]∥Proc of Cryptographic Hardware and Embedded Systems, 1999:80-93.

[8] ?rs S B, Batina L, Preneel B, et al. Hardware implementation of elliptic curve processor over GF(p)[C]∥Proc of IEEE International Conference on Application-Specific Systems, Architectures and Processors, 2003:433-443.

WUGui-ming,born in 1981,post doctor，engineer,his research interests include high-performance computer architecture, and reconfigurable computing.

DesignandimplementationofhighradixMontgomerymodularmultiplicationarraystructures

WU Gui-ming，XIE Xiang-hui，WU Dong，ZHENG Fang，YAN Xin-kai

(State Key Laboratory of Mathematical Engineering and Advanced Computing,Wuxi 214125,China)

Two linear arrays for high radix Montgomery modular multiplication are proposed. They use two different parallelization methods, both of which can exploit pipelined parallelism through task assignment and task scheduling along different loop dimensions. The two linear arrays for 256-bit modular multiplication using the radix of 216, are implemented on Xilinx XC5VLX330 FPGA. The experimental results show that both linear arrays have the latencies of 84 cycles, and the throughput of 1/17 and 1/21, respectively. Compared with the related work, our designs have higher throughput. Moreover, the balance between performance and hardware overhead can be achieved.

modular multiplication;linear array;FPGA;pipeline

2013-08-05;

：2013-10-26

中國(guó)博士后科學(xué)基金資助項(xiàng)目；國(guó)家863計(jì)劃資助項(xiàng)目(2013AA010105)

1007-130X(2014)02-0201-05

TP302

：A

10.3969/j.issn.1007-130X.2014.02.002

鄔貴明(1981-),男,四川隆昌人，博士后，工程師，研究方向?yàn)楦咝阅苡?jì)算機(jī)體系結(jié)構(gòu)和可重構(gòu)計(jì)算。E-mail:wu.guiming@meac-skl.cn

通信地址：214125 江蘇省無錫市濱湖區(qū)楝澤路30號(hào)山水城軟件園數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室Address:State Key Laboratory of Mathematical Engineering and Advanced Computing,Shanshuicheng Software Park,30 Lianze Rd,Binhu District,Wuxi 214125,Jiangsu,P.R.China