Máy nào giờ cũng nhiều lõi — con máy đo bài này có 10. Trực giác nói: chia việc ra 10 phần, chạy trên 10 lõi, xong nhanh gấp 10. Đẹp trên giấy, nhưng gần như không bao giờ đạt trên đồng hồ. Bài này đo tăng tốc thật khi tăng số luồng, cho ba loại công việc khác nhau, và đối chiếu với luật Amdahl — công thức nói trước cho ta cái trần mà mọi nỗ lực thêm lõi sẽ đụng phải.
Luật Amdahl: phần tuần tự đặt trần
Ý tưởng của luật Amdahl đơn giản mà sắc. Chia công việc thành hai phần: một phần song song hóa được (tỉ lệ p) mà N lõi cùng làm, và một phần buộc tuần tự (tỉ lệ 1−p) mà chỉ một lõi làm được — khởi tạo, đọc đầu vào theo thứ tự, gộp kết quả cuối, những đoạn phụ thuộc lẫn nhau. Với N lõi, tăng tốc tối đa là:
tăng tốc = 1 / ( (1-p) + p/N )
Cho N tiến tới rất lớn, số hạng p/N teo về 0, và tăng tốc chặn ở 1/(1−p). Nghĩa là: nếu chỉ 10% công việc buộc tuần tự (p = 0,9), thì dù bạn có một triệu lõi, tăng tốc tối đa cũng chỉ là 1/0,1 = 10 lần. Phần tuần tự — dù nhỏ — đặt một cái trần cứng mà không lượng lõi nào vượt qua. Đó là lý thuyết; giờ đo xem thực tế bám nó tới đâu, và nó còn tệ hơn vì những lý do gì.
Đo: ngay cả việc song song thuần cũng không đạt N
Trước hết đo trường hợp đẹp nhất: một công việc song song thuần (embarrassingly parallel) — mỗi luồng làm một khối tính toán nặng thuần CPU (trộn số, không đụng bộ nhớ chung, không đồng bộ gì). Đây là p ≈ 1, lẽ ra tăng tốc gần bằng N. Chia 4 tỉ bước tính cho 1, 2, 4, 8, 10 luồng:
Song song thuần (CPU-bound), nproc = 10:
1 luồng: 5.492 ms -> 1,00x
2 luồng: 2.780 ms -> 1,98x
4 luồng: 1.544 ms -> 3,56x
8 luồng: 846 ms -> 6,49x
10 luồng: 745 ms -> 7,38x (không phải 10x)
Ở 2 luồng gần như hoàn hảo (1,98x), nhưng càng thêm lõi càng hụt: 10 luồng chỉ đạt 7,38x, không phải 10. Mà đây là công việc không có phần tuần tự nào đáng kể, không chia sẻ dữ liệu, không đồng bộ. Cái hụt đến từ những chi phí thực mà luật Amdahl trần trụi bỏ qua: tạo và lập lịch luồng, hệ điều hành xen kẽ, các lõi chia sẻ tài nguyên vật lý (bộ nhớ đệm cấp cuối, đường truyền), và đây là 10 vCPU ảo hóa trên một máy chủ chung. Bài học đầu: ngay cả song song lý tưởng cũng không đạt N — phần cứng và hệ điều hành lấy phần chênh.
Đo: 10% tuần tự, tăng tốc tụt về Amdahl
Giờ thêm một phần tuần tự thật. Cùng khối lượng tính, nhưng 10% chạy trên một luồng trước, 90% còn lại chia cho N luồng (p = 0,9). Đối chiếu tăng tốc đo được với công thức Amdahl:
10% tuần tự + 90% song song (p = 0,9), nproc = 10:
luồng | đo được | Amdahl lý thuyết
2 | 1,80x | 1,82x
4 | 2,84x | 3,08x
8 | 4,19x | 4,71x
10 | 4,53x | 5,26x (trần khi N rất lớn = 10x)
Hai điều đáng chú ý. Thứ nhất, đường đo bám sát đường Amdahl (hơi thấp hơn vì cộng thêm các chi phí thật ở phần trước) — luật Amdahl không phải lý thuyết suông, nó tiên đoán đúng hình dạng thực tế. Thứ hai, chỉ 10% tuần tự đã kéo tăng tốc 10 luồng từ 7,38x (khi gần như toàn song song) xuống còn 4,53x. Một phần mười công việc không chịu song song hóa đã cắt hơn một nửa lợi ích của mười lõi. Và dù thêm bao nhiêu lõi nữa, trần lý thuyết vẫn chỉ là 10x. Đây là điều làm nhiều người bất ngờ: cái phần tuần tự nhỏ bé bạn xem thường mới là thứ quyết định trần.
Đo hớ: có việc thêm lõi gần như vô ích
Trước khi đo, tôi tưởng cứ tránh phần tuần tự thì tăng tốc sẽ tốt. Nhưng có một kẻ chặn thứ ba không nằm trong công thức Amdahl, và tôi gặp nó khi đo một công việc song song thuần về mặt logic nhưng nghẽn băng thông bộ nhớ: cộng tổng một mảng 400 MB, chia đều cho các luồng. Mỗi luồng làm việc trên phần riêng, không chia sẻ, không đồng bộ — tưởng phải scale gần tuyến tính như phần (A). Đo ra:
Nghẽn băng thông bộ nhớ (tổng mảng 400 MB), nproc = 10:
2 luồng: 1,95x
4 luồng: 2,33x
8 luồng: 3,19x
10 luồng: 3,28x
Chỉ 3,28x với 10 luồng — tệ hơn cả trường hợp 10% tuần tự! Vậy mà chẳng có dòng nào tuần tự cả. Lý do: công việc này không nghẽn ở CPU mà nghẽn ở băng thông bộ nhớ. Cộng một mảng khổng lồ chủ yếu là chờ dữ liệu từ RAM về, và tất cả các lõi tranh nhau cùng một bus nhớ. Thêm lõi không thêm băng thông; 10 lõi cùng khát dữ liệu vẫn phải xếp hàng qua đúng một đường ống. Đây là điều mà bài mảng và cache đã chạm tới: có những công việc bị chặn bởi bộ nhớ chứ không phải bộ tính, và với chúng, thêm lõi gần như vô ích. Đo hớ của tôi là đã tưởng "không có phần tuần tự thì scale tốt" — quên rằng băng thông bộ nhớ là một tài nguyên chung, và tranh chấp nó cũng đặt trần y như phần tuần tự vậy.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: trước khi thêm luồng, tìm và đo phần tuần tự. Một chương trình có 5% việc tuần tự có trần tăng tốc 20x, 20% thì trần chỉ 5x — bất kể máy chủ 64 lõi. Nên chỗ đáng đầu tư thường không phải "thêm lõi" mà "thu nhỏ phần tuần tự": song song hóa nốt đoạn khởi tạo, gộp kết quả theo cây thay vì tuần tự, bỏ những điểm đồng bộ toàn cục. Một phần trăm tuần tự cắt bớt đáng giá hơn một lõi thêm vào khi bạn đã ở gần trần.
Hệ quả thứ hai: hỏi công việc nghẽn ở đâu — CPU hay bộ nhớ — trước khi kỳ vọng scale. Việc nặng tính toán (mã hóa, nén, tính SIMD, mô phỏng) thường scale khá theo lõi. Việc chủ yếu di chuyển dữ liệu (quét mảng lớn, sao chép, cộng tổng) nghẽn băng thông và scale rất kém — với chúng, đổi thuật toán để chạm bộ nhớ ít đi (dữ liệu gọn hơn, bố cục thân thiện cache) đáng giá hơn thêm lõi nhiều. Đo IPC hay đơn giản là đo tăng tốc theo luồng sẽ cho biết bạn đang ở loại nào.
Hệ quả thứ ba là bài học đo lường bao trùm: "nhanh gấp N lần" là một lời hứa lý thuyết; cái trần thật thấp hơn nhiều và phải đo mới biết ở đâu. Con số mang theo: trên 10 lõi, công việc song song thuần nhất chỉ đạt 7,38x (chi phí luồng + tài nguyên chung); thêm 10% việc tuần tự tụt còn 4,53x đúng như Amdahl tiên đoán (trần lý thuyết 10x); và việc nghẽn băng thông bộ nhớ chỉ 3,28x vì mọi lõi tranh một bus. Ba cái trần — phần tuần tự, chi phí đồng bộ, băng thông bộ nhớ — cùng kéo tăng tốc xuống dưới N. Trước khi mua thêm lõi (hay thuê thêm máy), hãy đo tăng tốc theo số luồng và tìm xem trần của bạn nằm ở đâu; thường nó gần hơn bạn nghĩ.
Thử ba mươi giây
Lấy một tác vụ bạn hay chạy song song — nén một thư mục với tar | xz -T0, build một dự án với make -jN, hay bất cứ công cụ nào nhận cờ số luồng. Chạy nó với 1 luồng, đo thời gian; rồi 2, 4, 8 luồng, đo lại mỗi lần. Vẽ tăng tốc (thời-gian-1-luồng chia thời-gian-N-luồng) theo số luồng: bạn gần như chắc chắn thấy đường cong cong xuống, phẳng dần, chứ không phải đường thẳng lên. Điểm nó bắt đầu phẳng chính là lúc phần tuần tự (hoặc băng thông, hoặc I/O đĩa) của tác vụ đó bắt đầu đặt trần — và bạn vừa đo được luật Amdahl của chính mình, không cần công thức nào.
