Số học phần cứng: Ripple-Carry, Carry-Lookahead & Fixed-point

Mở đầu: Vì sao chip 64-bit không nhanh gấp đôi chip 32-bit khi cộng số?

Trực giác phần mềm mách bảo: cộng 2 số 64-bit chỉ là "cộng 2 số 32-bit, làm gấp đôi khối lượng" — CPU nào đủ mạnh thì chi phí gần như không đổi. Nhưng ở mức mạch số, phép cộng không hề miễn phí theo độ rộng bit. Bộ cộng đơn giản nhất — nối chuỗi các bộ cộng 1-bit, mỗi bit chờ cờ nhớ (carry) từ bit liền trước — có độ trễ tăng tuyến tính theo số bit: cộng 64-bit chậm gấp 16 lần so với cộng 4-bit, không phải "gấp đôi". Đây chính là lý do CPU 64-bit thật không dùng bộ cộng ngây thơ này — họ trả thêm diện tích silicon để đổi lấy một kiến trúc cộng có độ trễ tăng theo logarit, gần như không đổi khi bit tăng gấp đôi.

Bài này mổ xẻ 2 kiến trúc bộ cộng kinh điển — Ripple-Carry (lan truyền nhớ) và Carry-Lookahead (nhìn trước nhớ) — chứng minh bằng công thức vì sao cái sau nhanh hơn hẳn khi bit-width lớn, dù tốn thêm diện tích. Sau đó bạn sẽ thấy đánh đổi tương tự ở phép nhân (tuần tự ít diện tích vs tổ hợp 1 chu kỳ nhưng tốn diện tích), và một cạm bẫy số học kinh điển khác: khi số fixed-point tràn, mạch của bạn nên bão hoà hay lặng lẽ cuộn vòng — chọn sai sẽ tạo ra bug chỉ lộ diện ở đúng vài tổ hợp input hiếm gặp. Toàn bộ bộ cộng, bộ nhân trong bài đều chạy thật trên engine VeriLite của trang này — không phải sơ đồ minh hoạ suông.

1. Ripple-Carry Adder: cộng đúng, nhưng chờ nhau từng bit

Cách "hiển nhiên" nhất để cộng 2 số nhiều bit: ghép nối n bộ cộng đầy đủ (full adder) 1-bit, mỗi bộ nhận cờ nhớ cin từ bộ liền trước và tạo ra cờ nhớ cout cho bộ liền sau — giống hệt cách bạn cộng tay 2 số nhiều chữ số, cộng từ hàng đơn vị rồi "nhớ" dần sang hàng chục, hàng trăm. Đây gọi là Ripple-Carry Adder (RCA) — "ripple" (gợn sóng) vì cờ nhớ lan truyền tuần tự qua từng tầng, không tầng nào tính được trước khi tầng trước nó xong.

module rca4 (
  input  logic a0, a1, a2, a3,  // toán hạng A, bit 0 (LSB) → bit 3 (MSB)
  input  logic b0, b1, b2, b3,  // toán hạng B
  input  logic cin,             // carry-in ban đầu
  output logic s0, s1, s2, s3,  // tổng, từng bit
  output logic cout             // carry-out cuối cùng (bit tràn)
);
  logic c1, c2, c3;             // carry nội bộ giữa các tầng — đây là "dây gợn sóng"

  // Tầng 0: full adder — PHẢI xong trước khi tầng 1 có carry để dùng
  assign s0 = a0 ^ b0 ^ cin;
  assign c1 = (a0 & b0) | (cin & (a0 ^ b0));

  // Tầng 1: chờ c1 từ tầng 0
  assign s1 = a1 ^ b1 ^ c1;
  assign c2 = (a1 & b1) | (c1 & (a1 ^ b1));

  // Tầng 2: chờ c2 từ tầng 1
  assign s2 = a2 ^ b2 ^ c2;
  assign c3 = (a2 & b2) | (c2 & (a2 ^ b2));

  // Tầng 3: chờ c3 từ tầng 2 — carry đã "gợn sóng" qua đủ 4 tầng
  assign s3 = a3 ^ b3 ^ c3;
  assign cout = (a3 & b3) | (c3 & (a3 ^ b3));
