Thực thi suy đoán và dự đoán rẽ nhánh(Speculative Execution & Branch Prediction)

1. Tổng quan

A. Định nghĩa

Dự đoán rẽ nhánh(Branch Prediction) là kỹ thuật phần cứng đoán trước hướng của lệnh rẽ nhánh có điều kiện trước khi kết quả (đúng/sai) và địa chỉ đích của nó được xác định, nhằm cung cấp các lệnh tiếp theo mà không bị dừng, còn thực thi suy đoán(Speculative Execution) là cơ chế cốt lõi của thực thi không theo thứ tự (out-of-order) thực thi trước các lệnh chưa được xác định dựa trên phỏng đoán đó, rồi phản ánh kết quả (commit) nếu đoán đúng và quay lui (rollback/squash) nếu đoán sai.

Dự đoán rẽ nhánh và thực thi suy đoán cùng chia sẻ một mục đích: "khoản đầu tư để không làm rỗng đường ống". Bộ xử lý hiện đại nâng thông lượng bằng đường ống sâu chia mỗi lệnh thành nhiều giai đoạn như nạp lệnh (fetch), giải mã (decode), thực thi (execute) và hoàn tất (write-back), nhưng lệnh rẽ nhánh có điều kiện chỉ biết được "lệnh ở địa chỉ nào sẽ nạp tiếp theo" khi đã tới giai đoạn thực thi. Nếu không dự đoán mà mỗi lần đều chờ kết quả rẽ nhánh, phần đầu của đường ống sẽ trống (bubble) trong vài chu kỳ và hiệu năng sụt giảm mạnh. Dự đoán rẽ nhánh lấp khoảng trống đó bằng phỏng đoán, còn thực thi suy đoán thực sự đẩy các lệnh trên đường phỏng đoán vào tài nguyên tính toán, giành trước lợi ích "nếu đoán đúng".

Ở đây phải phân biệt khái niệm dự đoán(prediction) và suy đoán(speculation). Dự đoán là hành vi suy luận "đoán sẽ rẽ theo hướng nào", còn suy đoán là mô hình thực thi "chạy trước trên tiền đề rằng suy luận có thể sai, trong khi vẫn giữ khả năng hoàn tác". Như vậy thực thi suy đoán là khái niệm cấp cao áp dụng chung cho nhiều loại phỏng đoán — không chỉ dự đoán rẽ nhánh mà cả dự đoán mơ hồ bộ nhớ (memory disambiguation), dự đoán giá trị, v.v. — và trụ cột quan trọng nhất nâng đỡ độ chính xác của nó là dự đoán rẽ nhánh. Trong bài thi Kỹ sư chuyên nghiệp, cách rõ ràng nhất là mô tả hai thứ này như quan hệ giữa "bộ não phỏng đoán (bộ dự đoán rẽ nhánh)" và "cơ thể di chuyển theo phỏng đoán nhưng có thể hủy (động cơ thực thi suy đoán)".

Độ chính xác của thực thi suy đoán phụ thuộc vào năng lực khôi phục dự đoán sai(misprediction recovery). Nếu khi đoán sai mà kết quả của các lệnh đã thực thi suy đoán rò rỉ vào trạng thái kiến trúc (thanh ghi, bộ nhớ) thì chương trình sẽ hoạt động sai, nên phần cứng cô lập "trạng thái trước khi xác định" bằng các cấu trúc như bộ đệm sắp xếp lại (ROB), đổi tên thanh ghi và điểm kiểm tra, rồi vứt bỏ toàn bộ khi dự đoán sai. Vì thiết kế "suy đoán và vứt bỏ" này đã trở thành gốc rễ của họ lỗ hổng Spectre và Meltdown năm 2018, chủ đề này là một trường hợp tiêu biểu nơi hiệu năng và an ninh giao nhau.

Tóm trong một câu, cách dự đoán rẽ nhánh và thực thi suy đoán đóng góp cho hiệu năng là "một vòng tuần hoàn tốt không bao giờ làm dừng đường ống, và nhờ không dừng mà giữ nhiều lệnh cùng bay một lúc". Nhưng vòng tuần hoàn tốt này chỉ thành lập "khi phỏng đoán đúng đủ thường xuyên". Khi độ chính xác dự đoán tụt, công việc được thực thi trước theo suy đoán bị vứt bỏ hàng loạt, chỉ tiêu tốn điện trong một vòng luẩn quẩn, và đường ống càng sâu thì tổn thất đó càng bị khuếch đại. Do đó suy đoán không phải bữa trưa miễn phí mà là một giao dịch mua chịu dựa trên tài sản bảo đảm "dự đoán chính xác", và thứ chịu trách nhiệm về chất lượng tài sản bảo đảm ấy là bộ dự đoán rẽ nhánh tinh vi.

B. Bối cảnh ra đời và sự cần thiết

