[處理器芯片]-5 超標量CPU實現之ALU

ALU（Arithmetic Logic Unit，算術邏輯單元），是CPU執行單元中最主要的組成部分。

1 主要功能

算術運算：執行加法、減法、乘法和除法等算術運算。

邏輯運算：執行與、或、非、異或等邏輯運算。

移位運算：執行邏輯左移、邏輯右移、算術右移等移位運算。

比較運算：執行大小比較等比較運算。

超標量CPU中的加法器、減法器、乘法器、除法器和移位器在硬件實現中，依賴于組合邏輯和時序邏輯的設計。加法器通過基本的半加器和全加器實現，減法器利用二進制補碼和加法實現，移位器則通過簡單的位操作實現，乘法器可以采用Booth算法或陣列乘法器，除法器則通過順序減法和移位實現。通過這些基礎電路的優化和組合，超標量CPU能夠高效執行復雜的算術操作。

2 加法器（Adder）

加法器是用于執行二進制加法的基本電路。常見的加法器包括半加器、全加器和多位加法器（如行波進位加法器、先行進位加法器）。

1）半加器（Half Adder）

半加器用于兩個單比特的加法：輸入兩個單比特 `A` 和 `B`，輸出和 `Sum` 和進位 `Carry`

邏輯實現。

module HalfAdder(input A, B, output Sum, Carry);

????assign Sum = A ^ B; ??// 異或運算

????assign Carry = A & B; // 與運算

endmodule

2）全加器（Full Adder）

全加器用于兩個單比特和前一位進位的加法：輸入兩個單比特 `A` 和 `B`，前一位進位 `Cin`，輸出和 `Sum` 和進位 `Cout`。

邏輯實現

module FullAdder(input A, B, Cin, output Sum, Cout);

????assign Sum = A ^ B ^ Cin; ????????????// 異或運算

????assign Cout = (A & B) | (Cin & (A ^ B)); // 與或運算

endmodule

3）多位加法器（Ripple Carry Adder）

行波進位加法器是由多個全加器級聯而成：輸入兩個多比特二進制數 `A` 和 `B`，輸出和 `Sum` 和進位 `Cout`

邏輯實現

module RippleCarryAdder #(parameter WIDTH = 8)(input [WIDTH-1:0] A, B, output [WIDTH-1:0] Sum, output Cout);

????wire [WIDTH:0] Carry; // 進位鏈

????assign Carry[0] = 0;

????

????genvar i;

????generate

????????for (i = 0; i < WIDTH; i = i + 1) begin: add_bit

????????????FullAdder FA (.A(A[i]), .B(B[i]), .Cin(Carry[i]), .Sum(Sum[i]), .Cout(Carry[i+1]));

????????end

????endgenerate

????

????assign Cout = Carry[WIDTH];

endmodule

3 減法器（Subtractor）

減法可以通過加法實現，使用二進制補碼進行減法操作，即：`A - B` 可以表示為 `A + (~B + 1)`。

4位減法器邏輯實現

module Subtractor #(parameter WIDTH = 4)(input [WIDTH-1:0] A, B, output [WIDTH-1:0] Diff);

????wire [WIDTH-1:0] B_complement;

????assign B_complement = ~B + 1; // 計算B的補碼

????RippleCarryAdder #(WIDTH) RCA (.A(A), .B(B_complement), .Sum(Diff), .Cout());

endmodule

4 乘法器（Multiplier）

乘法器用于執行二進制乘法，現代乘法器通常由部分積生成器（Partial Product Generator）、部分積壓縮器（Partial Product Compressor）和最終加法器（Final Adder）構成。

工作原理

乘法運算單元是處理器中的關鍵組件之一，基本原理是將被乘數（Multiplicand）和乘數（Multiplier）分解成若干部分積（Partial Products），然后將這些部分積進行累加得到最終的乘積。乘法運算單元可以采用不同類型的乘法器，如布爾乘法器、串行乘法器、并行乘法器等，具體選擇取決于性能和面積的要求。

主要組件

3.1）部分積生成器

部分積生成器的任務是根據乘數的每一位生成對應的部分積。每一個部分積是被乘數與乘數某一位的乘積。

例如，對于 4 位乘數和被乘數：

- 乘數 `B`：\( B_3B_2B_1B_0 \)

- 被乘數 `A`：\( A_3A_2A_1A_0 \)

生成的部分積為：

- 第 0 位：`P_0 = B_0 * A`

- 第 1 位：`P_1 = B_1 * A << 1`

- 第 2 位：`P_2 = B_2 * A << 2`

- 第 3 位：`P_3 = B_3 * A << 3`

Booth 算法

Booth 算法進行乘法操作可以有效減少部分積生成的位數，從而減少計算量，其基本思想是利用乘數的位模式，將部分積中連續的1和0序列合并為一個更大的值或更小的值，以減少需要執行的加法和移位操作。

1）Booth 編碼：對乘數進行 Booth 編碼，將每兩位乘數轉換為一個 Booth 編碼值，可以是0、1或-1。

2）循環運算：從最低位開始，對每兩位乘數進行 Booth 編碼并執行相應的加法和移位操作，生成部分積的一部分。

3）部分積累加：每次循環產生的部分積通過累加器累加，最終得到完整的部分積。

實現示例

輸入：被乘數A = 1010 (十進制：10)

??????乘數B = 0110 (十進制：6)

Booth 編碼：0101 (十進制：5)

???????????1100 (十進制：-4)

循環運算：

1）A 的最低位為 0，保持部分積不變。

2）A 的第二低位為 1，部分積左移一位并加上 B。

???部分積：00000000

??????????+ 0110

??????????--------

??????????00000110

