Thêm phép tính vào vòng lặp mà không chậm hơn: vì sao?

Nhiều phần trong sê-ri đã chạm tới cụm từ "memory-bound" — vòng lặp bị bộ nhớ trói chứ không phải phép tính. Phần này tôi đo thẳng cái trần ấy: băng thông bộ nhớ (memory bandwidth), số byte tối đa chuyển được giữa CPU và RAM mỗi giây.

Hình dung một cái ống nước dẫn vào bồn. Bạn có thể lắp thêm bao nhiêu vòi hoa sen, đầu phun tinh xảo tùy thích ở đầu ra — nhưng lượng nước chảy ra mỗi giây vẫn bị chặn bởi tiết diện cái ống, không phải bởi mấy cái vòi. Với vòng lặp duyệt dữ liệu lớn, băng thông bộ nhớ chính là cái ống đó: một tài nguyên hữu hạn, và nó thường mới là thứ thực sự quyết định tốc độ, chứ không phải bạn làm bao nhiêu phép tính bên trong. Tôi đo bằng bài kiểm kinh điển STREAM trong container gcc:13 trên host ARM, và con số vừa cho thấy cái trần, vừa hé một điều bất ngờ về việc một lõi cần bao nhiêu.

STREAM: đo byte mỗi giây, không phải phép mỗi giây

STREAM chạy vài vòng lặp đơn giản trên các mảng lớn hơn cache (để mỗi phần tử phải đi RAM), rồi tính GB/s = tổng byte đọc và ghi chia thời gian. Các vòng khác nhau ở lượng phép tính và tỉ lệ đọc/ghi:

• copy b[i]=a[i] — 0 phép tính (16 byte/phần tử: 1 đọc + 1 ghi).
• scale b[i]=k*a[i] — 1 phép nhân (16 byte).
• add c[i]=a[i]+b[i] — 1 phép cộng (24 byte: 2 đọc + 1 ghi).
• triad c[i]=a[i]+k*b[i] — 1 nhân + 1 cộng (24 byte).

Nếu tốc độ do phép tính quyết định, copy (không phép) phải nhanh hơn hẳn triad (hai phép). Nếu do băng thông quyết định, chúng đạt GB/s xấp xỉ nhau. Đo sẽ phân xử.

Đo: mọi vòng đều đụng cùng một trần

STREAM 1 luồng, mảng 256 MB double (>>cache), host ARM, g++ -O2:

   read/sum   (8 B/pt)   : 14,1 GB/s   (*) không phải băng thông thật
   copy  b=a  (16 B/pt)  : 68,0 GB/s
   scale b=k*a(16 B/pt)  : 65,2 GB/s
   add   c=a+b(24 B/pt)  : 91,6 GB/s
   triad c=a+k*b(24 B/pt): 80,3 GB/s

Nhìn copy, scale, add, triad: dù lượng phép tính khác hẳn (copy không phép, triad nhân+cộng), tất cả đạt ~65–92 GB/s — cùng một cỡ. Nút cổ chai không phải phép tính mà là băng thông bộ nhớ: thêm một phép nhân hay cộng gần như không làm vòng chậm hơn, vì CPU vẫn đang đợi dữ liệu từ RAM. Mấy cái vòi hoa sen không đổi được lưu lượng cái ống. (Chênh lệch giữa các dòng chủ yếu do tỉ lệ đọc/ghi: tôi đếm byte kiểu "hữu ích" của STREAM, nhưng mỗi lần ghi thực ra kéo thêm một lần đọc-để-sở-hữu (RFO) dòng cache, nên lưu lượng thật cao hơn — vì thế add đọc-nhiều lại cho GB/s "đếm được" cao hơn copy.)

Một chú ý quan trọng: read/sum chỉ 14 GB/s — không phải băng thông đọc thật của máy. Đó là vì s += a[i] tạo một chuỗi phụ thuộc số thực: mỗi phép cộng chờ tổng trước, nên vòng bị latency-bound chứ không lấp nổi băng thông. Muốn đo băng thông đọc thật phải phá chuỗi (nhiều tổng độc lập, phần 3). Cấu trúc vòng lặp quyết định bạn có chạm được trần băng thông hay không.

Đo: một luồng cần bao nhiêu để lấp băng thông?

Câu hỏi kinh điển: một lõi có đủ để dùng hết băng thông RAM không, hay phải nhiều lõi? Tôi chạy triad với số luồng tăng dần:

Triad đa luồng (host ARM):
   1 luồng : 81,4 GB/s
   2 luồng : 94,2 GB/s
   4 luồng : 95,1 GB/s
   8 luồng : 94,6 GB/s