Sự cần thiết của dự đoán rẽ nhánh tăng theo cấp số nhân khi đường ống sâu dần. Ở đường ống 5 giai đoạn ban đầu, độ trễ rẽ nhánh chỉ 1–2 chu kỳ, nhưng khi cuộc đua tần số gay gắt lên và đường ống sâu tới 10–20 giai đoạn trở lên, một lần dự đoán sai dẫn tới hàng chục chu kỳ lãng phí. Trong chương trình thông thường, cứ khoảng 5–7 lệnh lại xuất hiện một lần rẽ nhánh, nên chỉ cần độ chính xác dự đoán giảm chút ít là hiệu năng tổng thể sụp đổ. Chẳng hạn ở đường ống 15 giai đoạn với hình phạt dự đoán sai 15 chu kỳ và rẽ nhánh chiếm 20% tổng số lệnh, chỉ cần nâng độ chính xác dự đoán từ 90% lên 95% là hiệu năng cảm nhận đã thay đổi đáng kể. Đây là lý do các nhà thiết kế CPU đã đầu tư một phần lớn ngân sách transistor vào bộ dự đoán rẽ nhánh.

Thực thi suy đoán cũng là điều kiện tiên quyết để khai thác song song mức lệnh(ILP, Instruction-Level Parallelism). Bộ xử lý thực thi không theo thứ tự thực thi sớm các lệnh không có phụ thuộc dữ liệu, bất kể thứ tự, để các đơn vị tính toán không nghỉ; nhưng nếu dừng tại một rẽ nhánh thì không thể khai thác chút song song nào ở phía sau nó. Thực thi suy đoán kéo về và thực thi cả các lệnh "bên kia" rẽ nhánh, nhờ đó tạo ra một cửa sổ lệnh (instruction window) rộng giữ hàng chục đến hàng trăm lệnh ở trạng thái "đang bay (in-flight)". Nói cách khác, động lực cốt lõi để các lõi hiệu năng cao ngày nay nâng IPC (lệnh/chu kỳ) chính là suy đoán quyết liệt vận hành trên nền dự đoán rẽ nhánh chính xác.

Sự cần thiết này gắn trực tiếp với hiệu năng thực tế, dù là máy chủ, di động hay HPC. Xử lý truy vấn nhiều rẽ nhánh có điều kiện trong động cơ cơ sở dữ liệu, điều phối lệnh trong trình thông dịch và JIT, các vòng lặp dày đặc rẽ nhánh trong động cơ game đều nhạy cảm với độ chính xác dự đoán rẽ nhánh. Ngược lại, từ góc độ an ninh, người ta phát hiện rằng dữ liệu bí mật có thể rò rỉ qua dấu vết mà "lệnh đã thực thi suy đoán rồi bị vứt bỏ" để lại trong trạng thái vi kiến trúc như bộ nhớ đệm — phơi bày nghịch lý rằng suy đoán vì hiệu năng lại trở thành bề mặt tấn công (attack surface). Do đó chủ đề này là một lĩnh vực cốt lõi của Kỹ sư chuyên nghiệp, đòi hỏi hiểu đồng thời hiệu năng kiến trúc và an ninh hệ thống.

Xét về lịch sử, dự đoán rẽ nhánh và thực thi suy đoán trở thành chủ đạo cùng với việc thương mại hóa các bộ xử lý superscalar, không theo thứ tự trong thập niên 1990 (Intel P6, MIPS R10000, v.v.). Các nhà thiết kế thời đó đặt "bằng mọi giá không để đơn vị tính toán nghỉ" làm nhiệm vụ tối thượng, và câu trả lời là suy đoán chạy trước sang bên kia rẽ nhánh. Trong hơn hai thập niên sau đó, bộ dự đoán tinh vi dần đều đặn — từ bộ đếm 2 bit tới bộ dự đoán tương quan, thiết kế đấu loại, và TAGE/perceptron — và cửa sổ lệnh mở rộng từ hàng chục lên quy mô hàng trăm lệnh. Suy đoán vì vậy không phải kỹ thuật của một thế hệ cụ thể mà là triết lý thiết kế liên tục nâng đỡ hiệu năng của CPU đa dụng hiện đại, và chính vì bén rễ sâu như thế mà nó trở thành cấu trúc không dễ loại bỏ ngay cả sau Spectre.

2. Cấu trúc đường ống thực thi suy đoán

Bộ dự đoán rẽ nhánh và động cơ thực thi suy đoán phối hợp, chia thành "dự đoán" ở giai đoạn nạp lệnh và "kiểm chứng/khôi phục" ở giai đoạn thực thi và hoàn tất, như dưới đây.

flowchart LR
  PC["Bộ đếm chương trình(PC)"] --> FETCH["Nạp lệnh(Fetch)"]
  BP["Bộ dự đoán rẽ nhánh(BHT/BTB/RAS)"] -->|"hướng·đích dự đoán"| FETCH
  FETCH --> DEC["Giải mã·đổi tên(Decode/Rename)"]
  DEC --> ROB["đăng ký vào Bộ đệm sắp xếp lại(ROB)"]
  ROB --> EXEC["Thực thi không theo thứ tự(Out-of-Order)"]
  EXEC -->|"kết quả rẽ nhánh thực tế"| CHK{"dự đoán trúng?"}
  CHK -->|"Có(Hit)"| COMMIT["Hoàn tất theo thứ tự(Commit)"]
  CHK -->|"Không(Miss)"| FLUSH["xả đường ống·khôi phục trạng thái"]
  FLUSH -->|"nạp lại từ PC đúng"| PC
  COMMIT -->|"cập nhật bộ dự đoán(học)"| BP
  FLUSH -->|"cập nhật bộ dự đoán(học)"| BP
  style BP fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style CHK fill:#fef7e0,stroke:#f9ab00,stroke-width:2px

