[發明專利]用于大數乘法的方法及系統

有效

• 申請號: 200880102372.8
• 申請日: 2008-08-08
• 公開（公告）號: CN101790718A
• 公開（公告）日: 2010-07-28
• 發明（設計）人: 文森特·杜帕丘斯;拉塞爾·霍布森
• 申請（專利權）人: 愛特梅爾公司
• 主分類號: G06F7/00
• 分類號: G06F7/00
• 代理公司: 北京律盟知識產權代理有限責任公司 11287
• 代理人: 孟銳

1.一種操作乘法電路以計算兩個操作數A與B的乘積的計算機實施的方法，所 述兩個操作數中的至少一者寬于與所述乘法電路相關聯的寬度，其中所述操作數中的 每一者包括以特定權數j及i為特征的一個或一個以上相連的有序字寬操作數段A_j及 B_i，其中j是從0到k的整數且其中i是從0到m的整數，且字具有規定數目n的位， 且其中所述乘法電路執行字寬操作數段對乘法運算矩陣，所述矩陣包括m+1個行及 k+m+2個列，每一行具有權數x且每一列具有權數y，所述乘法電路可存取存儲器， 所述方法包括：

同時對一對行執行乘法運算，其中對于每一對行，從所述存儲器讀取一對對應 B_i字寬操作數段，且針對k+2個列中的每一者反復地執行字寬操作數段對乘法運算 A_j*B_i，使得對于所述矩陣中的每一列，需要最多兩個額外存儲器讀取操作及一個存儲 器寫入操作。

2.根據權利要求1所述的方法，其中對根據每一對中所包含的所述行的所述權 數的增加或減小的權數值的數字序列而選擇的若干對行執行所述乘法運算。

3.根據權利要求1所述的方法，其中對從所述m+1個行中隨機選擇的若干對行 執行所述乘法運算。

4.根據權利要求1所述的方法，其中針對具有權數y₁的列的字寬操作數段對乘 法運算包括執行A_j字寬操作數段乘以B_i字寬操作數段的至少一個乘法運算，其中所 述A_j字寬操作數的所述權數j與所述B_i字寬操作數段的所述權數i的和等于所述列的 所述權數y₁。

5.根據權利要求1所述的方法，其進一步包括：

計算所述k+m+2個列中的每一者的n位最終列結果，其中列的最終列結果包括 相對于所述列針對所述m+1個行中的所述每一者執行的所述字寬操作數段對乘法運 算的累加的最低有效n位字。

6.根據權利要求5所述的方法，其中計算列的n位最終列結果包括：對于針對 所述列所計算的最終一對行，累加所述字寬操作數段對乘法運算的結果、如果有所述 列的中間列結果的情況下的所述中間列結果、及如果有作為針對先前所計算的列而確 定的累加結果的上部字的進位值的情況下的所述進位值，以確定所述列的累加結果， 其中所述n位最終列結果包括所述列的所述累加結果的最低有效n個位。

7.根據權利要求5所述的方法，其中列的中間列結果包括：對于并非為針對所 述列將要計算的所述最終對行的一對行，累加所述字寬操作數段對乘法運算的結果、 如果有所述列的先前所計算的中間列結果的情況下的所述中間列結果、及如果有先前 所計算的列的進位值的情況下的所述進位值，以確定所述列的中間累加結果，其中所 述中間列結果包括所述列的所述中間累加結果的所述最低有效n個位。

8.根據權利要求7所述的方法，其中所述列的所述中間累加結果的上部字包括 所述列的將要在下一列的累加運算中使用的進位值。

9.根據權利要求1所述的方法，其中將從存儲器讀取的對應于所述對行的所述 對B_i字寬操作數段存儲于高速緩沖存儲器中，同時執行針對所述對行的所述乘法運算。