25% code chạy tuần tự thì 1000 lõi cũng chỉ nhanh 4 lần: định luật Amdahl

Hình dung buổi sáng đi làm của bạn gồm hai phần: hai mươi phút ngồi tàu điện (giờ tàu cố định, bạn không cách nào làm nhanh hơn) cộng với quãng đi bộ ra ga và từ ga tới công ty (phần bạn kiểm soát được — có thể chạy, đạp xe, hay đi xe máy cho nhanh). Bây giờ bạn quyết tâm rút ngắn buổi sáng: bạn mua xe, phóng như bay, thậm chí tưởng tượng dịch chuyển tức thời cả quãng đi bộ về 0. Kết quả? Buổi sáng vẫn không bao giờ ngắn hơn hai mươi phút — vì cái phần tàu điện cố định đó là sàn không thể phá. Nếu tàu chiếm 25% tổng thời gian, thì dù đi bộ nhanh vô hạn, bạn nhiều lắm chỉ rút ngắn được xuống 1/4 — nhanh gấp 4 lần, hết. Đó chính là định luật Amdahl, và nó bi quan hơn nhiều người tưởng.

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à như buổi sáng kia, nó khắc nghiệt. 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ự (chuyến tàu cố định). 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ôi trường đo: container gcc:13 trên host ARM AArch64, 10 lõi, workload dựng phần tuần tự s cố định + phần song song chia N. Con số tuyệt đối đổi theo máy; điều bền vững là hình dạng: speedup bão hòa quanh trần 1/s, và thực tế nằm dưới đường Amdahl lý thuyết.)

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. Giống buổi sáng: nếu bạn đi một chuyến xa hơn nhiều (quãng đi bộ dài gấp bội) mà vẫn chỉ hai mươi phút tàu, thì cái tàu cố định giờ chỉ chiếm một phần nhỏ, và tăng tốc quãng đi bộ lại đáng giá. Đâ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, đú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.

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

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 lật 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.

Hai niềm tin gặp nhau ở một sự thật: 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 — như muốn buổi sáng ngắn hơn thì phải làm gì đó với chuyến tàu, chứ không phải chạy nhanh hơn nữa trên quãng đi bộ vốn đã nhanh.

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

Điều đầ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.

Điều 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ể.

Chỗ này Amdahl leo thẳng từ đa lõi lên tận kiến trúc phân tán, và đó là nơi nó tốn tiền thật. Khi bạn scale ngang một hệ (thêm máy chủ, thêm node), cùng định luật áp dụng: nếu còn một điểm tuần tự dùng chung — một database ghi qua một primary duy nhất, một dịch vụ điều phối một-leader, một khóa toàn cục, một bước shuffle/reduce phải gom về một chỗ — thì phần đó chạy ở tốc độ một node dù cụm có trăm máy, và nó chặn thông lượng cả cụm đúng như chuyến tàu chặn buổi sáng. Đây là lý do dân phân tán ám ảnh với việc xóa điểm serial: sharding để không có primary đơn, thiết kế không-chia-sẻ (shared-nothing), tránh coordinator toàn cục. Và có một mở rộng đáng sợ hơn Amdahl: Universal Scalability Law (USL) thêm một số hạng cho chi phí coherence/đồng bộ giữa các node — nó nói speedup không chỉ bão hòa mà còn có thể giảm khi thêm node quá điểm tối ưu (đúng cái scale âm ta đã đo), vì cái giá "mọi người nói chuyện với mọi người" tăng theo bình phương. Mẫu số chung, từ 10 lõi tới 1000 máy: thứ quyết định bạn scale được tới đâu là phần không chia được, và tối ưu nghĩa là săn lùng rồi cắt nó — không phải mua thêm phần cứng.

Muốn tự soi thì ướ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. Vài phút 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.