Có thể tóm gọn luồng này trong một cái nhìn như sau. Dự đoán rẽ nhánh vận hành theo bốn nhịp — "phỏng đoán, thực thi, kiểm chứng, khôi phục" — với mỗi giai đoạn ăn khớp bất đồng bộ ở một vị trí đường ống khác nhau.

sequenceDiagram
  participant F as Giai đoạn nạp lệnh(Fetch)
  participant P as Bộ dự đoán rẽ nhánh(Predictor)
  participant E as Đơn vị thực thi(Execute)
  participant R as Bộ đệm sắp xếp lại(ROB)
  F->>P: hướng·đích rẽ nhánh của PC này?
  P-->>F: dự đoán(taken, địa chỉ đích)
  F->>R: đăng ký các lệnh suy đoán theo thứ tự
  R->>E: thực thi không theo thứ tự các lệnh đã sẵn sàng
  E-->>R: thông báo kết quả rẽ nhánh thực tế
  alt dự đoán trúng
    R->>R: hoàn tất theo thứ tự(commit)
    R-->>P: huấn luyện bộ dự đoán bằng kết quả
  else dự đoán sai
    R->>R: vứt bỏ tất cả sau rẽ nhánh(squash)
    R-->>F: yêu cầu nạp lại từ PC đúng
    R-->>P: hiệu chỉnh bộ dự đoán bằng kết quả sai
  end

Điểm cốt lõi trong hai hình trên là sự tách biệt theo thời gian giữa dự đoán và kiểm chứng. Giai đoạn nạp lệnh tin vào hướng/đích do bộ dự đoán rẽ nhánh cung cấp và cấp lệnh không ngơi nghỉ, còn kết quả rẽ nhánh thực tế được chốt mãi về sau ở giai đoạn thực thi. Ở khoảng giữa, các lệnh đã nạp và thực thi suy đoán được xếp vào ROB theo thứ tự và được đánh dấu "chưa commit". Nếu dự đoán đúng, rẽ nhánh đó và các lệnh sau nó lần lượt commit vào trạng thái kiến trúc theo thứ tự chương trình; nếu sai, mọi mục ROB sau rẽ nhánh đó bị vô hiệu và việc nạp lại bắt đầu từ địa chỉ đúng. Dù là commit hay xả, kết quả đều được phản hồi về bộ dự đoán và dùng cho việc học nhằm nâng độ chính xác của dự đoán kế tiếp.

A. Các thành phần của bộ dự đoán rẽ nhánh

Dự đoán rẽ nhánh chỉ hoàn chỉnh khi đoán đúng cả "hướng (taken/not-taken)" lẫn "địa chỉ đích". Cấu trúc tiêu biểu đảm nhận dự đoán hướng là bảng lịch sử rẽ nhánh(BHT, Branch History Table). Dạng cơ bản nhất đặt một bộ đếm bão hòa 2 bit(saturating counter) tại mỗi chỉ mục băm từ địa chỉ rẽ nhánh, quản lý bốn trạng thái: strongly-taken, weakly-taken, weakly-not-taken và strongly-not-taken. Bộ dự đoán 1 bit có nhược điểm sai hai lần liên tiếp ở đầu và cuối vòng lặp, trong khi 2 bit thêm quán tính "không lật hướng ngay sau một lần trượt", cho độ chính xác khoảng 95% trên các mẫu lặp lại. Cỗ máy trạng thái nhỏ bé này là điểm xuất phát kinh điển của dự đoán rẽ nhánh.

Nhìn sâu hơn một chút vào cách bộ đếm bão hòa 2 bit hoạt động sẽ thấy rõ dụng ý thiết kế. Các trạng thái là 00 (not-taken mạnh), 01 (not-taken yếu), 10 (taken yếu) và 11 (taken mạnh); bộ đếm tăng 1 khi rẽ nhánh là taken và giảm 1 khi not-taken, bão hòa ở hai đầu. Dự đoán được quyết bởi bit cao nhất (taken nếu 10 hoặc 11). Mấu chốt của cấu trúc này là ngay cả khi một kết quả ngoại lệ xảy ra một lần ở trạng thái "mạnh", nó không lật hướng dự đoán ngay mà chỉ chuyển sang trạng thái "yếu". Nhờ vậy, một "ngoại lệ trong quy luật" — như lần not-taken duy nhất ở cuối vòng lặp chạy 100 lần — không làm hỏng dự đoán khi vào vòng lặp lần sau. Có thể nói đó là thiết kế gói trực giác thống kê "hãy tin xu hướng gần đây nhưng khoan dung với một bất thường đơn lẻ" vào một cỗ máy trạng thái rất nhỏ.

