怎么設(shè)計(jì)一個(gè)32位超前進(jìn)位加法器？

最近在做基于MIPS指令集的單周期CPU設(shè)計(jì)，其中的ALU模塊需要用到加法器，但我們知道普通的加法器是串行執(zhí)行的，也就是高位的運(yùn)算要依賴低位的進(jìn)位，所以當(dāng)輸入數(shù)據(jù)的位數(shù)較多時(shí)，會(huì)造成很大的延遲，影響整個(gè)CPU的性能，為了減小這種延遲，遂采用超前進(jìn)位加法器（也叫先行進(jìn)位加法器），下面來介紹一下設(shè)計(jì)的原理：

設(shè)二進(jìn)制加法器第 i 位為Ai， Bi，輸出為Si，進(jìn)位輸入為Ci，進(jìn)位輸出為C（i+1），則有：

Si = Ai ⊕ Bi ⊕ Ci （1-1）

C(i + 1) = Ai * Bi + Ai * Ci + Bi * Ci = Ai * Bi +（Ai+Bi）* Ci （1-2）

令Gi = Ai * Bi , Pi = Ai + Bi，則: C(i + 1) = Gi + Pi * Ci

當(dāng) Ai 和 Bi 都為1時(shí)，Gi = 1， 產(chǎn)生進(jìn)位C(i+1) = 1；

當(dāng) Ai 和 Bi 有一個(gè)為1時(shí)，Pi = 1，傳遞進(jìn)位C(i+1)= Ci；

（說明：“*”表示與邏輯、“+”表示或邏輯、“⊕”表示異或邏輯）

因此Gi定義為進(jìn)位產(chǎn)生信號(hào)，Pi定義為進(jìn)位傳遞信號(hào)。Gi的優(yōu)先級(jí)比Pi高，也就是說：當(dāng)Gi = 1時(shí)(當(dāng)然此時(shí)也有 Pi = 1)，無條件產(chǎn)生進(jìn)位，而不管Ci是多少；當(dāng)Gi = 0 而 Pi = 1時(shí)，進(jìn)位輸出為Ci，跟Ci之前的邏輯有關(guān).

第一步：設(shè)計(jì)4位超前進(jìn)位加法器 (至于為什么要先設(shè)計(jì)4位的，后面有詳解)

舉例：設(shè)4位加數(shù)和被加數(shù)為 A 和 B，進(jìn)位輸入為C_in，進(jìn)位輸出為C_out，對(duì)于第 i 位的進(jìn)位產(chǎn)生Gi = Ai * Bi ,進(jìn)位傳遞Pi = Ai + Bi , i = 0,1,2,3 。于是各級(jí)進(jìn)位輸出，遞歸的展開Ci，有：

C0 = C_in

C1 = G0 + P0*C0

C2 = G1 + P1*C1 = G1 + P1*G0 + P1*P0 *C0

C3 = G2 + P2*C2 = G2 + P2*G1 + P2*P1*G0 + P2*P1*P0*C0

C4 = G3 + P3*C3 = G3 + P3*G2 + P3*P2*G1 + P3*P2*P1*G0 + P3*P2*P1*P0*C0 （1-3）

C_out = C4

由此可以看出，各級(jí)的進(jìn)位彼此獨(dú)立，只與輸入數(shù)據(jù) Ai、Bi 和 C_in有關(guān)，而且并行產(chǎn)生，不就達(dá)到了設(shè)計(jì)目的——將各級(jí)間的進(jìn)位級(jí)聯(lián)傳播給去掉了，減小了串行進(jìn)位產(chǎn)生的延遲。

實(shí)現(xiàn)上述邏輯表達(dá)式（1-3）的電路稱為超前進(jìn)位部件（Carry Lookahead Unit），也稱為CLA部件。通過這種進(jìn)位方式實(shí)現(xiàn)的加法器稱為超前進(jìn)位加法器。因?yàn)楦鱾€(gè)進(jìn)位是并行產(chǎn)生的，所以是一種并行進(jìn)位加法器。

4位CLA部件電路如圖1所示：

圖1：4位CLA超前部件電路

(可能有人就想到，如果要設(shè)計(jì)32位超前進(jìn)位加法器，是不是可以按照同樣的方法直接推導(dǎo)到C32，就可以一次性并行產(chǎn)生所有位的進(jìn)位。。。但是，我們想想，根據(jù)表達(dá)式，進(jìn)位越往后，比如C5、C6......C31、C32，表達(dá)式會(huì)越來越復(fù)雜，這是因?yàn)樵黾恿诉壿嬮T的輸入端個(gè)數(shù)，將會(huì)使得電路中需要具有大驅(qū)動(dòng)信號(hào)和大扇入門，這會(huì)大大增加門的延遲，起不到提高電路性能的作用，這種方法叫做全先行進(jìn)位，而當(dāng)位數(shù)較多時(shí)，很顯然這種方式并不現(xiàn)實(shí)，因此更多位數(shù)的加法器可通過4位CLA部件和4位超前進(jìn)位加法器來實(shí)現(xiàn)，后面再細(xì)說)

