Ở bài work stealing ta thấy tải không biết trước cần cân bằng động. Nhưng ngay cả tải biết trước cũng có một cái bẫy: bạn chia đều số phần tử cho mỗi lõi, tưởng thế là công bằng — rồi phát hiện chương trình vẫn chậm như thể chỉ dùng một hai lõi. Vì "chia đều số phần tử" không bằng "chia đều khối lượng việc" khi mỗi phần tử tốn khác nhau. Tôi đo hiện tượng này bằng OpenMP, và con số cho thấy một luồng có thể làm gấp hai mươi lần luồng khác dù nhận đúng bằng số phần tử.
Tải lệch và kẻ tụt hậu
Nhiều vòng lặp thực có tải lệch: mỗi lần lặp tốn một lượng công khác nhau. Duyệt một cây không cân bằng, xử lý các file kích thước khác nhau, một vòng lồng mà số lần lặp trong phụ thuộc chỉ số ngoài. Tôi mô phỏng trường hợp kinh điển nhất — tải tam giác: việc của phần tử i tỉ lệ thuận với i. Phần tử 0 gần như không tốn gì; phần tử cuối tốn nhiều nhất. Tổng việc là một tam giác.
Bây giờ chia vòng M phần tử cho 10 luồng theo cách mặc định của #pragma omp parallel for: chia khối (schedule(static)) — mỗi luồng nhận một dải index liền nhau. Luồng 0 nhận [0, M/10) (toàn phần tử nhẹ), luồng 9 nhận [9M/10, M) (toàn phần tử nặng). Mỗi luồng nhận đúng bằng số phần tử — M/10 cái — nhưng khối lượng việc thì chênh lệch khủng khiếp. Luồng 9 làm gấp nhiều lần luồng 0.
Điều then chốt: khi các luồng chạy song song và có một rào đồng bộ ở cuối (join, barrier), tổng thời gian bằng thời gian của luồng chậm nhất, không phải trung bình. Luồng nhanh xong sớm rồi ngồi không chờ. Cái luồng chậm nhất đó — kẻ tụt hậu, straggler — một mình quyết định bạn phải chờ bao lâu. Tôi đo trong container gcc:13 (10 lõi, -O2 -fopenmp), tải tam giác M = 40.000, và đo thời gian làm việc thật của từng luồng để phơi bày mất cân bằng.
Đo: một luồng làm 21,7 lần luồng khác
Với chia khối, thời gian làm việc thật của mỗi luồng (đo bằng cách cho mỗi luồng tự bấm giờ phần của nó, không đợi ở rào):
Thời gian từng luồng (chia khối, ms):
5 24 38 57 72 87 87 99 115 117
^luồng 0 (index nhẹ) luồng 9 (index nặng)^
luồng nhanh nhất : 5 ms
luồng chậm nhất : 117 ms -> lệch 21,7 lần
trung bình : 70 ms
tổng thời gian : 127 ms (= luồng chậm nhất, KHÔNG phải 70)
Luồng 0 làm xong phần của nó trong 5 ms rồi ngồi chờ 112 ms. Luồng 9 cày 117 ms. Cùng số phần tử, nhưng lệch 21,7 lần về thời gian. Và tổng thời gian tường (127 ms) bằng đúng luồng chậm nhất — cả 9 luồng kia đóng góp không làm nó nhanh hơn được một mili giây nào sau khi chúng đã xong. Đây là kẻ tụt hậu quyết định tất cả: bạn có 10 lõi, nhưng ở đoạn cuối chỉ 1 lõi còn chạy trong khi 9 lõi rảnh rỗi. Hiệu suất thực tế gần với dùng một hai lõi hơn là mười.
Đáng chú ý: con số trung bình (70 ms) nói dối. Nếu bạn chỉ đo thời gian trung bình mỗi luồng và nghĩ "à mỗi luồng làm 70 ms", bạn sẽ ngạc nhiên khi tổng lại là 127 ms. Với song song, số đo đúng là MAX, không phải AVG — vì rào đồng bộ bắt cả nhóm chờ kẻ chậm nhất.
Đo: chia xen kẽ san tam giác gần như miễn phí
Cách sửa rẻ nhất cho tải tam giác: đừng cho một luồng một dải liền, mà rải xen kẽ — luồng 0 lấy phần tử 0, 10, 20, ...; luồng 1 lấy 1, 11, 21, ...; vòng tròn. Trong OpenMP đây là schedule(static, 1) (cyclic). Mỗi luồng bây giờ nhận một hỗn hợp index nhẹ và nặng đều nhau, nên khối lượng việc cân bằng. Đo:
wall lệch luồng so chia khối
chia khối : 127 ms 21,7×
chia xen kẽ : 91 ms 1,1× -> nhanh 1,40×
dynamic : 84 ms ~1× -> nhanh 1,52×
guided : 83 ms ~1× -> nhanh 1,53×
Chia xen kẽ đưa độ lệch giữa các luồng từ 21,7× xuống 1,1× — gần như cân bằng hoàn hảo — và tổng thời gian giảm từ 127 xuống 91 ms, nhanh 1,40×. Điều đẹp nhất: nó tĩnh, không tốn phí điều phối lúc chạy — trình biên dịch chia index theo công thức, mỗi luồng biết ngay phần của mình. Với tải có cấu trúc dự đoán được (như tam giác), chia xen kẽ là bữa trưa miễn phí.
Hai lựa chọn còn lại — dynamic và guided — nhanh hơn chút nữa (1,52×). Chúng phát lô động: luồng nào xong lô thì xin lô tiếp, nên cân bằng mọi kiểu tải, kể cả tải lệch bất quy tắc mà chia xen kẽ không đoán được. Đổi lại chúng tốn một chút phí điều phối (giành hàng đợi lô chung — đúng cái chi phí đồng bộ ta đã đo). Ở đây tải tam giác có cấu trúc, nên chia xen kẽ tĩnh (không phí) đã gần bằng dynamic; với tải hỗn loạn hơn, dynamic sẽ bỏ xa xen kẽ.
Một lần tôi đo hớ (hai lần): index đều ≠ việc đều, và MAX ≠ AVG
Tôi vào đo với niềm tin trực giác: "chia đều số phần tử cho mỗi lõi là cân bằng tải rồi". Sai — khi mỗi phần tử tốn khác nhau, chia đều số index không bằng chia đều khối lượng việc. Chia khối cho tải tam giác khiến một luồng làm 117 ms còn luồng khác 5 ms, lệch 21,7 lần, và tổng thời gian kẹt ở kẻ chậm nhất. Chia đều đầu việc không phải chia đều sức nặng.
Nhưng tôi còn vấp một đo hớ thứ hai ngay trong lúc đo — và nó đáng kể lại. Lần đầu tôi đo thời gian mỗi luồng bên trong vùng omp for bình thường. Kết quả ra "lệch 1,0×" cho cả chia khối lẫn chia xen kẽ — như thể không có mất cân bằng nào! Tôi suýt kết luận sai rằng chia khối cân bằng tốt. Lý do: omp for có một rào ngầm ở cuối — mọi luồng chờ nhau ở đó, nên đồng hồ của luồng nhanh cũng chạy tới khi luồng chậm xong, và tất cả báo cùng một thời gian. Cái rào che mất kẻ tụt hậu. Chỉ khi thêm nowait (bỏ rào, mỗi luồng bấm giờ đúng phần việc của nó) thì lệch 21,7× mới lộ ra.
Bài học đo lường kép: (1) cân bằng tải là chia đều việc, không phải chia đều đầu mục — và (2) đo song song phải nhìn đúng đại lượng: tổng thời gian là MAX của các luồng, không phải AVG, và công cụ đo của bạn (cái rào ngầm) có thể che chính hiện tượng bạn muốn thấy. Nếu tin con số trung bình hay con số bị rào làm phẳng, tôi đã kết luận "mọi thứ cân bằng" trong khi thực tế một lõi gánh tất cả. Đúng như tinh thần đo lường vi mô đúng cách: phải hiểu công cụ đo đang đo cái gì trước khi tin nó.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: khi tải lệch, đừng chia khối — chọn cách chia hợp với hình dạng tải. Nếu tải có cấu trúc dự đoán được (tăng dần, giảm dần), chia xen kẽ (schedule(static,1)) san nó gần như miễn phí. Nếu tải bất quy tắc hay không biết trước, dùng dynamic/guided (hay work stealing) để san động, chấp nhận chút phí điều phối. Mặc định chia khối chỉ tối ưu khi tải đều — điều bạn phải kiểm, không mặc định.
Hệ quả thứ hai: đo bằng MAX, không phải AVG, và coi chừng kẻ tụt hậu. Trong mọi hệ song song có điểm đồng bộ (barrier, join, một bước gộp cuối), tổng thời gian do luồng chậm nhất quyết định. Một luồng lệch tải làm cả nhóm chờ — cùng nguyên lý với định luật Amdahl: một phần "chậm" nhỏ chặn toàn bộ. Khi tối ưu, hãy tìm và cắt kẻ tụt hậu, đừng nhìn con số trung bình dễ chịu.
Hệ quả thứ ba là tinh thần đo lường: hiểu công cụ đo trước khi tin số nó cho. Con số mang theo: chia đều số phần tử KHÔNG bằng cân bằng tải khi mỗi phần tử tốn khác nhau — tải tam giác chia khối làm luồng ôm index lớn thành straggler (117ms so 5ms, lệch 21,7×), tổng thời gian = luồng CHẬM NHẤT (127ms) chứ không phải trung bình (70ms); chia xen kẽ (cyclic) san tam giác gần miễn phí (lệch 1,1×, nhanh 1,40×), dynamic/guided san mọi tải (1,52×). Cân bằng = chia đều VIỆC, đo bằng MAX; và coi chừng rào ngầm che mất mất cân bằng khi đo per-thread (phải nowait).
Thử ba mươi giây
Nghĩ về một vòng lặp song song bạn có mà mỗi lần lặp tốn khác nhau — duyệt các nhánh cây độ sâu khác nhau, nén các file cỡ khác nhau, một vòng lồng for i { for j<i {...} }. Nếu bạn chia nó cho N luồng theo dải liền (luồng 0 lấy phần đầu, luồng N-1 lấy phần cuối), hỏi: phần của luồng nào nặng nhất? Với tải tăng dần, luồng cuối ôm hết việc nặng, các luồng đầu xong sớm ngồi chơi, và bạn chờ đúng luồng cuối — dùng N lõi mà nhanh như dùng một hai. Thử đổi sang chia xen kẽ (schedule(static,1) trong OpenMP, hay i += N thủ công) và đo lại: bạn rất có thể thấy nhanh lên đáng kể mà không đổi một dòng logic. Ba mươi giây hình dung ai là kẻ tụt hậu đó dạy bạn phản xạ quan trọng nhất của cân bằng tải — đo bằng luồng chậm nhất, và chia đều việc chứ không phải đếm đầu phần tử.