Cấu trúc đảm nhận dự đoán đích là bộ đệm đích rẽ nhánh(BTB, Branch Target Buffer). Nếu BHT trả lời "có đi hay không" thì BTB lưu "nếu đi thì đi đâu", như một bộ nhớ đệm. Khi tra BTB bằng PC ở giai đoạn nạp lệnh và trúng, địa chỉ đích thu được ngay để có thể nạp địa chỉ đó ở chu kỳ sau — thậm chí không cần chờ giải mã lệnh rẽ nhánh. Đặc biệt trong mã có nhiều rẽ nhánh gián tiếp như gọi/trả về hàm, tỷ lệ trúng BTB quyết định hiệu năng. Địa chỉ trả về của hàm được dự đoán gần như hoàn hảo bằng một ngăn xếp địa chỉ trả về(RAS, Return Address Stack) riêng, tận dụng tính chất gọi-và-trả về lồng nhau như ngăn xếp: push địa chỉ trả về khi gọi (call) và pop khi trả về (ret) để cấp đích, cho độ chính xác rất cao trừ khi đệ quy quá sâu.

Ý tưởng quyết định nâng độ chính xác dự đoán hướng là bộ dự đoán tương quan(correlating), hai cấp(two-level). Xuất phát từ quan sát rằng kết quả của một rẽ nhánh có tương quan với kết quả của các rẽ nhánh gần đây khác, nó dùng thêm thanh ghi lịch sử toàn cục(GHR, Global History Register), ghi các kết quả rẽ nhánh gần đây dưới dạng chuỗi bit, vào việc lập chỉ mục BHT. gshare tiêu biểu tạo chỉ mục bằng cách XOR địa chỉ rẽ nhánh với lịch sử toàn cục, nên ngay cả cùng một rẽ nhánh cũng dùng bộ đếm khác khi ngữ cảnh (lịch sử) khác. Tiến xa hơn, bộ dự đoán đấu loại(tournament) đặt cả bộ dự đoán dựa trên lịch sử toàn cục lẫn bộ dựa trên lịch sử cục bộ (per-branch), và để một bộ chọn khác (meta-predictor) chọn bên nào chính xác hơn. Các lõi hiệu năng cao mới nhất áp dụng TAGE(TAgged GEometric) kết hợp nhiều độ dài lịch sử khác nhau, hoặc bộ dự đoán perceptron nền tảng mạng nơ-ron, đạt độ chính xác quanh 99%.

B. Thực thi suy đoán và khôi phục dự đoán sai

Trái tim của động cơ thực thi suy đoán là bộ đệm sắp xếp lại(ROB) và đổi tên thanh ghi. Lệnh thực thi không theo thứ tự, nhưng chỉ riêng "commit" phản ánh vào trạng thái kiến trúc là bắt buộc phải tuân thứ tự chương trình, và ROB đóng vai trò hàng đợi vòng bảo toàn thứ tự này. Mỗi lệnh nhận chỗ trong ROB theo thứ tự nạp và, dù đã thực thi xong, vẫn giữ tạm kết quả cho tới khi mọi lệnh trước nó đã commit. Đổi tên thanh ghi ánh xạ thanh ghi kiến trúc lên tập thanh ghi vật lý lớn hơn, đặt giá trị tính suy đoán vào "thanh ghi vật lý trước khi xác định" để loại bỏ phụ thuộc giả và làm việc quay lui dễ dàng.

Quá trình khôi phục tại khoảnh khắc phát hiện dự đoán sai quyết định độ chính xác của thực thi suy đoán. Khi lệnh rẽ nhánh cho ra kết quả thực tế ở giai đoạn thực thi mà khác với dự đoán, phần cứng vứt bỏ (squash) mọi lệnh đã vào ROB sau rẽ nhánh đó, cuộn bảng đổi tên về ảnh chụp (điểm kiểm tra) tại thời điểm rẽ nhánh, và tiếp tục nạp từ đích đúng. Lúc này, để không phản ánh ghi vào bộ nhớ từ trước, lệnh lưu trữ chỉ nằm trong bộ đệm lưu trữ(store buffer) cho tới khi commit và chỉ chảy ra bộ nhớ đệm/bộ nhớ tại thời điểm ROB commit. Nhờ vậy, về nguyên tắc một lệnh lưu trữ suy đoán bị chặn khỏi việc hiện ra với các lõi khác hoặc để lại tác dụng phụ không thể hoàn tác.

Vấn đề là tuy "trạng thái kiến trúc" được khôi phục hoàn hảo, trạng thái vi kiến trúc thì không. Nếu một lệnh nạp thực thi suy đoán chạm vào một địa chỉ bộ nhớ nào đó, dấu vết dữ liệu đó được nạp vào bộ nhớ đệm vẫn còn lại ngay cả khi lệnh về sau bị vứt bỏ. Kẻ tấn công có thể truy ngược dấu vết này qua kênh phụ bộ nhớ đệm (cache side channel) đo chênh lệch thời gian truy cập, và phục dựng giá trị bí mật mà một đường "lẽ ra không bao giờ được thực thi" đã chạm tới. Nghĩa là phần cứng thành công "làm cho kết quả như chưa từng xảy ra" nhưng không xóa được "dấu vết vật lý rằng nó đã được thực thi", và khoảng hở này chính là bản chất của lỗ hổng thực thi suy đoán.

