漣波進位、先行進位、進位保留加法器的差異:延遲、電路規模、用途比較

三者都是由全加器組成的加法電路,差別在於處理進位的方式。漣波進位加法器將全加器串接,進位從低位依序傳到高位,因此延遲與位元數n成正比(O(n))。先行進位加法器由各位元的產生訊號與傳遞訊號平行求出所有進位,將先行電路階層化後,延遲只需O(log n)。進位保留加法器把三個數在不傳遞進位的情況下整理成和與進位兩個數,延遲與位元數無關,只有一級全加器。乘法器以進位保留加法器組成的樹(如華里士樹)減少部分積,最後剩下的兩個數再用高速加法器相加。

項目漣波進位加法器先行進位加法器進位保留加法器
輸入與輸出將兩個數(與進位輸入)相加,輸出一個和與進位輸出將兩個數(與進位輸入)相加,輸出一個和與進位輸出把三個數整理成和S與進位Cy兩個數(A + B + C = S + Cy)
進位的處理各全加器等待來自低位的進位,再依序傳到高位使用產生訊號g = a·b與傳遞訊號p = a ⊕ b,展開c(i+1) = g(i) + p(i)·c(i),平行求出進位不傳給相鄰位元,而是作為左移一位的數交給下一級
延遲的增加方式O(n)。最壞情況下進位從最低位傳到最高位O(log n)(先行電路階層化時)O(1)。與位元數無關,只有一級全加器
64位元的參考值進位通過64級全加器以4位元區塊組成3個階層。若用平行前綴加法器,Kogge-Stone型的進位計算為log₂64 = 6級一級為一個全加器的延遲。將64個部分積整理成兩個數的華里士樹為10級
電路規模最小。n位元需要n個全加器多出先行電路的部分。越快的架構閘與佈線越多(Kogge-Stone型約為n log n)一級為n個全加器,沒有傳遞進位的電路。乘法器整棵樹的規模與部分積的位元數(約n²)成正比
結果的形式一般的二進位數一般的二進位數分成和與進位兩個數的冗餘形式。要成為單一值,最後需用一般的加法器相加
主要用途不要求速度的小型電路與低功耗電路。在FPGA中常以專用的進位電路(進位鏈)實作CPU的ALU、位址計算、浮點運算單元、乘法器最後一級的加法乘法器的部分積加總(華里士樹、Dadda樹)、乘積累加的累積、多個數的加總
相關方式進位跳躍加法器、進位選擇加法器(速度與面積介於中間)平行前綴加法器(Kogge-Stone型、Brent-Kung型等)4:2壓縮器,以及與減少部分積的布斯演算法組合

數值為具代表性的大致參考值,會因世代或產品而異。

適用於什麼情況

漣波進位加法器
用於位元數少,或比起速度更重視面積與功耗時。電路簡單而規則,在FPGA這類具有專用高速進位路徑的元件上,能以這種形式有效率地實作。
先行進位加法器
用於必須快速完成一次兩數相加時,例如CPU的ALU,以及位於關鍵路徑上的加法器。依階層化方式與平行前綴加法器的種類,在級數與面積、佈線量之間取捨。
進位保留加法器
用於相加三個以上的數時。中途不等待進位傳遞就減少數的個數,最後只用先行進位加法器等相加一次,因此在加總大量部分積的乘法器,以及反覆累積乘積的MAC中效果很大。

常見問題

O(n)與O(log n)的差距實際上有多大?

在64位元時,漣波進位加法器的進位要通過64級全加器,而Kogge-Stone型的平行前綴加法器,進位計算只要log₂64 = 6級。每一級的延遲依電路而異,無法單純相比,但位元數越多差距越大,在GHz級處理器的64位元加法中,漣波進位加法器會來不及。

如何用數字確認進位保留加法器的動作?

輸入4位元的5(0101)、6(0110)、7(0111),收集各位元和的數S為0100(4),收集各位元進位並左移一位的數Cy為1110(14)。4 + 14 = 18,與5 + 6 + 7一致。各位元是獨立的全加器,因此不需要等待進位。

華里士樹的級數如何決定?

每一級的進位保留加法器把三個數整理成兩個,因此數的個數每級約減為三分之二。部分積有h個時,一級後變成2⌊h/3⌋ + (h mod 3)個;8個需4級、16個需6級、32個需8級、64個需10級才剩下兩個。級數大約與位元數的對數成正比,最後剩下的兩個數用高速加法器相加,乘積便完成。

為什麼大位元數時不直接使用先行進位的展開式?