* 4位超前部件完成了，現(xiàn)在來完成4位超前進(jìn)位加法器：

首先每一位都會(huì)產(chǎn)生進(jìn)位傳遞信號(hào)和進(jìn)位產(chǎn)生信號(hào)，然后將四位數(shù)據(jù)分別產(chǎn)生的進(jìn)位傳遞信號(hào)和進(jìn)位產(chǎn)生信號(hào)送到4位CLA部件，供CLA并行產(chǎn)生每一位的進(jìn)位信號(hào)Ci，然后再送回給每一位的低進(jìn)位（C_in）,就完成了4位超前進(jìn)位加法器，聽不懂，沒關(guān)系，看下圖：

圖2：1位加法器

圖3：4位超前進(jìn)位加法器

說明：1位加法器如圖2所示，輸入有A、B兩個(gè)加數(shù)，還有來自低位的進(jìn)位C_in，輸出有得到的和 Si ，還有 進(jìn)位產(chǎn)生信號(hào)Gi和進(jìn)位傳遞信號(hào)Pi，之所以引出這兩個(gè)信號(hào)，是為了為后面的4位超前進(jìn)位加法器做鋪墊，有人可能奇怪為什么沒有向高位的進(jìn)位位，這是因?yàn)槊恳晃坏倪M(jìn)位位是由CLA部件產(chǎn)生的，我們用四個(gè)如圖2所示的1位加法器和一個(gè)如圖1所示的4位超前進(jìn)位部件，就組成了圖3所示的4位超前進(jìn)位加法器，至此我們也就完成了4位超前進(jìn)位加法器的設(shè)計(jì)。

那么，問題來了，4位超前進(jìn)位加法器和我們最初要設(shè)計(jì)的32位超前進(jìn)位加法器有什么聯(lián)系呢？有經(jīng)驗(yàn)的朋友很快就能反應(yīng)過來，是不是可以用八組4位超前進(jìn)位加法器級(jí)聯(lián)起來，完成32位的設(shè)計(jì)，但是，如果僅僅按照普通的級(jí)聯(lián)，也就是將八組4位超前進(jìn)位加法器串聯(lián)起來，整個(gè)設(shè)計(jì)相當(dāng)于組內(nèi)超前進(jìn)位，組間串行進(jìn)位，這種方法是可行的，但不是我們的目的，因?yàn)樗€是會(huì)影響整個(gè)系統(tǒng)的性能，為了達(dá)到最優(yōu)的設(shè)計(jì)方法，我們采用組內(nèi)超前進(jìn)位，組間也是超前進(jìn)位的方法進(jìn)行設(shè)計(jì)，這種方法叫做兩級(jí)或多級(jí)先行進(jìn)位加法器。

問題又來了，采用組內(nèi)和組間都是超前進(jìn)位的方式，到底該怎么設(shè)計(jì)呢？其實(shí)我們可以類比4位加法器的設(shè)計(jì)，為了完成4位的超前進(jìn)位加法器，我們把1位加法器引出了它的進(jìn)位產(chǎn)生信號(hào)Gi和進(jìn)位傳遞信號(hào)Pi，供4位CLA使用，那么我們是否可以把4位超前進(jìn)位加法器的進(jìn)位產(chǎn)生信號(hào)Gm和進(jìn)位傳遞信號(hào)Pm也引出來，然后用四組4位超前進(jìn)位加法器和一個(gè)4位CLA完成16位超前進(jìn)位加法器的設(shè)計(jì)呢，答案當(dāng)然是可以的。

首先，我們對(duì)圖3所示的4位超前進(jìn)位加法器進(jìn)行封裝，并且引出進(jìn)位產(chǎn)生信號(hào)Gm和進(jìn)位傳遞信號(hào)Pm，如圖4所示：

圖4：封裝后的4位超前進(jìn)位加法器

說明：圖4也是4位超前進(jìn)位加法器，它和圖3的區(qū)別是引出了進(jìn)位產(chǎn)生信號(hào)Gm和進(jìn)位傳遞信號(hào)Pm，有心的朋友會(huì)發(fā)現(xiàn)它和圖2所示的1位加法器很相似，不同的地方僅僅是位數(shù)變成了四位，既然和1位加法器相似，那么我們就可以按照同樣的方法用四個(gè)圖4所示的4位超前進(jìn)位加法器和一個(gè)CLA設(shè)計(jì)16位超前進(jìn)位加法器，問題又來了，圖4所示的4位超前加法器的進(jìn)位產(chǎn)生信號(hào)Gm和進(jìn)位傳遞信號(hào)Pm怎么來的呢？

首先來看1位加法器的進(jìn)位產(chǎn)生信號(hào)Gi和進(jìn)位傳遞信號(hào)Pi是怎么來的：

既然是1位加法器，那么它的進(jìn)位信號(hào)是C1，

由 C(i + 1) = Ai * Bi + Ai * Ci + Bi * Ci = Ai * Bi +（Ai+Bi）* Ci 得：

當(dāng) i = 0 時(shí)，即1位加法器的進(jìn)位信號(hào) C1 = A0 * B0 + （A0 + B0）* C0

