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: phải có việc độc lập để lấp. Phần này đo mặt trái: khi các phép tính xâu thành một chuỗi phụ thuộc — mỗi phép cần kết quả phép ngay trước — thì cái lõi tám cổng kia gần như vô dụng. Tốc độ khi ấy bị trói bởi đường tới hạn (critical path): tổng độ trễ (latency) của 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. 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ề rộng khổng lồ của lõi hoàn toàn phí phạm.
Một lần tôi đo hớ: "lõi rộng thì gì cũng nhanh" và "phép nào cũng ~1 chu kỳ"
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". Đo phá tan: 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 đo cũng phá một niềm tin ngược, ẩn hơn: "mọi phép tính đều tốn cỡ một chu kỳ, nên chỉ cần đếm số phép là ước lượng được thời gian". 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.
Bài học đo lường: một CHUỖI PHỤ THUỘC chạy ở tốc độ TỔNG ĐỘ TRỄ (đường tới hạn), KHÔNG hưởng lợi từ lõi rộng/ILP/đa lõi (chúng tăng thông lượng, không giảm độ trễ). Độ trễ mỗi phép chênh nhau khủng khiếp: add 1 ck, mul 3 ck, udiv 7,5 ck, nạp L1 4 ck, nạp RAM 475 ck (108 ns) — chênh tới ~475x. 'Lõi rộng thì gì cũng nhanh' và 'phép nào cũng ~1 chu kỳ' đều SAI. Nếu tin "lõi rộng cứu tất cả" tôi kỳ vọng sai ở code phụ thuộc; nếu tin "phép nào cũng 1 chu kỳ" tôi ước lượng sai hàng trăm lần khi có chia hoặc nạp-RAM.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầ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.
Hệ quả 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.
Hệ quả thứ ba là tinh thần đo lường: hiệu năng của code phụ thuộc do đường tới hạn quyết định, và các phép không hề bình đẳng về độ trễ. Con số mang theo: chuỗi phụ thuộc = tổng độ trễ (ILP/đa lõi không giúp); add 1, mul 3, udiv 7,5, nạp L1 4, nạp RAM ~475 chu kỳ. Rút ngắn/tránh bước đắt trên đường tới hạn; phá thành việc độc lập để chuyển sang giới hạn thông lượng. Cùng "số phép", nhưng loại phép và cách chúng phụ thuộc mới định đoạt thời gian — và một nạp-RAM ẩn trên đường tới hạn có thể đắt hơn cả trăm phép cộng cộng lại.
Thử ba mươi giây
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, và 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 bạn 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.
