Hai phần đầu sê-ri nói về nhánh làm nghẽn đường ống lệnh (pipeline). Nhưng có một cách khác làm nghẽn pipeline mà không dính gì tới nhánh: sự phụ thuộc giữa các lệnh.

Hình dung một dây chuyền và tám công nhân. Nếu công việc là "mỗi người sơn xong một lớp rồi chuyền cho người kế sơn lớp tiếp" — mỗi lớp phải đợi lớp trước khô — thì tám người vẫn chỉ làm được tốc độ của một, bảy người còn lại đứng chờ. Nhưng nếu chia cho mỗi người một món đồ riêng để sơn trọn vẹn, cả tám làm cùng lúc, xong nhanh gấp bội. CPU hiện đại chạy nhiều lệnh cùng lúc trong một lõi (song song mức lệnh — ILP) đúng như tám công nhân đó, nhưng chỉ khi các lệnh độc lập. Nếu lệnh sau cần kết quả lệnh trước, nó phải chờ. Điều này dẫn tới một kết quả phản trực giác: hai đoạn code với y hệt số phép tính có thể chênh nhau vài lần chỉ vì cách chúng phụ thuộc nhau. Tôi đo trong container gcc:13 trên host ARM, và con số cho thấy "cùng số phép tính thì cùng thời gian" là một lầm tưởng.

Chuỗi phụ thuộc chờ, phép độc lập chạy song song

Mỗi lõi CPU có nhiều đơn vị thực thi và có thể phát nhiều lệnh mỗi chu kỳ — nếu chúng độc lập. Đây là ILP (instruction-level parallelism). Kẻ thù của nó là chuỗi phụ thuộc (dependency chain):

  • Chuỗi phụ thuộc: mỗi lệnh cần kết quả của lệnh trước. Chúng phải chạy tuần tự — lệnh sau đợi lệnh trước xong. Tốc độ bị giới hạn bởi độ trễ (latency) của phép tính: nếu một phép cộng số thực mất ~4 chu kỳ để cho kết quả, một chuỗi n phép cộng phụ thuộc mất ~4n chu kỳ, dù CPU có thể làm nhiều hơn.

  • Phép độc lập: không cần kết quả của nhau, nên CPU chạy chúng song song (nhiều cái cùng lúc trong pipeline). Tốc độ bị giới hạn bởi thông lượng (throughput): bao nhiêu phép mỗi chu kỳ — thường ~1 hoặc hơn.

Ví dụ kinh điển: cộng dồn một mảng. Viết s += a[i] với một biến s tạo một chuỗi phụ thuộc dài — mỗi phép cộng chờ giá trị s mới nhất (mỗi lớp sơn chờ lớp trước khô). Nếu ta tách thành nhiều biến tích lũy độc lập (s0, s1, … mỗi cái cộng một phần rồi gộp cuối), các chuỗi trở nên độc lập và chạy song song. Cùng số phép cộng, nhưng đồ thị phụ thuộc khác hẳn.

Đo: 6,7 lần nhanh hơn, cùng số phép cộng

Tôi cộng dồn 65.536 số double (nằm trong cache, để không bị giới hạn bộ nhớ) nhiều lần, so 1 biến tích lũy với 2/4/8 biến độc lập:

Cộng 65536 double (trong cache) x400 lần, CÙNG số phép cộng, g++ -O2 (không ffast-math), ARM:

   số accumulator độc lập      | ns/phép cộng | nhanh hơn 1 acc
   ----------------------------|--------------|----------------
   1 acc (chuỗi phụ thuộc)     |  0,569 ns    | 1x  (latency-bound)
   2 acc độc lập               |  0,265 ns    | 2,15x
   4 acc độc lập               |  0,133 ns    | 4,29x
   8 acc độc lập               |  0,085 ns    | 6,69x

Nhìn dòng 1 acc: cộng dồn bằng một biến mất 0,569 ns mỗi phép cộng. Đây là latency-bound — mỗi phép cộng s += a[i] phải đợi giá trị s từ phép cộng ngay trước, nên chúng chạy tuần tự với tốc độ bằng độ trễ của một phép cộng số thực. CPU có thừa đơn vị thực thi, nhưng chuỗi phụ thuộc trói tay nó — bảy công nhân đứng chờ.

Nhìn xuống 2, 4, 8 acc: chỉ bằng cách tách thành nhiều biến tích lũy độc lập — không thêm một phép cộng nào — thời gian giảm còn 0,265, 0,133, rồi 0,085 ns. Với 8 biến, nhanh hơn 6,69 lần so với một biến. Các chuỗi độc lập lấp đầy pipeline: trong lúc chuỗi này chờ, chuỗi kia chạy, nên CPU luôn có việc làm. Cùng khối lượng tính toán, chỉ khác cấu trúc phụ thuộc, mà nhanh gần bảy lần.

Nhìn kỹ mức tăng: 1→2 (2,15x), 2→4 (gần gấp đôi nữa), 4→8 (chỉ 1,56x). Mức lợi giảm dần — dấu hiệu sắp bão hòa: khi số chuỗi độc lập đủ để che hết độ trễ (số accumulator ≥ latency/throughput), thêm nữa không giúp vì đã hết cổng cộng số thực để chạy song song. Đây là giới hạn phần cứng, không phải phần mềm.