因為把進位式完全展開後,越高位的項越多,很快就需要輸入數極多的閘。因此會以約4位元的區塊求出群組產生訊號G與群組傳遞訊號P,在上一層使用相同形式的先行電路。平行前綴加法器就是把這個想法一般化的架構。

理解度檢測

將全加器串聯而成的漣波進位加法器,其缺點下列哪一項正確?

  1. A無法處理負數
  2. B進位從低位依序傳遞,因此延遲與位元數成正比增加
  3. C即使位元數增加,電路規模也不變
查看答案與解析

正確答案:B. 進位從低位依序傳遞,因此延遲與位元數成正比增加

在漣波進位加法器中,各全加器要等待來自低位的進位後才進行計算,因此進位從最低位依序傳到最高位,延遲與位元數成正比增加。64位元時就是64級全加器的延遲,對於以GHz動作的CPU而言太慢。由於電路小而單純,用於不要求速度的用途。要提高速度,可使用先行進位、進位選擇、平行前綴(Kogge-Stone等)加法器。

先行進位(carry-lookahead)加法器之所以高速,下列哪一項理由正確?

  1. A為了減少加法的位元數
  2. B為了使時脈頻率變為2倍
  3. C因為各位元的進位不必等待來自低位的傳遞,而是從輸入平行計算
查看答案與解析

正確答案:C. 因為各位元的進位不必等待來自低位的傳遞,而是從輸入平行計算

先行進位加法器利用各位元的產生 G = A·B(必定產生進位)與傳遞 P = A⊕B(讓低位的進位通過),如 C1 = G0 + P0·C0、C2 = G1 + P1·G0 + P1·P0·C0 … 這樣從輸入平行計算各位數的進位。延遲只隨位元數的對數成長。不過由於式子會變長,實際上是將4位元左右的區塊階層式地組合使用。

下列何者是超前進位加法器所使用的各位數的產生訊號 g 與傳遞訊號 p 的定義(a、b為該位數的輸入),以及往上一位數的進位 c(i+1) 之算式的正確組合?

  1. Ag = a + b、p = a・b、c(i+1) = p + g・c(i)
  2. Bg = a・b、p = a ⊕ b、c(i+1) = g + p・c(i)
  3. Cg = a ⊕ b、p = a・b、c(i+1) = g・p・c(i)
查看答案與解析

正確答案:B. g = a・b、p = a ⊕ b、c(i+1) = g + p・c(i)

當該位數的 a 與 b 皆為1時,不論來自下方的進位為何,必定會產生進位,因此產生訊號為 g = a・b。若 a 與 b 僅有其中一個為1,則會把來自下方的進位直接傳往上方,因此傳遞訊號為 p = a ⊕ b(也有採用OR的情況)。故 c(i+1) = g(i) + p(i)・c(i),將其展開後,各位數的進位僅需由輸入的 g、p 與最低位的進位,即可以兩級邏輯平行求得。若把產生與傳遞弄混,算式便無法正確計算。

  1. 在乘法器中,加總大量部分積時會使用進位保留加法器,其主要理由為下列何者?
  2. 關於高速乘法器所使用的華勒斯樹(Wallace tree)的特徵,下列何者正確?
  3. 下列哪一項是全加器輸入的正確組合?

前往電腦算術的練習題

相關名詞的解說

全加器
將兩個位元與來自低位的進位共 3 個輸入相加,輸出和與往高位的進位的電路。沒有進位輸入的稱為半加器。串聯連接即成為多位元加法器。
先行進位加法器
由各位數的產生訊號 g = a·b 與傳遞訊號 p = a ⊕ b,不等待來自低位的傳遞,並行求出進位的加法器。即使位元數多,延遲也小。也稱為進位前瞻加法器(carry-lookahead adder)。
進位保留加法器
將三個數在不傳遞進位的情況下,彙整成「和」與「進位」兩個數的加法器。只是逐位排列全加器,延遲固定,因此用於乘法器中加總大量部分積。
華里士樹(Wallace tree)
在乘法器中,以進位保留加法器的樹並行減少大量部分積的結構。級數只需位元數的對數程度,用於高速乘法器。最後以一般加法器將兩個數相加。
布斯演算法(Booth's algorithm)
將乘數的位元序列每兩位元等分段,置換成有號的位數,以減少部分積數量的乘法方法。基數4的布斯法可使部分積減少約一半。
關鍵路徑
電路中延遲最大、決定可動作之最高時脈頻率的路徑。在 STA 中相當於 slack 最小的路徑,高速化要從減少此路徑的延遲開始。

相關的比較