Bài 6: Song Song Cấp Lệnh & Thực Thi Ngoài Thứ Tự (Tomasulo)

Mở đầu: một nhân chạy nhanh hơn bằng cách phát nhiều lệnh cùng lúc

Bài 5 giữ pipeline luôn ĐẦY lệnh bằng cách đoán trước hướng rẽ nhánh. Nhưng pipeline vô hướng (scalar) của Bài 4 vẫn chỉ PHÁT đúng 1 lệnh/chu kỳ, và luôn theo ĐÚNG thứ tự chương trình. CPU hiệu năng cao hiện đại đi xa hơn: phát nhiều lệnh mỗi chu kỳ (superscalar), và cho phép lệnh SAU chạy xong TRƯỚC lệnh trước nếu không có phụ thuộc dữ liệu THẬT — gọi là thực thi ngoài thứ tự (Out-of-Order execution, OOO). Cái giá: phải giải quyết phụ thuộc dữ liệu GIẢ sinh ra do số thanh ghi kiến trúc hữu hạn, và phải đảm bảo trạng thái kiến trúc cuối cùng vẫn ĐÚNG như chạy tuần tự — bài này xây thuật toán kinh điển giải quyết cả hai: Tomasulo.

1. Song song cấp lệnh (ILP) & CPU Superscalar

ILP (Instruction-Level Parallelism) đo mức độ các lệnh LIỀN KỀ trong chương trình có thể chạy song song mà không đổi kết quả. CPU vô hướng (scalar) phát 1 lệnh/chu kỳ; CPU siêu vô hướng (superscalar) có nhiều đơn vị chức năng (ALU, bộ nhân, bộ tải/lưu) và có thể phát/thực thi NHIỀU lệnh đồng thời — nhưng tận dụng được bao nhiêu phụ thuộc HOÀN TOÀN vào việc chương trình có đủ lệnh ĐỘC LẬP hay không.

2. Phụ thuộc dữ liệu giả & Đổi tên thanh ghi (Register Renaming)

Ngoài RAW (hazard THẬT, đã học ở Bài 4), tồn tại 2 loại phụ thuộc chỉ xuất hiện vì CHƯƠNG TRÌNH tái sử dụng cùng MỘT tên thanh ghi kiến trúc cho 2 giá trị KHÔNG liên quan nhau về mặt logic:

Đổi tên thanh ghi (register renaming) loại bỏ hoàn toàn WAR/WAW: mỗi lần một lệnh GHI vào thanh ghi kiến trúc, nó được gán một "phiên bản" MỚI (trong Tomasulo là chỉ số ROB — Reorder Buffer), và Register Alias Table (RAT) ghi nhớ "thanh ghi X hiện đang trỏ tới phiên bản nào". Lệnh sau đọc/ghi thanh ghi đó sẽ tự động dùng ĐÚNG phiên bản tương ứng — không còn tranh chấp vật lý nào giữa các "phiên bản" khác nhau của cùng một tên thanh ghi.

// RAT[r] = null          -> gia tri DUNG cua thanh ghi r nam trong regFile
// RAT[r] = robIndex       -> gia tri MOI nhat cua r con dang "bay" trong ROB
//                            tai vi tri robIndex, CHUA duoc commit

// Khi ISSUE mot lenh ghi vao thanh ghi dest:
//   RAT[dest] = robIndexMoiVuaCapPhat   // "DOI TEN" - tao PHIEN BAN MOI
// -> lenh SAU do doc "dest" se lay dung PHIEN BAN MOI nay qua RAT,
//    con lenh TRUOC do (da doc "dest" luc issue, truoc khi bi doi ten)
//    van giu nguyen gia tri CU cua no - khong bi anh huong boi lenh ghi de.

3. Thuật toán Tomasulo: Reservation Station + CDB + ROB

Tomasulo (IBM 360/91, 1967) là thuật toán OOO đầu tiên và vẫn là nền tảng của CPU OOO hiện đại (x86, ARM). 3 thành phần chính:

• Reservation Station (RS) — mỗi đơn vị chức năng có vài "trạm đặt chỗ" giữ lệnh đang chờ toán hạng; khi CẢ 2 toán hạng sẵn sàng, RS tự động bắt đầu thực thi (không cần đợi lệnh trước xong nếu không phụ thuộc).
• CDB (Common Data Bus) — bus dữ liệu DÙNG CHUNG để broadcast kết quả: mọi RS đang chờ giá trị đó "nghe lỏm" (snoop) CDB và tự cập nhật toán hạng ngay khi giá trị xuất hiện. Vì là tài nguyên DÙNG CHUNG, CHỈ 1 lệnh được ghi kết quả (write-result) mỗi chu kỳ — lệnh THUA phải đợi thêm.
• ROB (Reorder Buffer) — bộ đệm giữ MỌI lệnh đang "bay" theo ĐÚNG thứ tự chương trình; dù các lệnh hoàn tất TÍNH TOÁN ngoài thứ tự, commit (ghi chính thức vào thanh ghi kiến trúc) luôn lấy từ ĐẦU ROB — đảm bảo trạng thái kiến trúc cuối cùng giống hệt chạy tuần tự.