Một điểm quan trọng: với số thực double, trình biên dịch không tự tách accumulator ở -O2, vì đổi thứ tự cộng số thực sẽ đổi kết quả làm tròn (cộng số thực không kết hợp — (a+b)+c ≠ a+(b+c) về bit). Nên tối ưu này phải tự làm tay, hoặc bật -ffast-math (cho phép compiler reassociate). Với số nguyên (cộng kết hợp), -O2 thường tự làm.

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với một trực giác sâu: "thời gian = số phép tính × chi phí mỗi phép; cùng số phép cộng thì cùng thời gian". Con số bác ngay: cùng y hệt số phép cộng trên cùng dữ liệu, một biến tích lũy (0,569 ns) chậm hơn tám biến độc lập (0,085 ns) 6,7 lần. CPU không phải máy đếm phép tính chạy tuần tự — nó là máy chạy song song nhiều lệnh, và cái quyết định tốc độ là đồ thị phụ thuộc giữa các lệnh, không chỉ số lượng chúng. Một chuỗi phụ thuộc dài bỏ phí phần lớn năng lực của lõi.

Nhưng nếu vì thấy accumulator giúp mà tin "vậy cứ càng nhiều accumulator càng nhanh, tách thật nhiều vào" thì cũng sai. Mức lợi giảm dần (2,15x → 2,0x → 1,56x) và sẽ bão hòa. Khi số chuỗi độc lập đủ che hết độ trễ, CPU đã chạy hết công suất — thêm accumulator chỉ tốn thanh ghi mà không nhanh thêm, thậm chí chậm lại nếu tràn thanh ghi (register spill). Số accumulator tối ưu là ~độ trễ chia throughput của phép tính (thường 4–8 cho FP add), không phải "càng nhiều càng tốt".

Về đến code hằng ngày

Việc đầu tiên: trên vòng lặp số học nóng, phá chuỗi phụ thuộc bằng nhiều accumulator độc lập. Cộng dồn, tích lũy, tính chuẩn/tổng bình phương — nếu một biến tích lũy tạo chuỗi phụ thuộc dài, tách thành 4–8 biến độc lập (unroll thủ công) rồi gộp cuối có thể nhanh vài lần. Đây là một trong những tối ưu tay hiệu quả nhất cho code số thực, vì trình biên dịch không tự làm được (do ràng buộc làm tròn), khác với số nguyên.

Việc thứ hai: thiết kế để lệnh độc lập, tránh chuỗi phụ thuộc dài không cần thiết. Một biểu thức như x = x*a + b lặp lại là chuỗi phụ thuộc thuần — chậm. Nếu bài toán cho phép, tính nhiều luồng độc lập song song thay vì một chuỗi dài. Và biết rằng cấu trúc phụ thuộc, chứ không phải số phép tính, thường là thứ giới hạn code compute-bound — đó là lý do đôi khi "làm nhiều việc hơn theo cách song song" lại nhanh hơn "ít việc theo cách tuần tự".

Cái nguyên lý "phụ thuộc tuần tự bóp nghẹt song song" này lên tầng cao thì đổi tên nhưng không đổi bản chất, và biết nó giúp nhận ra nút thắt ở nơi bất ngờ. Stream tuần tự của Java gộp bằng một accumulator; muốn dùng nhiều lõi thì parallelStream — nhưng nó chỉ đúng đắn khi phép gộp kết hợp được (associative), y hệt ràng buộc làm tròn ở trên, đó là lý do interface Collector đòi tính kết hợp. Reduce trong Spark/MapReduce cũng vậy: gộp song song đòi hàm kết hợp và giao hoán. Còn cái bẫy "chuỗi phụ thuộc nối tiếp" thì hiện ra ở kiến trúc: một chuỗi microservice gọi nhau A→B→C, hay một pipeline await này rồi mới await kia trong khi chúng độc lập, chính là "một accumulator" ở quy mô hệ thống — gọi song song những phần độc lập (Promise.all, goroutine) là "tách accumulator" phiên bản mạng. Nguyên tắc chung: tốc độ do đồ thị phụ thuộc quyết định, ở mọi tầng — cái gì bắt buộc nối tiếp, và cái gì có thể chạy cùng lúc.

Muốn tự thấy thì cộng dồn một mảng double vừa trong cache theo hai cách. Một: một biến double s = 0; for i: s += a[i];. Hai: bốn biến s0..s3 cộng bốn phần tử mỗi vòng (s0 += a[i]; s1 += a[i+1]; ...) rồi gộp s0+s1+s2+s3 cuối. Bấm giờ (nhớ volatile sink và min nhiều lần) — bạn sẽ thấy bản bốn biến nhanh vài lần dù cộng đúng số phép như bản một biến. Rồi thử tám biến: nhanh thêm chút, nhưng ít hơn kỳ vọng — bạn đang chạm giới hạn phần cứng (bão hòa). Cuối cùng, biên dịch bản một biến với -ffast-math và xem trình biên dịch tự làm điều bạn vừa làm tay (vì giờ nó được phép đổi thứ tự cộng). Ba mươi giây đó cho thấy điều mà "cùng số phép tính thì cùng thời gian" giấu đi: CPU chạy nhiều lệnh cùng lúc, và một chuỗi phụ thuộc dài bỏ phí năng lực đó — phá chuỗi ra thành các luồng độc lập là cách mở khóa tốc độ mà số phép tính không đổi.