多字乘法－累加電路和蒙哥馬利模乘法－累加電路的製作方法
2023-06-01 10:28:01 1
專利名稱：多字乘法－累加電路和蒙哥馬利模乘法－累加電路的製作方法
技術領域：
本發明涉及多字乘法-累加(MAC)電路和蒙哥馬利(Montgomery)模MAC電路。更具體地說，本發明涉及適於執行蒙哥馬利算法的模乘法和累加的多字MAC電路，以及涉及基於該電路的蒙哥馬利模MAC電路。
背景技術：
近年來，也被稱為電子商務(e-commerce)的在線交易市場得到了快速地發展，其中在網絡上發生涉及資金轉移的商業行為。人們比以前更加頻繁地在網絡上交換諸如他們的信用卡號碼的個人信息。這些重要的個人信息必須得到保護，以免受惡意第三方的竊聽以及篡改攻擊。因此，使用加密技術以確保電子商務中信息傳輸的安全是必須的。
一種現代的加密算法——公鑰密碼系統採用被稱為公鑰和私鑰的一對密鑰。發送者使用接收者的公鑰對他/她的信息加密，接收者使用他/她自己的秘密的私鑰對接收到的信息解密。假設，例如某人正在在線商店購買物品。在線商店的伺服器將它們的公鑰發送給購買者，使得他/她可以以加密的形式發送他/她的信用卡號碼和其他信息。商店能夠使用它們的私鑰對接收到的信息解碼。該系統的優點在於，公鑰對公眾是完全可得知的。即，公鑰密碼系統允許我們可以和公開了它們的密鑰的任何人進行安全的通信。
公鑰算法的一個例子是RSA，該算法是用三位設計人Ron Rivest、Adi Shamir和Leonard Adleman的名字命名的。RSA密碼系統依賴於大整數的質數分解的困難性，使用模乘過程來確保密文的安全。即，當給定某個數字x和整數n時，對於計算機來說，計算出x的冪模n相對容易，這裡的「模」(mod)是用於計算除以n所得餘數的運算符。但是，由於質數分解的困難性，所以當n非常大時，完成逆過程非常地難，這意味著起始數字x不能被輕易地重現。RSA正是基於模算法的這個性質。
但是，RSA與比如數據加密標準(DES)的對稱密碼系統相比，需要對模乘的更大量的計算，並且這一情況導致需要更快的算法。蒙哥馬利(Montgomery)模乘方法是減少計算負擔的方案之一。當選擇與整數N互質的基數R使得R＞N時，蒙哥馬利算法從滿足0≤T≤R×N的輸入值T計算T×R-1mod N(即，T×R-1除以整數N的餘數)，其中模N被表示為不可約的N階多項式。R-1指代基數R模N的乘法逆元；即，R和R-1滿足R×R-1＝1。通過重複進行加法、乘法和移位運算，而不需要要求重複減法的耗時的除法，該算法實現了「模N」的計算。這尤其在N非常大時，是一個顯著的優點。具體可見P.L.Montgomery所著的「ModularMultiplication without Trial Division」，Mathematics of Computation，第44卷，第170期，第519～521頁，1985年。
更具體地說，使用輸入值A、B、C、R、N和ND，算法以如下方式進行T＝A×B+C…………(1)M＝T×ND mod R …………(2)X＝(M×N+T)/R…………(3)Y＝X-N …………(4)其中，ND滿足條件R×R-1-N×ND＝1，T和M是表示中間變量的變量。X和Y是輸出值，其中，當Y＞0時，X將被選作計算的最終輸出值，當Y≤0時，Y將被選作最終輸出值。每個輸入值A、B、C和N將以例如長度為2048位的多字數據的形式給出，並且在給定存儲器區域中被存儲為一系列數據字。基數R是2的冪(例如，22048)，並且存儲器僅存儲它的指數(該例子中是2048)，而不是R本身的值。基本上，輸入值ND是類似其他輸入值的多字數據。但是，在實際計算中只需要ND的有限數目的位，這取決於所使用的乘法器的位寬。其原因將在後面討論。
第一等式(1)是乘積求和運算，這通常通過使用具有固定運算數據寬度(例如，32位)的乘法器-累加器(MAC運算器)，被實現為(d，e)＝a×b+c+d的迭代，其中d和e分別表示在每次迭代中所獲得結果的較高位和較低位，並且其中d被返回輸入側以在其後的迭代中使用。更具體地說，下面示出了用於執行第一等式(1)的算法(1.1)for(i＝0 to s-1){(1.2)a＝A[i](1.3)d＝0(1.4)for(j＝0 to s-1{(1.5)b＝B[j](1.6)if(i＝＝0)c＝C[j](1.7)else c＝T[i+j](1.8)(d，e)＝a×b+c+d(1.9)T[i+j]＝e(1.10) }(1.11) T[i+s]＝d(1.12)}該過程包括使用循環變量i和j的雙重循環結構，其中從行1.4到1.10的內循環嵌套在從行1.1到1.12的外循環中，使得迭代計算將從較低位進行到較高位。在行1.1、1.4和1.11中的符號s表示通過將數據長度除以字長得到的常數。括號[]用於指向變量的特定數據字，從其最低有效的字算起。例如，在字長為32位的情況中，A
表示變量A底端的32位。
圖11是傳統的多字MAC電路的框圖。該多字MAC電路900由存儲器901、MAC運算器902和寄存器903、904、905、906和907組成。存儲器901存儲用於計算的給定的多字輸入值A、B和C。這些輸入值A、B和C被從存儲器901中讀出，並通過寄存器903、904和905逐字被提供給MAC運算器902。MAC運算器902計算A×B+C，結果T經由寄存器907被回寫到存儲器901中。
圖11的傳統多字MAC電路900如下進行前述算法。假設，有一個控制電路(未示出)產生循環變量i和j，並將它們提供給存儲器901作為它的地址輸入。輸入值A[i]、B[j]和C[j]是字的數組，每個字的寬度為W位。多字MAC電路900從存儲器901讀出各輸入值A[i]、B[j]和C[j]的值，其中可以讀取T[i+j]替代C[j]。這些A[i]、B[j]和C[j]被設定到寄存器903、904和905中，分別作為用於MAC運算器的輸入a、b和c的新的數據。MAC運算器902計算(d，e)＝a×b+c+d(即，執行行1.8)，並且將結果d和e發送到它們對應的寄存器906和907。前一個寄存器906允許d返回到MAC運算器902，作為下一次循環的輸入，而後一個寄存器907將e提供給存儲器901以替換T[i+j]。
傳統的多字MAC電路900以上述的方式進行前面的算法。該過程包括在外循環開始處(行1.2)讀取被乘數a之後，在內循環的每次迭代中從存儲器901讀取輸入值b和c，並將輸出值e寫入到存儲器901。為了不停止流水線而以全時鐘速率運行MAC運算器902，要求存儲器901具有每個時鐘周期傳輸3個字的能力。推薦使用多口存儲器設備或多個單獨的存儲器設備，作為給存儲器901足夠帶寬的解決方案。例如，參見日本專利申請公開No.2002-207589的圖1。
返回參考(1)到(5)的算法，第三等式(3)基本上以與(1)同樣的方式被執行。由於除數R是2的冪，所以可以簡單地通過將被除數右移來完成除以R的運算。前三個等式(1)、(2)和(3)可以逐個地進行，但是由於多字的值ND必須以其全長進行計算，所以該方法並不必然有效。對於這方面，在C.K.Koc，「High-Speed RSA Implementation」，技術報告TR 201，RSA實驗室，第2.0版，11月，第48～49頁，1994年中描述了一種改進的處理技術。根據該文章中所建議的算法，第一等式(1)從底端位到頂端位逐步地計算中間變量T。每次出現T的新值時，該過程對值T的底端的字執行等式(2)，從而確定另一個中間變量M的底端的字。利用T和M的這些局部值，該過程前進到等式(3)以計算輸出值X的對應的部分。儘管等式(1)中的ND實際上是多字值，但是改進的算法並不同時需要所有的字，而只是每次一個字。
發明內容
本發明提供了一種多字乘法-累加(MAC)電路，該電路能夠對每個被提供為多字數據的給定輸入值進行MAC運算。該電路包括如下的元件(a)為多個多字數據提供存儲的存儲器；(b)MAC運算器，該MAC運算器具有不同位長的被乘數和乘數輸入埠，用於計算從存儲器讀出的多字數據的乘積的和；和(c)用於將多字數據提供給MAC運算器的多個寄存器，其中在每個時鐘周期中要被提供的數據量被調節，使得由所述MAC運算器在一個時鐘周期中所消耗和產生的數據總量將等於或小於存儲器在一個時鐘周期中所能傳輸的最大數據量。
當結合以舉例方式圖示了本發明優選實施例的附圖時，本發明的上述以及其他目的、特徵和優點將在下面的說明中變得清楚。
圖1是根據本發明實施例的多字MAC電路的概念圖。
圖2示出了根據本發明更具體的實施例的蒙哥馬利模MAC電路的結構。
圖3示出了在本發明實施例中所使用的MAC運算器的結構。
圖4示出了根據本發明實施例的存儲器管理。
圖5示出了控制命令寄存器的示例。
圖6和圖7是示出了根據本發明實施例的蒙哥馬利模MAC電路的操作的時序圖的第一和第二部分。
圖8是具有單個MAC運算器的蒙哥馬利模MAC電路的框圖。
圖9是具有三個MAC運算器的蒙哥馬利模MAC電路的框圖。
圖10示出了MAC運算器的結構，該MAC運算器的多輸入加法器被中間寄存器分為兩級。
圖11是傳統的多字MAC電路的框圖。
具體實施例方式
在「背景技術」部分中，我們已經討論了多字MAC電路為何需要具有高數據傳輸能力的存儲器。但是，為此目的而使用多口存儲器將導致晶片尺寸變大。此外，為個別的變量分配單獨的存儲器使得布線設計更加困難。另一方面，單口存儲器佔用的晶片空間較少，但是它的傳輸數據的能力限於每個時鐘周期一個字，這對於MAC運算器來說太慢而不能在每個時鐘周期產生輸出。這意味著，由於缺乏足夠的存儲器帶寬，MAC運算器不能呈現所希望的性能。回想例如為執行等式(1)所設計的多字MAC電路900。因為這種傳統的電路僅僅允許在依次接收了3個單字輸入值A、B和C之後才開始，所以它耗費至少3個時鐘周期來產生單個MAC結果。
鑑於上述情況，本發明的一個目的是提供一種適於利用單口存儲器的更加有效的多字乘法-累加電路。
本發明的另一個目的是提供一種適於利用單口存儲器的更加有效的蒙哥馬利模乘法-累加電路。
多字MAC電路下面將參考附圖對本發明優選的實施例進行詳細地說明，其中假設基數R是2的冪，並且N是奇數。
圖1是根據本發明實施例的多字乘法-累加(MAC)電路的概念圖。為了從給定的多字輸入數據A、B和C計算A×B+C，所圖示的多字MAC電路10包括存儲器11、MAC運算器12和寄存器13、14、15、16和17。存儲器11是單口存儲器，用於存儲輸入值A、B和C以及接收計算結果，其中的每個都是例如長度為2048位的多字數據。存儲器11的數據寬度由指代「word」的符號「W」標註。即，存儲器11提供每個時鐘周期一個字(1W)的數據傳輸速度。
輸入三個輸入值A、B和C，MAC運算器12進行被乘數A和乘數B的乘法，然後將C與乘積相加，其中被乘數和乘數的數據寬度是不同的。更具體地說，被乘數A的寬度是三個字(3×W)，而乘數B的寬度是三分之一個字(W/3)。MAC運算器12從這樣的輸入值計算A×B+C，並輸出結果。
圖1最上面的寄存器13存儲了A的三個字(3×W)的部分，A是由多個字構成的輸入值。括號中的值用作指明輸入值的特定部分的索引。具體地說，在A[i]中的索引i在0≤i≤s-1的範圍內變化，其中s表示構成輸入值A的數據字的數目(即，s等於由A的數據長度除以字長W)。從而，A[i]指從零算起的第i個字，A
是最低有效的字。寄存器13存儲A[i]、A[i+1]和A[i+2]，它們是A的第i個字到第(i+2)個字。這三個字被輸入到MAC運算器12作為輸入「a」。
下兩個寄存器14和15被用來存儲輸入值B和C，每個寄存器中一個字。這些寄存器14和15中的每一個都起到讀取緩衝器的功能，其將給定數據存儲一段時間，同時在每次被請求的時候輸出所存儲的數據的一部分。即，它們通過與時鐘信號(未示出)同步地每次發送它們所存儲的數據的三分之一(W/3)，向MAC運算器12提供輸入值「b」和「c」。這樣的緩衝功能能夠很容易地通過將它們設計為移位寄存器來實現。
倒數第二個寄存器16存儲了MAC運算器輸出的較高的三個字(3×W)的部分，被稱為輸出「d」，用於被MAC運算器12自身用作下一次運算周期的輸入。相應地，MAC運算器12計算(d，e)＝a×b+c+d。
最下面的寄存器17存儲了MAC運算器輸出的最低的三分之一個字(W/3)的部分，被稱為「e」輸出。該寄存器17起到寫緩衝器的功能，其從MAC運算器12接收輸出數據，每次三分之一個字(W/3)，並且當累加的數據大小到達一個字(W)時將其寫到存儲器11中。
照這樣來安排寄存器13到17。注意，通過MAC運算器輸入埠的不一樣的位寬，在每個時鐘時刻要被提供給MAC運算器12的數據量被優化，使得被提供給MAC運算器12和由MAC運算器12產生的數據總量將與存儲器11所能提供的數據傳輸速率相平衡。在圖1的例子中，MAC運算器12在一個時鐘周期中消耗B和C的寄存器值的三分之一(W/3)，並且在該周期中產生長度為三分之一個字(W/3)的結果值。注意，因為MAC輸出的前三個字(3×W)被返回到寄存器16以在下一個時鐘周期中使用，所以沒有考慮它們。從而，在當前情況中，在每個單個的時鐘周期中，所產生和消耗的數據總量等同於一個字(W)，這等於我們為存儲器11所假設的最大數據傳輸能力(W每時鐘周期)。該帶寬計算證明了使用單口存儲器是合理的。
與傳統的具有相等輸入位寬的MAC運算器不同，本發明的MAC運算器12具有位寬不同的被乘數和乘數的輸入埠，用於計算乘積的和。所提出的MAC運算器12的這種非對稱設計允許通過使用合適加速技術來提高性能，加速技術比如是分布式進位處理(將在後面說明)和流水線數據處理(也將在後面說明)。此外，對於它們的實現所需的門電路數目，所提出的MAC運算器12與傳統的MAC運算器是相當的。
圖1的多字MAC電路10如下操作。根據本發明的實施例，多字MAC電路10執行具有雙循環結構的算法，除了對寄存器的數據寬度的選擇之外，其與傳統電路的算法類似。即，其通過重複外循環和內循環，進行MAC運算。外循環從較低位到較高位向MAC運算器12提供輸入值A，每次3個字(3W)，而內循環提供另外的輸入值B和C，每次三分之一個字(W/3)。
開始的時候，多字MAC電路10訪問存儲器11三次，以讀取多字輸入數據A的指定部分(A[i]、A[i+1]、A[i+2])，首先發生的是A的底端的三個字。從存儲器11所讀出的這三個字的值被設定到寄存器13中，用於由MAC運算器12用作它的「a」輸入。然後，另外兩個讀周期接著從存儲器11將另外的輸入數據B和C的一個字長的部分設定在它們對應的寄存器14和15中。B和C的這些值不是被整個地提供，而是每次只提供W/3給MAC運算器12，以用作它的「b」和「c」輸入。
MAC運算器12在一個時鐘周期中計算(d，e)＝a×b+c+d，產生了三又三分之一個字(3×W+W/3)的輸出數據。「d」輸出，或MAC輸出的較高三個字的部分，被發送到寄存器16。該寄存器值「d」將被用作隨後的時鐘周期的輸入，在該時鐘周期中，寄存器14和15將提供「b」和「c」輸入的下三分之一(W/3)。另一方面，「e」輸出，或MAC輸出的最低三分之一個字，被發送到寄存器17以緩衝。該寄存器17的內容直到它被「e」輸出的三個實例充滿時，將被傳輸到存儲器11。
內循環過程以上述方式結束它的第一次迭代，消耗了在寄存器14和15中的單個字的數據。然後，第二次迭代開始於從存儲器11將多字輸入值B和C的接下來的有效字加載到它們對應的寄存器14和15中，從而允許MAC運算器12以如上所述的同樣的方式計算(d，e)＝a×b+c+d。
因為在多字MAC電路10中所使用的存儲器是單口存儲器，所以不可能同時讀出B和C的新的值。為了將這些從寄存器14和15提供給多字MAC電路10的兩個輸入B和C同步，舉例來說，前一寄存器14具有比另一寄存器15更多的位。於是，將B加載到寄存器14的存儲器讀周期首先發生，該寄存器通過它的擴展位將數據移位，這期間其另一寄存器15能夠從存儲器11接收C。於是，兩個寄存器的值同時到達它們各自的MAC運算器12的輸入埠，每次W/3，從而使得MAC運算器12能夠繼續運行而不中斷。這將在下面詳細地說明。
在完成對輸入數據B和C的所有字的MAC運算時，多字MAC電路10通過讀出輸入數據A的接下來的有效的三個字，而前進到外循環過程的下一次迭代。在加載新的一組A[i]、A[i+1]和A[i+2]時，多字MAC電路10執行更多的迭代，直到A的整組數據字都被進行了計算。
利用本發明的上述電路結構，MAC運算器12能夠使用帶寬有限的單口存儲器進行操作，而在其使用中不犧牲效率。即，所提出的電路能夠在每個時鐘周期產生其輸出，從而使得可以提供有效的多字乘法器-累加器。
蒙哥馬利模乘法-累加我們將描述作為圖1的多字MAC電路10的一個應用的蒙哥馬利模乘法-累加。我們所提出的過程用給定的輸入數據A、B、C和N執行蒙哥馬利模乘法-累加，並將結果X和Y以及Y的符號輸出到單口存儲器。為了舉例說明的目的，我們假設輸入數據A、B、C和N的長度為256位，基數R是2256，並且另外的輸入數據ND的長度為64位。該過程還使用變量T和M來表示中間結果。給定的256位的輸入值A和B每個都被劃分為16位的段，被如下表示A(255:0)＝{a15，a14，a13，a12，...a3，a2，a1，a0}；B(255:0)＝{b15，b14，b13，b12，...b3，b2，b1，b0}；其中，a15和b15是最頂端的段，而a0和b0是最底端的段。該表示法也適用於其他的值和變量C、N、T、M、X和Y。
使用上面定義的輸入值和變量，蒙哥馬利模乘法-累加的算法如下進行T＝A×B+C …………(5)M＝{t3，t2，t1，t0}×ND mod 264…(6)X＝(M×N+T)/264…………(7)Y＝X-N …………(8)其中，當Y＞0時，X將被選作計算的最終結果，而當Y≤0時，Y將被選作計算的最終結果。注意，這裡在等式(6)和(7)中的除數不是R＝2256本身，而是264。這是因為該算法使用了我們先前參考C.K.Koc的「High-Speed RSA Implementation」所提到的技術。更具體地說，在計算等式(5)的過程中，從較低端到較高端按照步進的方式確定中間變量T。每次當T的新的部分變得可用時，算法通過引用T的底端的字計算等式(6)，來確定另一中間變量M底端的字。然後，通過將T和M的這些值應用到等式(7)獲得輸出值X。
圖2示出了根據本發明實施例的蒙哥馬利模乘法器-累加器(MAC)電路100的結構。為了實現等式(5)到(8)的蒙哥馬利模乘法-累加算法，所圖示的電路100使用了串聯的兩個MAC模塊110和120，每一個都具有如圖1所示的多字MAC電路10的功能。這些MAC模塊110和120被耦合到存儲器(在圖2中未示出)。本實施例的蒙哥馬利模MAC電路100還包括減法單元130來計算等式(8)。
儘管圖2沒有將其示出，但是蒙哥馬利模MAC電路100還包括64位寬的單口存儲器，其只允許在一個時鐘周期中對單個地址的要麼讀取要麼寫入的訪問。該存儲器存儲用於計算的輸入值A、B、C和N，以及接收將作為計算結果而獲得的輸出值X和Y。它也可以作為中間變量T和M的臨時存儲裝置。專用於存儲其他輸入值R和ND的寄存器在圖2中也沒有被示出，由於它們的數據寬度較小，因此與存儲器分開設置。
第一MAC模塊110負責等式(5)，為此，它使用MAC運算器111(稱為「第一MAC運算器」，以與第二MAC模塊中的對應部分相區別)和它周邊的數據寄存器，這些寄存器包括A寄存器(A-REG)112、B寄存器(B-REG)113、C寄存器(C-REG)114和D寄存器(D-REG)115。給定輸入值A、B和C，第一MAC運算器111計算A×B+C，其中被乘數A和乘數B具有不同的位寬。具體地說，第一MAC運算器111為得到乘積項A×B而進行64位乘16位的乘法。
A寄存器112存儲從存儲器中讀出的給定的多字輸入值A的64位部分。B寄存器113存儲從存儲器中讀出的給定的多字輸入值B的64位部分，其與時鐘信號(未示出)同步地從最低的字開始每次16位地被傳輸到第一MAC運算器111。此外，B寄存器113具有32位容量的附加緩衝器，因此是「64+32位」。雖然存儲器不允許在單個時鐘周期中同時讀出兩個輸入值B和C，但是可以通過比C提前兩個周期讀取B，將B和C同時提供給第一MAC運算器111。
在外循環的第一次迭代中，C寄存器114存儲從存儲器中讀出的給定的多字輸入值C的64位部分。在外循環第二次和隨後的迭代中，它被用來存儲輸出值X。C寄存器114自身每次右移16位，因此在與時鐘信號(未示出)同步地從最低的字開始將數據傳輸到第一MAC運算器111。
D寄存器115存儲第一MAC運算器111所產生的80位的中間變量T的較高64位。該D寄存器115實際被提供為68位寬的寄存器，以存儲由第一MAC運算器111產生並被發回給第一MAC運算器111的四個進位位，這將在下面說明。
利用上述寄存器的配置，第一MAC運算器111以每個時鐘周期16位的速率取得輸入值B和C。儘管MAC輸出具有80位的寬度，但是較高64位將用作下一個時鐘周期的MAC輸入，這意味著輸出數據的淨數僅是16位。在這種情況中，每個單個時鐘周期中所產生和消耗的數據總量是48位，這低於我們對單口存儲器所假設的最大數據傳輸能力(每個時鐘周期64位)。
第二MAC模塊120由MAC運算器121(第二MAC運算器)和它周邊的數據寄存器組成，這些寄存器包括F寄存器(F-REG)122、G寄存器(G-REG)123、E寄存器(E-REG)124和H寄存器(H-REG)125。第二MAC運算器121負責等式(6)和(7)。在計算{t3，t2，t1，t0}×ND時，第二MAC運算器121集中於較低的64位，以獲得模264的運算。然後將等式(6)的結果應用到隨後的等式(7)的處理，於是得到M×N+T。
在計算等式(6)時，F寄存器122存儲從另一寄存器(未示出)接收的輸入值ND。當計算等式(7)時，它存儲從I寄存器133(後面將說明)接收的中間變量M。
G寄存器123存儲從存儲器中讀出的給定的多字輸入值N的64位部分。該G寄存器123在每個時鐘周期自身右移16位，從而從最低的位開始將N的值提供給第二MAC運算器121。但是，當計算等式(6)的M時，G寄存器123將加載另一個中間變量T的較低16位，以由第二MAC運算器121使用。
E寄存器124存儲從等式(5)獲得的中間變量T的較低16位，以由第二MAC運算器121使用。當計算等式(6)時，將E寄存器124設為零，因為中間變量T的最低64位{t3，t2，t1，t0}在那時進入了G寄存器123。
H寄存器125存儲第二MAC運算器121所產生的80位中的較高64位。該H寄存器125實際上為68位寬的寄存器，另外的四個位的部分存儲由第二MAC運算器121所產生並被發回第二MAC運算器121的進位位，如將在下面所說明的。
利用上述寄存器的配置，在處理等式(6)中，第二MAC運算器121以每個時鐘周期16位的速率取得中間變量T的值。儘管所產生的MAC輸出具有80位的寬度，但是它的較高64位被用作下一個時鐘周期的MAC輸入，這意味著僅僅是剩餘的16位被視為真正的輸出。因此，在每個單個時鐘周期中所產生和消耗的與等式(6)有關的數據總量是32位。
當計算等式(7)時，第二MAC運算器121以每個時鐘周期16位的速率取得輸入值N以及中間變量T，同時在每個時鐘周期產生16位的輸出數據。這些數據消耗和產生加起來一共是48位。從上面的計算可以看出，所需的數據速率低於我們對單口存儲器所假設的最大數據傳輸能力(每個時鐘周期64位)。
減法單元130由16位的減法器131和它相關聯的寄存器組成，這些寄存器包括J寄存器(J-REG)132、I寄存器(I-REG)133、K寄存器(K-REG)134以及進位寄存器135和136。16位的減法器131負責等式(8)，用於產生最後的計算結果。J寄存器132存儲從存儲器讀出的多字輸入值N的64位部分。該J寄存器132每個時鐘周期自身右移16位，從而從最低的位開始將N提供給16位減法器131。
I寄存器133接收第二MAC模塊120的16位的輸出，其要麼是由等式(6)獲得的中間變量M，要麼是等式(7)右側的M×N+T的值。當中間變量M累積到64位時，它被提供給F寄存器122，以由第二MAC模塊120計算等式(6)。M×N+T的值在除以264之後將被寫入到存儲器中。該除法可以通過跳過存儲器寫的前四個時鐘周期來實現，即，拋棄M×N+T的最低64位。更詳細的細節將在下面進行討論。
K寄存器134累加等式(8)的Y，該值每次從16位的減法器131輸出16位，直到數據數量達到64位，並準備好被傳輸到存儲器。
MAC運算器的結構在討論圖2的蒙哥馬利模MAC電路100的操作的細節之前，我們將描述如何構建MAC運算器111和121以及如何管理存儲器，並給出控制命令寄存器的例子。
圖3示出了在本發明實施例中所使用的MAC運算器的結構。如從該圖可以看出的，第一MAC運算器111被設計來進行(64位×16位+16位+64位)的計算，從而輸出80位。AIN[63:0]指代輸入值A的64位數據，它從圖2中所說明的A寄存器112被提供。BIN[15:0]指代輸入值B的16位數據，它從B寄存器113被提供。類似地，CIN[15:0]表示輸入值C的16位數據，它從C寄存器114被提供。DIN[63:0]指代從D寄存器115所提供的64位數據，其保存了80位寬MAC輸出中的頂端的64位。XOUT[79:0]指代第一MAC運算器111的80位的輸出數據。YOUT[3:0]和YIN[3:0]表示第一MAC運算器111的4位的進位輸出和進位輸入，前者被發送到D寄存器115，後者接收自D寄存器115。
第一MAC運算器111由部分乘積發生器201、多輸入加法器塊202以及多個16位進位加法器203到207組成。部分乘積發生器201計算AIN和BIN的部分乘積，其被標為AB00[63:0]到AB15[63:0]。儘管沒有示出細節，但是該部分乘積發生器201被構建為包含四組並聯布置的16×16部分乘積電路的與(AND)陣列。多輸入加法器塊202將這些部分乘積AB00[63:0]到AB15[63:0]、CIN和DIN加總。五個16位的進位加法器203到207共同承擔分解進位位的任務。它們僅被要求在每個時鐘周期中解決它們自己16位的輸出。
進位加法器203到207接收四個進位輸入YIN[3:0]，並產生四個進位輸出YOUT[3:0]，對輸出數據的每16位部分產生一位進位輸出。進位輸出YOUT[3:0]被設定在D寄存器115中，以便在MAC操作隨後的周期中用作進位輸入YIN[3:0]。進位加法器的這種結構使進位信號傳播的延遲最小化，並且其因此減少了電路的最後結果的延遲時間，這使得可以提高工作時鐘的頻率。
當第一MAC運算器111的AIN和BIN具有不同的位寬時，進位加法器的位寬可以被確定為使得它適合AIN或BIN中較小的那一個。
對於位寬的設置進一步地說，傳統的MAC運算器具有(W)×(W)+(W)+(W)的結構，其中W表示一個字的長度，因此它們的進位加法器具有寬度W。另一方面，在本實施例中的第一MAC運算器111具有64×16+16+64或(2W)×(W/2)+(W/2)+(2W)的結構，其中字寬W是32位，因此它的全體進位加法器203到207具有寬度W/2或16位。當傳統的MAC運算器產生與所提出的第一MAC運算器111相同量的輸出時，後者由於其輸出延遲時間較小，因此能夠更快地運行。必須注意到，如本實施例中的那些的具有被劃分開的進位處理體系結構的MAC運算器在計算結束時將需要一些額外的時間來處理待處理的進位。但是，這種被劃分開的體系結構的缺點可以從其更高的工作時鐘頻率及由此得到的運算時間的減少的優勢中得到很好地補償，尤其是在要處理的數據比算術運算器的字長要長得多的多字MAC應用中。儘管我們已經討論了第一MAC模塊110中的第一MAC運算器111，這也適用於第二MAC模塊120中的第二MAC運算器121。
存儲器數據管理下面我們將說明在本發明的實施例中如何管理存儲器。本實施例的蒙哥馬利模MAC電路100被設計成與單個的一體的存儲器系統一起運行，該存儲器系統存儲不同種類的用於計算的數據。每段被存儲的數據能夠通過它的頭地址(top address)及數據長度進行識別。應當可以在計算開始之前為所有的輸入值A、B、C和N，以及輸出值X和Y分配適當的存儲器區域。
儘管在附圖中沒有明確示出，但是蒙哥馬利模MAC電路100處在中央處理單元(CPU)或其他規定輸入數據和計算結果的設備的控制下，在下面將其稱為「外部控制器」。該外部控制器必須依據等式(8)中所進行的減法運算的結果，選擇X或Y作為它的最終計算輸出。選擇要輸出哪一個的步驟將增加外部控制器的存儲器管理任務的複雜性。
圖4示出了根據本發明實施例的存儲器管理。除上述外部控制器外，蒙哥馬利模MAC電路100提供多個指針寄存器，作為它的存儲器管理機制的一部分。這些指針寄存器保存每個存儲器區域的頭地址，而不進行複製。在圖4的示例中，「Amem」、「Bmem」...「Nmem」是被外部控制器用來指定存儲器上的數據區域的名稱，它們與單獨的指針寄存器唯一地相關聯。即，一個指針寄存器允許外部控制器指定單個的特定數據區域。例如，當外部控制器指定「Amem」時，它引用從由與該名稱「Amem」相關聯的指針寄存器指向的物理存儲地址「011000」開始的數據區域。
圖5示出了控制命令寄存器的示例。所圖示的控制命令寄存器可以由外部控制器讀取和寫入。如圖4所說明的，在存儲器中所定義的數據區域通過它們的名稱「Amem」到「Nmem」而被引用，為它們的每一個都指派了唯一的四位代碼。為了給每個輸入值分配存儲空間中的區域，圖5的控制命令寄存器具有被命名為「N arg」、「A arg」等的六個四位欄位，這裡「arg」是「自變量」的縮寫。這些自變量欄位將由表示具體數據區域的四位代碼所填充。
圖5的控制命令寄存器的長度是32位，其中bit[3:0](最低的四位)為輸出值Y指定數據讀/寫(R/W)區域，bit[7:4]為另一輸出值X指定工作區域，其中如果需要的話，X和Y將交換它們的位置。術語「工作區域」指代用於臨時數據的存儲器區域，其內容可以用其他數據重寫或變得不確定。bit[11:8]為輸入值C指定數據讀/寫區域。類似的，bit[15:12]和bit[19:16]分別為另外的輸入值B和A指定數據讀/寫區域。bit[23:20]為另一輸入值N指定讀/寫區域。最後，bit[31]是用於開始或停止計算的控制位。
利用上述存儲器管理機制，在讀或寫特定的輸入或輸出數據時，蒙哥馬利模MAC電路100確定出將使用哪個物理存儲器區域。這通過識別由外部控制器已經指定作為數據源或目標的每個數據區域名稱，以及引用與該名稱相關聯的指針寄存器來實現。然後，蒙哥馬利模MAC電路100以我們在等式(5)到(8)中已經描述的方式開始計算。所得到輸出值X和Y被存儲在它們各自的所指定的存儲器區域中。如果最後的等式(8)產生Y＜0，那麼蒙哥馬利模MAC電路100必須交換X和Y。該任務能夠通過簡單地交換相應的指針寄存器的內容(即，所分配的數據區域的頭地址)來完成。
外部控制器先前通過指定它們各自的數據區域名稱定義了輸出數據區域和工作區域。通過改變指針寄存器的值，在保持數據區域名稱和它們的預期數據內容之間的關聯的一致性的同時，能夠移動或交換存儲器中的數據條目。這一特徵幫助了外部控制器管理存儲器區域。
蒙哥馬利模乘法-累加過程可以包括存儲器值和比如「0」或「1」的常數值之間的運算，如在T＝A×1+0的計算中。命令寄存器允許指定常數「0」或「1」，以替代數據區域名稱，因此不再需要將這些常數值寫入到存儲器中。如圖5所示，命令寄存器中的自變量欄位可以包括特殊代碼，該特殊代碼不是被指定用於存儲器區域的，而是用於常數值的。以這種方式為蒙哥馬利模MAC電路100提供常數值。
上述存儲器管理機制和控制算法使得外部控制器易於管理蒙哥馬利模MAC電路100。雖然這樣的機制和算法能夠被實現為外部控制器本身的一部分，但是如果外部控制器是能力不足以處理這些任務的嵌入式處理器，則可以不選擇該選項。在這種情形中，上述被集成在蒙哥馬利模MAC電路100中的指針寄存器將極大地幫助外部控制器來管理存儲器中的大量數據，因而使得蒙哥馬利模MAC電路100能夠表現出它的全部性能。
蒙哥馬利模MAC電路的操作現在參考圖6和圖7的時序圖，我們將更加詳細地討論圖2的蒙哥馬利模MAC電路100是如何操作的。
圖6和圖7是示出根據本發明實施例的蒙哥馬利模MAC電路的操作的時序圖的第一和第二部分。在該時序圖最頂端的一行上所示出的是時鐘周期序號，其後是指示來自外部控制器的存儲器讀或寫操作的「存儲器訪問」。標題為「存儲器讀數據」和「存儲器寫數據」的第三和第四行分別示出了從存儲器讀出的數據和向存儲器寫入的數據。隨後的行表示圖2中所描述的蒙哥馬利模MAC電路100的每個寄存器的值。它們是A寄存器112的全部64位、B寄存器113的較低16位、C寄存器114的較低16位、D寄存器115的全部64位、E寄存器124的全部16位、F寄存器122的全部64位、G寄存器123的較低16位、H寄存器125的全部64位、I寄存器133的較高16位、J寄存器132的較低16位以及K寄存器133的較高16位。
該時序圖中所用符號如下「-」短劃線標記表示計算的中間結果。陰影表示「不確定」。在I寄存器133的行中所示出的劃叉標記「×」指代不需要處理的輸出值。標註「無關」表示該值可以是「0」或「1」。
處理開始於對於給定輸入值A的最低64位A{a3，a3，a1，a0}的步驟。直到T1的時間被用於計算等式(6)的中間變量M。來自外部控制器(未示出)的存儲器讀訪問發生在時鐘周期#1到#3，其將三個輸入值B、A和C的64位部分依這樣的順序從存儲器中讀出，並將這些值設定到對應的寄存器中。具體地說，A{a3，a3，a1，a0}被設定到A寄存器112，B{b3，b3，b1，b0}被設定到B寄存器113，C{c3，c3，c1，c0}被設定到C寄存器114。這些值由第一MAC運算器111進行計算。
上述步驟之後的第一MAC運算是{a3，a3，a1，a0}×b0+c0，如早先所解釋的那樣，本實施例的第一MAC運算器111被設計來一次處理輸入值B和C的1 6位，同時使用另外的輸入值A的全部64位。該MAC運算產生中間變量T的較低16位或t0，其被發送到G寄存器123。G寄存器123中的t0的值被提供給第二MAC運算器121，與F寄存器122中的另一個64位的輸入值ND一起用於等式(6)的計算。結果的底端16位，實際上是中間變量M的最低16位，進入到I寄存器133的最頂端16位。第一MAC運算器111對剩餘的b1到b3以及c1到c3重複上述處理，從而使得I寄存器133通過自身移位來接收更多的16位結果m1、m2和m3。以這種方式，在I寄存器133中獲得了M{m3，m3，m1，m0}。
對輸出值X的計算開始於時間T1。存儲器讀周期發生在時鐘周期#5，以取得輸入值B的最低64位部分B{b3，b3，b1，b0}，在下一周期之後的時鐘周期，發生另一個讀周期，以讀取C的最低64位部分，或C{c3，c3，c1，c0}。如早先所提到的，由於B寄存器113具有長度為32位的附加緩衝器，所以B寄存器113和C寄存器114的底端16位被同時提供給第一MAC運算器111。由於A寄存器112已經加載有A的最低64位，所以第一MAC運算器111迅速執行等式(5)，並從而每次16位地產生中間變量T。所得到的t0、t1、t2和t3以這一順序被傳輸到E寄存器124，用於第二MAC運算器121。還被提供給對第二MAC運算器121的有F寄存器122中的64位中間變量M和G寄存器123中的64位輸入值N。N已經在時鐘周期#8從存儲器中被讀出，並且它的四個16位段(n0、n1、n2和n3)逐個被發送到第二MAC運算器121。第二MAC運算器121計算等式(7)，並將結果X設定到I寄存器133的頂端16位。但是，所得到的I寄存器133中的64位值將不被寫入到存儲器中，因為如我們早先所描述的，等式(7)涉及除以264。圖6示出了有劃叉標記(「×」)的被拋棄數據。
在時鐘周期#9，發生另一個存儲器周期，以讀取輸入值B的第二部分B{b7，b6，b5，b4}。之後是對於其他輸入值C和N的類似的讀周期，從而允許兩個MAC運算器111和121分別計算等式(5)和(7)。所得到的輸出值X被每次16位地發送到I寄存器133。當X{x3，x2，x1，x0}已經在I寄存器133中時，在時鐘周期#18發生存儲器寫周期，從而將X的64位輸出值存入存儲器。
以大致相同的方式計算剩餘的輸出值X{x7，x6，x5，x4}、X{x11，x10，x9，x8}和X{x15，x14，x13，x12}。例外是計算輸出值X的最後四個段X{x15，x14，x13，x12}的時候。在該計算期間，等式(5)中的輸入值B和C被強制成為零，在等式(7)中，M是「無關」，N被設定為零。
這以A{a3，a2，a1，a0}，即輸入值A的前64位的段，結束第一步驟。下一個步驟在T2以A的第二段或A{a7，a6，a5，a4}開始。但是，與第一步驟不同，該新的步驟和隨後的步驟使用在存儲器中的先前的輸出值X代替C。
然後以圖7所示的方式處理第三段A{a11，a10，a9，a8}和第四段A{a15，a14，a13，a12}。在最後的步驟中，16位減法器131承擔在等式(8)的執行中的任務，以產生Y的輸出值。當第二MAC運算器121產生另外的輸出X新的16位值時，16位的減法器131從J寄存器132接收輸入值N{n3，n2，n1，n0}的各部分。由於在時鐘周期#87的存儲器讀訪問，N的值已經被加載到J寄存器132中了。減法運算的結果被每次16位地傳輸到K寄存器134，這在它們構成64位輸出值Y{y3，y2，y1，y0}和在時鐘周期#94被一起寫入到存儲器之前進行。但是，為了給這樣的存儲器寫周期分配時間，需要暫時停止乘法-累加流水線。剩餘的輸出值Y{y7，y6，y5，y4}、Y{y11，y10，y9，y8}和Y{y15，y14，y13，y12}以與上面相同的方法被計算並被存入存儲器中。
如從上面的說明能夠看出的那樣，所提出的蒙哥馬利模MAC電路100在四個時鐘周期的時期中產生三個64位的存儲器讀和一個64位的存儲器寫。該存儲器帶寬需求對於電路100足夠小，以有效地使用數據寬度為64位的單口存儲器進行操作，使得它的內部MAC運算器111和121能夠以完全的時鐘速率運行。
儘管我們已經說明了具有兩個MAC運算器的示例性實施方式，但是本發明不應該限於該特定類型。作為另一種方法，可以引入分時技術，以通過使用單個MAC運算器來執行等式(5)到(7)，而不會對MAC運算器使用的效率造成太多負面影響。
作為再一種方法，等式(5)到(7)可以由三個級聯的MAC運算器同時處理。儘管其在計算M＝T×ND中的較低的MAC運算器使用，但是由於該體系結構總體上提供了流水線上更穩定的數據流，因此它能夠進行更快的計算。
此外，考慮到每個輸入值A、B和N不是單個的字，而是由多個數據字組成的，因此也可以通過使用四個或更多的串聯的MAC運算器對這樣的輸入值的多個數據字同時處理。這是另一種加快計算的方法。
單MAC運算器結構圖8是具有單個MAC運算器的蒙哥馬利模MAC電路的框圖。儘管該電路實際上需要用於等式(8)的減法器，但是由於我們已經在圖2中對這樣的電路的結構和功能進行了討論，所以該框圖就對此進行了省略。基於同樣的理由，也從圖示中省略了64位寬的用於存儲輸入值和輸出值的單口存儲器。
所圖示的蒙哥馬利模MAC電路300由MAC運算器301和其相關聯的寄存器組成，這些寄存器包括A寄存器(A-REG)302、B寄存器(B-REG)303、C寄存器(C-REG)304、D寄存器(D-REG)305和E寄存器(E-REG)306。前三個寄存器302到304被用來為MAC運算器301提供輸入值，比如64位的輸入值A、B、C、N和ND；中間變量M和T；以及輸出值X。
A寄存器302是65位的寄存器，其為MAC運算器301提供從存儲器讀出的A或ND或M的64位的值，並具有從64位部分擴展的1個附加位。B寄存器303存儲從存儲器讀出的A、B、或N的64位的值，並將其每次16位地提供給MAC運算器301。B寄存器303具有附加的32個位，因此其總長度為96位。與此相似，C寄存器304存儲從存儲器讀出的C、T或X的64位的值，並將每次16位地提供給MAC運算器301。
D寄存器305和E寄存器306接收MAC運算器301的輸出。D寄存器305保存較高65位，以在下一個周期中用作MAC運算器301的輸入，而E寄存器306則在每次進行MAC運算時接收最低的16位。當填充滿它的64位容量時，E寄存器306將數據送出到存儲器作為中間變量T或輸出值X，或送出到A寄存器302作為中間變量M。
圖8的蒙哥馬利模MAC電路300通過對單個MAC運算器301的分時來處理所有的等式(5)到(7)。該MAC運算器301被配置來執行65×16+16+65(位)的MAC運算，並且根據下面所述的原因產生81位的輸出。
在二進位方法用於求冪的情況中，作為蒙哥馬利模乘法-累加的應用，該過程可能涉及平方運算(T＝A×A)，並因而希望加速這類計算。考慮到其雙循環過程，可以通過如下過程將迭代的數目減少將近一半如果i＞j則跳過；如果i＝j則計算T＝T+A[i]×A[j]；如果i＜j則計算T＝T+2×A[i]×A[j]。項2×A[i]×A[j]可以通過將A[i]×A[j]的結果左移1位來實現。在MAC運算器301中實現該功能將增加電路結構的複雜性，這將導致更長的判別途徑。根據圖8的結構，位移功能可以通過對A寄存器302增加1個附加位來實現，使得如果i＜j，則經擴展的A寄存器302將自身左移，以將給定輸入值A[i]乘2。本發明的這一方法成功的加快了計算，同時保持了MAC運算器301儘可能的簡單。
三MAC運算器結構儘管在說明本發明時我們已經假設使用單口存儲器，但是用於存儲輸入值和輸出值的存儲器可以是多口存儲器。如已經解釋的那樣，在最後階段的進位處理可以被實現為用於更快計算的多個加法器。此外，由於本發明的用於乘數和被乘數的輸入數據寬度不相同，所以在MAC運算器的設計中提供了更多的變化。這包括集成許多MAC運算器以增加計算速率，如將在圖9中所描述的那樣。這些流水線技術可以與多口存儲器體系結構的優點相結合，這將使得可以進一步加速。
圖9是具有三個MAC運算器的蒙哥馬利模MAC電路的框圖。該電路對於三個等式(5)到(7)中每一個使用一個專用的MAC運算器。儘管該電路實際上需要用於等式(8)的減法器，但是由於我們已經在圖2中對這樣的電路的結構和功能進行了討論，所以該框圖對此進行了省略。從圖中也省略了用於輸入值和輸出值的存儲器，對於該存儲器，我們假設使用數據寬度為512位的三口存儲器。
所圖示的蒙哥馬利模MAC電路400由三個MAC運算器411、421和431以及多個耦合到它們的寄存器組成。第一MAC運算器411計算等式(5)，接收來自A寄存器(A-REG)412的輸入值A、來自B寄存器(B-REG)413的B以及來自C寄存器(C-REG)414的C或X，其中X是計算的最終結果。MAC輸出的頂端512位被設定到D寄存器(D-REG)415中，以用作第一MAC運算器411的下一個輸入。
第二MAC運算器421計算等式(6)，接收來自H寄存器(G-REG)422的512位的輸入值ND、來自E寄存器(E-REG)423的中間變量T，其中T是第一MAC運算器411的最低32位輸出。M寄存器(M-REG)424鎖存MAC輸出的頂端480位，並將它們返回到第二MAC運算器421，以用作下一個輸入。
第三MAC運算器431在包括N寄存器(N-REG)432、P寄存器(P-REG)433、R寄存器(R-REG)435、X寄存器(X-REG)436和V寄存器(V-REG)437的周邊寄存器以及被耦合到R寄存器(R-REG)435的多路轉換器(MUX)434的合作下計算等式(7)。N寄存器432保存512位的輸入值N。P寄存器433或保存512位的輸入值N，或接收第二MAC運算器的輸出(即，中間變量M)的最低32位。該P寄存器433為第三MAC運算器每次16位地提供它所存儲的數據。多路轉換器434選擇第一MAC運算器的輸出(即，中間變量T)的底端32位或其頂端480位。所選擇的值被設定到R寄存器435，以用作第三MAC運算器431的輸入。第三MAC運算器431的輸出進入到兩個寄存器較低32位進入X寄存器436，較高512位進入V寄存器437。X寄存器436取得各個所產生的32位數據，並在被填滿其512位的容量時，將這些數據發送到存儲器作為輸出值X。V寄存器437的512位數據被返回到第三MAC運算器431或被寫入到存儲器。
圖10示出了MAC運算器的結構，該MAC運算器的多輸入加法器通過插入中間寄存器而被分為兩個塊。所圖示的MAC運算器411由部分乘積發生器501、多輸入加法器塊502、中間寄存器503、四輸入加法器504以及544位的進位分解加法器505組成。部分乘積發生器501是16個部分乘積運算器501-1、501-2、...、501-16的平行陣列，其中的每個進行32位的值的乘法。
部分乘積發生器501接收來自A寄存器412的512位，它們被分配到16個部分乘積運算器501-1、501-2、...、501-16中，每個分配32位。另一方面，B寄存器413將它的底端32位提供給所有的部分乘積運算器501-1、501-2、...、501-16，同時每次自身右移32位。所得到的部分乘積在多輸入加法器塊502中被加總，並通過中間寄存器503被發送到四輸入加法器504。該四輸入加法器504還接收來自D寄存器415的512位的數據和來自C寄存器414的32位的數據，它們被加到A×B的值上。最後，544位的進位分解加法器505處理四輸入加法器504的進位輸出，從而將結果的頂端512位發送到D寄存器415，並將剩餘的32位發送到E寄存器416。
上述結構使用中間寄存器503，來在多輸入加法器塊502和四輸入加法器504之間的位置將第一MAC運算器411分為兩級，因此使得這兩級能夠以流水線的方式操作。如果第一級(多輸入加法器塊502)和第二級(544位進位分解加法器505)在它們的延遲時間方面相等，那麼第一MAC運算器411的處理速率將被最大化。第一級的延遲時間是乘數大小(即需要相加的項的數目)的函數。另一方面，第二部分的延遲時間是第一MAC運算器411輸出位寬的函數。
考慮其被乘數和乘數的輸入埠具有相同位寬的MAC運算器。由於在前的多輸入加法級將比在後的進位分解級具有大得多的延遲時間，所以我們將不能夠通過按照如上所述的相同的方式插入中間寄存器503來提高這類MAC運算器的速率。另一方面，本發明的第一MAC運算器411具有位寬不同的被乘數和乘數輸入埠。這意味著可以選擇適當的位寬，使得兩級具有平衡的延遲時間。所提出的MAC運算器411從而可以具有流水線結構的總體性能優勢。
第一MAC運算器411的上述特徵也適用於第二MAC運算器421，因為它們結構相似。第三MAC運算器431除它具有513位加法器功能外，與其他的運算器基本類似。我們所以省略了對它們的說明。
下面給出圖9的電路如何進行蒙哥馬利模乘法-累加的概述，首先假設每個輸入值不超過512位。
從給定的輸入值A、B和C，以及輸入值X的底端32位，第一MAC運算器411計算中間變量T，並輸出它的底端32位。基於另一給定的輸入值ND和在前一階段所獲得的中間變量T的底端32位，第二MAC運算器421計算另一個中間變量M，並輸出它的底端32位。第三MAC運算器431接收另一給定的輸入值N、從第二MAC運算器421所提供的中間變量M的底端32位以及從第一MAC運算器411所提供的中間變量T的底端32位。從這些輸入，第三MAC運算器431計算輸出值X，並發送其底端32位。三個MAC運算器411、421和431將它們各自的任務重複16次。在這些迭代結束時，圖9的電路400將使D寄存器415中的中間變量T的頂端512位、V寄存器437中的輸出值X的頂端512位、X寄存器436中的輸出值的底端512位變得可用。之後，結束第三MAC運算器431的周期，其中其將由多路轉換器434所選擇的中間變量T的較高位與輸出值X的較低位相加。該結果被設定到V寄存器437中，並且在該V寄存器437中的X的較高的位被寫入到存儲器中，作為計算的最終結果。
當數據大小大於512位時，圖9的蒙哥馬利模MAC電路400如下操作首先，使用給定的輸入值A的最低有效的512位，蒙哥馬利模MAC電路400將上述過程重複16次，同時將所有產生的中間變量到M保存到P寄存器433中。然後，電路400將所得到的中間變量M傳輸到N寄存器432，並用從存儲器讀出的輸入值N加載P寄存器433，這等同於交換N寄存器432和P寄存器433的內容。第三MAC運算器431繼續每次32位地計算輸出值X，接收512位的M、N的底端32位以及T的底端32位。通過對給定輸入值A的整個長度重複上述過程，電路400獲得了對超過512位的大輸入值的蒙哥馬利模乘法-累加。
結論對上述說明概括地說，所提出的多字MAC電路具有至少一個擁有不同位寬的被乘數和乘數輸入埠的MAC運算器。該MAC運算器周邊有用於存儲從存儲器讀出的數據的多個寄存器。由於在每個時鐘周期中要被提供給MAC運算器的數據量被調整，使得在一個時鐘周期中由MAC運算器所消耗和產生的數據總量將等於或小於存儲器在一個時鐘周期中所能傳輸的最大數據量。該MAC運算器能夠使用帶寬有限的單口存儲器，而不犧牲其使用的效率。單口存儲器沒有多口存儲器複雜，這意味著所提出的MAC電路可以被實現而不佔用太多晶片空間。
所提出的MAC電路能夠被用來使用RSA公鑰密碼系統對數據加密或解密，這涉及到模算術操作。因此，本發明適用於，但不限於，含有這樣的密碼晶片的ID卡或類似設備。
已經假設基數R是2的冪並且N是奇數，對本發明進行了說明。但是，我們並不試圖將本發明限制於該條件。本發明在基數大於整數N且與整數N互質時，也能很好地工作。
前面被視為僅僅是對本發明的原理的示例表示。而且，由於許多的修改和改變對於本領域的普通技術人員來說是容易的，所以不希望將本發明限制於所圖示和說明的具體構造和應用，因此，所有適合的修改和等同物可以被視為落入所附權利要求及其等同物中的發明範圍之內。
權利要求
1.一種對每個被提供為多字數據的給定輸入值進行乘法-累加運算的多字乘法-累加電路，包括為多個多字數據提供存儲的存儲器；乘法-累加運算器，所述乘法-累加運算器具有位寬不同的被乘數和乘數輸入埠，以計算從所述存儲器讀出的所述多字數據的乘積的和；和用於將所述多字數據提供給所述乘法-累加運算器的多個寄存器，其中，在每個時鐘周期中所提供的數據量被調節，使得由所述乘法-累加運算器在一個時鐘周期中所消耗和產生的數據總量將等於或小於所述存儲器在一個時鐘周期中所能傳輸的最大數據量。
2.根據權利要求1所述的多字乘法-累加電路，其中所述存儲器是單口存儲器。
3.根據權利要求1所述的多字乘法-累加電路，其中所述乘法-累加運算器包括多個進位加法器。
4.一種對從存儲器讀出的多字數據進行蒙哥馬利模乘法-累加運算的蒙哥馬利模乘法-累加電路，所述電路包括至少一個乘法-累加模塊，所述模塊包括乘法-累加運算器，所述乘法-累加運算器具有位長不同的被乘數和乘數輸入埠，以計算從所述存儲器讀出的多字數據的乘積的和；和用於將所述多字數據提供給所述乘法-累加運算器的多個寄存器，其中，在每個時鐘周期中所要提供的數據量被調節，使得由所述乘法-累加運算器在一個時鐘周期中所消耗和產生的數據總量將等於或小於所述存儲器在一個時鐘周期中所能傳輸的最大數據量。
5.根據權利要求4所述的蒙哥馬利模乘法-累加電路，還包括與所述至少一個乘法-累加模塊串聯的另一個乘法-累加模塊。
6.根據權利要求4所述的蒙哥馬利模乘法-累加電路，其中所述存儲器是單口存儲器。
7.根據權利要求4所述的蒙哥馬利模乘法-累加電路，其中所述乘法-累加運算器包括多個進位加法器。
8.根據權利要求4所述的蒙哥馬利模乘法-累加電路，還包括指針寄存器，所述指針寄存器存儲在存儲器中的每段多字數據的頭地址，其中所述指針寄存器與數據區域名稱相關聯，其中外部控制器通過所述數據區域名稱指定在所述存儲器中的數據源和目標，以及通過不改變由所述外部控制器所指定的所述數據區域名稱，而只交換被包含在與所述被指定的數據區域名稱相關聯的所述指針寄存器中的所述頭地址，使兩個數據源或兩個目標被相互替代。
全文摘要
本發明公開了一種適用於使用單口存儲器的多字乘法－累加電路和蒙哥馬利模乘法－累加電路。該電路由乘法－累加(MAC)運算器和周邊的寄存器組成。該MAC運算器具有位寬不同的被乘數和乘數輸入埠，以計算從存儲器讀出的多字數據的乘積的和。寄存器用作要被提供給MAC運算器的單獨的輸入埠的多字數據的緩衝存儲裝置。對在每個時鐘周期中被提供給MAC運算器的數據量被調節，使得由MAC運算器在一個時鐘周期中所消耗和產生的數據總量將等於或小於存儲器在一個時鐘周期中所能傳輸的最大數據量。該特徵使得能夠使用帶寬有限的單口存儲器，而不會對MAC運算器的使用效率造成負面影響。
文檔編號G06F7/544GK1648853SQ20041005817
公開日2005年8月3日 申請日期2004年8月13日 優先權日2004年1月26日
發明者向田健二, 武仲正彥, 鳥居直哉, 柳井升一 申請人:富士通株式會社