endmodule

Vì tầng thứ i không thể tính sum hay carry-out của mình cho tới khi nhận được carry-in từ tầng i-1, toàn bộ chuỗi n tầng phải hoàn tất tuần tự. Nếu mỗi full adder có độ trễ cổng là $t_{FA}$, độ trễ đường tới hạn (critical path) của cả bộ cộng n-bit là:

$$T_{RCA}(n) = n \cdot t_{FA} = O(n)$$

Tăng gấp đôi bit-width, độ trễ tăng gấp đôi — tuyến tính. Đây chính là lý do nêu ở đầu bài: bộ cộng 64-bit kiểu RCA chậm gấp 16 lần bộ cộng 4-bit, không phải nhanh hơn nhờ "công nghệ hiện đại" — bản chất kiến trúc quyết định, không phải tốc độ transistor.

2. Carry-Lookahead Adder: tính trước cờ nhớ, không chờ dây gợn sóng

Ý tưởng của Carry-Lookahead Adder (CLA): thay vì để mỗi tầng chờ carry từ tầng trước, tính trước mọi cờ nhớ trung gian, song song, chỉ dựa vào a, b và cin ban đầu — không tầng nào phải chờ tầng khác. Chìa khoá là 2 tín hiệu trung gian cho mỗi bit i:

• Generate $G_i = a_i \cdot b_i$ — bit này tự sinh carry (cả 2 đều là 1, chắc chắn có nhớ, không cần biết carry vào là gì).
• Propagate $P_i = a_i \oplus b_i$ — bit này truyền tiếp carry (đúng 1 trong 2 là 1: nếu có carry vào thì có carry ra, không thì không).

Với $G_i$, $P_i$ đã biết (tính song song, chỉ tốn 1 tầng cổng), mọi carry trung gian có thể viết lại thành công thức chỉ phụ thuộc a, b, cin ban đầu — không còn phụ thuộc dây chuyền:

$$c_1 = G_0 + P_0 \cdot c_{in}$$ $$c_2 = G_1 + P_1 G_0 + P_1 P_0 \cdot c_{in}$$ $$c_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 \cdot c_{in}$$

module cla4 (
  input  logic a0, a1, a2, a3,
  input  logic b0, b1, b2, b3,
  input  logic cin,
  output logic s0, s1, s2, s3,
  output logic cout
);
  logic g0, g1, g2, g3;  // generate — bit này TỰ SINH carry
  logic p0, p1, p2, p3;  // propagate — bit này TRUYỀN TIẾP carry
  logic c1, c2, c3;

  // Tầng 0: sinh G/P cho CẢ 4 bit CÙNG LÚC — không bit nào chờ bit nào
  assign g0 = a0 & b0;  assign p0 = a0 ^ b0;
  assign g1 = a1 & b1;  assign p1 = a1 ^ b1;
  assign g2 = a2 & b2;  assign p2 = a2 ^ b2;
  assign g3 = a3 & b3;  assign p3 = a3 ^ b3;

  // Tầng 1: mỗi carry tính THẲNG từ g/p + cin — KHÔNG đợi carry bit liền trước
  assign c1 = g0 | (p0 & cin);
  assign c2 = g1 | (p1 & g0) | (p1 & p0 & cin);
  assign c3 = g2 | (p2 & g1) | (p2 & p1 & g0) | (p2 & p1 & p0 & cin);
  assign cout = g3 | (p3 & g2) | (p3 & p2 & g1) | (p3 & p2 & p1 & g0) | (p3 & p2 & p1 & p0 & cin);

  // Tầng 2: sum chỉ cần p và carry tương ứng (2 tầng cổng, không phụ thuộc chuỗi dài)
  assign s0 = p0 ^ cin;
  assign s1 = p1 ^ c1;
  assign s2 = p2 ^ c2;
  assign s3 = p3 ^ c3;
endmodule

