Nhiều thuật toán song song chạy theo pha: mọi luồng làm xong bước hiện tại, rồi mới cùng sang bước sau. Mô phỏng vật lý theo bước thời gian, giải phương trình trên lưới lặp, mô hình BSP (Bulk Synchronous Parallel) — tất cả cần một điểm nơi mọi luồng gặp nhau trước khi đi tiếp. Công cụ cho việc đó là barrier (rào đồng bộ): mọi luồng gọi barrier_wait và không luồng nào qua được cho tới khi tất cả đã tới. Nghe đơn giản và vô hại — nhưng tôi đo, và barrier có hai chi phí mà nhiều người xem nhẹ: bản thân nó không rẻ, và nó khuếch đại mọi mất cân bằng tải.
Rào là điểm mọi luồng phải gặp nhau
barrier_wait làm một việc: luồng gọi nó dừng lại cho tới khi đủ N luồng cùng gọi, rồi cả N được thả ra cùng lúc. Để làm được, hầu hết luồng phải ngủ (chờ trong nhân) và được đánh thức khi luồng cuối cùng tới. Nghĩa là mỗi lần qua rào kéo theo việc đưa các luồng vào ngủ và đánh thức lại — chính cái chi phí chuyển ngữ cảnh ~8,5 µs ta đã đo, nhân với số luồng.
Và một tính chất đặc trưng: rào chờ luồng chậm nhất. Vì không ai qua được cho tới khi tất cả tới, thời gian của một pha = thời gian của luồng lâu nhất trong pha đó. Tôi đo cả hai điều này trong container gcc:13 (10 lõi), dùng pthread_barrier_t.
Đo (a): mỗi rào 8 tới 41 µs, tăng theo N
Cho N luồng lặp nhiều lần: làm một việc tí xíu rồi barrier_wait. Đo thời gian trung bình mỗi lần qua rào, với N khác nhau:
N=2 luồng : 8,0 µs / rào
N=4 luồng : 15,7 µs / rào
N=8 luồng : 34,4 µs / rào
N=10 luồng : 41,2 µs / rào
Rào không rẻ, và đắt dần theo số luồng: 8 µs cho 2 luồng, tới 41 µs cho 10 luồng. Con số 8 µs ở N=2 không ngẫu nhiên — nó xấp xỉ một chuyển ngữ cảnh, vì mỗi rào phải đánh thức luồng đang ngủ. Khi N tăng, phải đồng bộ và đánh thức nhiều luồng hơn, nên chi phí tăng gần tuyến tính. Ý nghĩa thực tế: nếu thuật toán của bạn có nhiều pha ngắn, riêng khâu qua rào giữa các pha đã ngốn thời gian đáng kể — mỗi pha trả thêm ~34 µs (ở 8 luồng) chỉ cho việc đồng bộ, bất kể việc thật trong pha lớn hay nhỏ. Đây là lý do "thêm barrier cho chắc" là một ý tồi: mỗi rào thừa là một khoản ~N chuyển ngữ cảnh, serialize các luồng không cần thiết.
Đo (b): một luồng chậm làm cả nhóm chậm
Đây là chi phí quan trọng hơn, và tinh vi hơn. Vì rào chờ luồng chậm nhất, một luồng làm việc nặng hơn các luồng khác sẽ khiến mọi luồng chờ nó — mỗi pha. Tôi đo một tính toán 500 pha, 8 luồng, mỗi pha mỗi luồng làm ~50 µs việc rồi qua rào. So hai trường hợp: cân bằng (mọi luồng ~50 µs) và lệch (luồng 0 làm gấp 4 lần, ~200 µs; bảy luồng kia vẫn 50 µs):
CÂN BẰNG (mọi luồng ~50µs) : 66,5 ms
LỆCH (1 luồng nặng gấp 4) : 116,0 ms -> chậm 1,75×
Chỉ một luồng trong tám làm việc nặng, mà toàn bộ tính toán chậm đi 1,75 lần. Vì sao? Vì mỗi pha, bảy luồng nhẹ xong sau ~50 µs rồi ngồi chờ ở rào, trong khi luồng 0 cày ~200 µs; rào chỉ mở khi luồng 0 xong, nên mỗi pha kéo dài bằng luồng 0 (~200 µs thay vì ~50 µs). Nhân với 500 pha, sự chênh lệch tích lũy thành 50 ms dôi ra. Đây là straggler ở bài cân bằng tải, nhưng lặp lại mỗi pha — barrier khuếch đại tải lệch qua từng vòng, vì mỗi vòng đều phải chờ kẻ chậm nhất. Tổng thời gian = tổng của max mỗi pha, không phải trung bình.
Một lần tôi đo hớ: barrier không rẻ và khuếch đại tải lệch
Tôi vào đo với hai niềm tin. Thứ nhất: "barrier rẻ, chỉ là một lời gọi hàm". Sai — mỗi rào tốn 8 tới 41 µs (đánh thức N luồng), và trong một vòng lặp nhiều pha, chi phí đó cộng dồn đáng kể. Thứ hai, phổ biến hơn: "thêm barrier cho chắc, đồng bộ nhiều thì an toàn". Cũng sai — mỗi rào thừa serialize các luồng (bắt chúng gặp nhau khi không cần) và trả chi phí đánh thức, làm chậm mà không thêm tính đúng.
Nhưng đo hớ sâu nhất là về straggler: tôi tưởng một luồng chậm chỉ ảnh hưởng phần việc của nó, ai ngờ nó kéo cả tính toán chậm theo — vì rào biến "một luồng chậm" thành "mọi luồng chờ". Bài học đo lường: barrier là điểm mọi luồng phải gặp nhau, nên hiệu năng của nó nhạy với luồng chậm nhất, không phải trung bình — và mọi mất cân bằng tải bị nhân lên theo số pha. Nếu tôi tối ưu bằng cách nhìn thời gian trung bình của các luồng, tôi sẽ hoàn toàn bỏ lỡ vì sao thuật toán chậm; phải nhìn kẻ chậm nhất mỗi pha. Đúng tinh thần đo lường vi mô đúng cách, và cùng nguyên lý Amdahl: một phần chậm nhỏ (một luồng, hay một pha) chặn toàn bộ.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: cân bằng tải giữa các luồng trong mỗi pha, vì rào chờ kẻ chậm nhất. Trong tính toán theo pha, việc chia đều khối lượng (không chỉ số phần tử) giữa các luồng quan trọng gấp bội, vì mất cân bằng bị nhân với số pha. Nếu một luồng luôn nặng hơn, cả nghìn pha đều chờ nó. Đo thời gian từng luồng mỗi pha (kẻ chậm nhất), không chỉ tổng, để tìm và cắt straggler.
Hệ quả thứ hai: giảm số rào — gộp pha, đừng thêm rào thừa. Mỗi rào tốn ~N chuyển ngữ cảnh; nếu bạn có nhiều pha rất ngắn, chi phí đồng bộ giữa chúng có thể át việc thật. Cân nhắc gộp nhiều bước nhỏ vào một pha lớn hơn (ít rào hơn), hoặc dùng đồng bộ điểm-điểm thay vì rào toàn cục khi chỉ vài luồng cần gặp nhau. Và tuyệt đối đừng rắc barrier "cho chắc" — mỗi cái là một khoản phí thật.
Hệ quả thứ ba là tinh thần đo lường: đo kẻ chậm nhất, không đo trung bình, ở mọi điểm đồng bộ. Con số mang theo: mỗi barrier KHÔNG rẻ — tốn 8µs (2 luồng) tới 41µs (10 luồng), tăng theo N vì phải đồng bộ + đánh thức N luồng (~N chuyển ngữ cảnh); và rào chờ luồng CHẬM NHẤT mỗi pha nên một luồng nặng (gấp 4, trong 8 luồng) làm CẢ tính toán chậm 1,75× (66,5->116ms qua 500 pha) — tải lệch bị khuếch đại qua từng pha (tổng = tổng MAX mỗi pha). Cân bằng tải để kẻ chậm nhỏ, gộp pha để bớt rào, đừng thêm barrier cho chắc.
Thử ba mươi giây
Nếu bạn có (hoặc đọc) một thuật toán song song chạy theo pha — vòng lặp mà mỗi vòng mọi luồng phải đồng bộ trước khi sang vòng sau — hỏi hai câu. Một: mỗi vòng, các luồng có làm lượng việc xấp xỉ nhau không? Nếu một luồng luôn nặng hơn (xử lý phần dữ liệu lớn hơn, nhánh sâu hơn), thì mỗi vòng cả nhóm chờ nó, và cái chậm đó nhân với số vòng — cân bằng lại tải là đòn tối ưu lớn nhất. Hai: có rào nào không thực sự cần không? Mỗi rào tốn hàng chục µs đánh thức; nếu hai bước liên tiếp không thực sự phụ thuộc toàn cục, có thể bỏ rào giữa chúng. Ba mươi giây soi "kẻ chậm nhất mỗi pha" và "rào nào thừa" đó thường tìm ra vì sao một tính toán theo pha chậm hơn kỳ vọng — và nhắc rằng ở mọi điểm đồng bộ, cái quyết định là luồng chậm nhất, không phải luồng trung bình.