我們把 （A0 * B0）叫做進(jìn)位產(chǎn)生信號(hào)Gi，把（A0 + B0）叫做進(jìn)位傳遞信號(hào)Pi 【原因前面已經(jīng)講過】

顯然 Gi 和 Pi 分別時(shí)1位加法器的進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳遞信號(hào).

再來看4位加法器的進(jìn)位產(chǎn)生信號(hào)Gm和進(jìn)位傳遞信號(hào)Pm該怎么來：

既然是4位加法器，那么它的進(jìn)位信號(hào)是C4，

由 C(i + 1) = Ai * Bi + Ai * Ci + Bi * Ci = Ai * Bi +（Ai+Bi）* Ci 得：

當(dāng) i = 3 時(shí)，即4位加法器的進(jìn)位信號(hào)

C4 = A3 * B3 + （A3 + B3）* C3

= G3 + P3*C3

= G3 + P3*G2 + P3*P2*G1 + P3*P2*P1*G0 +P3*P2*P1*P0*C0【在設(shè)計(jì)4位CLA時(shí)已經(jīng)給出】

類比法得：把（G3 + P3*G2 + P3*P2*G1 + P3*P2*P1*G0）叫做進(jìn)位產(chǎn)生信號(hào)Gm，（P3*P2*P1*P0） 叫做進(jìn)位傳遞信號(hào)Pm，顯然 Gm 和 Pm 分別是四位加法器的進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳遞信號(hào).

第二步：設(shè)計(jì)16位超前進(jìn)位加法器

首先每一個(gè)封裝后的4位超前進(jìn)位加法器都會(huì)都會(huì)輸出進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳遞信號(hào)，將四個(gè)4位超前進(jìn)位加法器輸出的進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳遞信號(hào)輸入到4位CLA中，供CLA產(chǎn)生每一個(gè)4位超前進(jìn)位加法的低進(jìn)位信號(hào)，如下圖所示：

圖5：16位超前進(jìn)位加法器

至此，我們完成了16位超前進(jìn)位加法器的設(shè)計(jì)。

要想設(shè)計(jì)32位超前進(jìn)位加法器和設(shè)計(jì)16位超前進(jìn)位加法器一樣的方法，對(duì)16位超前進(jìn)位加法器進(jìn)行封裝，引出16位加法器的進(jìn)位產(chǎn)生信號(hào)Gx和進(jìn)位傳遞信號(hào)Px即可。

第三步：設(shè)計(jì)32位超前進(jìn)位加法器

因?yàn)槲覀円呀?jīng)有了16位超前進(jìn)位加法器，并且已經(jīng)引出了進(jìn)位產(chǎn)生信號(hào)Gx和進(jìn)位傳遞信號(hào)Px，那么我們只需要兩個(gè)16位的超前進(jìn)位加法器即可組成32位的加法器，但是超前部件CLA是4位的，意味著我們只需要用到CLA的低兩位，所以整個(gè)32位的超前進(jìn)位加法器模塊圖如下所示：

圖6：32位超前進(jìn)位加法器

至此，32位超前進(jìn)位加法器完成。

回顧：此次32位超前進(jìn)位加法器的設(shè)計(jì)以4位超前進(jìn)位加法器和4位CLA部件為基礎(chǔ)，采用組內(nèi)和組間都是超前進(jìn)位的方式，有效的減小了傳統(tǒng)加法器串行進(jìn)位導(dǎo)致的延遲問題，采用這種方法，只要設(shè)計(jì)合適位數(shù)的CLA部件，就可以設(shè)計(jì)任意位數(shù)的超前進(jìn)位加法器，需要注意的地方就是進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳遞信號(hào)的理解，以及CLA部件的理解，下面附上此次設(shè)計(jì)的源碼以及仿真波形圖：

1位加法器：

4位CLA部件：

4位超前進(jìn)位加法器：

4位超前進(jìn)位加法器RTL視圖：

16位超前進(jìn)位加法器：

16位超前進(jìn)位加法器RTL視圖：

32位超前進(jìn)位加法器：

32位超前進(jìn)位加法器RTL視圖：

但是，我們發(fā)現(xiàn)如果在32位超前進(jìn)位加法器中調(diào)用整個(gè)4位CLA，而我們僅僅只使用了兩位，導(dǎo)致了資源的浪費(fèi)，所以，我們修改代碼如下：

*32位超前進(jìn)位加法器：

*32位超前進(jìn)位加法器RTL視圖：

*32位超前進(jìn)位加法器仿真激勵(lì)：

*32位超前進(jìn)位加法器仿真波形圖：

從波形圖上可以看出，32位超前進(jìn)位加法器功能正確，只要理解了設(shè)計(jì)的目的，以及設(shè)計(jì)的思想，實(shí)現(xiàn)這個(gè)加法器并不困難，所以理解很重要，希望能給正在學(xué)習(xí)計(jì)算機(jī)原理與組成的朋友幫上忙，謝謝！

如有不足的地方，還請(qǐng)指正！