微處理器設計/加減模組

微處理器設計

加法和減法

加法和減法是相似的演算法。看一下減法，我們可以看到

a-b=a+(-b)

利用這種簡單的關係，我們可以看到加法和減法可以使用相同的硬體來執行。然而，使用這種設定時，必須注意在執行減法時反轉第二個運算元的值。還要注意，在二進位制補碼算術中，第二個運算元的值不僅要反轉，還要加 1。因此，在執行減法時，LSB 的進位輸入應該是 1 而不是 0。

那麼，我們在本頁的目標是找到適合執行加法的硬體。

位加法器

半加法器

半加法器是一種對兩個位進行二進位制加法的電路。半加法器沒有明確考慮進位輸入訊號。

在 SystemVerilog 中，可以按以下方式實現半加法器

module half_adder(input logic a, b, output logic carry_out, sum);
  assign {carry_out, sum} = a + b;
endmodule

全加法器

全加法器電路類似於半加法器，不同之處在於它們考慮了進位輸入和進位輸出。全加法器可以被視為一個 3 位加法器，具有 2 位結果，也可以被視為一個較大加法器中的單個階段（一個 3:2 壓縮器）。

如下所示，全加法器電路中的門延遲數量為 3

我們可以使用 Verilog 實現全加法器模組

module full_adder(a, b, cin, cout, s);
   input a, b, cin;
   output cout, s;
   wire temp;
   temp = a ^ b;
   s = temp ^ cin;
   cout = (cin & temp) | (a & b);
endmodule

序列加法器

序列加法器是一種 ALU，它一次計算輸出的每一位，重新使用一個全加法器（總計）。此影像顯示了一個 2 位序列加法器，以及相關的波形。

序列加法器的優點是它們在所有加法器中需要最少的硬體，但它們速度最慢。

並行加法器

並行加法器是一種 ALU，它使用一個全加法器來計算輸出的每一位，基本上是同時計算的。1947 年的 Whirlwind 計算機是第一個使用並行加法器的計算機。

在許多 CPU 中，CPU 在 “狀態暫存器” 中將並行加法器的最終進位輸出鎖存到外部 “進位標誌” 中。

在一些 CPU 中，鎖存的進位標誌值始終連線到並行加法器的第一個進位輸入；這使得使用 2 的補碼加法進行 “帶進位的加法”。（在極少數 CPU 中，迴圈進位 - 並行加法器的最終進位輸出直接連線到相同並行加法器的第一個進位輸入 - 執行 1 的補碼加法）。

行波進位加法器

長度超過 1 位的數字需要不止一個全加法器才能使用算術和按位邏輯指令進行操作^{[需要引用]}。操作較大的數字的一種簡單方法是將多個全加法器模組級聯在一起，形成一個 行波進位加法器，如上所示。行波進位加法器之所以這樣稱呼，是因為進位值從一個模組“傳播”到下一個模組，一直傳播到整個全加法器鏈。在進位訊號完全傳播到整個全加法器鏈之前，高位位的輸出值不正確，算術運算也不完整。

如果每個全加法器需要 3 個門延遲才能完成計算，那麼一個 n 位行波進位加法器將需要 3n 個門延遲。對於 32 位或 64 位計算機（或更高），這種延遲可能非常大。

行波進位加法器的優點是它們在所有加法器中需要最少的硬體（序列加法器除外），但它們速度最慢（序列加法器除外）。

使用我們上面定義的全加法器 Verilog 模組，我們可以在 Verilog 中定義一個 4 位行波進位加法器。可以邏輯地擴充套件加法器

wire [4:0] c;
wire [3:0] s;
full_adder fa1(a[0], b[0], c[0], c[1], s[0]);
full_adder fa2(a[1], b[1], c[1], c[2], s[1]);
full_adder fa3(a[2], b[2], c[2], c[3], s[2]);
full_adder fa4(a[3], b[3], c[3], c[4], s[3]);

在這個模組的最後，s 包含 4 位的和，而 c[4] 包含最終的進位輸出。

這種“行波進位”安排使得“加法”和“減法”比 ALU 的其他運算（AND、NAND、左移、除以二等）花費的時間長得多。一些 CPU 使用行波進位 ALU，並要求程式設計師插入 NOP 來給“加法”留出足夠的時間來完成。^[1] 其他一些 CPU 使用行波進位加法器，只是將時鐘頻率設定得足夠低，這樣進位位就有足夠的時間透過加法器傳播。還有一些 CPU 使用行波進位加法器，並使“加法”指令的執行週期比“異或”指令多，以便進位位在“加法”運算中可以透過加法器有更多的時間進行傳播，但不會在“異或”運算期間不必要地減慢 CPU 的速度。但是，如果每個指令的執行週期數相同，那麼流水線會變得簡單得多。

進位跳躍加法器

進位超前加法器

維基百科在 進位超前加法器 中提供了相關資訊

進位超前加法器使用特殊的 “超前” 模組來計算 4 個全加法器組的進位，並將此進位訊號傳遞到下一個 4 個全加法器組。超前單元也可以級聯，以最大限度地減少進位訊號完全傳播到鏈條末端的門延遲數量。進位超前加法器是速度最快的加法器電路之一，但它們需要大量的硬體來實現。實現進位超前加法器所需的電晶體數量與輸入數量的立方成正比。

兩個一位輸入 A 和 B 的加法如果在進位輸入情況下（或者等效地，無論較低有效位的和是否進位），加法總是進位，則稱為產生。例如，在十進位制加法 52 + 67 中，十位數字 5 和 6 的加法產生，因為無論個位數字是否進位，結果都會進位到百位數字（在這個例子中，個位數字顯然不會進位）。

在二進位制加法中， $A+B$ 產生當且僅當 A 和 B 都為 1。如果我們寫 $G(A,B)$ 來表示當且僅當 $A+B$ 產生時為真的二元謂詞，我們有

G(A,B)=A\cdot B

兩個一位輸入 A 和 B 的加法被稱為傳播，如果加法在有輸入進位時會進位（等價於，當和的下一個較低有效位進位時）。例如，在十進位制加法 37 + 62 中，十位數字 3 和 6 的加法傳播，因為如果個位進位（在本例中，它沒有），結果會進位到百位。注意，傳播和產生是相對於加法的一個單獨的數字定義的，不依賴於和中的任何其他數字。

在二進位制加法中， $A+B$ 傳播當且僅當 A 或 B 中至少有一個為 1。如果我們寫 $P(A,B)$ 來表示當且僅當 $A+B$ 傳播時為真的二元謂詞，我們有