C. Hai trục của suy đoán: suy đoán điều khiển và suy đoán dữ liệu

Thực thi suy đoán có thể chia, theo "đang phỏng đoán cái gì", thành suy đoán điều khiển (control speculation) và suy đoán dữ liệu (data speculation), và dự đoán rẽ nhánh là trường hợp tiêu biểu của loại trước. Suy đoán điều khiển, như đã nói ở trên, phỏng đoán hướng/đích của rẽ nhánh để đẩy luồng điều khiển tiến trước, giành trước chính đường thực thi của chương trình. Đường ống càng sâu, cả phần thưởng lẫn rủi ro của suy đoán điều khiển càng lớn, và ở chỗ một lần dự đoán sai quét sạch hàng chục lệnh chất trong cửa sổ, nó mang tính chất khoản đầu tư "rủi ro cao, lợi nhuận cao".

Suy đoán dữ liệu xuất hiện chủ yếu trong dự đoán mơ hồ bộ nhớ(memory disambiguation). Trong thực thi không theo thứ tự, khi muốn thực thi một lệnh nạp phía sau trước một lệnh lưu trữ phía trước, không thể biết trước khi thực thi liệu địa chỉ của hai lệnh có trùng (phụ thuộc nhau) hay không. Bộ xử lý phỏng đoán "sẽ không trùng" và thực thi lệnh nạp sớm, nhưng quay lui lệnh nạp đó và các lệnh sau nếu về sau phát hiện địa chỉ trùng. Cấu trúc đảm nhận dự đoán này là bộ dự đoán phụ thuộc bộ nhớ(memory dependence predictor), mà tối ưu hóa store-to-load forwarding của Intel là một ví dụ tiêu biểu. Dù là suy đoán điều khiển hay dữ liệu, bộ khung "phỏng đoán-thực thi-kiểm chứng-khôi phục" là như nhau, và cả hai đều có điểm chung về an ninh rằng dấu vết dự đoán sai có thể rò qua kênh phụ.

Một hàm ý quan trọng về mặt thực tiễn ở đây là "độ sâu suy đoán(speculation depth)" là một tham số thiết kế. Cửa sổ lệnh càng rộng và càng nhiều rẽ nhánh chưa giải quyết được suy đoán chồng lên, ILP càng lớn, nhưng chi phí vứt bỏ khi một rẽ nhánh sai và bề mặt kênh phụ mà đường sai để lại cũng càng lớn. Do đó lõi hiệu năng cao cho máy chủ cho phép cửa sổ rộng hàng trăm lệnh và suy đoán đa rẽ nhánh, trong khi lõi nhúng và di động bị ràng buộc điện năng thu hẹp cửa sổ và hạn chế độ sâu suy đoán để chọn hiệu suất và an toàn — nên bản thân mức quyết liệt của suy đoán trở thành quyết định thiết kế phân tách các dòng sản phẩm.

3. Phân loại và so sánh

Bộ dự đoán rẽ nhánh được phân loại như sau theo nguồn thông tin và cấu trúc lưu trữ, với sự đánh đổi rõ ràng giữa độ chính xác và chi phí phần cứng.

Phân loại	Căn cứ dự đoán	Cấu trúc tiêu biểu	Độ chính xác	Chi phí/giới hạn
Dự đoán tĩnh	quy tắc cố định lúc biên dịch	always-taken, rẽ nhánh lùi=taken	thấp (60–70%)	không phản ánh được mẫu lúc chạy
Động 1 bit	kết quả một lần trước đó	BHT đơn giản	trung bình	hai lỗi ở biên vòng lặp
Động 2 bit	quán tính của kết quả trước	bộ đếm bão hòa	khoảng 90%	không phản ánh tương quan liên rẽ nhánh
2 cấp/tương quan	lịch sử toàn cục·cục bộ	gshare, đấu loại	95%+	dung lượng bảng lịch sử·aliasing
Cao cấp	nhiều độ dài lịch sử·học	TAGE, perceptron	quanh 99%	tăng diện tích·điện·độ phức tạp

Khác biệt giữa dự đoán tĩnh và động vượt khỏi khoảng cách độ chính xác đơn thuần, đi tới câu hỏi "khi nào thu được thông tin". Dự đoán tĩnh nhúng các quy tắc — như "rẽ nhánh lùi của vòng lặp thường là taken" — bằng cách chỉ nhìn cấu trúc mã trong trình biên dịch, nên phần cứng đơn giản, nhưng không nắm được hành vi lúc chạy biến đổi theo dữ liệu đầu vào. Ngược lại, dự đoán động học từ lịch sử tích lũy trong lúc thực thi nên nắm được cả các mẫu phụ thuộc dữ liệu. Trong thực tiễn hai thứ được dùng bổ trợ cho nhau. Chẳng hạn macro likely()/unlikely() của nhân Linux chuyển tri thức của lập trình viên tới trình biên dịch dưới dạng gợi ý tĩnh để tối ưu bố trí rẽ nhánh, và trên nền đó bộ dự đoán động phần cứng đảm nhận các mẫu chi tiết.