// Moi chu ky, DUNG THU TU: Commit -> Write-result (1 broadcast/chu ky)
// -> giam remaining cac RS dang thuc thi -> WAITING->EXECUTING khi du toan
// hang -> Issue 1 lenh moi (doi ten dest qua RAT).
function runTomasulo(instructions, opts) {
  // ... xem cpu-core.js day du - day la vong lap chinh moi chu ky ...
  // 1. COMMIT dau ROB neu ready
  // 2. WRITE-RESULT: chi 1 broadcast/chu ky, uu tien robIndex NHO HON (lenh cu hon)
  // 3. Giam remaining RS dang EXECUTING
  // 4. WAITING -> EXECUTING khi Qj/Qk deu null (da nhan du toan hang qua CDB)
  // 5. ISSUE 1 lenh: RAT[dest] = robIndex moi (DOI TEN)
}
// Verified: chuong trinh MUL R1/ADD R2/SUB R1 (WAR tren R2, WAW tren R1)
// -> totalCycles=9, ipc=3/9=0.333, R1 cuoi=18 (tu SUB, dung in-order commit)

4. Tính toán IPC thực tế & hiệu quả thuật toán

Verified thật bằng engine: chương trình 3 lệnh MUL R1,R2,R3 / ADD R2,R4,R5 (WAR trên R2) / SUB R1,R6,R7 (WAW trên R1) — đổi tên giải quyết cả 2 phụ thuộc giả, chạy đúng 9 chu kỳ, IPC = $3/9 = \mathbf{0,333}$. R1 cuối cùng = 18 (từ SUB, đúng thứ tự chương trình nhờ in-order commit — KHÔNG phải 12 từ MUL bị ghi đè, đúng ngữ nghĩa WAW "ai ghi sau thắng"). Đáng chú ý: ADD (instr2) hoàn tất TÍNH TOÁN (writeback chu kỳ 5) TRƯỚC MUL (instr1, writeback chu kỳ 6) — hoàn thành NGOÀI thứ tự — nhưng vẫn commit ĐÚNG thứ tự chương trình (chu kỳ 7, 8, 9 cho instr1, instr2, instr3).

Lenh                Issue  ExecStart  Writeback  Commit
MUL R1, R2, R3        1        2          6          7
ADD R2, R4, R5        2        3          5          8
SUB R1, R6, R7        3        4          7          9

# ADD (writeback=5) xong TRUOC MUL (writeback=6) - hoan thanh NGOAI thu tu.
# Nhung commit van DUNG thu tu chuong trinh: 7, 8, 9 (MUL, ADD, SUB).
# Tong 9 chu ky, IPC = 3/9 = 0.333.

Đối chứng: CÙNG 3 phép tính đó nhưng viết thành chuỗi RAW THẬT (mỗi lệnh dùng kết quả lệnh ngay trước) — mất tới 11 chu kỳ, IPC chỉ $3/11 = \mathbf{0,273}$ — chậm hơn hẳn vì phụ thuộc thật KHÔNG có cách nào loại bỏ, đúng pitfall Mục 1.

// Chuong trinh A: MUL R1 / ADD R2 (WAR) / SUB R1 (WAW) -> 9 chu ky, IPC=0.333
// Chuong trinh B: MUL R1 / ADD R2,R1 (RAW that) / SUB R3,R2 (RAW that)
//                 -> 11 chu ky, IPC=0.273 (cham hon vi PHU THUOC THAT)
// Chuong trinh C: MUL R1 / ADD R4 / SUB R5 (khong xung dot gi ca)
//                 -> CUNG 9 chu ky nhu chuong trinh A - chung minh renaming
//                    da lam A nhanh NGANG BANG truong hop khong co xung dot!

5. Thực hành: Bộ giả lập Tomasulo thu nhỏ tương tác

Chọn một chương trình mẫu bên dưới để xem bảng lập lịch Tomasulo THẬT (Issue/Exec Start/Writeback/Commit từng lệnh) — so sánh trực tiếp chương trình có WAR/WAW (renaming giải quyết) với chuỗi RAW thật (không giải quyết được) và chương trình không xung đột gì:

Tóm lược

• ✅ CPU superscalar phát nhiều lệnh/chu kỳ, nhưng bị nghẽn bởi phụ thuộc dữ liệu THẬT (RAW) — verified: chuỗi RAW thật mất 11 chu kỳ so với 9 chu kỳ của phiên bản có WAR/WAW.
• ✅ WAR/WAW là phụ thuộc GIẢ (chỉ vì trùng tên thanh ghi) — đổi tên thanh ghi (RAT) loại bỏ HOÀN TOÀN, khác hẳn RAW không thể loại bỏ.
• ✅ Tomasulo = Reservation Station (chờ toán hạng) + CDB (broadcast, 1 lệnh/chu kỳ) + ROB (commit đúng thứ tự chương trình dù hoàn thành ngoài thứ tự).
• ✅ Verified: R1 cuối cùng = 18 (từ SUB, lệnh ghi SAU trong chương trình) — in-order commit đảm bảo đúng ngữ nghĩa WAW dù ADD hoàn tất tính toán trước MUL.
• ✅ Pitfall: ROB đầy (thường do một lệnh kẹt lâu ở đầu ROB) gây ROB stall, ngừng phát lệnh mới hoàn toàn.

Trắc nghiệm ôn tập