Bài trước kết thúc với hai con số: một chuỗi phép cộng phụ thuộc nhau chạy đúng một phép mỗi chu kỳ, nhưng khi các phép cộng độc lập, cùng một lõi CPU làm được gần 3 phép mỗi chu kỳ. Chương trình thì vẫn viết từng dòng một. Vậy CPU tìm ra việc làm song song ở đâu?
Bài này trả lời câu đó, rồi đi tới vấn đề lớn nhất của CPU hiện đại: nó tính nhanh hơn rất nhiều so với tốc độ bộ nhớ đưa dữ liệu tới. Lộ trình: dây chuyền và thực thi không theo thứ tự, đoán nhánh (và vì sao sắp xếp một mảng có thể làm vòng lặp nhanh gấp 11 lần), bức tường bộ nhớ và các tầng cache, dòng cache và tính cục bộ, rồi hệ quả cho code bạn viết hằng ngày, kể cả code Python.
Mọi con số trong bài đều đo trên máy thật, bằng C (clang, -O2) và Python 3.12, một luồng, mỗi phép đo lấy lần nhanh nhất trong 3 lần. Kích thước cache và độ trễ khác nhau giữa các dòng CPU; điều đáng xem là hình dạng của các con số.
Dây chuyền, và làm nhiều lệnh một lúc
Bài trước đã chia một lệnh thành bốn bước: lấy lệnh, giải mã, thực thi, ghi kết quả. CPU không làm xong lệnh này rồi mới bắt đầu lệnh kia; nó xếp chúng thành một dây chuyền (pipeline), như dây chuyền lắp ráp: mỗi chu kỳ, mỗi trạm làm một việc cho một lệnh khác nhau.
chu kỳ: 1 2 3 4 5 6
lệnh 1: lấy giải mã thực thi ghi
lệnh 2: lấy giải mã thực thi ghi
lệnh 3: lấy giải mã thực thi ghi
CPU thật có dây chuyền dài hơn nhiều (hơn chục trạm) và rộng hơn: mỗi chu kỳ nó lấy và giải mã vài lệnh cùng lúc, và có nhiều bộ thực thi (nhiều bộ cộng, bộ nhân, bộ đọc bộ nhớ) chạy song song. Đó là lý do bốn chuỗi phép cộng độc lập ở bài trước chạy được 2,9 phép mỗi chu kỳ.
Nhưng lệnh trong chương trình thường phụ thuộc nhau: x = a + b rồi y = x * 2 thì phép nhân phải chờ phép cộng. Để không phải đứng chờ, CPU hiện đại nhìn trước hàng trăm lệnh, tìm những lệnh đã có đủ dữ liệu, và chạy chúng trước, không theo thứ tự trong chương trình (out-of-order execution). Kết quả vẫn được "công bố" theo đúng thứ tự, nên từ phía chương trình, mọi thứ trông như chạy tuần tự. Bên trong thì không.
Đoán nhánh
Dây chuyền có một vấn đề với câu lệnh if. Để giữ dây chuyền đầy, CPU phải lấy lệnh tiếp theo ngay, trước khi biết điều kiện của if đúng hay sai, vì điều kiện đó còn đang nằm ở mấy trạm phía sau. Nó không thể chờ. Nên nó đoán: bộ đoán nhánh (branch predictor) nhớ mỗi câu if lần trước rẽ hướng nào và theo mẫu nào, rồi đoán lần này. CPU chạy tiếp theo hướng đã đoán. Nếu đoán đúng, không mất gì. Nếu đoán sai, mọi việc đã làm theo hướng sai bị vứt bỏ, và dây chuyền phải nạp lại từ đầu.
Thí nghiệm kinh điển: cộng các số lớn hơn hoặc bằng 128 trong một mảng một triệu số ngẫu nhiên từ 0 tới 255. Chạy hai lần: một lần với mảng như ban đầu, một lần sau khi sắp xếp. Cùng các con số, cùng vòng lặp, cùng kết quả:
static long run(const int *data) {
long sum = 0;
for (int rep = 0; rep < 50; rep++)
for (int i = 0; i < N; i++)
if (data[i] >= 128) { sum += data[i]; __asm__ volatile(""); } // a real branch the CPU has to guess
return sum;
}
(Dòng __asm__ volatile("") trống để giữ câu if là một nhánh thật. Không có nó, trình biên dịch đủ khôn để thay câu if bằng một lệnh chọn giá trị không rẽ nhánh, và phép đo ra 0.)
| Mảng | Mỗi phần tử |
|---|---|
| Thứ tự ngẫu nhiên | 2,43 ns |
| Đã sắp xếp | 0,22 ns |
Nhanh gấp 11 lần chỉ vì thứ tự. Với mảng đã sắp xếp, nửa đầu toàn số nhỏ hơn 128 và nửa sau toàn số lớn hơn: câu if rẽ cùng một hướng hàng trăm nghìn lần liên tiếp, và bộ đoán gần như không bao giờ sai. Với mảng ngẫu nhiên, không có mẫu nào để học, nên khoảng một nửa số lần đoán là sai. Tính ngược lại: mỗi lần đoán sai tốn khoảng (2,43 − 0,22) ÷ 0,5 ≈ 4,4 ns, tức khoảng 20 chu kỳ vứt đi.
Đoán và chạy trước cũng có mặt trái. Năm 2018, lỗ hổng Spectre cho thấy những việc CPU làm theo hướng đoán sai, dù bị "vứt bỏ", vẫn để lại dấu vết trong cache, và một chương trình độc hại có thể đo dấu vết đó để đọc trộm dữ liệu. Tối ưu hiệu năng và bảo mật đôi khi kéo về hai phía ngược nhau.
Bức tường bộ nhớ
Phép cộng mất một chu kỳ. Còn lấy hai con số cần cộng từ bộ nhớ thì sao?
Để đo độ trễ thật của bộ nhớ, dùng kỹ thuật đuổi con trỏ (pointer chasing): một mảng mà mỗi ô chứa vị trí của ô tiếp theo cần đọc, xếp thành một vòng ngẫu nhiên đi qua mọi ô. Mỗi lần đọc phải chờ lần đọc trước xong mới biết đọc ở đâu, nên CPU không thể đọc trước hay chạy song song, và thời gian đo được chính là độ trễ của một lần đọc.
size_t *next = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) next[i] = i;
for (size_t i = n - 1; i > 0; i--) { // Sattolo's shuffle: one big random cycle through every slot
size_t j = (size_t)rand() % i, t = next[i]; next[i] = next[j]; next[j] = t;
}
size_t p = 0;
for (size_t i = 0; i < steps; i++) p = next[p]; // each load needs the previous one's result
Thay đổi kích thước mảng từ 4 KiB tới 128 MiB:
| Dữ liệu | Mỗi lần đọc | Khoảng bao nhiêu chu kỳ |
|---|---|---|
| 4 KiB – 128 KiB | 0,87 ns | ~4 |
| 256 KiB | 1,96 ns | ~9 |
| 1 MiB | 2,92 ns | ~13 |
| 4 MiB | 5,95 ns | ~27 |
| 16 MiB | 8,42 ns | ~38 |
| 32 MiB | 34,8 ns | ~160 |
| 64 MiB | 58,9 ns | ~270 |
| 128 MiB | 72,9 ns | ~330 |
Con số không tăng đều mà tăng theo bậc thang, và mỗi bậc là một tầng bộ nhớ:
- Tới 128 KiB: cache L1, nằm sát bộ thực thi, khoảng 4 chu kỳ.
- Từ 256 KiB tới 16 MiB: cache L2 (và các bộ đệm khác của CPU), từ 9 tới gần 40 chu kỳ.
- Từ 32 MiB trở lên: RAM thật, khoảng 330 chu kỳ ở 128 MiB.
Một lần đọc từ RAM tốn bằng hơn 300 phép cộng. CPU tính nhanh hơn bộ nhớ rất nhiều, và khoảng cách đó gọi là bức tường bộ nhớ. Cache là cách CPU sống chung với nó: những bộ nhớ nhỏ nhưng rất nhanh nằm ngay trên chip, giữ những dữ liệu vừa dùng và những dữ liệu có vẻ sắp dùng. Một phần lớn diện tích của con chip hiện đại là cache, không phải bộ tính toán. Nếu bạn đã đọc bài 3 của seri LLM, đây chính là bức tường đã khiến việc sinh chữ của mô hình ngôn ngữ phải chờ bộ nhớ thay vì chờ tính toán.
Dòng cache và tính cục bộ
Cache không lưu từng byte. Nó lưu theo từng dòng cache (cache line): một khối byte liền nhau, được đọc từ RAM cùng một lúc. Trên máy này một dòng là 128 byte (sysctl hw.cachelinesize); trên phần lớn CPU x86 là 64 byte. Đọc một số nguyên 4 byte nghĩa là kéo cả 128 byte xung quanh nó vào cache. Nếu chương trình dùng tiếp những byte bên cạnh, chúng đã có sẵn. Nếu không, phần còn lại bị lãng phí.
Thêm vào đó, CPU có các bộ đọc trước (prefetcher): khi thấy chương trình đọc lần lượt từng địa chỉ liền nhau, nó tự kéo các dòng tiếp theo vào cache trước khi được yêu cầu.
Cả hai cơ chế đều thưởng cho một thói quen: đọc dữ liệu theo đúng thứ tự nó nằm trong bộ nhớ. Thí nghiệm: cộng mọi phần tử của một ma trận 4.096 × 4.096 số nguyên (64 MiB). Trong C, ma trận được lưu theo từng hàng nối tiếp nhau, nên duyệt theo hàng là đi qua các byte liền nhau, còn duyệt theo cột là mỗi bước nhảy 4.096 × 4 = 16 KiB:
for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
sum += order == 0 ? m[(size_t)a * N + b] // rows: neighbours in memory
: m[(size_t)b * N + a]; // columns: 16 KiB apart
| Bình thường | Tắt vector hóa | |
|---|---|---|
| Theo hàng | 3 ms | 4 ms |
| Theo cột | 42 ms | 41 ms |
Cùng 16,7 triệu phép cộng, cùng kết quả, chậm hơn 10 lần. Theo cột, mỗi lần đọc rơi vào một dòng cache khác, chỉ dùng 4 trong 128 byte của dòng đó, và bộ đọc trước không đoán được bước nhảy. Cột "tắt vector hóa" để chắc rằng chênh lệch đến từ cache: với tùy chọn mặc định, trình biên dịch còn dùng lệnh SIMD (một lệnh cộng nhiều số cùng lúc) cho vòng theo hàng, nhưng tắt đi thì chênh lệch vẫn y như vậy.
Python cũng không thoát được
Có thể nghĩ Python quá xa phần cứng nên không bị ảnh hưởng. Thử: tạo một list 2 triệu số nguyên lớn, rồi tạo một list thứ hai chứa đúng những object đó nhưng xáo trộn thứ tự. Cộng cả hai:
import random, timeit
n = 2_000_000
a = [i * 3 + 1000 for i in range(n)] # big ints: each one a separate object, created one after another
b = a[:]; random.seed(0); random.shuffle(b) # the same objects, visited in random memory order
for name, xs in (("creation order", a), ("shuffled", b)):
t = min(timeit.repeat(lambda: sum(xs), number=3, repeat=3)) / 3
print(f"{name:15} {t*1000:6.1f} ms ({t/n*1e9:.1f} ns per element)")
| Thời gian | Mỗi phần tử | |
|---|---|---|
| Theo thứ tự tạo ra | 2,8 ms | 1,4 ns |
| Đã xáo trộn | 21,4 ms | 10,7 ns |
Cùng những con số, cùng tổng, chậm hơn 7,6 lần. Lý do: một list Python không chứa con số, nó chứa con trỏ tới các object số nguyên (bài trước: mỗi object 28 byte trở lên) nằm rải rác trên heap. Các object được tạo lần lượt thì tình cờ nằm cạnh nhau trong bộ nhớ, nên đi theo thứ tự tạo ra là đi qua bộ nhớ liền mạch. Xáo trộn list thì mỗi phần tử là một cú nhảy tới một chỗ ngẫu nhiên, đúng như thí nghiệm đuổi con trỏ ở trên.
Đây cũng là một lý do khiến NumPy nhanh: một mảng NumPy chứa các con số nằm liền nhau trong một khối bộ nhớ, không có con trỏ, không có object riêng cho từng số.
Hệ quả cho code
- Dữ liệu liền nhau nhanh hơn dữ liệu rải rác. Mảng thường nhanh hơn danh sách liên kết hay cây, dù lý thuyết độ phức tạp nói ngược lại cho một số thao tác, vì mỗi nút của danh sách liên kết là một lần có thể trượt cache.
- Duyệt theo thứ tự bộ nhớ. Với ma trận, vòng lặp ngoài theo hàng, vòng trong theo cột (với C, NumPy mặc định); với dữ liệu nhiều trường, cân nhắc lưu từng trường thành một mảng riêng nếu vòng lặp chỉ đọc một trường.
- Dữ liệu "nóng" càng nhỏ càng tốt. Thứ gì vừa trong L1 hay L2 thì nhanh gấp hàng chục lần thứ phải ra RAM.
- Nhánh khó đoán thì đắt. Trong vòng lặp nóng, một câu
ifrẽ ngẫu nhiên có thể tốn hơn cả phần việc chính; sắp xếp dữ liệu, hoặc viết lại không cần rẽ nhánh, có thể đáng giá. - Đo trước khi tối ưu. Mọi con số ở trên đều làm trình biên dịch phải bị "ngăn" lại mới đo được; trình biên dịch và CPU đã tự làm rất nhiều tối ưu, và trực giác dễ sai.
Tóm lại
| Khái niệm | Thực chất |
|---|---|
| Dây chuyền | Mỗi trạm làm một bước cho một lệnh khác nhau; mỗi chu kỳ một lệnh đi ra |
| Siêu vô hướng | Nhiều bộ thực thi song song: ~2,9 phép cộng mỗi chu kỳ khi không phụ thuộc nhau |
| Thực thi không theo thứ tự | Nhìn trước hàng trăm lệnh, chạy lệnh nào đã đủ dữ liệu |
| Đoán nhánh | Đoán hướng của if để giữ dây chuyền đầy; đoán sai mất ~20 chu kỳ |
| Bức tường bộ nhớ | L1 ~4 chu kỳ, L2 ~9–40, RAM ~330 |
| Dòng cache | Đọc theo khối 128 byte (64 byte trên phần lớn x86) |
| Tính cục bộ | Đọc theo thứ tự bộ nhớ: theo hàng nhanh gấp 10 lần theo cột |
| Python | List chứa con trỏ; xáo trộn thứ tự làm phép cộng chậm 7,6 lần |
Bài này coi "bộ nhớ" là một dãy địa chỉ đơn giản. Thật ra không phải vậy: mỗi chương trình thấy một không gian địa chỉ riêng, malloc 1 GB có thể không tốn một byte RAM nào, và địa chỉ mà chương trình dùng phải được dịch sang địa chỉ thật ở mỗi lần đọc. Bài sau: stack, heap, và bộ nhớ ảo.