Cấm thuật SIMD instruction tăng tốc x8

Chúng ta xét bài toán (với thuật chuẩn sử dụng Segment Tree) rất cổ điển sau: https://oj.vnoi.info/problem/segtree_itez1

Cho dãy A gồm N phần tử. Có Q truy vấn. Mỗi truy vấn thuộc 1 trong 2 loại:

1. Gán A[i] = x
2. Tìm giá trị nhỏ nhất của A[l], ..., A[r]

Ở bài này SIMD instruction giúp ta có thể tối ưu thuật toán trâu bò gấp gần 8x (nhanh ngang segment tree với bài này :)))

. Cũng may bài này test yếu nên chúng ta có thể thoải mái thử các thuật toán trâu bò.

Các bạn muốn tìm hiểu sâu về SIMD có thể đọc https://en.algorithmica.org/hpc/simd/

Các bạn đọc tiếp mình phân tích trong caption từng ảnh chứa code.

Ảnh 1: Chúng ta bắt đầu bằng thuật toán trâu bò với độ phức tạp N*Q rất cơ bản:

Truy vấn 1 ta đơn giản gán A[x] = y

Truy vấn 2 ta dùng 1 vòng for O(N) để tìm max.

Test bài này trên VNOJ rất yếu nên thuật toán N*Q AC với thời gian 11.2 giây

Lưu ý mình dùng thư viện đọc buffer (IO::get()) để thời gian đọc input không ảnh hưởng nhiều đến thời gian chạy.

Code đầy đủ: https://pastebin.com/m5ZRPfYC

Ảnh 2:

Để thực hiện các phép toán như lấy max, CPU cần lưu dữ liệu vào các register 32-bit hoặc 64-bit, rồi thực hiện các CPU instruction trên đó.

Với các máy tính hiện đại, có thêm 1 bộ register 256-bit. Các register này có thể lưu đồng thời 8 biến int hoặc 4 biến long long. Kết hợp với các register 256-bit này là các SIMD instruction cho phép ta thực hiện ĐỒNG THỜI các phép toán trên các biến này.

Áp dụng register 256-bit và SIMD instruction ta có thể tối ưu thuật trâu bò như sau:

Chia đoạn [x, y] thành các nhóm gồm 8 số:

A[x], A[x+1], ..., A[x+7]
A[x+8], A[x+9], ..., A[x+15]
...

(chú ý rằng sẽ có 1 nhóm cuối cùng không đủ 8 số, ta phải xử lý riêng)

Tiếp theo ta làm như sau:

1. Khởi tạo register 256-bit max_val = 8 số âm vô cùng
2. Với mỗi nhóm 8 số, lưu vào 1 register 256-bit khác (vals)
3. Dùng SIMD instruction, cập nhật max_val bằng max(max_val, vals). Chú ý SIMD instruction cho ta lấy max của 8 cặp số, chứ không phải là lấy max của 2 số 256-bit
4. Cuối cùng, lấy max của 8 số trong max_val
5. Xử lý riêng nhóm cuối cùng với < 8 phần tử.

=> Tăng tốc được gần 8x.

Code đầy đủ: https://pastebin.com/WDTjBdbA

EDIT: Code trong ảnh bị lỗi do mình copy từ bài khác 😂

Dòng comment "In each iteration..." phải là

// Process each group of 8 numbers

Ảnh 3:

Tự code SIMD instruction như trong ảnh 2 khá khó. Tuy nhiên trên thực tế ta có thể thêm 2 dòng ma thuật sau ở đầu code:

#pragma GCC target("avx2")
#pragma GCC optimize("O3")

2 dòng này cho compiler biết nó có thể cố gắng sử dụng SIMD instruction để tối ưu code. Với code bài này, compiler sinh code ra không tối ưu tự code SIMD, nhưng cũng nhanh hơn code trâu bò gần 5 lần!!

Code đầy đủ: https://pastebin.com/nNn1MZK4

Ảnh 4: bài ITEZ2 (https://oj.vnoi.info/problem/segtree_itez2) cũng có thể làm tương tự.

Ở bài này, các biến tính tổng cần 64-bit, nên ta chỉ tối ưu được gần 4 lần.

Bài này mình không đưa code full, các bạn có thể dùng nó để luyện tập.

Ảnh 5:

Thư viện của 1 bạn Nhật có sẵn 1 số SIMD instruction: https://nyaannyaan.github.io/library/misc/simd.hpp

Tuy nhiên không có code mẫu sử dụng nên có thể hơi khó dùng. Mặc dù vậy các bạn cũng có thể tìm được 1 số hàm cơ bản trong này.

Nguồn: Code cùng RR fanpage