Phần 10 vừa cho thấy một lõi CPU nuốt tới ~7,5 lệnh độc lập mỗi chu kỳ — rộng tới mức đáng kinh ngạc. Nhưng bề rộng ấy có một điều kiện tối quan trọng mà tôi suýt quên: phải có việc độc lập để lấp.

Hình dung một bếp nhà hàng có tám đầu bếp. Nếu có tám món độc lập, cả tám cùng làm, ra đồ ào ào. Nhưng nếu thực đơn là một món cầu kỳ bảy bước nối tiếp — ướp xong mới nấu, nấu xong mới trình bày, mỗi bước cần kết quả bước trước — thì bảy đầu bếp còn lại đứng nhìn, chỉ một người làm được tại mỗi thời điểm. Thêm đầu bếp chẳng rút ngắn nổi món ăn. Đó chính là một chuỗi phụ thuộc trong CPU, và tốc độ của nó bị trói bởi đường tới hạn (critical path): tổng độ trễ của cả chuỗi. Tôi đo độ trễ từng loại phép trong container gcc:13 trên host ARM, và khoảng cách giữa chúng lớn tới mức khó tin: từ 1 chu kỳ tới 475 chu kỳ cho cùng khái niệm "một bước".

Chuỗi phụ thuộc chạy ở tốc độ độ trễ, không phải thông lượng

Có hai giới hạn khác nhau với một dòng lệnh. Thông lượng (throughput) là bao nhiêu phép độc lập lõi làm xong mỗi chu kỳ — phần 10 đo được ~7,5 cho phép cộng. Độ trễ (latency) là bao lâu để một phép cho ra kết quả tính từ lúc toán hạng sẵn sàng. Hai con số này rất khác nhau: một lõi có thể bắt đầu nhiều phép nhân mỗi chu kỳ (thông lượng cao) nhưng mỗi phép nhân vẫn mất 3 chu kỳ mới xong (độ trễ 3).

Khi bạn viết một chuỗi phụ thuộc — x = f(x) lặp lại, mỗi bước cần kết quả bước trước — lõi không thể chạy song song, vì tại mỗi thời điểm chỉ có đúng một phép sẵn sàng (đúng cảnh món ăn bảy bước). Nó phải chờ phép trước xong (trả đủ độ trễ) rồi mới bắt đầu phép sau. Tốc độ của cả chuỗi = tổng độ trễ các phép trên đó — gọi là đường tới hạn. Lõi rộng 8 hay rộng 100 cũng không giúp: không có việc thứ hai để lấp vào.

Để đo độ trễ thuần của mỗi phép, tôi dựng một chuỗi phụ thuộc chỉ gồm phép đó (dùng assembly nội tuyến để trình biên dịch không gộp mất), rồi chia thời gian cho số phép. Vì mỗi phép chờ phép trước, ns mỗi phép chính là độ trễ của nó. Lấy phép cộng làm mốc: cộng số nguyên độ trễ 1 chu kỳ, nên ns/cộng cho tôi thời gian một chu kỳ (0,228 ns, ~4,4 GHz trên lõi này).

Đo: từ 1 chu kỳ tới 475 chu kỳ

Chuỗi phụ thuộc thuần, host ARM, g++ -O2 -fno-tree-vectorize:

   phép (mỗi bước chờ bước trước) | ns/phép | chu kỳ
   -------------------------------|---------|--------
   cộng số nguyên (add)           |  0,228  |   1,0
   nhân số nguyên (mul)           |  0,683  |   3,0
   chia số nguyên (udiv)          |  1,706  |   7,5
   nạp phụ thuộc, dữ liệu ở L1    |  0,910  |   4,0
   nạp phụ thuộc, dữ liệu ở RAM   | 108,1   | 475

Đọc cột chu kỳ: cùng là "một bước" trên một chuỗi phụ thuộc, nhưng độ trễ chênh nhau khủng khiếp. Phép cộng 1 chu kỳ. Phép nhân 3 chu kỳ — chậm hơn cộng gấp ba, dù cả hai đều "một phép số học". Phép chia tới 7,5 chu kỳ — chia luôn là phép đắt nhất trong số học nguyên. Một nạp phụ thuộc (đuổi con trỏ) khi dữ liệu ở L1 mất 4 chu kỳ (độ trễ nạp-dùng của L1). Và khi dữ liệu ở RAM, một nạp phụ thuộc ngốn 475 chu kỳ (108 ns) — đúng bằng độ trễ RAM đã đo ở phần 5.

Con số cuối là cú sốc: nạp một giá trị từ RAM theo kiểu phụ thuộc đắt gấp ~475 lần một phép cộng. Nếu chuỗi tới hạn của bạn là một loạt nạp phụ thuộc ra RAM — chính xác là những gì xảy ra khi đuổi con trỏ qua một danh sách liên kết hay cây rải rác — thì mỗi bước tốn 475 chu kỳ, và cái lõi 8-wide (làm được ~7,5 phép/chu kỳ) ngồi không suốt 474/475 thời gian. Bảy đầu bếp đứng nhìn.

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