Lý do bộ dự đoán tương quan vượt trội bộ 2 bit thuần là "tách biệt ngữ cảnh". Ngay cả cùng một rẽ nhánh thường có kết quả khác nhau tùy đường đã đi qua ngay trước đó (ví dụ các câu điều kiện nối chuỗi chia sẻ một biến như if (a) ...; if (a && b) ...), và trộn lịch sử toàn cục vào chỉ mục khiến mỗi ngữ cảnh học một bộ đếm khác, giảm nhiễu. Tuy nhiên khi bit lịch sử dài ra, bảng lớn lên và aliasing — nơi các rẽ nhánh khác nhau tranh cùng một mục — tăng lên, nên xung đột được giảm nhẹ bằng các kỹ thuật như băm XOR của gshare hay khớp thẻ của TAGE. Sự căng thẳng thiết kế "chứa nhiều ngữ cảnh hơn trong ít bộ nhớ hơn" như vậy là một trục cốt lõi của nghiên cứu dự đoán rẽ nhánh.

Hãy ước lượng hiệu quả bằng con số cụ thể. Ở một lõi có tỷ lệ rẽ nhánh 20% và hình phạt dự đoán sai 15 chu kỳ, giả định nền 1 chu kỳ mỗi lệnh, ở độ chính xác dự đoán 90% độ trễ phụ do rẽ nhánh khoảng 0,2 × 0,10 × 15 = 0,30 chu kỳ mỗi lệnh, nhưng nâng lên 99% giảm còn 0,2 × 0,01 × 15 = 0,03 chu kỳ — một phần mười — cải thiện rõ rệt CPI (chu kỳ mỗi lệnh). Chính vì độ nhạy này mà các CPU hàng đầu dành diện tích đáng kể cho các bộ dự đoán đa cấp hàng nghìn đến hàng chục nghìn mục và cho bộ lưu trữ chuyên dụng.

Làm ví dụ thực tiễn, khác biệt hiệu năng rẽ nhánh giữa mảng đã sắp xếp và mảng chưa sắp xếp cho thấy sức mạnh của dự đoán rẽ nhánh một cách kịch tính. Trong một phép đo chuẩn nổi tiếng, chạy cùng vòng lặp if (data[i] >= 128) sum += data[i]; với dữ liệu chỉ cần được sắp xếp thì nhanh gấp vài lần so với khi chưa sắp xếp. Trên dữ liệu đã sắp xếp, kết quả rẽ nhánh theo một mẫu đều đặn "liên tục not-taken rồi liên tục taken từ một điểm nào đó" so với ngưỡng, nên bộ dự đoán gần như luôn trúng, trong khi trên dữ liệu ngẫu nhiên các rẽ nhánh tản mát như tung đồng xu và dự đoán sai bùng nổ. Trường hợp hiệu năng đo được chênh nhau vài lần dù độ phức tạp thuật toán như nhau này nhắc ta rằng phân tích hiệu năng phải xét cả các hiệu ứng vi kiến trúc không giải thích được chỉ bằng "Big-O".

Một ví dụ khác là điều phối lệnh trong trình thông dịch. Câu switch trung tâm của trình thông dịch bytecode nhảy tới một rẽ nhánh gián tiếp khác nhau ở mỗi vòng lặp, và một mục BTB đơn lẻ dự đoán rẽ nhánh gián tiếp đa hướng này rất kém nên dự đoán sai thường xuyên. Để giảm nhẹ điều này, kỹ thuật threaded code (computed goto) sao chép rẽ nhánh điều phối vào cuối mỗi bộ xử lý bytecode đã được dùng; phân tán các điểm rẽ nhánh theo cách này khiến mỗi điểm học một ngữ cảnh lịch sử khác, nâng độ chính xác dự đoán và cải thiện hiệu năng trình thông dịch. Dẫu vậy, cũng nên hiểu rằng tiến bộ của TAGE và bộ dự đoán rẽ nhánh gián tiếp hiện đại đã thu hẹp khoảng cách đó so với trước kia.

4. Chuyên sâu: lỗ hổng thực thi suy đoán (Spectre·Meltdown) và ứng phó

Spectre và Meltdown, công bố năm 2018, là bước ngoặt cho thấy "suy đoán vì hiệu năng" có thể phá vỡ ranh giới an ninh ra sao. Chúng là các tấn công thực thi nhất thời(transient execution attack) lạm dụng các chức năng bình thường của CPU (thực thi suy đoán, thực thi không theo thứ tự, bộ nhớ đệm), và tác động lớn ở chỗ chúng không phải lỗi phần mềm mà là kênh phụ nội tại trong thiết kế vi kiến trúc. Nguyên lý chung có bốn bước: "đọc suy đoán giá trị bí mật rồi dùng nó làm chỉ mục truy cập bộ nhớ → bị vứt bỏ nhưng để lại dấu vết trong bộ nhớ đệm → đo dấu vết qua kênh phụ → phục dựng bí mật".

