[發明專利]一種異步迭代的多位整型乘法器及其計算方法

無效

• 申請號: 201010204727.3
• 申請日: 2010-06-18
• 公開（公告）號: CN101866278A
• 公開（公告）日: 2010-10-20
• 發明（設計）人: 劉怡俊
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06F7/523
• 分類號: G06F7/523
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

技術領域

本發明屬于64位計算機乘法器領域。特別涉及一種異步迭代的64位整型乘法器；本發明還包括該乘法器的計算方法。

背景技術

乘法器是現代計算機的基本組成部分，其性能的高低直接影響到計算機的整體運算和處理能力。現有乘法器的數學原理比較簡單——掃描乘數的每一位，產生部分積，然后將部分積進行累加，得到最終的結果。

上面的例子將5個部分積同時相加，需要4(5-1)個加法器。這是一種陣列乘法器的結構，n位陣列乘法器需要n-1個加法器，所需要的硬件較多。為了節省硬件資源，可以采用一種迭代的結構，將n個部分積用同一個加法器進行加法運算，迭代計算n-1次，其原理如下例所示：

迭代乘法器需要較少的硬件資源，但是其速度較慢——n位乘法器需要進行n-1次迭代的加法運算。這種劣勢在64位計算機中尤其突出，64位乘法器需要63次迭代，用64位二進制能表示的最大無符號自然數為2⁶⁴-1＝1844?67440737?0955?1615，18千億億！人們極少使用如此大的數字。而人們經常使用的數字完全可以用較少的位數表示，例如1000只用10個二進制數表示即可。但是由于64位CPU采用統一的表達形式，即使像1000這樣的數字也需要用64位表示，即0000...000?1111101000，前面有54個0。這樣，即使對于1000這樣較小的數字，普通的迭代乘法器也需要63次迭代。這63次迭代中，只有前9次有意義，而后54次所產生的部分積都為零。也就是說后54次加法運算只是進行無謂的加0運算，浪費了整個乘法器的運算時間。

隨著計算機進入到64位時代，計算機每次運算的范圍擴大了，運算能力也增強了。乘法器作為一個基本的運算單元，性能也急需得到改善。

發明內容

本發明的目的在于克服現有技術的不足，設計一種能有效節省運算時間的異步迭代的多位整型乘法器，本發明還包括該乘法器的計算方法。

本發明包括如下技術特征：一種異步迭代的多位整型乘法器，包括一個用于存放被乘數的寄存器R1，一個用于存放乘數和中間計算值的移位寄存器R2，一個用于進行迭代加法的加法器A1，移位寄存器R2在移位信號R2_CLK的作用下向右移動移位；寄存器R1和R2都與初始化信號Req連接；還包括一個用于檢測乘數高位零的個數，從而動態改變迭代乘法器累加次數的加法循環次數控制器，所述加法循環次數控制器通過移位信號R2_CLK與移位寄存器R2連接。

更進一步的，所述循環次數控制器包括一個八分頻電路、一個八位移位寄存器、或門連接電路；以及一個選擇器與門；

所述八分頻電路輸入端與加法時鐘信號連接，其輸出端與八位移位寄存器連接；

或門連接電路包括八個八輸入或門和七個二輸入或門，所述八個八輸入或門的輸入端與乘數的每個數位連接；每一個八輸入或門的輸出端分別與一個二輸入或門和八位移位寄存器連接；所述八位移位寄存器與選擇器與門連接；

所述選擇器與門的輸入端為CLK_add信號輸入端和CLK_shif信號輸入端，所述CLK_add信號為一個時鐘周期可以滿足一次64位的加法運算；CLK_shif信號為不需要做加法運算時，一個時鐘周期滿足一次移位操作；所述選擇器與門的輸出端分別連接移位信號R2_CLK輸出端和64分頻器，所述64分頻器的輸出端為結果信號端Ack。

本發明還包括一種異步迭代的多位整型乘法器的計算方法，先是掃描乘數MR，產生部分積，然后將部分積進行累加，最后得到結果；還通過一個循環次數控制器檢測乘數高位零的個數，從而動態改變迭代乘法器累加的次數。

跟進一步的，乘法器將64位的乘數MR按照8位一組分為8組，用一個八輸入或門檢測該組是否都為0；用Zg(7..0)表示；

Do(i)表示需不需要對第i組進行迭代加法運算，Do(i)的邏輯關系為：Do(i)＝Do(i+1)|Zg(i)，其中i＝0..6，|表示邏輯或；Do(7)＝Zg(7)；

如果對于第i組，Do(i)＝1，那么當j＜i，Do(j)都為1；即如果一組需要進行迭代運算，比它低位的部分積都需要進行迭代運算；

如果對于第i組，Do(i)＝0，那么當j＞i，Do(j)都為0；即如果發現某個i，第一次出現Do(i)＝0，迭代加法運算就結束了；