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      -> the CORRECT value of register r lives in regFile
// RAT[r] = robIndex   -> the NEWEST value of r is still "in flight" in the ROB
//                        at position robIndex, NOT yet committed

// When ISSUING an instruction that writes to register dest:
//   RAT[dest] = newlyAllocatedRobIndex   // "RENAME" - create a NEW VERSION
// -> later instructions reading "dest" get this NEW VERSION through the RAT,
//    while earlier ones (which read "dest" at issue time, before the rename)
//    keep their OLD value - untouched by the overwriting instruction.

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ự.

// Every cycle, IN THIS ORDER: Commit -> Write-result (1 broadcast per cycle)
// -> decrement `remaining` on the executing RSs -> WAITING->EXECUTING once the
// operands have arrived -> Issue 1 new instruction (renaming dest via the RAT).
function runTomasulo(instructions, opts) {
  // ... see cpu-core.js for the full version - this is the per-cycle main loop ...
  // 1. COMMIT the head of the ROB if it is ready
  // 2. WRITE-RESULT: only 1 broadcast per cycle, LOWER robIndex wins (older first)
  // 3. Decrement `remaining` on the EXECUTING reservation stations
  // 4. WAITING -> EXECUTING once Qj and Qk are both null (operands arrived via CDB)
  // 5. ISSUE 1 instruction: RAT[dest] = the new robIndex (THE RENAME)
}
// Verified: the program MUL R1 / ADD R2 / SUB R1 (WAR on R2, WAW on R1)
// -> totalCycles=9, ipc=3/9=0.333, final R1=18 (from SUB, thanks to in-order commit)

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

Trước hết là đơn vị đo. IPC (Instructions Per Cycle — số lệnh hoàn tất trên mỗi chu kỳ) chính là nghịch đảo của CPI mà Bài 4 đã dùng: \(\text{IPC} = 1/\text{CPI}\). Hai cách nói cùng một điều, chỉ khác chiều tốt — CPI càng thấp càng tốt, IPC càng cao càng tốt. Với CPU vô hướng lý tưởng, IPC tối đa là 1; superscalar sinh ra để vượt qua mốc đó. Ở quy mô 3 lệnh của các ví dụ dưới đây, IPC còn thấp vì chi phí khởi động pipeline chiếm phần lớn — điều đáng so sánh là IPC giữa các phiên bản với nhau, chứ không phải giá trị tuyệt đối.

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).

Instruction         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) finishes BEFORE MUL (writeback=6) - completion is OUT OF ORDER.
# But the commits still follow program order: 7, 8, 9 (MUL, ADD, SUB).
# 9 cycles in total, 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.

// Program A: MUL R1 / ADD R2 (WAR) / SUB R1 (WAW) -> 9 cycles, IPC=0.333
// Program B: MUL R1 / ADD R2,R1 (real RAW) / SUB R3,R2 (real RAW)
//            -> 11 cycles, IPC=0.273 (slower, because the dependency is REAL)
// Program C: MUL R1 / ADD R4 / SUB R5 (no conflicts at all)
//            -> ALSO 9 cycles, same as program A - proof that renaming made A
//               exactly AS FAST AS having no conflict in the first place!

5. Vì sao phải có ROB: Ngoại lệ chính xác (Precise Exception)

Tới đây ROB đã xuất hiện hàng chục lần với vai trò "cam kết đúng thứ tự để ra đúng kết quả cuối". Nhưng nếu chỉ cần đúng kết quả cuối thì đâu cần cả một cấu trúc đắt đỏ như vậy — Mục 2 đã cho thấy đổi tên thanh ghi tự nó đủ để giữ ngữ nghĩa luồng dữ liệu. Lý do thật sự ROB tồn tại nằm ở chỗ khác, và nó chỉ lộ ra khi có chuyện bất thường xảy ra giữa chừng.

Giả sử một lệnh gây ngoại lệ (exception): chia cho 0, tràn số, hoặc phổ biến nhất — truy cập một địa chỉ chưa có trong bộ nhớ (page fault, Bài 8). CPU phải nhảy vào trình xử lý của hệ điều hành, xử lý xong rồi chạy tiếp chương trình. Muốn chạy tiếp được thì trạng thái thanh ghi lúc đó phải chính xác (precise): đúng như thể chương trình vừa chạy tuần tự tới đúng lệnh đó rồi dừng lại — không thiếu một lệnh nào trước nó, và không thừa một lệnh nào sau nó.

Nhưng CPU này thực thi NGOÀI thứ tự. Ta đã đo ở Mục 4: lệnh 2 writeback ở chu kỳ 5, lệnh 1 mãi chu kỳ 6. Vậy nếu lỗi xảy ra giữa chừng thì trạng thái thanh ghi trông ra sao? Chạy thử cả hai kiểu máy trên đúng chương trình WAR/WAW của Mục 4:

// Same program as section 4. Writeback cycles measured: [6, 5, 7]
// instr2 (ADD) finishes at cycle 5 - BEFORE instr1 (MUL) at cycle 6

// Case A: instruction 1 (MUL) faults
architecturalStateOnFault(program, { initialRegs, faultAt: 0 });
// with ROB    -> R2 = 3   (initial value: nothing has committed yet)
// without ROB -> R2 = 11  written by instr2, which has NOT run yet in program order

// Case B: instruction 2 (ADD) faults
architecturalStateOnFault(program, { initialRegs, faultAt: 1 });
// with ROB    -> R1 = 12  instr1 committed, exactly as the program requires
// without ROB -> R1 = 10  instr1 comes BEFORE the fault yet has not taken effect

Đó chính là công việc của ROB: cho phép thực thi lộn xộn thoải mái bên trong, nhưng hiệu lực ra thanh ghi kiến trúc thì tuyệt đối theo thứ tự chương trình. Bất kỳ lúc nào cũng có một ranh giới rõ ràng — mọi thứ đã commit là quá khứ chắc chắn, mọi thứ trong ROB là tính toán chưa chính thức tồn tại.

6. 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.
• ✅ Lý do thật sự cần ROB là ngoại lệ chính xác: verified, khi lệnh 1 gây lỗi, máy có ROB giữ R2 = 3 (chưa lệnh nào commit) còn máy không ROB đã để R2 = 11 — giá trị của một lệnh CHƯA được phép chạy.
• ✅ Verified hướng ngược lại: lỗi ở lệnh 2 thì máy không ROB lại để R1 = 10, tức lệnh 1 nằm TRƯỚC lỗi mà chưa có hiệu lực. Trạng thái không khớp bất kỳ thời điểm nào của chương trình, nên không thể chạy tiếp.
• ✅ Cùng cơ chế đó cho phép squash nhánh đoán sai — nên ROB là điều kiện cần của cả OOO lẫn dự đoán nhánh (Bài 5), và là lý do Spectre chỉ để lại dấu vết trong cache chứ không trong thanh ghi.

Trắc nghiệm ôn tập