Kết quả làm tôi bất ngờ: một luồng đã đạt 81 GB/s — khoảng 85% của đỉnh ~95 GB/s. Chỉ cần hai luồng là bão hòa memory controller (~94–95 GB/s), và thêm luồng nữa vô ích. Trên lõi Apple Silicon này, một core gần như tự mình dùng hết băng thông bộ nhớ — trái với hình dung quen thuộc từ server x86, nơi một lõi chỉ rút được một phần nhỏ và phải nhiều lõi mới đầy băng thông. Kiến trúc khác nhau cho kết luận khác nhau — đo máy của bạn mới chắc.

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

Tôi vào đo với mô hình quen thuộc: "vòng lặp nhanh chậm theo số phép tính nó làm". Con số bác ngay: copy (không phép tính), add, triad (nhân+cộng) đều ~65–92 GB/s — cùng trần băng thông. Với vòng memory-bound, thêm hay bớt phép tính gần như không đổi thời gian, vì CPU dành phần lớn thời gian đợi RAM, không phải tính. Đếm phép tính để ước tốc độ một vòng duyệt mảng lớn là nhìn nhầm nút cổ chai — thứ cần đếm là byte chuyển.

Nhưng đo cũng lật một niềm tin ngược mà tôi mang sẵn từ kiến thức x86: "một luồng không bao giờ dùng hết băng thông RAM, phải nhiều lõi". Trên lõi Apple này thì sai: một luồng đã đạt ~85% đỉnh, hai luồng bão hòa. Đây là đặc tính của máy — Apple Silicon cho mỗi lõi một hàng đợi bộ nhớ rất sâu (MLP, phần 15) nên một core rút được gần trọn băng thông. Trên server x86 nhiều kênh RAM thì cần nhiều lõi. Không có con số vạn năng; phải đo đúng phần cứng.

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

Việc đầu tiên: với vòng memory-bound, giảm BYTE chuyển, không phải phép tính. Dùng kiểu dữ liệu nhỏ hơn (float thay double, int32 thay int64), nén dữ liệu, và nhất là chặn (blocking/tiling) để tái dùng dữ liệu trong cache thay vì đọc lại từ RAM. Đây là lý do nhân ma trận theo khối nhanh hơn nhiều: nó cắt số byte đi RAM, không cắt số phép nhân.

Việc thứ hai: biết trần băng thông của máy để đặt kỳ vọng. Nếu vòng của bạn cần chuyển X byte và máy chạy Y GB/s, thời gian tối thiểu là X/Y — không thuật toán nào trong cùng lượng dữ liệu phá được trần đó. Đo GB/s một lần cho bạn "tốc độ ánh sáng" của các vòng duyệt dữ liệu. Và nhớ truy cập tuần tự mới đạt băng thông này; ngẫu nhiên thì thấp hơn nhiều.

Cái ống nước này có mặt ở mọi tầng, và thường bị bỏ quên đúng lúc quan trọng. Spark hay các engine xử lý dữ liệu lớn sống chết với nó: chọn định dạng cột nén (Parquet), đẩy bộ lọc xuống gần nguồn (predicate pushdown), chỉ đọc những cột cần — tất cả là để giảm byte kéo qua đĩa và mạng, đúng tinh thần "giảm byte, đừng đếm phép". Trong Java, một vòng cộng mảng double[] khổng lồ cũng memory-bound y hệt, và người ta chuyển sang float[] hay mảng byte gói chặt vì lý do băng thông chứ không phải số phép cộng. Còn khi dữ liệu vượt một máy, "băng thông" đổi tên thành thông lượng mạng và đĩa, nhưng bài toán không đổi: khối lượng byte di chuyển mới là trần, và roofline model — công cụ chuẩn để phân tích hiệu năng — chính là cách vẽ ra hai cái trần "tính toán" và "băng thông" rồi xem code của bạn đụng cái nào. Với dữ liệu lớn, đơn vị đúng để suy nghĩ là byte mỗi giây, không phải phép mỗi giây.

Muốn tự thấy thì cấp ba mảng double lớn hơn cache nhiều (mỗi cái vài trăm MB), bấm giờ bốn vòng và tính GB/s = byte/thời gian: copy b[i]=a[i], scale b[i]=k*a[i], add c[i]=a[i]+b[i], triad c[i]=a[i]+k*b[i]. Cả bốn đạt GB/s xấp xỉ nhau dù triad làm gấp đôi phép tính so với copy — vì tất cả bị băng thông trói. Rồi chia mảng cho nhiều luồng chạy triad song song và đo GB/s tổng: tăng 1, 2, 4, 8 luồng, bạn sẽ thấy nó bão hòa ở một mức (trần của memory controller) và thêm luồng không giúp. Con số bão hòa đó là băng thông đỉnh của máy bạn, và số luồng để đạt nó cho biết một lõi mạnh cỡ nào. Ba mươi giây đó cho thấy điều mà "đếm phép tính" giấu đi: với dữ liệu lớn, CPU phần lớn thời gian đợi bộ nhớ, và tốc độ thật được đo bằng byte mỗi giây — một cái trần mà chỉ giảm lượng byte chuyển mới vượt qua được.