Tôi vào đo, mang theo hào hứng vừa có từ phần 10: "lõi này rộng 8, nuốt 7,5 lệnh mỗi chu kỳ — vậy cứ thêm việc, thêm song song, thêm lõi là nhanh". Con số bác ngay: một chuỗi phụ thuộc không hưởng lợi gì từ bề rộng đó. Cái lõi 8-wide chạy một chuỗi nạp-phụ-thuộc-RAM ở đúng 475 chu kỳ mỗi bước, y như một lõi hẹp. Đường tới hạn là trần cứng — thứ duy nhất phá được nó là rút ngắn chính chuỗi (ít bước hơn, hoặc bước rẻ hơn) hoặc biến nó thành việc độc lập, chứ không phải thêm cổng/lõi. ILP và đa lõi tăng thông lượng, không giảm độ trễ của một chuỗi.

Nhưng nếu vì thế mà rơi vào niềm tin ngược — "mọi phép tính đều tốn cỡ một chu kỳ, chỉ cần đếm số phép là ước lượng được thời gian" — thì sai tới hàng trăm lần. Trên cùng một lõi: cộng 1 chu kỳ, nhân 3, chia 7,5, nạp L1 4, nạp RAM 475. Một vòng lặp "ít phép" nhưng mỗi phép là chia hoặc nạp-RAM có thể chậm hơn nhiều một vòng "nhiều phép" toàn cộng. Đếm số phép mà bỏ qua loại phép và độ trễ của chúng là ước lượng sai bản chất. Đặc biệt, một phép "nạp bộ nhớ" trông vô hại trong mã nguồn lại có thể là bước 475-chu-kỳ đắt nhất cả chuỗi.

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

Việc đầu tiên: rút ngắn đường tới hạn — giảm chiều dài chuỗi phụ thuộc và tránh các bước độ trễ cao. Nếu vòng lặp nóng của bạn là một chuỗi phụ thuộc, hãy hỏi: có phép nào đắt trên đường tới hạn không? Thay chia bằng nhân nghịch đảo tính sẵn; tránh nạp phụ thuộc ra RAM trong chuỗi (đuổi con trỏ qua cấu trúc rải rác) — đây là lý do sâu xa vì sao mảng liền thắng danh sách liên kết: mảng cho truy cập tuần tự (prefetch giấu độ trễ), còn con trỏ rải rác đặt một nạp-RAM 475-chu-kỳ ngay trên đường tới hạn.

Việc thứ hai: phá chuỗi thành việc độc lập khi có thể — đúng bài học phần 3. Nếu bạn phải làm nhiều phép độ trễ cao, hãy sắp chúng độc lập để lõi rộng chạy chồng lên nhau (nhiều accumulator, nhiều con trỏ đuổi song song). Khi ấy độ trễ của từng phép ẩn sau nhau, và bạn chuyển từ giới hạn độ trễ sang giới hạn thông lượng — nơi cái lõi 8-wide mới phát huy.

Khái niệm "đường tới hạn" này không dừng ở một lõi CPU — nó là cách tư duy về mọi hệ thống có các bước phụ thuộc, và biết vậy giúp nhìn ra nút thắt thật ở tầng cao. Một request web gọi service A, chờ kết quả rồi mới gọi B, chờ tiếp rồi gọi C là một chuỗi phụ thuộc ở quy mô mạng: độ trễ tổng là A+B+C nối tiếp, và thêm CPU/máy chủ không cứu được — cái cứu được là gọi song song những phần độc lập (đúng tinh thần "phá chuỗi"), hoặc cắt bớt số chặng. Một pipeline CI/CD với các stage nối tiếp, một chuỗi migration database phải chạy tuần tự, một DAG công việc trong Spark/Airflow — tất cả có một "đường tới hạn" là chuỗi phụ thuộc dài nhất, và đó mới là thứ định đoạt thời gian hoàn thành, không phải tổng khối lượng việc. Câu hỏi luôn giống nhau: cái gì nối tiếp bắt buộc, và bước đắt nhất trên đó là gì?

Muốn tự thấy thì dựng năm chuỗi phụ thuộc, mỗi chuỗi chỉ một loại phép, và bấm giờ ns mỗi bước (nhớ volatile sink, min nhiều lần, chặn trình biên dịch gộp bằng assembly hoặc dữ liệu phụ thuộc runtime). Một: x += 1 lặp lại — bạn được thời gian một chu kỳ. Hai: x = x * c (nhân) — khoảng 3 lần chậm hơn. Ba: x = num / x (chia) — đắt hơn nữa, cỡ 7-8 chu kỳ. Bốn: đuổi con trỏ trong một mảng nhỏ vừa L1 (p = a[p]) — vài chu kỳ, độ trễ nạp L1. Năm: đuổi con trỏ trong một mảng lớn hơn cache rất nhiều (hàng trăm MB) — và bạn sẽ thấy nó nhảy vọt lên cả trăm nanô giây mỗi bước, hàng trăm chu kỳ, vì mỗi bước là một nạp-RAM phụ thuộc nằm chình ình trên đường tới hạn. Ba mươi giây đó cho thấy điều mà "lõi rộng thì gì cũng nhanh" và "phép nào cũng một chu kỳ" cùng giấu đi: khi các phép xâu chuỗi phụ thuộc, tốc độ bị trói ở tổng độ trễ — và độ trễ giữa một phép cộng và một lần chạm RAM chênh nhau tới gần năm trăm lần.