Phần 5 và phần 11 đo được một con số đáng sợ: đuổi con trỏ ngẫu nhiên ra RAM tốn ~100 ns mỗi bước. Từ đó dễ kết luận: bộ nhớ chậm, mỗi lần chạm hụt cache (cache miss) là một cú chờ trăm nanô giây, và N lần miss thì tốn N lần độ trễ. Nhưng con số 100 ns kia có một điều kiện ẩn mà tôi đã bỏ qua: các lần miss ấy phụ thuộc nhau (mỗi bước cần địa chỉ từ bước trước). Điều gì xảy ra nếu chúng độc lập? Tôi đo trong container gcc:13 trên host ARM, và câu trả lời lật ngược trực giác: lõi thực thi ngoài thứ tự (out-of-order) có thể giữ hàng chục lần miss bay cùng lúc, biến trăm nanô giây thành vài.
Nhiều lần miss độc lập bay cùng lúc
Một lõi CPU hiện đại thực thi ngoài thứ tự: khi gặp một lệnh phải chờ (ví dụ một load đang đợi dữ liệu từ RAM), nó không đứng im. Nó chạy tiếp các lệnh sau độc lập, và nếu trong đó có thêm những load khác cũng miss cache, nó phát luôn các lần nạp đó. Kết quả: nhiều lần chạm hụt cache cùng bay trong không trung một lúc, chờ RAM song song. Hiện tượng này gọi là song song mức bộ nhớ (MLP — memory-level parallelism).
Hệ quả then chốt: nếu bạn có N lần miss độc lập, tổng thời gian không phải N × độ trễ — mà gần bằng một độ trễ (miễn N còn trong khả năng "chứa" của phần cứng). Nhưng nếu các miss phụ thuộc nhau (mỗi cái cần kết quả cái trước, như đuổi con trỏ), chúng buộc phải nối đuôi — không chồng lên nhau được, và bạn trả đủ N × độ trễ. Câu hỏi đo: phần cứng chứa được bao nhiêu miss độc lập cùng lúc?
Đo: từ 102 ns xuống 3,9 ns
Tôi đuổi con trỏ trên một mảng 256 MB (mỗi bước là một cú miss ra RAM), nhưng chạy K chuỗi độc lập song song: K con trỏ, mỗi vòng cập nhật cả K. Vì K con trỏ ở K vị trí khác nhau, K lần nạp độc lập nhau. Tăng K, đo ns mỗi lần truy cập:
Đuổi con trỏ 256 MB, K chuỗi ĐỘC LẬP song song, host ARM:
K | ns/truy cập | tăng tốc vs K=1
---|-------------|----------------
1 | 102,3 | 1,0x (1 miss/lúc = full latency)
2 | 52,6 | 1,9x
4 | 26,8 | 3,8x
8 | 13,6 | 7,5x
16 | 7,29 | 14x
24 | 4,99 | 20x
32 | 3,91 | 26x (vẫn đang scale)
Đường cong gần như tuyến tính nghịch: K=1 tốn 102 ns (một miss mỗi lúc, đúng độ trễ RAM), K=2 còn 52,6 ns (1,9x — hai miss chồng nhau), K=8 xuống 13,6 ns (7,5x), K=16 còn 7,29 ns (14x), và K=32 chỉ 3,9 ns — nhanh gấp 26 lần so với một chuỗi. Cùng thao tác "chạm một ô nhớ ngẫu nhiên ở RAM", nhưng làm 32 cái độc lập thì mỗi cái rẻ đi 26 lần, vì lõi cho chúng bay song song.
Chú ý ở K=32 nó vẫn đang scale (26x, chưa bão hòa) — nghĩa là lõi này giữ được ít nhất ~26–32 lần miss outstanding cùng lúc. Đây là độ sâu MLP rất lớn (Apple Silicon nổi tiếng với hàng đợi bộ nhớ khổng lồ). Một lõi không chỉ rộng về tính toán (phần 10) mà còn sâu về số lần chờ bộ nhớ nó chịu được cùng lúc.
Một lần tôi đo hớ: "N miss = N×latency" và "RAM ngẫu nhiên luôn ~100 ns"
Tôi vào đo với mô hình tuần tự trong đầu: "cache miss là một cú chờ; gặp miss thì CPU đứng lại chờ xong mới đi tiếp; nên N lần miss tốn N × độ trễ". Đo phá tan: lõi không đứng chờ — nó phát tiếp các miss độc lập, và 32 lần miss độc lập hoàn thành trong thời gian chỉ hơn một lần miss chút ít (3,9 ns/cái so với 102 ns khi đơn lẻ). "N miss = N × latency" chỉ đúng khi chúng phụ thuộc nhau; với miss độc lập, chi phí gần như chia đều cho độ song song. Nếu tôi tin mô hình cũ, tôi không thể giải thích vì sao một vòng quét băm/gather "toàn miss" lại nhanh hơn hẳn con số N × 100 ns dự đoán.
Nhưng đo cũng chỉnh một niềm tin khác tôi vừa rút ra từ phần 5: "truy cập RAM ngẫu nhiên luôn ~100 ns". Sai — thiếu một chữ. Truy cập ngẫu nhiên phụ thuộc (đuổi con trỏ đơn, mỗi bước cần bước trước) mới là 102 ns. Truy cập ngẫu nhiên độc lập (nhiều luồng, biết trước các địa chỉ) chỉ 3,9 ns nhờ MLP — cùng là "chạm RAM ngẫu nhiên" nhưng chênh 26 lần. Cái quyết định không phải "ngẫu nhiên hay không", mà là "phụ thuộc hay độc lập". Con trỏ chase chậm không vì nó ngẫu nhiên, mà vì nó nối đuôi — bỏ phí toàn bộ khả năng MLP của lõi.
Bài học đo lường: lõi OUT-OF-ORDER che độ trễ bộ nhớ bằng SONG SONG MỨC BỘ NHỚ (MLP): nhiều cache miss ĐỘC LẬP bay cùng lúc. Đo: đuổi 1 con trỏ = 102 ns (phụ thuộc, 1 miss/lúc); K chuỗi độc lập -> ~102/K, K=32 còn 3,9 ns = 26x, chưa bão hòa (lõi giữ >= ~26-32 miss outstanding). 'N miss = N×latency' SAI (chỉ đúng khi phụ thuộc); 'RAM ngẫu nhiên luôn ~100 ns' SAI (phụ thuộc 102 ns vs độc lập 3,9 ns). Nếu tin "N miss = N×latency" tôi ước lượng thừa hàng chục lần; nếu tin "ngẫu nhiên luôn chậm" tôi bỏ lỡ chuyện làm miss độc lập giúp 26 lần.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: làm các truy cập bộ nhớ ĐỘC LẬP để chúng chồng lên nhau. Nếu bạn phải chạm nhiều vị trí rải rác (tra băm hàng loạt, gather, duyệt nhiều cây), hãy sắp để các lần chạm không phụ thuộc nhau — xử lý một lô khóa cùng lúc thay vì lần lượt, để lõi phát nhiều miss song song. Đây là ý tưởng sau batching và software pipelining trong cấu trúc dữ liệu: cùng số lần miss, nhưng độc lập thì nhanh hơn hàng chục lần.
Hệ quả thứ hai: tránh chuỗi phụ thuộc dài của các truy cập bộ nhớ. Đuổi con trỏ qua danh sách liên kết hay cây là phản đề của MLP — mỗi bước phải chờ bước trước, không miss nào chồng được, trả đủ độ trễ. Nếu có thể, thay bằng cấu trúc cho phép biết trước nhiều địa chỉ (mảng chỉ số, cây phẳng hóa) để phát nhiều truy cập độc lập. Đây là một lý do sâu nữa vì sao mảng thắng danh sách liên kết — không chỉ prefetch, mà cả MLP.
Hệ quả thứ ba là tinh thần đo lường: độ trễ của một lần miss không phải giá bạn trả — độ trễ chia cho độ song song mới là. Con số mang theo: miss phụ thuộc (đuổi con trỏ) = full latency ~100 ns; K miss độc lập = ~100/K nhờ MLP (đo K=32 -> 3,9 ns = 26x, lõi giữ >= ~26-32 miss); phụ thuộc hay độc lập quyết định, không phải ngẫu nhiên hay không. Làm truy cập độc lập, tránh chuỗi phụ thuộc bộ nhớ. Cùng một đống cache miss, sắp cho độc lập thì lõi nuốt song song; xâu thành chuỗi thì nó trả từng cái một — chênh nhau vài chục lần.
Thử ba mươi giây
Cấp một mảng lớn hơn cache (vài trăm MB), tạo một chu trình đuổi con trỏ ngẫu nhiên, rồi đo hai cách. Một: đuổi một con trỏ p = a[p] vài chục triệu bước — bạn được ~100 ns mỗi bước, độ trễ RAM đầy đủ, vì mỗi bước phụ thuộc bước trước. Hai: giữ K con trỏ độc lập (p0=a[p0]; p1=a[p1]; ...) và cập nhật cả K mỗi vòng, chia thời gian cho tổng số lần chạm. Tăng K = 2, 4, 8, 16, 32: bạn sẽ thấy ns mỗi lần chạm giảm gần tỉ lệ nghịch với K — tới K=16, 32 vẫn còn giảm — vì lõi cho hàng chục miss bay song song. Điểm nó ngừng giảm cho bạn độ sâu MLP của máy (số miss tối đa nó giữ cùng lúc). Ba mươi giây đó cho bạn thấy điều mà "mỗi cache miss là một cú chờ trăm nanô giây" giấu đi: lõi không đứng chờ từng miss — nó phóng cả một bầy miss độc lập cùng lúc, và bí quyết tăng tốc code nặng bộ nhớ là cho nó nhiều việc độc lập để phóng.
