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. 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), nhưng chỉ khi các lệnh độc lập. Nếu lệnh sau cần kết quả của 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. 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ó.
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.
Một lần tôi đo hớ: "cùng số phép tính thì cùng thời gian" và "cứ nhiều accumulator là nhanh mãi"
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". Đo phá tan: 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 đo cũng phá một niềm tin ngược — cái mà người vừa thấy accumulator giúp dễ mắc: "vậy cứ càng nhiều accumulator càng nhanh, tách thật nhiều vào". 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".
Bài học đo lường: thời gian phụ thuộc ĐỒ THỊ PHỤ THUỘC giữa các lệnh, không chỉ SỐ lệnh. Chuỗi phụ thuộc dài (một accumulator) bị giới hạn bởi ĐỘ TRỄ (latency-bound); tách thành N phép độc lập cho CPU chạy song song (ILP, throughput-bound) — đo: 1 acc 0,569 ns vs 8 acc 0,085 ns = 6,7x dù CÙNG số phép cộng. Nhưng mức lợi GIẢM dần (2,15/2,0/1,56x) và bão hòa khi hết cổng thực thi (~latency/throughput accumulator là đủ). Với double, g++ -O2 KHÔNG tự tách (đổi thứ tự cộng đổi làm tròn) — phải tự làm hoặc -ffast-math. Nếu tôi tin "cùng số phép tính thì cùng thời gian" tôi bỏ lỡ ILP; nếu tin "càng nhiều accumulator càng tốt" tôi vượt điểm bão hòa vô ích.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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ự".
Hệ quả thứ ba là tinh thần đo lường: CPU chạy song song ngầm — hiệu năng nằm ở đồ thị phụ thuộc, không chỉ số lệnh. Con số mang theo: chuỗi phụ thuộc (1 acc) latency-bound chậm hơn phép độc lập (8 acc) throughput-bound tới 6,7x dù cùng số phép cộng; lợi ích bão hòa ~4-8 accumulator (hết cổng thực thi); với FP, tự tách vì compiler không reassociate. Đo bằng cách so 1 vs N accumulator. "Cùng công việc" không có nghĩa "cùng thời gian" — cách bạn sắp xếp các phép phụ thuộc quyết định CPU chạy chúng nối đuôi hay chồng lên nhau.
Thử ba mươi giây
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 bạn 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.
