Hiệu năng tính toán: Amdahl, CUDA và data locality

Giới thiệu

Bài này học trần song song và cách dùng GPU đúng. Dùng để biết khi nào thêm máy là phí tiền.

Kiến thức cần nhớ

Luật Amdahl

• Định nghĩa: phần tuần tự quyết trần tăng tốc tối đa.
• 10% tuần tự thì vô hạn máy cũng tối đa 10 lần.
• Ví dụ đời thường: như đoàn xe chờ 1 cầu hẹp.
• Phải đo tỉ lệ tuần tự trước khi mua máy.
• Sửa phần tuần tự thường lời hơn thêm máy mới.

CUDA và GPU

• CPU như vài đầu bếp giỏi làm món khó lẻ.
• GPU như nghìn phụ bếp cùng thái rau giống nhau.
• Điều kiện thắng: data lớn, phép đều, ít rẽ nhánh.
• Ví dụ đời thường: như in 1000 tờ cùng mẫu thì nhanh.
• Data nhỏ và rẽ nhánh nhiều thì CPU vẫn thắng.

Locality

• Định nghĩa: chở tính tới chỗ data rẻ hơn ngược lại.
• Mỗi máy tính trên miếng data nó đang có.
• Giữ nóng cache RAM, tính và truyền gối nhau.
• Ví dụ đời thường: như nấu tại chợ thay vì chở rau xa.
• Thêm GPU mà quên locality thì trễ vẫn chững lại.

Ví dụ

• Input: 95% song song, 64 máy -> Output: chỉ nhanh ~15 lần.
• Giải thích: 5% tuần tự thành trần cứng theo Amdahl.

# Ước trần Amdahl
tuan_tu = 0.05  # 5% bắt buộc nối tiếp
tran = 1 / tuan_tu  # máy vô hạn cũng vậy
print(tran)  # 20 lần là trần

💻 Bài tập

Ngôn ngữ: C++17 với OpenMP (Bài 1-2), Python với NumPy/CuPy hoặc PyTorch (Bài 3). Nộp vào day-110/.

Bài 1: Định luật Amdahl

1. Viết double amdahl(double p, int n) trả $\frac{1}{(1 - p) + p / n}$.
2. In bảng tăng tốc lý thuyết với p = 0.5, 0.9, 0.95, 0.99 và n = 1, 2, 4, 8, 16, 64, 1024.

p = 0.95, n = 64   -> ~15.4
p = 0.90, n = vô hạn -> 10

3. Viết chương trình có phần tuần tự (đọc file, 20% thời gian) và phần song song bằng #pragma omp parallel for (tính tổng bình phương $10^8$ số). Đo tăng tốc thật với 1, 2, 4, 8 luồng. So với Amdahl.

Bài 2: Data locality và cache

1. Nhân 2 ma trận $1024 \times 1024$ bằng 3 thứ tự vòng lặp: ijk, ikj, jki. In thời gian. Giải thích bằng cách truy cập bộ nhớ theo hàng.
2. Viết bản chia khối (tiling) khối 32 và 64. So thời gian.
3. Duyệt mảng 2D theo hàng và theo cột với kích thước từ 1 MB tới 256 MB. Vẽ thời gian, chỉ ra các mốc cache L1, L2, L3.

Bài 3: CPU và GPU (nâng cao)

Nếu không có GPU, dùng Google Colab.

1. Nhân ma trận $n \times n$ với n = 64, 256, 1024, 4096 trên NumPy (CPU) và CuPy hoặc PyTorch CUDA (GPU). Đo cả thời gian chép dữ liệu sang GPU.
2. Chỉ ra n mà GPU bắt đầu thắng khi tính cả thời gian chép.
3. Bài nhiều rẽ nhánh: với mỗi phần tử, lặp Collatz tới 1 và đếm bước. So CPU (Numba hoặc C++) và GPU.

✅ Tiêu chí hoàn thành

• Bảng Amdahl và số đo thật so với lý thuyết.
• Bảng 3 thứ tự vòng lặp và bản tiling có số thật.
• Hình thời gian duyệt theo kích thước mảng.
• Bảng CPU vs GPU có cột thời gian chép dữ liệu.

❓ Câu hỏi ôn tập

• Trần Amdahl do đâu?
• GPU thắng CPU khi nào?
• Locality nghĩa là gì?
• Vì sao thêm GPU bị chững?

🌕 Bạn đã hoàn thành ngày 110. Làm hết bài tập phía trên rồi sang ngày tiếp theo.