Suốt sê-ri ta đo các mảnh riêng lẻ của đồng thời — khóa, atomic, cache, cân bằng tải. Giờ đến câu hỏi bao trùm nhất: khi song song hóa một chương trình, tối đa nó nhanh lên được bao nhiêu? Câu trả lời có một định luật nổi tiếng — định luật Amdahl — và nó bi quan hơn nhiều người tưởng. Tôi đo speedup thật của một workload có phần tuần tự cố định, so với công thức, và phát hiện thực tế còn khắc nghiệt hơn cả Amdahl.
Amdahl: phần tuần tự là trần
Hầu như mọi chương trình có một phần không song song hóa được — đọc cấu hình, khởi tạo, một bước tổng hợp cuối, một đoạn phải chạy tuần tự. Gọi s là tỉ lệ thời gian dành cho phần tuần tự đó. Định luật Amdahl nói: với N luồng,
speedup(N) = 1 / ( s + (1 - s)/N )
Phần tuần tự s chạy mãi ở tốc độ một luồng; phần song song (1-s) được chia cho N. Khi N tiến tới vô cực, (1-s)/N tiến về 0, và speedup tiến tới 1/s — một trần không thể vượt. Điều đáng sợ: trần đó thấp một cách bất ngờ. Chỉ 5% tuần tự → trần 20 lần; 25% tuần tự → trần chỉ 4 lần, dù bạn có một nghìn lõi. Một phần nhỏ tuần tự bóp nghẹt toàn bộ lợi ích song song.
Tôi kiểm chứng bằng cách dựng một workload có phần tuần tự cố định (s) cộng phần song song chia cho N luồng, đo speedup thật theo N cho vài mức s, trong container gcc:13 (10 lõi).
Đo: khớp hình dạng Amdahl, nhưng tệ hơn
s = 0% (song song hoàn toàn, trần vô hạn):
N=8 : 4,67× N=10 : 5,20× (lý tưởng 8×, 10×)
s = 5% (trần Amdahl 20×):
N=8 : 3,97× (Amdahl 5,93) N=10 : 4,15× (Amdahl 6,90)
s = 25% (trần Amdahl 4×):
N=8 : 2,44× (Amdahl 2,91) N=10 : 2,44× (chững lại)
Với 25% tuần tự, speedup đo được chững ở 2,44× — và về mặt lý thuyết không bao giờ vượt được 4× dù thêm bao nhiêu lõi. Một phần tư công việc chạy tuần tự đã cắt ba phần tư tiềm năng song song. Đường cong đo được khớp hình dạng Amdahl: tăng nhanh lúc đầu, rồi cong xuống và bão hòa. Đây là bức tranh mà contention và scaling đã hé lộ, giờ được đóng khung bằng một định luật.
Một lần tôi đo hớ: thực tế còn dưới Amdahl
Tôi vào đo với niềm tin lạc quan phổ biến: "thêm lõi thì tăng tốc tỉ lệ; nếu chương trình gần như song song hoàn toàn thì nó sẽ scale gần tuyến tính". Đo phá tan điều đó theo hai tầng.
Tầng thứ nhất, chính Amdahl: một phần tuần tự nhỏ cũng chặn mạnh (25% → trần 4×). Nhưng tầng thứ hai bất ngờ hơn: thực tế còn dưới cả Amdahl. Nhìn dòng s=0% — workload song song hoàn toàn, không có phần tuần tự nào theo thiết kế — mà chỉ đạt 5,2× trên 10 lõi, không phải 10×. Vì sao? Vì Amdahl chỉ tính phần tuần tự tường minh trong code của bạn; nó bỏ qua các chi phí ẩn mà mọi chương trình song song thật đều gánh: băng thông bộ nhớ giới hạn (các lõi tranh nhau đường tới RAM), cân bằng tải không hoàn hảo, chi phí đồng bộ, tần số CPU giảm khi nhiều lõi bận. Những thứ này đóng vai một phần tuần tự ẩn — như thể s không phải 0 mà là một giá trị dương ngầm định.
Bài học đo lường: Amdahl là một trần lạc quan, không phải dự đoán. Nó cho bạn giới hạn tốt nhất có thể nếu phần song song hoàn hảo; thực tế luôn ở dưới vì overhead thật. Nếu tôi tin "code song song hoàn toàn sẽ đạt 10× trên 10 lõi", tôi đã kỳ vọng gấp đôi cái đo được. Cả Amdahl lẫn phép đo cùng chỉ một hướng: muốn nhanh hơn, hãy giảm phần tuần tự (và chi phí ẩn), đừng chỉ ném thêm lõi.
Một tia sáng: bài toán lớn hơn scale tốt hơn
Amdahl bi quan, nhưng có một góc nhìn bù lại đáng biết. Amdahl giả định kích thước bài toán cố định — bạn có cùng lượng việc, thêm lõi để làm nhanh hơn (gọi là "strong scaling"). Nhưng thực tế người ta thường dùng máy mạnh hơn để giải bài lớn hơn, không phải bài cũ nhanh hơn. Khi bài toán lớn lên, phần song song thường lớn theo (nhiều dữ liệu để chia) trong khi phần tuần tự (khởi tạo, đọc cấu hình) gần như không đổi — nên tỉ lệ s giảm khi bài lớn hơn, và trần Amdahl nới ra. Đây là quan sát của Gustafson: với "weak scaling" (bài lớn theo số lõi), song song vẫn đáng dù Amdahl nói gì cho bài cố định. Bài học kép cho đo lường, đúng tinh thần đo tác động đúng cách: (1) đo speedup ở đúng kích thước bài toán bạn sẽ chạy, vì s phụ thuộc kích thước; và (2) đừng chỉ hỏi "nhanh hơn bao nhiêu với bài này", mà "giải được bài lớn cỡ nào trong cùng thời gian". Cùng một đường cong scaling, hai câu hỏi cho hai kết luận.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: tính phần tuần tự trước khi mơ về nhiều lõi. Trước khi song song hóa, ước lượng s — phần code phải chạy tuần tự. Nếu s là 25%, đừng mong quá 4× dù mua bao nhiêu CPU; tiền mua thêm lõi sau điểm đó là lãng phí. Con số 1/s cho bạn trần lý thuyết; hãy dùng nó để quyết định có đáng song song hóa không.
Hệ quả thứ hai: tối ưu song song thật sự là giảm phần tuần tự, không phải thêm luồng. Nếu bạn đã chạm trần scaling, thêm luồng vô ích; việc đáng làm là tìm và cắt phần tuần tự — song song hóa thêm một bước, hay giảm chi phí ẩn (giảm tranh chấp bộ nhớ, cân bằng tải tốt hơn). Mỗi phần trăm tuần tự cắt được nới trần lên đáng kể.
Hệ quả thứ ba là tinh thần đo lường: đo speedup thật, đừng tin lý thuyết lạc quan. Con số mang theo: speedup song song bị chặn bởi phần tuần tự (Amdahl: trần = 1/s) — s=5% chặn ở 20×, s=25% chặn ở CHỈ 4× (đo được chững ~2,44× trên 10 lõi) dù bao nhiêu lõi; và thực tế còn DƯỚI Amdahl — ngay cả workload s=0 chỉ đạt 5,2× trên 10 lõi vì chi phí ẩn (băng thông, cân bằng, đồng bộ) là một phần tuần tự ẩn; nên tối ưu song song phải nhắm giảm phần tuần tự, không chỉ thêm lõi. Amdahl là trần lạc quan; đo cho bạn hiện thực khắc nghiệt hơn.
Thử ba mươi giây
Ước lượng phần tuần tự của một chương trình bạn định song song hóa: bao nhiêu phần trăm thời gian nằm ở khâu không chia được cho nhiều luồng (đọc/ghi file tuần tự, khởi tạo, tổng hợp cuối, một vùng khóa lớn)? Gọi nó là s, rồi tính 1/s — đó là trần tuyệt đối. Nếu s = 10%, trần là 10× dù bạn có 100 lõi; nếu s = 50%, trần là 2×, và song song hóa gần như không đáng. Ba mươi giây tính nhẩm đó có thể tiết kiệm cho bạn hàng tuần công song song hóa một chương trình mà phần tuần tự sẽ chặn nó lại — và nhắc rằng cách tăng tốc thật là cắt phần tuần tự, không phải đếm lõi.
