適用於模除算法的新架構及非交織一維脈動架構的製作方法與工藝

2023-05-16 18:58:42 1

本實用新型涉及密碼晶片領域，特別是指一種適用於模除算法的新架構及非交織一維脈動架構。

背景技術：
在晶片內部的電路中需要進行信號的各種變換處理，即進行二進位的加減乘除操作，加減乘除的運算速度對晶片內部電路的處理速度與面積有著直接的影響。由於乘除運算均可歸結為加減運算，所以加減運算的進位傳播速度，決定了運算的關鍵延時與性能。現有技術中，為了消除加減運算的進位傳播，採用基於Takagi的擴展加減算法，並採用冗餘數算術消除進位傳播。然而，在Takagi算法中，不平衡的流水線導致在不同的情況下，分配到一個時鐘周期內的計算量不同，使得某些周期內的時間被浪費；並且由於使用了冗餘數算術，Takagi算法的硬體實現需要更複雜的邏輯，更大的面積。Takagi算法中一次迭代要計算a←(a+qb)/4和r←(r+qs)/4(modm)，這些計算比算法ModDiv中的要複雜。在硬體實現中，一次迭代中的計算被分配到一個時鐘周期內完成。Takagi算法勢必會導致更多的硬體資源和更長的關鍵路徑延時。對於Takagi算法的一次迭代，如果a是偶數，只需要計算a←a/2和r←r/2(modm)。而如果a是奇數，需要計算a←(a+qb)/4和r←(r+qs)/4(modm)，比a是偶數的情形複雜。這就導致硬體實現的流水線在各次迭代中不平衡。對於a是偶數的情形，一部分時鐘周期就被浪費了。在Takagi算法中，這兩個計算分別還依賴於ai+2，bi+2和ri+2si+2，mi+2。因此，如果Takagi算法被用最優調度向量映射為脈動架構，這個相對複雜的依賴關係會降低硬體利用率。