Spectre Variant 1 (vượt kiểm tra biên, Bounds Check Bypass), trong mã như if (x < array_len) y = array2[array[x] * 4096];, khiến bộ dự đoán rẽ nhánh đoán "trong biên" ngay cả khi x ngoài biên, nên nó đọc suy đoán array[x] (một bí mật ngoài biên) và dùng giá trị đó để nạp một dòng bộ nhớ đệm cụ thể của array2. Khi kết quả rẽ nhánh được chốt, lệnh nạp đó bị vứt bỏ, nhưng đo dấu vết bộ nhớ đệm để lại trong array2 làm lộ byte bí mật. Variant 2 (tiêm đích rẽ nhánh, Branch Target Injection) để kẻ tấn công đầu độc BTB sao cho một rẽ nhánh gián tiếp của tiến trình nạn nhân nhảy suy đoán tới một gadget do kẻ tấn công chọn. Meltdown là biến thể đọc suy đoán bộ nhớ nhân trước khi kiểm tra quyền hoàn tất trong lúc thực thi không theo thứ tự, phá vỡ trực tiếp ranh giới người dùng-nhân.

Phân biệt khác biệt căn bản giữa Spectre và Meltdown là bí quyết cho bài thi Kỹ sư chuyên nghiệp. Vì Meltdown lạm dụng cuộc đua(race) giữa kiểm tra quyền và thực thi suy đoán, nó bị chặn tương đối gọn gàng chỉ bằng tách bảng địa chỉ nhân khỏi bảng trang người dùng (KPTI). Nghĩa là tồn tại lời giải "ngăn chính truy cập bất hợp pháp đó". Ngược lại, Spectre lạm dụng dự đoán rẽ nhánh — một chức năng hiệu năng bình thường và thiết yếu — nên không thể loại bỏ chính bộ dự đoán, và chỉ có thể giảm nhẹ bằng cách cắt suy đoán có chọn lọc cho từng mẫu mã cụ thể. Do đó nảy sinh bất đối xứng: Meltdown gần với "khiếm khuyết có thể sửa", còn Spectre gần với "rủi ro còn lại về mặt cấu trúc".

Lý do những tấn công này mở ra lĩnh vực mới "an ninh vi kiến trúc" ngay từ đầu là vì đối tượng tấn công không phải khiếm khuyết logic trong phần mềm mà là "tác dụng phụ vật lý đo được". Các chênh lệch thời gian cực nhỏ mà hoạt động bình thường để lại — như bộ nhớ đệm có được nạp hay không, tranh chấp cổng, thay đổi trạng thái TLB — đều có thể trở thành kênh rò rỉ bí mật. Để chặn hoàn toàn tấn công thì phải tạo ra "suy đoán không quan sát được", điều khó đạt mà không hy sinh hiệu năng. Rốt cuộc, an ninh thực thi suy đoán định hình thành bài toán giảm nhẹ rủi ro với mục tiêu thực tế không phải "đưa thông tin rò rỉ về 0" mà "hạ băng thông rò rỉ xuống mức khiến tấn công bất khả thi".

Nghiên cứu về sau phơi bày rằng Spectre và Meltdown chỉ là trường hợp đặc biệt, hé lộ một địa hình rộng của các tấn công thực thi nhất thời. Nối tiếp là họ MDS (ZombieLoad, RIDL, Fallout) rò rỉ dữ liệu cũ bằng cách khai thác độ trễ cổng nạp; L1TF (Foreshadow) nhắm bộ nhớ đệm L1 trong môi trường ảo hóa; Retbleed lạm dụng dự đoán trả về để vượt retpoline; và Downfall nhắm thanh ghi dấu phẩy động và vector. Dù vectơ tấn công của chúng khác nhau (bộ dự đoán rẽ nhánh, bộ đệm lưu trữ, ngăn xếp trả về, v.v.), chúng chia sẻ bộ khung chung "chạm suy đoán vào bí mật và để lại dấu vết vi kiến trúc". Do đó đã tái diễn mô thức "đập chuột chũi", trong đó chặn một biến thể vẫn để biến thể mới xuất hiện chừng nào còn một vectơ tương tự.

Ứng phó được thực hiện ở ba lớp: phần mềm, vi mã và phần cứng. Về phần mềm, đã đưa vào chèn một LFENCE chặn suy đoán sau kiểm tra biên, retpoline biến rẽ nhánh gián tiếp thành dạng không thể đoán để ngăn tiêm BTB, và KPTI (KAISER) tách không gian địa chỉ nhân khỏi bảng trang người dùng. Về phần cứng/vi mã, đã thêm các tính năng cô lập thường trực như IBRS, IBPB, STIBP ngăn nhiễm chéo trạng thái bộ dự đoán rẽ nhánh, và eIBRS ở các CPU thế hệ sau. Tuy nhiên các giảm nhẹ này thường kèm suy giảm hiệu năng (từ vài tới vài chục phần trăm trên một số khối lượng công việc), một lần nữa khắc sâu "đánh đổi an ninh-hiệu năng", và an ninh vi kiến trúc trở thành chủ đề nghiên cứu thường trực khi các biến thể như MDS, L1TF, Retbleed, Downfall tiếp nối sau đó. Xu hướng gần đây hội tụ vào các thiết kế giữ cho dữ liệu nạp suy đoán không ảnh hưởng tới kênh phụ (ví dụ trì hoãn phản ánh dữ liệu suy đoán vào bộ nhớ đệm, cô lập ở mức phần cứng) và các kỹ thuật trình biên dịch/HĐH tắt suy đoán có chọn lọc ở các vùng nhạy cảm an ninh.

