Rắc parallel for lên vòng tính tổng: chương trình không chậm đi, nó nói dối mất 90%

Hình dung mười tình nguyện viên kiểm một núi phiếu bầu, và có đúng một tờ tổng chung treo trên tường. Cách làm ngây thơ: ai đếm xong một nắm phiếu thì lên bảng, xóa con số cũ, cộng phần mình vào, ghi lại. Thảm họa ngay: hai người cùng đọc "100", mỗi người cộng nắm của mình rồi ghi đè — một trong hai lần cộng bốc hơi. Làm vậy hàng triệu lần, phần lớn số phiếu biến mất, con số cuối ra bé tí so với thực tế. Cách "an toàn" là bắt mỗi người chờ tới lượt độc quyền cầm bút — đúng, nhưng cả nhóm xếp hàng, chậm hơn cả một người làm hết. Cách khôn: mỗi người tự đếm vào tờ giấy riêng, cuối cùng cộng mười tờ lại một lần. Đúng và nhanh. Ba cách kiểm phiếu đó chính là ba cách song song hóa một vòng tính tổng.

Ở 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 — đúng cái tờ tổng chung.

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 (hai người cùng ghi đè tờ tổng). 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 (chỉ một người được cầm bút mỗi lúc). 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ể). Đúng "mỗi người một tờ giấy riêng, cuối cùng cộng mười tờ". 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ôi trường đo: container gcc:13 trên host ARM AArch64, 10 lõi, -O2 -fopenmp, tổng mảng 20 triệu phần tử, đối chiếu với tổng tuần tự đúng 139.999.979. Con số tuyệt đối đổi theo máy; điều bền vững: naive sai, atomic đúng-mà-chậm-vì-tranh-chấp, reduction đúng-và-nhanh.)

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

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. Và niềm tin đối nghịch — "thấy race thì cứ atomic là sửa xong" — cũng sai: atomic đúng nhưng biến song song thành chậm hơn cả tuần tự 75 lần vì tranh chấp điểm ghi chung.

Điều làm tôi giật mình khi đo: cái sai naive 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.

Hai niềm tin gặp nhau ở một bài học: 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. 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, đúng tinh thần đo lường vi mô đúng cách.

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

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

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

Chỗ này cái khuôn "gộp cục bộ rồi hợp" là một trong những mẫu nền tảng nhất của tính toán, và nhận ra nó giúp bạn dùng đúng API ở mọi ngôn ngữ. Java Stream reduce() (và sum(), Collectors) bắt buộc phép gộp phải kết hợp được (associative) kèm một combiner — chính là để runtime tự chia cục bộ rồi hợp an toàn khi bạn gọi parallelStream(); và cái bẫy kinh điển là dùng forEach cộng dồn vào một biến chung trong parallel stream (đúng naive race ở trên) thay vì reduce — tài liệu Java cảnh báo thẳng điều này. LongAdder cũng là reduction của một biến đếm (mảng ô per-thread, sum() gộp cuối). Ở tầng dữ liệu lớn, chữ "Reduce" trong MapReduce nghĩa đen là bước này: mỗi mapper sinh tổng cục bộ (partial), reducer gộp lại — và Spark aggregate/treeReduce đòi hàm kết hợp vì lý do y hệt. Gần gũi hơn: mọi SELECT SUM(x) ... GROUP BY trong SQL là một reduction mà database tự song song hóa an toàn cho bạn (tính tổng cục bộ mỗi phân vùng rồi gộp) — bạn được hưởng đúng mẫu này mà không phải nghĩ. Mẫu số chung: gộp song song đúng luôn là "mỗi worker một tổng riêng, hợp một lần cuối", và mọi API gộp tử tế đều xây quanh tính kết hợp để làm được điều đó.

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