Nhìn công thức $c_3$, số lượng số hạng OR tăng theo bit-width — một bộ CLA "phẳng" 1 tầng cho cả 64-bit sẽ có cổng OR/AND với fan-in khổng lồ (không thực tế trên silicon thật). Giải pháp công nghiệp: chia thành các khối nhỏ (vd 4-bit/khối), mỗi khối tự CLA nội bộ, rồi ghép nhiều khối theo cây lookahead phân cấp (giống hệt sơ đồ cộng tay theo nhóm chữ số). Với cách ghép cây nhị phân này, số tầng cần thiết chỉ tăng theo $\log_2 n$:

$$T_{CLA}(n) \approx t_{PG} + \lceil \log_2 n \rceil \cdot t_{level} = O(\log n)$$

trong đó $t_{PG}$ là độ trễ tầng sinh G/P ban đầu (1 tầng cố định), còn $t_{level}$ là độ trễ mỗi tầng kết hợp lookahead trong cây. Khi n tăng gấp đôi, $T_{CLA}$ chỉ tăng thêm đúng 1 tầng — khác hẳn RCA phải tăng gấp đôi toàn bộ độ trễ.

3. Demo tương tác: Đua Ripple-Carry vs Carry-Lookahead

Cả 2 module trên chạy thật trên VeriLite — đổi từng bit a/b/cin để tự kiểm chứng chúng luôn cho ra cùng kết quả (khác kiến trúc, giống chức năng). Bên dưới là bảng "STA mini" — mô hình ước lượng đơn giản hoá độ trễ theo công thức $T_{RCA}(n)$/$T_{CLA}(n)$ ở trên (không phải phân tích STA đầy đủ từng cổng thật — đó là chủ đề Bài 8), cho phép chọn bit-width để thấy khoảng cách 2 đường cong doãng ra thế nào.

// Xem đầy đủ 2 module rca4 / cla4 ở Mục 1 và Mục 2 phía trên,
// hoặc tải file adder_race.sv ở cuối bài để chạy trên Verilator/EDA Playground.

4. Nhân phần cứng: 1 chu kỳ tốn diện tích, hay nhiều chu kỳ tiết kiệm diện tích?

Phép nhân phần cứng đối mặt đánh đổi diện tích ↔ tốc độ tương tự, nhưng ở một trục khác — số chu kỳ clock cần thiết:

Bộ nhân shift-add dưới đây tách thành 5 thanh ghi riêng biệt (mỗi thanh ghi 1 khối always_ff): cờ busy, bộ đếm count, phần dư số nhân mrem (dịch phải mỗi chu kỳ), số hạng cộng addend (dịch trái mỗi chu kỳ), và bộ tích luỹ acc. Bấm Step Clock nhiều lần để xem acc "lớn dần" qua từng chu kỳ — trực quan hoá đúng bản chất tuần tự của kiến trúc này.

module mult4_shiftadd (
  input  logic clk, rst, start,
  input  logic [3:0] a, b,
  output logic [7:0] product,
  output logic done
);
  logic [7:0] acc, addend;
  logic [3:0] mrem;
  logic [2:0] count;
  logic busy;

  // 5 thanh ghi, MỖI thanh ghi 1 khối always_ff riêng — engine áp dụng đồng loạt
  // cho TẤT CẢ khối cùng 1 cạnh clock, nên chúng đọc đúng trạng thái CHUNG trước
  // cạnh clock, dù khai báo ở 5 khối tách biệt.
  always_ff @(posedge clk) begin
    if (rst) busy <= 0;
    else busy <= (start && !busy) ? 1 : (busy && (count == 3)) ? 0 : busy;
  end

  always_ff @(posedge clk) begin
    if (rst) count <= 0;
    else count <= (start && !busy) ? 0 : (busy) ? (count + 1) : count;
  end

  always_ff @(posedge clk) begin
    if (rst) mrem <= 0;
    else mrem <= (start && !busy) ? b : (busy) ? (mrem >> 1) : mrem;
  end

  always_ff @(posedge clk) begin
    if (rst) addend <= 0;
    else addend <= (start && !busy) ? a : (busy) ? (addend << 1) : addend;
  end

  always_ff @(posedge clk) begin
    if (rst) acc <= 0;
    else acc <= (start && !busy) ? 0 : (busy && (mrem % 2 == 1)) ? (acc + addend) : acc;
  end

  assign product = acc;
  assign done = !busy;