5. Điểm cân nhắc và hàm ý

Từ góc độ Kỹ sư chuyên nghiệp, thực thi suy đoán và dự đoán rẽ nhánh mang những hàm ý chiến lược sau, trải rộng từ thiết kế hiệu năng tới vận hành an ninh.

Thứ nhất, tối ưu hiệu năng phải khởi đầu từ "mã thân thiện với rẽ nhánh". Vì bộ dự đoán rẽ nhánh mạnh ở các mẫu đều đặn và yếu ở rẽ nhánh ngẫu nhiên phụ thuộc dữ liệu, trong các vòng lặp nóng nên thay rẽ nhánh bằng di chuyển có điều kiện (cmov), phép bit không rẽ nhánh hay bảng tra, hoặc sắp xếp dữ liệu để nâng tính dự đoán được của kết quả rẽ nhánh. Dùng PGO (Profile-Guided Optimization) của trình biên dịch cùng gợi ý likely/unlikely có thể giảm dự đoán sai trên đường nóng một cách hệ thống.

Thứ hai, đánh đổi an ninh-hiệu năng phải được quyết theo mô hình đe dọa của tổ chức. Ở các môi trường vượt ranh giới tin cậy như đám mây đa thuê bao và trình duyệt, giảm nhẹ Spectre nên bật mặc định, nhưng trên các nút HPC của một miền tin cậy duy nhất, cũng hợp lý khi nới lỏng có chọn lọc một số giảm nhẹ để lấy lại hiệu năng. Nghĩa là áp dụng phân biệt dựa trên "ranh giới nằm ở đâu" hợp lý hơn áp dụng toàn bộ các giảm nhẹ, và vì thế phân loại đe dọa theo tài sản và khối lượng công việc phải đi trước.

Thứ ba, lỗ hổng phần cứng là một trục mới của quản lý vòng đời vá lỗi. Khác với lỗ hổng phần mềm, khiếm khuyết vi kiến trúc đan xen qua vi mã, phần sụn, nhân và trình ảo hóa, nên cần một thể chế quản lý cấu hình và quản lý thay đổi liên kết việc phân phối vi mã của nhà cung cấp CPU với các bản vá HĐH. Đưa lịch sử lỗ hổng và chi phí giảm nhẹ của một thế hệ CPU cụ thể vào các mục đánh giá ở khâu mua sắm cũng thuộc về quyết định ở tầm Kỹ sư chuyên nghiệp.

Thứ tư, lựa chọn kiến trúc gắn liền với điện năng, tỏa nhiệt và khả năng mở rộng. Suy đoán quyết liệt nâng ILP nhưng khi dự đoán sai thì mọi công việc đã làm bị lãng phí, hạ hiệu suất điện. Trên di động và biên, bộ dự đoán được đơn giản hóa và độ sâu suy đoán bị hạn chế để tiết kiệm điện, trong khi máy chủ tối đa hóa thông lượng bằng bộ dự đoán lớn chính xác. Khi các khối lượng công việc ít rẽ nhánh và song song dữ liệu cao như suy luận AI tăng lên, nên cân nhắc như một chiến lược kiến trúc sự phân vai giữa CPU đa dụng lấy suy đoán làm trung tâm và GPU/NPU ít phụ thuộc suy đoán.

Thứ năm, chẩn đoán dựa trên khả năng quan sát (observability) là quan trọng. Vì hầu hết CPU phơi bày tỷ lệ dự đoán sai rẽ nhánh, số lần trượt BTB, v.v. qua bộ đếm hiệu năng (PMU), nên đo lường dự đoán sai ở các điểm nóng bằng công cụ như perf và chọn đối tượng tối ưu trên cơ sở bằng chứng. Không phải tối ưu dựa vào phỏng đoán, mà vòng lặp đo-phân tích-cải tiến mới là chuẩn mực của kỹ thuật hiệu năng.

Tài liệu tham khảo

Hennessy & Patterson, "Computer Architecture: A Quantitative Approach" (các chương về dự đoán rẽ nhánh và thực thi suy đoán)
Intel, "Speculative Execution Side Channel Mitigations" sách trắng: https://www.intel.com/content/www/us/en/developer/articles/technical/software-security-guidance/overview.html
Spectre Attacks (Kocher et al., 2019): https://spectreattack.com/
Meltdown (Lipp et al., 2018): https://meltdownattack.com/
Linux kernel documentation, "Hardware vulnerabilities": https://www.kernel.org/doc/html/latest/admin-guide/hw-vuln/index.html

Tóm tắt một câu: Dự đoán rẽ nhánh đoán trước hướng/đích của rẽ nhánh để lấp khoảng trống của đường ống sâu, còn thực thi suy đoán là động cơ ILP kéo lệnh về và chạy trên phỏng đoán đó rồi quay lui khi dự đoán sai; trạng thái kiến trúc được khôi phục nhưng dấu vết vi kiến trúc như bộ nhớ đệm vẫn còn và trở thành gốc rễ của Spectre·Meltdown, nên phải thiết kế hiệu năng và an ninh cùng nhau.