技術實現要素：
本實用新型要解決的技術問題是提供一種實現更小的關鍵路徑延時和計算時間的適用於模除算法的新架構及非交織一維脈動架構。為解決上述技術問題，本實用新型提供技術方案如下：一種適用於模除算法的新架構，包括MxN的單元序列，M為迭代次數加一，N為處理的模數位長加一，前M-1行運算單元中的每一行均能夠完成一次迭代，第M行的運算單元能夠完成最後的修正，其中：對於第一行運算單元：第一行運算單元包括位於最右側有1個單元B和左側的N-1個單元A，最右側的單元B為單元B(0，0)，B(0，0)有九個輸入，從左到右分別是除數y1位、模數m1位、被除數x1位、0、模數m1位、除數y0位、模數m0位、被除數x0位和0，單元B(0，0)有13個輸出信號，其中，有8個信號經過一個寄存器後傳入與單元B(0，0)左側相鄰的單元A(0，1)，這8個信號包括五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c10、c20、c30，另外5個信號經過兩個寄存器後連入第二行的單元B(1，0)的輸入端，分別為與單元B(0，0)左側相鄰的單元A(0，1)同樣有九個輸入，從左到右分別為除數y2位、模數m2位、被除數x2位和0經過1個寄存器作為單元A(0，1)輸入，以及模數m2位、除數y1位、模數m1位、被除數x1位、0經過1個寄存器作為單元A(0，1)的輸入，單元A(0，1)有13個輸出信號，其中，8個信號經過一個寄存器後傳入與單元A(0，1)左側相鄰的單元A(0，2)，分別是五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c11、c21、c31，另外5個信號經過兩個寄存器後連入第二行的與單元A(0，1)的下面對應的單元A(1，1)的輸入，分別為單元A(0，2)有九個輸入，從左到右分別是除數y3位、模數m3位、被除數x3位、0經過2個寄存器作為A(0，2)的輸入，以及模數m3位、除數y2位、模數m2位、被除數x2位、0經過2個寄存器作為A(0，2)的輸入，單元A(0，2)有13個輸出信號，其中，8個信號經過一個寄存器後傳入單元A(0，2)左側相鄰的單元A(0，3)，這8個信號包括五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c12、c22、c32，另外5個信號經過兩個寄存器後連入第二行的與單元A(0，2)的下面對應的單元A(1，2)的輸入，分別為單元A(0，3)有九個輸入，從左到右分別是除數y3位、模數m3位、被除數x3位、0經過3個寄存器作為A(0，3)的輸入，以及模數m3位、除數y3位、模數m3位、被除數x3位、0經過3個寄存器作為A(0，2)的輸入，單元A(0，3)有13個輸出信號，其中，8個信號經過一個寄存器後傳入單元A(0，3)左側相鄰的單元A(0，4)，這8個信號包括五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c13、c23、c33，另外5個信號z0、經過兩個寄存器後連入第二行的與單元A(0，3)的下面對應的下面單元A(1，3)；單元A(0，4)和後續單元A的信號輸入和連接方式均和單元A(0，1)、A(0，2)、A(0，3)相同；對於第二至第M-1行運算單元：第二至第M-1行運算單元的單元組合、信號連接方式分別和第一行相同；對於第M行運算單元：第M行運算單元包括位於最右側的1個單元D和左側的N-1個單元C，單元D、C為符號擴展位，其中，單元D的輸入為b1、s0，b1為A(2，1)的輸出信號經過三個寄存器的輸出，s0為B(2，0)的輸出信號經過4個寄存器的輸出，單元D的輸出為s3、z0，其中，s3和連入單元C的輸入s3和單元D左側的第一個單元C除了從單元D傳來的信號外，還有一個輸入信號來自單元A(2，1)的輸出信號經過三個寄存器的輸出，單元D左側的第一個單元C的輸出為s3、z1，其中，s3和連入下一個單元C的輸入s3和si，左側其他的單元C連接方式均和它相同；上述的單元A包括3個異或XOR-AND門、2個數據選擇器MUX和3個全加器FullAdder，3個XOR-AND門和2個MUX從左向右依次排列，從左向右依次為第一XOR-AND門、第二XOR-AND門、第三XOR-AND門、第一MUX和第二MUX，第一XOR-AND門、第二XOR-AND門、第三XOR-AND門的下方分別對應的設置第一FullAdder、第二FullAdder和第三FullAdder，第二MUX輸入分別為ri、si、swap，其中，swap作為地址輸入信號，第二MUX的輸出為第一MUX輸入分別為ai、bi、swap，其中，swap作為地址輸入信號，第二MUX的輸出為bi，第三XOR-AND門包括第三XOR門和第三AND門，第三XOR門的輸入為mi+1、s2，第三XOR門的輸出連接第三AND門的被加數輸入端，第三AND門的加數端輸入v2，第三AND門的輸出端連接第三FullAdder的加數輸入端，第三FullAdder的被加數輸入端為第二FullAdder的本位和輸出，第三FullAdder的進位信號輸入為c3i-1，進位信號輸出為c3i，第三FullAdder的本位輸出為第二XOR-AND門包括第二XOR門和第二AND門，第二XOR門的輸入為si+1、s1，第二XOR門的輸出連接第二AND門的被加數輸入端，第二AND門的加數輸入端輸入ri+1，第二AND門的輸出端連接第二FullAdder的加數輸入端，第二FullAdder的被加數輸入端輸入ri+1，第二FullAdder的進位信號輸入為c2i-1，其進位信號輸出為c2i，第一XOR-AND門包括第一XOR門和第一AND門，第一XOR門的輸入為bi+1、s1，第一XOR門的輸出連接第一AND門的被加數輸入，第一AND門的加數輸入為v1，第一AND門的輸出連接第一FullAdder的加數輸入端，第一FullAdder的被加數輸入端為ai+1，進位信號輸入為c1i.其進位信號輸出為上述的單元B包括單元A和控制單元Ctrl組成，控制單元Ctrl的輸入為a1、b1、a0、r0、s0，控制單元Ctrl的輸出v1、s1、v2、s2、swap、c1、c2和c3的初始值連接至單元A的同名端；單元C和單元D所完成的運算是求相反數，其中，單元C由異或門和半加器連接組成，其中異或門輸入為si、s3，輸出連入半加器的被加數輸入端，另加數輸入信號是進位信號c4i-1，其本位輸出為進位為s1，單元D由單元C組成，其中，輸入信號si為s0，c4i-1連接b1，傳入單元C的輸出為s3、c40，本位輸出為進一步的，第一行至第M-1行中的每一行，從右到左，每兩個相鄰的單元組合成了一個單元組合，構成一個單元組合的兩個單元之間的流水線寄存器均去掉。上述的適用於模除算法的新架構得到的非交織一維脈動架構，所述非交織一維脈動構架由所述適用於模除算法的新架構沿著向量方向投影得到，包括從左向右依次連接的2個運算單元E和1個運算單元F，其中：運算單元E包括2個左右設置的單元A，以及8個MUX組成，輸入從左到右依次為m2i+2、a2i+1、b2i+1、r2i+1、s2i+1、m2i+1、a2i、b2i、r2i、s2i，其中，a2i+1、b2i+1、r2i+1、s2i+1、a2i、b2i、r2i、s2i分別是從左到右每個MUX的一個數據輸入端，它們的另一個數據輸入端分別是單元A的輸出地址選擇信號均為運算單元F的輸出init信號，8個MUX的輸出經過一個寄存器後分別為單元E的輸出a′2i+1、b′2i+1、r′2i+1、s′2i+1、a′2i、b′2i、r′2i、s′2i，其中，a′2i+1、b′2i+1、r′2i+1、s′2i+1分別連入左側單元A的輸入a2i+1、b2i+1、r2i+1、s2i+1端及右邊單元A的輸入端a2i+1、b2i+1、r2i+1、s2i+1，a′2i、b′2i、r′2i、s′2i連入右側單元A的輸入端a2i、b2i、r2i、s2i，運算單元E的輸出信號a2i+2、b2i+2、r2i+2、s2i+2連入左側單元A的同名輸入端，m2i+2與單元A的m2i+2相連，右側單元A的輸出信號v1、s1、v2、s2、swap、c12i、c22i、c32i連接左側單元A的同名輸入端，單元A的輸出信號v1、s1、v2、s2、swap、c12i+1、c22i+1、c32i+1連入下一個運算單元E；運算單元F包括單元A、B和8個MUX，其中，運算單元F的輸入從左到右依次為m2、a1(y1)、b1(m1)、r1(x1)、s1(0)、m1、si(y0)、b0(m0)、r0(x0)、s0(0)，init第一周期為1，以後均為0，其中，init為新的控制信號，它為1表示該周期初始化該運算單元的寄存器，即從外部接收輸入數據，從左到右每個MUX的一個數據輸入端分別為a1、b1、r1、s1、a0、b0、r0和s0，它們的另一個數據輸入端分別是單元A的輸出地址選擇信號均為init信號，8個MUX的輸出經過一個寄存器後分別為運算單元F的輸出a′1、b′1、r′1、s′1、a′0、b′0、r′0、s′0，其中，a′1、b′1、r′1、s′1分別連入單元A的輸入端ai、bi、ri、si及單元B的輸入端a1、b1、r1、s1，a′0、b′0、r′0、s′0連入單元B的輸入端a0、b0、r0、s0，相鄰運算單元E的輸出信號a2、b2、r2、s2連入單元A的輸入ai+1、bi+1、ri+1、si+1，m2與單元A的mi+1相連，單元B的輸出信號v1、s1、v2、s2、swap、c10、c20、c30連接單元A的同名輸入端，單元A的輸出信號v1、s1、v2、s2、swap、c11、c21、c31連入下一個運算單元E。本實用新型的實施例具有以下有益效果：本實用新型中，採用ModDiv算法得到一個適用於模除算法的新架構，ModDiv算法與Tagaki算法都是基於擴展了的加減算法。然而，這兩種算法在控制r的增長方面用的方法不同。Takagi將兩次迭代組合成一次迭代，將前一次迭代的r←(r+qs)/2(modm)和後一次迭代的r←r/2(modm)組合成r←(r+qs)/4(modm)，相應地，a←(a+qb)/2和a←a/4組合成a←(a+qb)/4。這樣就保證執行r←(r+qs)/4(modm)之後，|r|＜m。然而，這種方法給硬體實現帶來兩點明顯的不利，第一，Takagi算法中一次迭代要計算a←(a+qb)/4和r←(r+qs)/4(modm)，這些計算比算法ModDiv複雜，在硬體實現中，一次迭代中的計算被分配到一個時鐘周期內完成。Takagi算法勢必會導致更多的硬體資源和更長的關鍵路徑延時；第二，a是奇數比a是偶數的情形複雜，這就導致硬體實現的流水線在各次迭代中不平衡，對於a是偶數得情形，一部分時鐘周期就被浪費了。本實用新型的算法ModDiv，計算ai和ri分別只依賴於ai+1、bi+1、ri+1、si+1和mi+1，但在Takagi算法中，這兩個計算分別還依賴於ai+2、bi+2、ri+2、si+2和mi+2。因此，如果Takagi算法被用最優調度向量映射為脈動架構，這個相對複雜的依賴關係會降低硬體利用率。通過比較Takagi算法和算法ModDiv，可以得出算法ModDiv適合脈動架構實現的優點。與現有技術相比，本實用新型能夠實現更小的關鍵路徑延時和計算時間的優點。附圖說明圖1為本實用新型的適用於模除算法的新架構的結構示意圖；圖2為本實用新型的適用於模除算法的新架構的單元A的結構示意圖；圖3為本實用新型的適用於模除算法的新架構的單元B的結構示意圖；圖4為本實用新型的適用於模除算法的新架構的單元C的結構示意圖；圖5為本實用新型的適用於模除算法的新架構的單元D的結構示意圖；圖6為本實用新型的適用於模除算法的新架構的配對後的結構示意圖；圖7為本實用新型的非交織一維脈動架構的結構示意圖；圖8為本實用新型的非交織一維脈動架構的單元E的結構示意圖；圖9為本實用新型的非交織一維脈動架構的單元F的結構示意圖。具體實施方式為使本實用新型要解決的技術問題、技術方案和優點更加清楚，下面將結合附圖及具體實施例進行詳細描述。一方面，本實用新型提供一種適用於模除算法的新架構，包括MxN的單元序列，M為迭代次數加一，N為處理的模數位長加一，為了簡明起見，如圖1所示，提供了一個4x5的單元序列的實施例，該實施例可以完成3次迭代，可以處理的模數位長為4個字節，前三行運算單元中的每一行均能夠完成一次迭代，第四行的運算單元能夠完成最後的修正，其中：對於第一行運算單元：第一行運算單元包括位於最右側有1個單元B和左側的4個單元A，最右側的單元B為單元B(0，0)，B(0，0)有九個輸入，從左到右分別是除數y1位、模數m1位、被除數x1位、0、模數m1位、除數y0位、模數m0位、被除數x0位和0，單元B(0，0)有13個輸出信號，其中，有8個信號經過一個寄存器(寄存器為通用寄存器，該寄存器是邊沿觸發的寄存器，是時序電路的基本組成部分，用於同步輸入信號。下文中的寄存器均為該通用寄存器)後傳入與單元B(0，0)左側相鄰的單元A(0，1)，這8個信號包括五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c10、c20、c30，另外5個信號經過兩個寄存器後連入第二行的單元B(1，0)的輸入端，分別為與單元B(0，0)左側相鄰的單元A(0，1)同樣有九個輸入，從左到右分別為除數y2位、模數m2位、被除數x2位和0經過1個寄存器作為單元A(0，1)輸入，以及模數m2位、除數y1位、模數m1位、被除數x1位、0經過1個寄存器作為單元A(0，1)的輸入，單元A(0，1)有13個輸出信號，其中，8個信號經過一個寄存器後傳入與單元A(0，1)左側相鄰的單元A(0，2)，分別是五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c11、c21、c31，另外5個信號經過兩個寄存器後連入第二行的與單元A(0，1)的下面對應的單元A(1，1)的輸入，分別為單元A(0，2)有九個輸入，從左到右分別是除數y3位、模數m3位、被除數x3位、0經過2個寄存器作為A(0，2)的輸入，以及模數m3位、除數y2位、模數m2位、被除數x2位、0經過2個寄存器作為A(0，2)的輸入，單元A(0，2)有13個輸出信號，其中，8個信號經過一個寄存器後傳入單元A(0，2)左側相鄰的單元A(0，3)，這8個信號包括五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c12、c22、c32，另外5個信號經過兩個寄存器後連入第二行的與單元A(0，2)的下面對應的單元A(1，2)的輸入，分別為單元A(0，3)有九個輸入，從左到右分別是除數y3位、模數m3位、被除數x3位、0經過3個寄存器作為A(0，3)的輸入，以及模數m3位、除數y3位、模數m3位、被除數x3位、0經過3個寄存器作為A(0，2)的輸入，單元A(0，3)有13個輸出信號，其中，8個信號經過一個寄存器後傳入單元A(0，3)左側相鄰的單元A(0，4)，這8個信號包括五個控制信號v[1]、s[1]、v[2]、s[2]、swap和三個進位信號c13、c23、c33，另外5個信號z0、經過兩個寄存器後連入第二行的與單元A(0，3)的下面對應的下面單元A(1，3)；單元A(0，4)和後續單元A的信號輸入和連接方式均和單元A(0，1)、A(0，2)、A(0，3)相同；對於第二、三行運算單元：第二行和第三行運算單元的單元組合、信號連接方式分別和第一行相同；對於第四行運算單元：第四行運算單元包括位於最右側的1個單元D和左側的4個單元C，單元D、C為符號擴展位，其中，單元D的輸入為b1、s0，b1為A(2，1)的輸出信號經過三個寄存器的輸出，s0為B(2，0)的輸出信號經過4個寄存器的輸出，單元D的輸出為s3、z0，其中，s3和連入單元C的輸入s3和，單元D左側的第一個單元C除了從單元D傳來的信號外，還有一個輸入信號來自單元A(2，1)的輸出信號經過三個寄存器的輸出，單元D左側的第一個單元C的輸出為s3、z1，其中，s3和連入下一個單元C的輸入s3和si，左側其他的單元C連接方式均和它相同；如圖2所示，上述的單元A包括3個異或XOR-AND門、2個數據選擇器MUX和3個全加器FullAdder，3個XOR-AND門和2個MUX從左向右依次排列，從左向右依次為第一XOR-AND門、第二XOR-AND門、第三XOR-AND門、第一MUX和第二MUX，第一XOR-AND門、第二XOR-AND門、第三XOR-AND門的下方分別對應的設置第一FullAdder、第二FullAdder和第三FullAdder，第二MUX輸入分別為ri、si、swap，其中，swap作為地址輸入信號，第二MUX的輸出為第一MUX輸入分別為ai、bi、swap，其中，swap作為地址輸入信號，第二MUX的輸出為bi，第三XOR-AND門包括第三XOR門和第三AND門，第三XOR門的輸入為mi+1、s2，第三XOR門的輸出連接第三AND門的被加數輸入端，第三AND門的加數端輸入v2，第三AND門的輸出端連接第三FullAdder的加數輸入端，第三FullAdder的被加數輸入端為第二FullAdder的本位和輸出，第三FullAdder的進位信號輸入為c3i-1，進位信號輸出為c3i，第三FullAdder的本位輸出為第二XOR-AND門包括第二XOR門和第二AND門，第二XOR門的輸入為si+1、s1，第二XOR門的輸出連接第二AND門的被加數輸入端，第二AND門的加數輸入端輸入ri+1，第二AND門的輸出端連接第二FullAdder的加數輸入端，第二FullAdder的被加數輸入端輸入ri+1，第二FullAdder的進位信號輸入為c2i-1，其進位信號輸出為C2i，第一XOR-AND門包括第一XOR門和第一AND門，第一XOR門的輸入為bi+1、s1，第一XOR門的輸出連接第一AND門的被加數輸入，第一AND門的加數輸入為v1，第一AND門的輸出連接第一FullAdder的加數輸入端，第一FullAdder的被加數輸入端為ai+1，進位信號輸入為c1i.其進位信號輸出為如圖3所示，上述的單元B包括單元A和控制單元Ctrl組成，控制單元Ctrl的輸入為a1、b1、a0、r0、s0，控制單元Ctrl的輸出v1、s1、v2、s2、swap、c1、c2和c3的初始值連接至單元A的同名端；單元C和單元D所完成的運算是求相反數，如圖4-5所示，單元C由異或門和半加器連接組成，其中異或門輸入為si、s3，輸出連入半加器的被加數輸入端，另加數輸入信號是進位信號c4i-1，其本位輸出為進位為s1，單元D由單元C組成，其中，輸入信號si為s0，c4i-1連接b1，傳入單元C的輸出為s3、c40，本位輸出為本實施例中，採用ModDiv算法得到一個適用於模除算法的新架構，ModDiv算法與Tagaki算法都是基於擴展了的加減算法。然而，這兩種算法在控制r的增長方面用的方法不同。Takagi將兩次迭代組合成一次迭代，將前一次迭代的r←(r+qs)/2(modm)和後一次迭代的r←r/2(modm)組合成r←(r+qs)/4(modm)，相應地，a←(a+qb)/2和a←a/4組合成a←(a+qb)/4。這樣就保證執行r←(r+qs)/4(modm)之後，|r|＜m。然而，這種方法給硬體實現帶來兩點明顯的不利，第一，Takagi算法中一次迭代要計算a←(a+qb)/4和r←(r+qs)/4(modm)，這些計算比算法ModDiv複雜，在硬體實現中，一次迭代中的計算被分配到一個時鐘周期內完成。Takagi算法勢必會導致更多的硬體資源和更長的關鍵路徑延時；第二，a是奇數比a是偶數的情形複雜，這就導致硬體實現的流水線在各次迭代中不平衡，對於a是偶數得情形，一部分時鐘周期就被浪費了。本實施例的算法ModDiv，計算ai和ri分別只依賴於ai+1、bi+1、ri+1、si+1和mi+1，但在Takagi算法中，這兩個計算分別還依賴於ai+2、bi+2、ri+2、si+2和mi+2。因此，如果Takagi算法被用最優調度向量映射為脈動架構，這個相對複雜的依賴關係會降低硬體利用率。通過比較Takagi算法和算法ModDiv，可以得出算法ModDiv適合脈動架構實現的優點。與現有技術相比，本實施例能夠實現更小的關鍵路徑延時和計算時間的優點。作為本上述實施例的一種改進，如圖6所示，第一行、第二行和第三行中的每一行，從右到左，每兩個相鄰的單元組合成了一個單元組合，構成一個單元組合的兩個單元之間的流水線寄存器均去掉。本實施例對於大多數應用，特別是ECC應用，以交織的方式執行兩個互相無關的計算是不實際的。用直接映射的方法得到的脈動架構總是存在一個周期的空閒。本實施例中，採用配對技術，推導出一個非交織的脈動架構，如圖5所示，對於每一行，從右到左，每兩個相鄰的單元被組合成一個單元，這兩個單元之間的流水線寄存器去除(如圖5空心方框所示)。按照線性映射的表達方式，這個調度方法所對應的調度向量是坐標為x的單元在時刻被調度，硬體利用率為另一方面，本實用新型的實施例還提供一種由上述的適用於模除算法的新架構得到的非交織一維脈動架構，如圖7所示，非交織一維脈動構架由適用於模除算法的新架構沿著向量方向投影得到，包括從左向右依次連接的2個運算單元E和1個運算單元F，其中：如圖8所示，運算單元E包括2個左右設置的單元A，以及8個MUX組成，輸入從左到右依次為m2i+2、a2i+1、b2i+1、r2i+1、s2i+1、m2i+1、a2i、b2i、r2i、s2i，其中，a2i+1、b2i+1、r2i+1、s2i+1、a2i、b2i、r2i、s2i分別是從左到右每個MUX的一個數據輸入端，它們的另一個數據輸入端分別是單元A的輸出地址選擇信號均為運算單元F的輸出init信號，8個MUX的輸出經過一個寄存器後分別為單元E的輸出a′2i+1、b′2i+1、r′2i+1、s′2i+1、a′2i、b′2i、r′2i、s′2i，其中，a′2i+1、b′2i+1、r′2i+1、s′2i+1分別連入左側單元A的輸入a2i+1、b2i+1、r2i+1、s2i+1端及右邊單元A的輸入端a2i+1、b2i+1、r2i+1、s2i+1，a′2i、b′2i、r′2i、s′2i連入右側單元A的輸入端a2i、b2i、r2i、s2i，運算單元E的輸出信號a2i+2、b2i+2、r2i+2、s2i+2連入左側單元A的同名輸入端，m2i+2與單元A的m2i+2相連，右側單元A的輸出信號v1、s1、v2、s2、swap、c12i、c22i、c32i連接左側單元A的同名輸入端，單元A的輸出信號v1、s1、v2、s2、swap、c12i+1、c22i+1、c32i+1連入下一個運算單元E；如圖9所示，運算單元F包括單元A、B和8個MUX，其中，運算單元F的輸入從左到右依次為m2、a1(y1)、b1(m1)、r1(x1)、s1(0)、m1、si(y0)、b0(m0)、r0(x0)、s0(0)，init第一周期為1，以後均為0，其中，init為新的控制信號，它為1表示該周期初始化該運算單元的寄存器，即從外部接收輸入數據，從左到右每個MUX的一個數據輸入端分別為a1、b1、r1、s1、a0、b0、r0和s0，它們的另一個數據輸入端分別是單元A的輸出地址選擇信號均為init信號，8個MUX的輸出經過一個寄存器後分別為運算單元F的輸出a′1、b′1、r′1、s′1、a′0、b′0、r′0、s′0，其中，a′1、b′1、r′1、s′1分別連入單元A的輸入端ai、bi、ri、si及單元B的輸入端a1、b1、r1、s1，a′0、b′0、r′0、s′0連入單元B的輸入端a0、b0、r0、s0，相鄰運算單元E的輸出信號a2、b2、r2、s2連入單元A的輸入ai+1、bi+1、ri+1、si+1，m2與單元A的mi+1相連，單元B的輸出信號v1、s1、v2、s2、swap、c10、c20、c30連接單元A的同名輸入端，單元A的輸出信號v1、s1、v2、s2、swap、c11、c21、c31連入下一個運算單元E。本實施例中，調度向量的選擇取決於該運算單元在什麼時刻投入運算。考慮任意一次迭代，如相鄰運算單元間流水，則縱坐標加一，被調度時間也加一；如相鄰單元配對，則縱坐標加二，調度時間才加一。下面再考慮迭代所用時間，除第一次迭代外，每個運算單元的輸入都取決於上一行兩個相鄰運算單元的輸出，若相鄰流水，則每次迭代增加兩周期；若相鄰配對，則每次迭代增加一周期。所以權2調度向量選為(1，1/2)。而投影向量的選擇要滿足最高但不超過100％的硬體使用率。選擇權3的投影向量，該一維脈動架構的硬體利用率是這說明對於一個運算來說，達到100％的硬體利用率；如果我們選擇該一維脈動架構的硬體利用率超過100％，有控制冒險(controlhazard)，即同一個硬體資源同一時間被復用的情況，是不允許的。因此，本實施例中的投影向量選擇本實施例的計算單元和控制單元內的數據通路更加簡單，因此關鍵路徑延時更短，與Takagi算法的架構相比，本實施例的架構的計算速度能夠比Takagi的架構提高一倍，這將有效地緩解當今ECC處理器中普遍存在的素域除法性能瓶頸。本實施例能夠在更高的工作頻率下工作、實現更小的關鍵路徑延時和計算時間，所以具有更好的性能。上述實施例中，均是以4x5的單元序列的實施例進行說明的，為適應迭代次數的要求，單元序列MxN中的M可以為2以上的任意整數，為適應模數位長的要求，單元序列MxN中的N可以為小於等於384的任意8的倍數(該設計處理的最大位長為384bit，最小單位為byte)。所以M的取值範圍可以是2，3，4…N的取值範圍可以是8，16，24，32…384，因此，本實用新型的適用於模除算法的新架構可以根據迭代次數和處理模數位長的要求選取相應的MxN單元序列。下面，本實用新型提供一種完整的實施例：關於模除問題的基本描述是：給定三個整數x，y，m滿足gcd(y，m)＝1，那麼x除以y模m就是找出一個整數z使得yz≡x(modm)。本實用新型提出了一個適合於脈動架構的模除算法，如表1，注意到輸入輸出的界限由於硬體實現的問題被特意指出。子函數，帶有特徵的模除以2算法。在硬體實現中，數據的範圍決定了所需數據通路的位寬和存儲單元的位寬，範圍越大所需要的位寬就越大。在算法ExtPM中，輸入x，y滿足|x|，|y|＜m。但是經過算法ExtPM的變換後，並不能保證輸出z滿足|z|＜m也就是說：算法輸入和輸出的範圍不一致。算法輸入和輸出範圍一致的要求在一些需要多次迭代調用模除的應用(包括橢圓曲線算數)中是必須的。表1擴展加減算法而得的模除算法為了解決這個問題，注意到導致z值的範圍變大的原因在於子算法ModDiv2的第4行總是加m。引入一個取值為±1的標誌f。當該標誌為正時，算法ModDiv2的第4行加m；否則減m。並且，每次算法ModDiv2的第4行被執行時，改變f的符號，這樣就保證算法ModDiv2的第4行的加m和減m交替進行，從而保證輸出z滿足|z|＜m。在算法ExtPM中引入上文介紹的標誌f，得到表1的模除算法ModDiv。此項提出的算法是加減算法的延伸，此種算法和模除算法一模一樣，除了使用帶有特徵的模除以2算法。把(r+qs)/2(modm)用硬體實現，我們應用了如果(r+qs)為奇數，我們算出r←(r+qs+m)/2或者r←(r+qs)/2因為得到r的覺得值可能比m大，我們必須把r值降到範圍(-m，m)內。比較時涉及一些加、減條件。然而，在脈動架構中，進位鏈為流水結構，一次比較有一段很長的延時，模除運算相對於這個延時會拖延流水線的正常運行。為了解決這個問題，我們引進了一個信號控制是加m(如果p＝1)還是減m(如果p＝-1)當被除數在模除運算中是奇數，一個所謂的，帶有特徵的模除以2算法，如表2，如果被除數是奇數這個信號會被取反，關於m的加減操作會交替進行，因此，我們可以確信在運算r←MODDIV2FLAG(r+qs，m)及運算r←MODDIV2FLAG(r，m)後|z|＜m。Input：x，m，p：misodd.Output：y：2y＝x(modm).(1)ifx≡0(mod2)theny←x/2；(2)elsey←(x+pm)/2；p＝-p；表2帶有標誌的模除以2算法ModDiv算法正確性證明：為了證明模除算法的後置條件，我們提出以下引理：引理1：在算法ModDiv每次迭代開始時，b是奇數。引理2：在算法ModDiv中，引入兩個輔助變量α和β，並且在第一行插入α←n和β←n，在第6行插入α←α-1，在第13行插入那麼在每次迭代開始時，|a|＜2α，|b|＜2β，φ＝min(α，β)，並且δ＝α-β。引理3：在算法ModDiv中，當第4行被執行|r|＜m，當第14行被執行後|s|＜m。引理4：在算法ModDiv每次迭代開始時，xa≡yr(modm)，xb≡ys(modm)。引理5：在算法ModDiv每次迭代中，gcd(a，b)保持不變。這些引理的證明是顯而易見的，所以省略了。基於這些引理，可以證明算法的正確性。因為相鄰兩次迭代中第6行至少被執行一次，那麼根據引理2，至多經過4n次迭代後，φ變為0，算法終止。a＝0，|b|＝gcd(y，m)＝1(運用引理1，2，5)，|s|＜m(運用引理3)，並且ys≡xb＝±x(modm)(運用引理4)。經過第16行的修正之後，我們有ys≡x(modm)。綜上，輸出z滿足yz≡x(modm)，|z|＜m。我們的算法和Tagaki算法相比，改善是顯著的。兩種算法都是基於擴展了的加減算法。然而，這兩種算法在控制r的增長方面用的方法不同。Takagi將兩次迭代組合成一次迭代，將前一次迭代的r←(r+qs)/2(modm)和後一次迭代的r←r/2(modm)組合成r←(r+qs)/4(modm)，相應地a←(a+qb)/2和a←a/4組合成a←(a+qb)/4。這樣就保證執行r←(r+qs)/4(modm)之後，|r|＜m。然而，這種方法給硬體實現帶來兩點明顯的不利。第一，Takagi算法中一次迭代要計算a←(a+qb)/4和r←(r+qs)/4(modm)，這些計算比算法ModDiv中的要複雜。在硬體實現中，一次迭代中的計算被分配到一個時鐘周期內完成。Takagi算法勢必會導致更多的硬體資源和更長的關鍵路徑延時。第二，a是奇數比a是偶數的情形複雜。這就導致硬體實現的流水線在各次迭代中不平衡。對於a是偶數得情形，一部分時鐘周期就被浪費了。而且，在算法ModDiv中，計算ai和ri分別只依賴於ai+1，bi+1和ri+1，si+1，mi+1。但在Takagi算法中，這兩個計算分別還依賴於ai+2，bi+2和ri+2，si+2，mi+2。因此，如果Takagi算法被用最優調度向量映射為脈動架構，這個相對複雜的依賴關係會降低硬體利用率。通過比較Takagi算法和算法ModDiv，可以看出算法ModDiv適合脈動架構實現的優點。而ModDiv算法需要的總迭代次數更多。直接映射所得的脈動架構：本實用新型，在算法ModDiv的脈動架構實現中，變量a，b，r，s，m，δ用2的補碼表示，φ用原碼表示因為φ是非負數。假設n是模數m的位長(即)。對於變量a、b、s和m，n+1位就足夠了。因為那麼對於r來說，n+2位就足夠了。從引理2可知，φ和|δ|不會超過n，因此表示φ和δ分別需要和位。將硬體算法映射到脈動架構的第一步是將算法轉換成位級依賴圖。算法ModDiv的位級依賴圖如圖1所示，該依賴圖示出了一個5×4的單元陣列，可以處理的模數位長n＝3，可以完成3次迭代。其中f1-f6是控制信號，c1-c4代表進位信號。其中，每個運算單元向前傳FA表示全加器，HA表示半加器，Ctrl表示控制邏輯。圖3中的控制單元Ctrl生成f1-f6和c1-c3的初始值。Ctrl包含寄存器p(實際上是算法ModDiv2Flag中標誌p的符號)、計數器φ、計數器δ。控制信號和進位信號的值由下列式子給出：f1＝a[0]，<![CDATA[f2=a1b1,]]><![CDATA[f3=a0r0+a0(r0s0),]]>f4＝p，f5＝a[0]sδ，c1[-1]＝f1，c2[-1]＝f2，<![CDATA[c3-1=f1(r0s0+f2(r0+s0)]]>寄存器和計數器的初始值由算法ModDiv給出，按照下列邏輯更新：1)如果f3＝1，那麼否則p保持不變。2)如果f5＝1，δ←-δ；否則如果a[0]＝0，δ←δ-1。3)如果a[0]＝0，φ≠0，δ≤0，那麼φ＝φ-1；否則φ保持不變。圖1最底一行的單元C和單元D所進行的計算(算法ModDiv第16行)是求相反數。這個計算可以由模除脈動架構所在的算術單元中的加法器或減法器來實現。我們用z′表示未經過這個計算的模除結果。圖1中建立了一個二維坐標系。每個單元被分配了一個坐標。利用線性映射技術，選擇最優調度向量投影向量將依賴圖映射為一維脈動架構。在圖3中，相鄰的調度平面之間放置了流水線寄存器(如圖中實心方框所示)，形成了一個二維脈動架構。沿著的方向將這個二維脈動架構投影成一維脈動架構的處理單元。該一維脈動架構的硬體利用率是這說明對於一個運算來說，每兩個時鐘周期有一個周期空閒。這也就意味著必須有兩個互相無關的計算以交織的方式被脈動架構執行，才能達到100％的硬體利用率，或者，如果我們選擇如果沒有兩個互相無關的計算先後進入脈動架構被執行，那麼脈動架構中有一半的PE空閒。非交織的脈動架構：對於大多數應用，特別是ECC應用，以交織的方式執行兩個互相無關的計算是不實際的。用直接映射的方法得到的脈動架構總是存在一個周期的空閒。下文將採用配對技術，推導出一個非交織的脈動架構。配對的過程如圖5所示。對於每一行，右到左，每兩個相鄰的單元被組合成一個單元，這兩個單元之間的流水線寄存器被刪除(如圖空心方框表示)。按照線性映射的表達方式，這個調度方法所對應的調度向量是坐標為x的單元在時刻被調度。硬體利用率因此為沿著之前投影向量的方向，得到一個非交織的一維脈動架構，如圖6所示。每個單元的內部細節如圖7所示，圖中實心方框表示流水線寄存器。一個新的控制信號f7被引入了，它表示PE的寄存器的初始化，從外部接收輸入數據。非交織脈動架構中的流水線寄存器數是直接映射所得的架構中的流水線寄存器數的一半，因此晶片面積更小。在假設不允許進行交織計算的前提下，非交織架構進行一次計算所需要的周期數是直接映射所得的架構的周期數的一半。直接映射所得的架構的關鍵路徑延時在單元B中，非交織的脈動架構的關鍵路徑在相鄰的兩個單元E之間。門級仿真後的時間分析表明，運用直接映射所得的關鍵路徑延時大概是非交織的架構的0.7(大於0.5)。因此非交織的脈動架構需要更少的運算時間。該脈動架構的面積複雜度是O(n)。關鍵路徑延時與n無關。當n變大使得計數器φ和δ中的加法器成為整體的關鍵路徑時，可以用移位器代替加法器，移位器的延時與n無關，空間複雜度是O(n)。該算法ModDiv至多經過4n個迭代終止，所以時間複雜度是O(n)。本實用新型技術方案帶來的有益效果：與Takagi算法的架構相比，本實用新型的計算單元和控制單元內的數據通路更加簡單，因此關鍵路徑延時更短，儘管每次運算所需的時鐘周期數較多，平均計算時間只是Takagi的架構的46％，最大計算時間是它的50％。本實用新型的架構的計算速度比Takagi的架構提高一倍，這將有效地緩解當今ECC處理器中普遍存在的素域除法性能瓶頸。本實用新型能夠在更高的工作頻率下工作，所以具有更好的性能。為了評估本文提出的非交織脈動架構的性能，並將它與Kaihara和Takagi提出的基於Takagi算法並採用冗餘數算術的模除架構相比較，用VHDL描述了本文的架構，在0.35μmCMOS標準單元工藝下，評估了綜合後的面積和關鍵路徑。本實用新型和文獻【10】架構相比的等效門數和關鍵路徑延時。文獻【10】提出的架構完成一次模除最多需要2n+5個時鐘周期。對於本文的架構，完成一次模除所需的最大時鐘周期未知。但是，在文獻【11】中被證明最大時鐘周期數不超過表1中將這個值作為本文架構的最大時鐘周期數。另外，基於以隨機數據為輸入的仿真，表1給出了【10】中的架構和本文的架構完成一次模除的平均計算時間(分別是1.72n和2.44n個時鐘周期)。從表1中可以看出：本文的架構的面積比文獻【10】的架構的面積大17％-21％。文獻【10】的架構採用的是Takagi算法。與本文算法相比，Takagi算法每次迭代的計算更加複雜，而且採用冗餘數算術導致幾近雙倍的硬體資源需求。但是，本文的脈動架構的細粒度流水線需要大量的流水線寄存器，數據信號和控制信號都需要用寄存器鎖存，所以，導致本文架構增加。然而，由於本文架構的計算單元和控制單元內的數據通路更加簡單，因此關鍵路徑延時更短。因此，平均計算時間和最大計算時間只是文獻【10】架構的46％和50％。這個提升有效地緩解了當今模除吞吐量的瓶頸。本實用新型，通過比較Takagi算法，改進擴展後的歐幾裡得算法，改進計算Montgomery逆的算法，及基於加減算法提出的統一的雙域除法算法的幾種架構，可以看出本文架構能夠在更高的工作頻率下工作，所以具有更好的性能。本實用新型中，模除算法及將算法映射到一個非交織的一維脈動架構。及擴展該架構之後，使其成為一個統一的支持雙域乘法和除法的脈動架構。模除脈動架構裡，數據均以2的補碼表示。為了與此兼容，擴展Montgomery模乘算法，使之能夠處理2的補碼表示的數據。擴展後的Montgomery模乘算法見表8，y-1＝0，並且y被符號擴展為n+1位。Input：x，y，m：misodd，|x|＜m，and|y|＜m.Output：z：z≡xy2-n-2(modm)，and|z|＜m.(1)z←0；(2)fori←0ton+1(3)z←ModDiv2Flag(z+x(y[i-1]-y[i])，m)表8擴展後的Montgomery模乘算法算法Montgomery中的變量z和x分別被映射到模除架構中的寄存器r和s。由控制單元B生成的各種控制信號以及進位信號的初始值由下式給出：<![CDATA[f1=yi-1yi,]]><![CDATA[f2=yi,]]><![CDATA[f3=f1r0+f1(r0s0),]]>f4＝p，f5＝0，c2[-1]＝f3，<![CDATA[c3-1=f1(r0s0+j2(r0+s0)]]>其他信號不需要被考慮。對於計算單元A，不需做任何修改，這樣架構就實現了運算(z，f)←ModDiv2Flag(z+x(y[i-1]-y[i])，m)。除了這些修改之外，還需要增加一個計數器i。如果我們將寄存器r和s分別初始化為0和x，將m並行輸入到埠m，將y串行輸入到單元B，那麼經過n+2個時鐘周期之後，寄存器r中就得到Montgomery模乘的結果。上述的修改所增加的硬體資源非常小，修改後的構架面積增加不到3％。另外，修改前後關鍵路徑延時不變，因為修改前的架構中的關鍵路徑在相鄰的兩個單元E之間，上述的修改並未改動單元E。因此，從面積和時間兩方面來看，將模除脈動架構擴展成統一的乘法除法架構是相當高效的。下面，對本實用新型的附圖進行說明：圖1為模除算法的位級依賴圖，每個單元都依賴於下一個單元的輸入，相鄰單元之間相互交織。最低位的運算單元輸入為x0、y0、x1、y1、m0、m1，輸出為控制信號f1、f2、f3、f4、f5和進位信號c1、c2、c3。八個輸出信號經過寄存器後，作為輸入信號被傳入下一個運算單元。圖2表明了圖1中單元A的內部細節結構圖。其中，單元A包括XOR-AND、XNOR-AND、MUX和FullAdder幾種邏輯單元，三個carry信號分別接到FullAdder的carry輸入，得到三個carry輸出，傳到下一個運算單元。圖3表明了圖1中單元B的內部細節結構圖。其中，單元B包括運算單元A和控制單元Ctrl，控制單元的輸入為a1、b1、a0、r0、s0，輸出為v1、s1、v2、s2、swap以及c1、c2、c3的初始值。其中，組合邏輯包括與門，異或門；時序邏輯包括寄存器f、計數器φ和計數器δ。如圖4-5所示，分別為圖1中單元C和單元D的內部細節結構圖。單元C和單元D所完成的運算是求相反數，其中，單元C由異或門和半加器連接組成，s3、si信號經過異或門後的輸出作為半加器的一個輸入，另一個輸入信號是低位傳來的進位信號ci-1。圖6為配對後的模除依賴圖，對於每一行，從右到左，每兩個相鄰的單元被組合成了一個單元，這兩個單元之間的流水線寄存器被刪除。現在，最低位運算單元的輸入為x0、m0、y0、m1、x1、y1、m2、x2、y2和m3，輸出為五個控制信號f1、f2、f3、f4、f5和三個進位信號c1、c2、c3，它們被傳入下一個配對後的運算單元。圖7為非交織的模除脈動架構。圖6實施例沿著之前投影向量的方向，得到圖7中非交織的一維脈動架構。最低兩位對應的運算單元輸入信號為x0、m0、y0、m1、x1、y1、m2，傳入下一個運算單元的輸出是五個控制信號和三個進位信號。在一個周期內，處理兩比特數據，得到兩比特結果。圖8展示的是圖7中單元E的內部細節結構圖。單元E包括兩個單元A和8個數據選擇器(MUX)。這裡引入新的控制信號f7，作為每個數據選擇器的選擇信號，用來表示該運算單元寄存器的初始化，從外部接收輸入數據。運算單元A之間的連接不變，A的四個輸出信號分別作為數據選擇器的一個輸入，另一端輸入來自於外部，用於寄存器初始化的過程。圖9展示的是圖7中單元F的內部細節結構圖。單元F由單元A，B以及八個數據選擇器組成，信號間的連接和運算單元E完全相同。參考文獻[1]R.L.Rivest，A.Shamir，andL.Adleman，「AMethodforObtainingDigitalSignaturesandPublic-KeyCryptosystems，」Comm.ACM，vol.21，no.2，pp.120-126，Feb.1978.[2]T.ElGamal，「APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms，」IEEETrans.InformationTheory，vol.31，no.4，pp.469-472，July1985.[3]N.Koblitz，「EllipticCurveCryptosystems，」Math.Computation，vol.48，no.177，pp.203-209，Jan.1987.[4]P.L.Montgomery，「ModularMultiplicationwithoutTrialDivision，」Math.Computation，vol.44，no.170，pp.519-521，Apr.1985.[5]C.D.Walter，「SystolicModularMultiplication，」IEEETrans.Computers，vol.42，no.3，pp.376-378，Mar.1993.[6]D.E.Knuth，SeminumericalAlgorithms，vol.2，thirded.Addison-Wesley，1997.[7]J.Stein，「ComputationalProblemsAssociatedwithRacahAlgebra，」J.ComputationalPhysics，vol.1，pp.397-405，1967.[8]R.P.BrentandH.T.Kung，「SystolicVLSIArraysforLinear-TimeGCDComputation，」Proc.VLSI』83，pp.145-154，Aug.1983.[9]N.Takagi，「AVLSIAlgorithmforModularDivisionBasedontheBinaryGCDAlgorithm，」IEICETrans.Fundamentals，vol.E8l-A，no.5，pp.724-728，May1998.[10]M.E.KaiharaandN.Takagi，「AHardwareAlgorithmforModularMultiplication/Division，」IEEETrans.Computers，vol.54，no.1，pp.12-21，Jan.2005.[11]R.P.BrentandH.T.Kung，「ASystolicAlgorithmforIntegerGCDComputation，」Proc.SeventhSymp.ComputerArithmetic，pp.118-125，June1985.[12]T.Jebelean，「DesigningSystolicArraysforIntegerGCDComputation，」Proc.Int』lConf.ApplicationSpecificArrayProcessors，pp.295-301，Aug.1994.[13]W.-C.Tsai，C.B.Shung，andS.-J.Wang，「TwoSystolicArchitecturesforModularMultiplication，」IEEETrans.VLSISystems，vol.8，no.1，pp.103-107，Feb.2000.以上所述是本實用新型的優選實施方式，應當指出，對於本技術領域的普通技術人員來說，在不脫離本實用新型所述原理的前提下，還可以作出若干改進和潤飾，這些改進和潤飾也應視為本實用新型的保護範圍。