endmodule

// So sánh: array multiplier tổ hợp — CHỈ 1 dòng, 1 chu kỳ, nhưng "1 dòng" này
// tổng hợp ra cả lưới n×n cổng AND + cây cộng thật trên silicon:
module mult4_array (
  input  logic [3:0] a, b,
  output logic [7:0] product
);
  assign product = a * b;
endmodule

5. Fixed-point Qm.n: Tràn số nên bão hoà hay lặng lẽ cuộn vòng?

Phần cứng không có kiểu float miễn phí — nhiều hệ thống nhúng/DSP dùng fixed-point: số nguyên có dấu chấm "ảo" cố định, ký hiệu Qm.n (m bit phần nguyên, n bit phần thập phân). Vấn đề xảy ra khi phép cộng 2 số fixed-point cho kết quả vượt quá giá trị lớn nhất biểu diễn được — và đây là lúc 2 triết lý xử lý tràn số dẫn tới hậu quả rất khác nhau.

// ❌ SAI: wrap-around ngầm định — không ai cảnh báo khi tràn
module fixed_add_wrap (
  input  logic [3:0] a, b,   // Q4.0 đơn giản: 4-bit không dấu, tối đa = 15
  output logic [3:0] sum
);
  assign sum = a + b;  // 10 + 7 = 17 → tràn 4-bit → CUỘN VÒNG thành 1! (17 mod 16)
endmodule

// ✅ ĐÚNG: bão hoà (saturate) — kẹp về giá trị lớn nhất khi phát hiện tràn
module fixed_add_saturate (
  input  logic [3:0] a, b,
  output logic [3:0] sum
);
  logic [4:0] raw;               // PHẢI rộng hơn 1 bit để giữ được thông tin tràn
  assign raw = a + b;            // 10 + 7 = 17 — raw đủ rộng nên KHÔNG mất bit tràn
  assign sum = (raw > 15) ? 15 : raw;  // phát hiện tràn → kẹp về 15, không cuộn vòng
endmodule

Không phải lúc nào wrap-around cũng sai — bộ đếm địa chỉ vòng, con trỏ FIFO (sẽ gặp ở Bài 7), hay số học modulo cố tình dùng wrap-around vì đó chính là ngữ nghĩa mong muốn. Vấn đề là chọn có chủ đích, không phải để mặc định ngầm định quyết định thay bạn. Đây cũng là cạm bẫy con dao 2 lưỡi tương tự lỗi tràn số nguyên trong phần mềm (xem ví dụ tràn int trong Series C) — chỉ khác là ở phần cứng, bạn phải tự thiết kế đúng logic bão hoà, không có thư viện chuẩn nào làm hộ.

Tóm lược

Bài này trang bị tư duy đánh đổi diện tích ↔ tốc độ ↔ độ an toàn trong số học phần cứng:

• ✅ Ripple-Carry Adder: đơn giản, ít diện tích, nhưng độ trễ $O(n)$ — carry phải lan truyền tuần tự qua từng tầng.
• ✅ Carry-Lookahead Adder: tính trước carry song song qua tín hiệu generate/propagate, đạt độ trễ $O(\log n)$ — đổi lại tốn thêm diện tích cho logic lookahead.
• ✅ Nhân phần cứng: shift-add tuần tự (n chu kỳ, ít diện tích) vs array multiplier tổ hợp (1 chu kỳ, tốn diện tích lưới $n \times n$).
• ✅ Fixed-point Qm.n: tràn số phải xử lý có chủ đích — bão hoà (saturate) hay cuộn vòng (wrap) đều hợp lệ tuỳ ngữ cảnh, nhưng để mặc định quyết định thay bạn là cạm bẫy kinh điển.

Trắc nghiệm ôn tập