10 lõi mà chỉ nhanh 7 lần, rồi 4 lần, rồi 3 lần — vì đâu?

Chín người phụ nữ không đẻ được một đứa bé trong một tháng. Câu nói cũ ấy gói gọn cả bài này: có những việc chia người ra làm nhanh gấp bội, nhưng cũng có phần buộc phải tuần tự, và chính cái phần bướng bỉnh đó — dù nhỏ — quyết định bạn nhanh được đến đâu. 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ồ. Tôi đo tăng tốc thật khi tăng số luồng, cho ba loại công việc khác nhau, rồi đối chiếu với luật Amdahl — công thức nói trước 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ì.

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ại là 10 vCPU ảo hóa trên một máy chủ dùng 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.

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.

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 đầu. Đ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. Tôi đã hố khi 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ề đến code hằng ngày

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

Điều 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 tăng tốc theo luồng sẽ cho biết bạn đang ở loại nào.

Và cùng cái trần đó chờ sẵn ở mọi tầng ứng dụng thật. Java parallelStream() hay một ForkJoinPool chỉ thắng khi phần việc mỗi phần tử đủ nặng và độc lập; ném một stream I/O-bound hay một tác vụ khóa chung vào đó là bạn đang trả chi phí chia-gộp cho một cái trần Amdahl thấp lè tè, có khi còn chậm hơn stream() tuần tự. Go dựng goroutine rẻ đến mức dễ quên rằng GOMAXPROCS lõi vẫn tranh cùng một bus nhớ. Và rõ nhất là cơ sở dữ liệu: thêm read-replica hay tăng max_parallel_workers chỉ cứu được truy vấn CPU-bound; một truy vấn quét bảng khổng lồ nghẽn ở I/O đĩa thì thêm worker cũng chỉ chen nhau qua cùng một đường ống, đúng như mảng 400 MB ở trên. Mẫu số chung: "nhanh gấp N lần" là lời hứa lý thuyết; ba cái trần — phần tuần tự, chi phí đồng bộ, băng thông/I/O chung — cùng kéo tăng tốc thật xuống dưới N, và phải đo mới biết trần của bạn nằm ở đâu.

Muốn tự thấy thì 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, chẳng cần công thức nào.