Ở bài OpenMP ta thấy #pragma omp parallel for biến một vòng lặp thành song song chỉ với một dòng — và với vòng các lần lặp độc lập thì nó đúng và nhanh. Nhưng có một lớp vòng lặp cực kỳ phổ biến mà "rắc pragma lên là xong" phản bội bạn theo cách tệ nhất có thể: không phải chậm, mà sai kết quả một cách thầm lặng. Đó là reduction — gộp nhiều giá trị thành một (tổng, tích, max, min). Tôi đo, và con số cho thấy vì sao reduction cần một cơ chế riêng, không phải một pragma bừa.
Vòng gộp có phụ thuộc ẩn
Xét vòng lặp quen thuộc nhất đời: tính tổng một mảng.
long sum = 0;
for (long i = 0; i < N; i++)
sum += a[i];
Nhìn thì giống một vòng for bình thường, nhưng nó có một điểm khác cốt tử so với vòng out[i] = f(in[i]): mọi lần lặp đọc và ghi cùng một biến sum. Lần lặp i cần giá trị sum mà lần i-1 vừa để lại. Đây là một phụ thuộc mang theo (loop-carried dependency): các lần lặp không độc lập, chúng nối tiếp nhau qua biến tích lũy.
Song song hóa nghĩa là chạy các lần lặp đồng thời trên nhiều lõi. Nhưng nếu các lần lặp phải nối tiếp qua sum, chạy đồng thời sẽ khiến chúng giẫm lên nhau. Câu hỏi tôi mang đi đo: điều gì thực sự xảy ra khi bạn phớt lờ phụ thuộc này và cứ #pragma omp parallel for? Và cách đúng để gộp song song là gì?
Tôi đo trong container gcc:13 (10 lõi, -O2 -fopenmp), tổng một mảng 20 triệu phần tử, giá trị nhỏ để tổng đúng tính được chính xác (139.999.979). Ba cách gộp, cùng so với tổng tuần tự đúng.
Đo (a): naive parallel cho kết quả SAI
Cách thứ nhất — rắc pragma thẳng lên, không nghĩ:
long sum = 0;
#pragma omp parallel for
for (long i = 0; i < N; i++)
sum += a[i]; // 10 luồng cùng đọc-ghi sum
Kết quả đo:
đúng (tuần tự) : 139.999.979
naive (10 luồng) : 14.000.005 -> SAI, mất 90%! (2,6 ms)
Không phải lệch một chút — mất 90% tổng. Tổng đúng là 140 triệu, chương trình song song trả về 14 triệu. Vì sao? sum += a[i] không phải một thao tác nguyên tử — nó là đọc sum, cộng, ghi lại sum. Khi 10 luồng cùng làm, luồng A đọc sum=100, luồng B cũng đọc sum=100, cả hai cộng phần của mình rồi ghi đè — một trong hai cập nhật biến mất. Với 10 luồng giẫm lên nhau hàng triệu lần, phần lớn cập nhật bị mất, chỉ còn lại đại khái phần của một luồng — nên ra ~1/10 tổng. Đây đúng là đua tranh đọc-sửa-ghi mà bài atomic đã mổ xẻ, nhưng lần này hậu quả không phải một con số lệch nhỏ — nó phá hủy 90% kết quả.
Điều nguy hiểm nhất: nó nhanh (2,6 ms) và không có lỗi nào báo. Chương trình chạy trơn tru, trả về một con số trông hợp lệ, chỉ có điều con số đó sai. Nếu bạn không có giá trị đúng để đối chiếu, bạn sẽ không bao giờ biết. Đây là loại bug tệ nhất trong song song: không sập, không chậm, chỉ âm thầm cho đáp án sai.
Đo (b): atomic đúng, nhưng chậm 267 lần
Cách thứ hai — sửa cho đúng bằng cách khóa từng cập nhật:
#pragma omp parallel for
for (long i = 0; i < N; i++) {
#pragma omp atomic
sum += a[i]; // mỗi cộng là một atomic add
}
#pragma omp atomic biến mỗi sum += a[i] thành một phép cộng nguyên tử — không cập nhật nào bị mất nữa. Kết quả đo:
atomic (10 luồng) : 139.999.979 -> ĐÚNG, nhưng 652 ms
reduction : 139.999.979 -> ĐÚNG, 2,4 ms
atomic / reduction : chậm 267 lần
Atomic cho đúng kết quả — nhưng mất 652 ms, chậm hơn reduction 267 lần, và thậm chí chậm hơn cả tổng tuần tự (8,6 ms) tới 75 lần! Vì bây giờ cả 10 luồng tranh nhau ghi vào đúng một biến sum — mỗi phép cộng phải giành quyền độc quyền lên dòng cache chứa sum, và dòng cache đó nảy qua nảy lại giữa các lõi 20 triệu lần. Bạn đã "song song hóa" nhưng thực chất biến nó thành tuần tự có thêm chi phí đồng bộ — tệ hơn cả không song song. Đây là bài học contention ở dạng thuần khiết nhất: chia sẻ một điểm ghi nóng giết chết mọi lợi ích song song.
Đo (c): reduction — đúng và nhanh
Cách thứ ba, và là cách đúng — reduction:
#pragma omp parallel for reduction(+:sum)
for (long i = 0; i < N; i++)
sum += a[i];
Mệnh đề reduction(+:sum) nói với trình biên dịch: mỗi luồng giữ một bản sum riêng (khởi tạo 0), cộng dồn phần việc của nó vào bản cục bộ đó — hoàn toàn không tranh chấp với luồng khác — rồi cuối cùng gộp 10 bản cục bộ thành một (10 phép cộng, không đáng kể). Kết quả: 139.999.979, đúng, chỉ 2,4 ms — đúng như tuần tự nhưng nhanh hơn 3,6 lần, và nhanh hơn atomic 267 lần.
Vì sao reduction thắng đậm? Nó loại bỏ điểm ghi chung. Trong suốt vòng lặp, mỗi luồng chỉ chạm biến cục bộ của mình (nằm trong cache riêng, không ai tranh) — đây là chính nguyên tắc "giảm chia sẻ ghi" xuyên suốt sê-ri. Việc gộp cuối chỉ xảy ra một lần cho mỗi luồng, không phải mỗi phần tử. So với atomic (đồng bộ mỗi phần tử), reduction đồng bộ mỗi luồng — ít hơn hàng triệu lần.
Và reduction có scale. Với việc nặng hơn mỗi phần tử, tôi đo speedup của reduction theo số luồng:
1 luồng : 110 ms 1,00×
4 luồng : 28 ms 3,88×
8 luồng : 22 ms 5,04×
10 luồng : 24 ms 4,57×
Speedup thật (5,04× ở 8 luồng), dưới tuyến tính vì định luật Amdahl và chi phí ẩn ta đã đo — nhưng đây là speedup thật trên kết quả đúng, không phải tốc độ giả trên đáp án sai.
Một lần tôi đo hớ: "song song hóa được" không bằng "rắc pragma"
Tôi vào đo với niềm tin của người vừa học OpenMP: "mọi vòng for chỉ cần thêm #pragma omp parallel for là song song hóa được". Với vòng độc lập thì đúng. Nhưng với vòng gộp (reduction), niềm tin đó vỡ theo cách tệ nhất: không phải chậm đi, mà cho kết quả SAI — tổng ra 14 triệu thay vì 140 triệu, mất 90%, mà không một lỗi nào báo.
Điều làm tôi giật mình khi đo: cái sai này nhanh và im lặng. Nếu bug làm chương trình sập hay chậm, bạn sẽ chú ý. Nhưng một tổng sai trả về trong 2,6 ms trông y hệt một tổng đúng — chỉ khác giá trị. Tôi chỉ bắt được vì có tổng tuần tự để đối chiếu; trong một hệ thực không có "đáp án đúng" sẵn, bug này lọt qua mọi bài test chạy một luồng và chỉ hỏng ở production đa luồng.
Bài học đo lường: song song không phải phép biến đổi giữ-nguyên-ngữ-nghĩa; với vòng có phụ thuộc mang theo, chạy song song đổi kết quả. Phải nhận ra phụ thuộc trước, rồi chọn cơ chế đúng. Và tôi đo được luôn cả cái bẫy thứ hai: sửa bằng atomic thì đúng nhưng biến song song thành chậm hơn cả tuần tự (267 lần so với reduction) vì tranh chấp điểm ghi chung. reduction không phải cú pháp trang trí cho gọn — nó là cách đúng về nghĩa và đúng về hiệu năng để gộp: mỗi luồng gộp cục bộ, rồi gộp các cục bộ. Ba con số — sai/chậm/đúng — chỉ hiện ra khi đo cả ba cách cạnh nhau.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: trước khi song song hóa một vòng, hỏi "các lần lặp có độc lập không?" Nếu vòng tích lũy vào một biến chung (tổng, đếm, max, nối chuỗi, gộp vào một tập), đó là reduction — không được rắc parallel for trần. Kiểm phụ thuộc là bước bắt buộc, không phải tùy chọn; bỏ qua nó không cho lỗi, chỉ cho đáp án sai.
Hệ quả thứ hai: dùng đúng công cụ gộp — reduction, không phải atomic. Khi đã nhận ra một reduction, dùng reduction(+:x) của OpenMP (hay std::reduce, hay tự gộp per-thread partial rồi cộng cuối). Đừng "sửa" race bằng cách khóa/atomic mỗi phần tử — nó đúng nhưng biến song song thành tuần tự đắt đỏ (đo được: chậm 267 lần). Nguyên tắc chung: giảm số lần đồng bộ (mỗi luồng một lần) thay vì đồng bộ mỗi phần tử.
Hệ quả thứ ba là tinh thần đo lường, đúng như đo lường vi mô đúng cách nhắc: với code đồng thời, "chạy ra số" không bằng "chạy ra số đúng" — luôn đối chiếu với đáp án tuần tự. Con số mang theo: rắc #pragma omp parallel for lên vòng GỘP (sum += a[i]) cho kết quả SAI — 14 triệu thay vì 140 triệu, mất 90% cập nhật do đua tranh đọc-ghi biến chung, không phải chậm mà SAI thầm lặng; sửa bằng atomic thì ĐÚNG nhưng tranh chấp điểm ghi chung làm chậm 267 lần (còn chậm hơn tuần tự); reduction(+:sum) — mỗi luồng cộng cục bộ rồi gộp cuối — vừa ĐÚNG vừa NHANH (2,4 ms, scale 5× ở 8 luồng). Nhận ra phụ thuộc mang theo TRƯỚC khi song song.
Thử ba mươi giây
Nhìn vòng lặp song song gần nhất của bạn (hay một vòng bạn định parallel for) và hỏi: nó có ghi vào một biến dùng chung giữa các lần lặp không? Một biến total, count, max, một list bạn append vào, một map bạn cập nhật. Nếu có, đó là reduction — và rắc parallel for trần lên nó sẽ cho kết quả sai (đua tranh), không phải chỉ chậm. Thử một thí nghiệm nếu có OpenMP: tính tổng một mảng lớn bằng #pragma omp parallel for không có reduction, rồi so với tổng tuần tự — bạn sẽ thấy con số song song nhỏ hơn hẳn, và khác nhau mỗi lần chạy. Thêm reduction(+:sum) và cả hai khớp lại. Ba mươi giây đó dạy bạn cái phản xạ quan trọng nhất của lập trình song song: kiểm phụ thuộc trước khi song song — vì với vòng gộp, song song hóa sai không làm chương trình chậm, nó làm chương trình nói dối.