3）A 的第三低位為 1，部分積左移一位并加上 B。

???部分積：00000110

??????????+ 0110

??????????--------

??????????00010000 (此時部分積的低4位即為結果)

部分積 P = 0001 0000 (十進制：16)

基于Booth算法的乘法器邏輯實現

module BoothMultiplier #(parameter WIDTH = 4)(input [WIDTH-1:0] A, B, output [2*WIDTH-1:0] Product);

????reg [2*WIDTH-1:0] P;

????reg [WIDTH-1:0] Q;

????reg Q_1;

????integer i;

????always @(A or B) begin

????????P = 0;

????????Q = B;

????????Q_1 = 0;

????????for (i = 0; i < WIDTH; i = i + 1) begin

????????????case ({Q[0], Q_1})

????????????????2'b01: P = P + (A << i);

????????????????2'b10: P = P - (A << i);

????????????????default: ;

????????????endcase

????????????Q_1 = Q[0];

????????????Q = Q >> 1;

????????end

????end

????assign Product = P;

endmodule

3.2）部分積壓縮器

部分積壓縮器用于減少部分積的層數，將得到的部分積需要按權值錯位相加，以得到最終的乘積結果。這個過程通常通過樹型結構的加法器實現，可以采用Wallace樹、Dadda樹等，需要確保加法過程中的進位被正確傳遞。

Wallace 樹壓縮

Wallace樹是一種常見的部分積壓縮器，利用全加器和半加器將部分積逐層壓縮。

邏輯實現

module WallaceTree(input [3:0] A, input [3:0] B, output [7:0] Product);

????wire [15:0] partial_products;

????// 生成部分積

????assign partial_products[3:0] = A & {4{B[0]}};

????assign partial_products[7:4] = A & {4{B[1]}};

????assign partial_products[11:8] = A & {4{B[2]}};

????assign partial_products[15:12] = A & {4{B[3]}};

????// 聲明中間結果

????wire [7:0] sum1, sum2, sum3, carry1, carry2, carry3;

????// 第一級壓縮

????assign sum1 = {partial_products[3:1], 1'b0} + partial_products[7:4];

????assign carry1 = {4'b0, partial_products[11:8]} + {4'b0, partial_products[15:12]};

????// 第二級壓縮

????assign sum2 = {carry1[3:1], 1'b0} + sum1[7:4];

????assign carry2 = carry1[7:4] + sum1[3:0];

????// 最后一級壓縮

????assign sum3 = sum2 + carry2;

????assign carry3 = {carry2[3:1], 1'b0};

????// 最終加法

????assign Product = sum3 + carry3;

endmodule

3.3）最終加法器（Final Adder）

最終加法器用于將壓縮后的部分積進行累加，得到最終的乘積，常見的加法可以參照第一章節內容，包括行波進位加法器和先行進位加法器。

結果輸出，將最終的乘積結果存儲在結果寄存器中，以便后續的使用或傳輸。

邏輯實現

module FinalAdder(input [7:0] sum, input [7:0] carry, output [7:0] Product);

????assign Product = sum + carry;

endmodule

4位乘法器實現示例

module Multiplier4Bit(input [3:0] A, B, output [7:0] Product);

????wire [3:0] P0, P1, P2, P3;

????// 部分積生成

????assign P0 = B[0] ? A : 4'b0000;

????assign P1 = B[1] ? (A << 1) : 4'b0000;

????assign P2 = B[2] ? (A << 2) : 4'b0000;

????assign P3 = B[3] ? (A << 3) : 4'b0000;

????// 部分積壓縮（Wallace Tree）

????wire [7:0] sum1, sum2, sum3, carry1, carry2, carry3;

????assign {carry1, sum1} = {4'b0, P0} + {2'b0, P1, 2'b0};

????assign {carry2, sum2} = {4'b0, P2, 4'b0} + {4'b0, P3};

????assign {carry3, sum3} = sum1 + carry1;

????// 最終加法

????assign Product = sum3 + carry2;

endmodule

5 除法器（Divider）

除法器用于執行二進制除法。常見的方法包括恢復余數法和非恢復余數法。

恢復余數法：通過順序減法和移位實現：

邏輯實現

module RestoringDivider #(parameter WIDTH = 4)(input [WIDTH-1:0] Dividend, Divisor, output [WIDTH-1:0] Quotient, Remainder);

????reg [2*WIDTH-1:0] A, Q, M;

????integer i;

????always @(Dividend or Divisor) begin

????????A = 0;

????????Q = Dividend;

????????M = Divisor << WIDTH;

????????

????????for (i = 0; i < WIDTH; i = i + 1) begin

????????????A = (A << 1) | Q[WIDTH-1];

????????????Q = Q << 1;

????????????A = A - M;

????????????if (A[2*WIDTH-1]) begin

????????????????Q[0] = 0;

????????????????A = A + M;

????????????end else begin

????????????????Q[0] = 1;

????????????end

????????end

????end

????assign Quotient = Q[WIDTH-1:0];

????assign Remainder = A[WIDTH-1:0];

endmodule

6 移位器（Shifter）

移位器用于執行二進制數的移位操作（左移和右移），可以是邏輯移位、算術移位或循環移位。

邏輯移位器：邏輯左移和右移邏輯實現

module LogicalShifter #(parameter WIDTH = 8)(input [WIDTH-1:0] A, input [2:0] Shift, output [WIDTH-1:0] Result);

????assign Result = (Shift[2]) ? {8'b0, A[WIDTH-1:8]} :

????????????????????(Shift[1]) ? {4'b0, A[WIDTH-1:4]} :

????????????????????(Shift[0]) ? {2'b0, A[WIDTH-1:2]} :

????????????????????A;

Endmodule