Vì sao mọi lập trình viên nên biết về SIMD

 (mitchellh.com)
1 điểm bởi GN⁺ 2 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • SIMD không phải là một kỹ thuật phức tạp chỉ dành cho phần mềm hiệu năng cao nhất, mà là một phương tiện tối ưu hóa thường ngày giúp tăng tốc các vòng lặp thông thường bằng cách xử lý dữ liệu liên tiếp theo nhiều giá trị cùng lúc
  • Mã SIMD điển hình tuân theo cấu trúc 5 bước: broadcast hằng số, duyệt theo đơn vị vector, tính toán song song, thu gọn/lưu kết quả và xử lý phần đuôi scalar
  • Vòng lặp tìm kiếm code point của Ghostty so sánh 4, 8 hoặc 16 giá trị u32 cùng lúc, về lý thuyết có thể tăng thông lượng xử lý lên tối đa 4 lần trên ARM NEON, 8 lần trên AVX2 và 16 lần trên AVX-512
  • Tổng thông lượng xử lý của terminal trên desktop Intel AVX2 đã nhanh hơn khoảng 5 lần; nếu không có độ rộng vector được hỗ trợ hoặc còn dữ liệu đầu vào dư, vòng lặp scalar hiện có sẽ xử lý toàn bộ đầu vào hoặc phần còn lại
  • Tự động vector hóa của trình biên dịch có thể bỏ lỡ cơ hội ngay cả với các vòng lặp đơn giản, vì vậy trước tiên hãy kiểm tra đầu ra đã tối ưu hóa; với các hot loop quan trọng, SIMD tường minh có thể giúp giữ cho hành vi và hiệu năng dự đoán được

SIMD làm gì

  • SIMD cho phép CPU xử lý nhiều giá trị song song bằng một lệnh duy nhất
    • Thay vì so sánh từng byte một, có thể so sánh 4, 8 hoặc nhiều byte hơn cùng lúc
    • Các vòng lặp như for (byte in bytes), for (character in string), for (value in array) có cơ hội được chuyển thành xử lý theo độ rộng vector
  • Nếu dữ liệu có hàng trăm, hàng nghìn hoặc hàng triệu byte, có thể đạt mức tăng tốc cục bộ 4 lần, 8 lần hoặc hơn tùy theo độ rộng song song
  • Nếu dữ liệu chỉ có vài phần tử hoặc vài chục phần tử thì không đáng áp dụng SIMD
  • simdutf và simdjson dùng các kỹ thuật SIMD phức tạp, nhưng SIMD thường ngày không cần phải phức tạp đến mức đó
  • Ví dụ dùng Zig, nhưng cấu trúc 5 bước áp dụng được cho các ngôn ngữ khác; cách mỗi ngôn ngữ hỗ trợ lệnh SIMD sẽ khác nhau

Cấu trúc 5 bước lặp lại

  1. Broadcast các hằng số cần thiết ra mọi lane và khởi tạo bộ tích lũy vector nếu cần
  2. Duyệt đầu vào theo từng khối có kích thước bằng độ rộng vector
  3. Thực hiện phép so sánh hoặc phép toán số học song song trên tất cả lane
  4. Thu gọn hoặc lưu kết quả vector theo thuật toán
  5. Phần còn lại không vừa một vector đầy đủ được xử lý bằng đuôi scalar (scalar tail), tức vòng lặp thông thường hiện có
  • Khi đã quen với cấu trúc này, bạn có thể phân rã vòng lặp thông thường thành cùng 5 bước, khiến việc viết SIMD cũng đơn giản như vòng lặp scalar
  • Nếu không thể biểu diễn đơn giản bằng cấu trúc này, tạm thời bỏ qua việc áp dụng SIMD thường là lựa chọn phù hợp

Vòng lặp tìm kiếm thực tế của Ghostty

  • Ghostty tiêu thụ dữ liệu trong mảng code point đã giải mã cho đến khi gặp giá trị nhỏ hơn hoặc bằng 0xF
    • Phần lớn dữ liệu terminal là ký tự thông thường để xuất ra, nên chúng được xử lý theo nhóm
    • Vòng lặp tìm điểm kết thúc của đoạn có thể xuất tiếp theo nhanh nhất có thể
  • Bản cài đặt scalar ban đầu kiểm tra từng code point một
while (end < cps.len and cps[end] > 0xF) end += 1;
  • Bản cài đặt vector dùng vector thông thường, không dùng intrinsic riêng cho CPU, và dài hơn bản scalar 12 dòng mã
  • Mức tăng thông lượng kỳ vọng tương ứng với số lane của vector
    • ARM NEON và Apple Silicon: tối đa 4 lần
    • AVX2, được hầu hết CPU x86 hiện đại hỗ trợ: tối đa 8 lần
    • AVX-512, được một số CPU Intel và AMD Zen 4 trở lên hỗ trợ: tối đa 16 lần
  • Trên desktop Intel AVX2, tổng thông lượng đo từ đầu vào chương trình terminal đến trạng thái terminal cuối cùng nhanh hơn khoảng 5 lần
    • Không đạt được toàn bộ mức tăng tốc lý thuyết do các công việc xung quanh SIMD
  • Ký tự điều khiển C0 vẫn tồn tại sau 0xF, nhưng 0xF là ngưỡng được dùng trong đường mã Ghostty này
    • ESC và các chuỗi điều khiển khác được xử lý ở đường riêng

Bước 1: Broadcast hằng số

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • simd.lanes(u32) của Ghostty trả về số lượng u32 mà CPU đích có thể xử lý đồng thời
    • Mỗi giá trị được gọi là một lane
    • ARM trả về 4, AVX2 trả về 8, AVX-512 trả về 16
    • Nếu không có kích thước vector có thể dùng, trả về null để bỏ qua mã SIMD
  • @Vector(lanes, u32) tạo kiểu vector với số lane tương ứng
    • Nếu lanes là 8, một V chứa 8 giá trị u32 có thể xử lý song song
  • Phép so sánh vector cần cả hai phía đều là vector, nên @splat(0xF) sao chép 0xF vào mọi lane
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Thuật toán này không cần bộ tích lũy vector, nhưng các thuật toán khác có thể khởi tạo bộ tích lũy ở bước này

Bước 2: Duyệt từng vector một

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • Nếu lanes là 8, vòng lặp chỉ chạy khi còn ít nhất 8 giá trị và nạp 8 giá trị vào values
  • Sau mỗi lần lặp, tăng end không phải 1 mà bằng số lane
  • Vì phải nạp được một vector đầy đủ, nếu chỉ còn 5 giá trị thì không đọc vector 8 lane
  • Các giá trị không vừa vào vector sẽ được đuôi scalar ở bước 5 xử lý

Bước 3: So sánh song song trên mọi lane

const greater_than_threshold = values > threshold;
  • Vì cả values và threshold đều là vector, toán tử > so sánh từng lane tương ứng bằng một phép toán vector
  • Với 8 lane, 8 phép so sánh tương đương cps[end] > 0xF được thực hiện song song
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • Không có vòng lặp bên trong tường minh; kết quả là vector chứa boolean theo từng lane
  • Không chỉ so sánh, cấu trúc tương tự cũng áp dụng được cho các phép toán mà kiểu vector hỗ trợ như cộng, nhân, giá trị nhỏ nhất, giá trị lớn nhất
  • Bản thân phép so sánh là một phép toán vector, nhưng việc nạp vector, thu gọn kết quả và tìm lane thất bại cần thêm lệnh

Bước 4: Thu gọn kết quả vector

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) kết hợp mọi boolean bằng and để tạo một boolean duy nhất
  • Nếu mọi lane đều true, chuyển sang vector tiếp theo; nếu có bất kỳ lane nào false, tìm vị trí chính xác đã thất bại
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast chuyển vector boolean thành mặt nạ số nguyên, mỗi lane 1 bit
    • 1 nghĩa là giá trị lớn hơn 0xF
    • 0 nghĩa là phép so sánh thất bại
  • Khi đảo mặt nạ, phép so sánh thất bại trở thành 1, và @ctz đếm số bit 0 trước bit 1 đầu tiên
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • Trong ví dụ này, @ctz(~mask) trả về 3, đưa end đến lane số 3 nơi có ký tự điều khiển đầu tiên 0x0A
  • Thu gọn kết quả là phần khác nhau nhiều nhất giữa các thuật toán trong 5 bước
    • Tính tổng có thể thu gọn bộ tích lũy vector thành một số duy nhất
    • Chuyển đổi có thể lưu toàn bộ vector vào buffer đầu ra
    • Tìm kiếm này tạo bit mask để tìm vị trí của một lane cụ thể

Bước 5: Xử lý đuôi scalar

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Nếu độ dài đầu vào không phải bội số chính xác của độ rộng vector, vòng lặp scalar ban đầu sẽ xử lý phần còn lại
  • Sau vòng lặp vector 8 lane, có thể còn từ 0 đến 7 giá trị
  • Trên CPU nơi simd.lanes(u32) là null, đoạn SIMD bị bỏ qua và vòng lặp scalar xử lý toàn bộ đầu vào
  • Bản cài đặt ban đầu đồng thời đảm nhiệm xử lý phần còn lại và fallback tương thích
  • Vector thông thường chỉ loại bỏ cú pháp riêng theo CPU, chứ không loại bỏ việc sinh mã riêng theo CPU
    • Zig chuyển các phép toán vector thành tập lệnh được bật trên đích

Những gì tự động vector hóa bỏ lỡ

  • Trình biên dịch có thể tự động vector hóa mã đơn giản, chẳng hạn vòng lặp số học đều đặn không có luồng điều khiển phức tạp
  • Trước khi viết SIMD thủ công, hãy biên dịch phiên bản scalar với tùy chọn tối ưu hóa và kiểm tra mã được sinh ra
  • Các trình biên dịch production thường xuyên bỏ lỡ cơ hội vector hóa; tự động vector hóa đã được nghiên cứu trong nhiều thập kỷ, nhưng nghiên cứu gần đây cũng xuất phát từ vấn đề này
  • Nếu một vòng lặp quan trọng đến mức mức tăng tốc 5 lần có ý nghĩa, bạn có thể viết vector hóa tường minh để giữ hành vi dự đoán được
    • Có thể tránh việc một thay đổi mã không liên quan hoặc cập nhật trình biên dịch âm thầm biến vòng lặp vector trở lại thành vòng lặp scalar

Phạm vi SIMD mà lập trình viên nên nắm

  • Khi phát hiện một hot loop tìm kiếm, so sánh, đếm hoặc chuyển đổi lượng lớn dữ liệu liên tiếp, bạn nên cân nhắc xử lý theo độ rộng vector
  • SIMD thường ngày tuân theo dạng đều đặn: chuẩn bị hằng số, nạp vector, tính toán song song, thu gọn kết quả và đuôi scalar
  • Nếu ngôn ngữ hỗ trợ SIMD tốt, bạn có thể cải thiện hiệu năng mà không cần trực tiếp biết assembly hay chi tiết riêng của từng CPU
  • Mức độ cần thiết với mọi lập trình viên không phải là các kỹ thuật phức tạp kiểu simdutf/simdjson, mà là khả năng nhận ra cơ hội áp dụng SIMD và tận dụng cấu trúc chung

Bài viết liên quan

1 bình luận

 
GN⁺ 2 giờ trước
Ý kiến trên Hacker News

  • Bài viết hay, nhưng mở đầu bằng việc nói rằng SIMD dễ hiểu và dễ viết như vòng lặp for, rồi ngay ví dụ đầu tiên đã biến một dòng mã scalar thành 12 dòng thì không thuyết phục lắm
    Thà nói thẳng rằng SIMD khó, nhưng kết quả xứng đáng thì tốt hơn. Nếu nhắm tới người mới, ngay từ bước 1 không nên dùng các thuật ngữ riêng của SIMD như broadcast mà không giải thích; còn bước 5 giải thích xử lý phần đuôi scalar là một cách tổ chức tốt

    • SIMD và ví dụ đầu tiên không hẳn là khó, mà gần với một công việc phiền phức hơn nhiều
      Phải xác định phần cứng xử lý được bao nhiêu phần tử mỗi lần, gom công việc theo kích thước đó, bung kết quả ra lại, xử lý riêng các phần tử còn dư, và cả hằng số cũng phải tạo thành vector được nhân bản. Từng việc không khó, nhưng làm tăng khối lượng công việc nên trở nên rườm rà
    • Tôi từng học Parallel-C, được tạo ra trong làn sóng Transputer khoảng năm 1990; đó là một ngôn ngữ bổ sung tính năng lập trình song song vào C
      Tính năng tôi thích nhất là par(; ; ), nơi trình biên dịch có thể tự động song song hóa vòng lặp for dưới một số điều kiện biên nhất định
    • Tôi khá đúng là nhóm độc giả mục tiêu nên đọc thấy thú vị, nhưng độ khó tăng quá nhanh, cảm giác giống meme khét tiếng vẽ con cú
    • Bản thân SIMD thì đơn giản; cái gượng gạo là cách dùng phép toán song song dữ liệu trong ngôn ngữ scalar
    • Một trong những sai lầm lớn nhất trong giáo dục kỹ thuật là tuyên bố một chủ đề là đơn giản để xóa bỏ nỗi sợ về nó. Đừng nói là đơn giản, hãy thực sự cho thấy điều đó
      Nếu chủ đề thực sự phức tạp, cần chia nó thành các phần nhỏ hơn và đơn giản hơn, rồi sắp xếp trình tự tốt để người học leo được đường cong học tập dốc và thấy rằng nó đáng công

  • Lời khuyên tốt hơn là mọi người nên biết lập trình mảng. Tối ưu hóa SIMD phần lớn cần lối tư duy đó, còn các kỹ thuật chỉ chuyên cho packed SIMD thì bất ngờ là khá hiếm
    Lập trình mảng giúp trình biên dịch dễ tự động vector hóa, nên thường tạo ra mã có hiệu năng tốt dù không trực tiếp dùng SIMD

    • Lập trình mảng theo kiểu thực hiện tất cả phép so sánh trước rồi mới tìm lỗi đầu tiên không giúp nhiều khi đoạn chạy ngắn. Vì bản thân nó không cung cấp kết thúc sớm, có thể tốn nhiều thời gian cho các phép so sánh không cần thiết
    • Tôi không thích ngôn ngữ mã nguồn đóng và MATLAB cũng có nhiều khiếm khuyết, nhưng ở đại học, việc viết mã vector hóa hiệu quả cho mô phỏng số là rất tự nhiên
      Tôi không có nhiều kinh nghiệm, nhưng Julia có vẻ là thứ gần nhất với một ngôn ngữ hiện đại hơn, biểu đạt tốt hơn và có năng lực vector hóa tương tự

  • Mấy ngày gần đây tôi đã tối ưu các phép toán ma trận của một dự án tin sinh học bằng AVX-512, và rất hài lòng
    Với phần lớn ứng dụng, nút thắt là quá trình đọc tập dữ liệu lớn từ bộ nhớ, nên thay vì đọc lặp lại cho nhiều phép toán, có thể dùng thanh ghi AVX và kernel hợp nhất để xử lý tất cả trong một lần. Tăng tốc 5 lần là chuyện thường; tôi đã dùng intrinsic trực tiếp, nhưng nếu dùng crate wide thì các phép toán thông thường trở nên rất đơn giản: https://docs.rs/wide/latest/wide/

  • Tuyệt đại đa số lập trình viên hoàn toàn không cần học SIMD. Tôi thắc mắc vì sao lại khiến mọi người hiểu nhầm rằng mọi lập trình viên phải biết thứ này mới là lập trình viên thật sự

    • Ít nhất thì cũng đáng biết đến sự tồn tại và khả năng của SIMD. Là lập trình viên, hẳn bạn từng viết một hot loop cộng hoặc so sánh các giá trị đơn giản, và việc biết rằng trình biên dịch có thể tối ưu nó theo kiến trúc CPU đích sẽ hữu ích trong nhiều tình huống

  • Nên đổi tiêu đề thành “mọi người nên biết khi nào SIMD không được áp dụng”
    Trình biên dịch hiện đại vector hóa rất tốt, nhưng chỉ cần một giả định hoặc một nhánh phụ thuộc dữ liệu là có thể đột ngột lùi về mã scalar. Biết cách kiểm tra báo cáo tối ưu hóa của trình biên dịch có thể còn giá trị hơn cách viết SIMD

    • Giải pháp cho tự động vector hóa tệ là tự viết mã SIMD, nên tôi nghi ngờ liệu biết xem báo cáo tối ưu hóa có thật sự giá trị hơn không
      Nếu chỉ xác định được vấn đề thì rốt cuộc cũng chỉ dừng ở “tiếc thật”
    • Thực tế đã xảy ra đúng chuyện như vậy: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • Năm ngoái, khi làm một bộ tổng hợp âm thanh, tôi bắt đầu học SIMD trên x86 và ARM: https://github.com/seclorum/SIMDSynth
    Cấu trúc synth đa âm sắc, đa âm rất phù hợp để học các nguyên lý SIMD vì nó áp dụng cùng một xử lý lên nhiều luồng dữ liệu. Tuy nhiên, việc gỡ lỗi khá khó, tôi rất cần một trình mô phỏng giúp hiểu trạng thái của từng pipeline xử lý, và có lẽ việc khảo sát công cụ SIMD cũng sẽ cần một khoản đầu tư lớn nữa

  • Bài viết hay và tôi mong nhiều ngôn ngữ hơn hỗ trợ SIMD, nhưng khi hai ngôn ngữ phổ biến nhất không hỗ trợ SIMD nguyên sinh, cách nói “mọi lập trình viên nên biết” nghe hơi lạ

    • Khó có thể khẳng định các ngôn ngữ phổ biến nhất cũng là những ngôn ngữ được kỹ sư phần mềm — đối tượng của các bài như thế này — dùng nhiều nhất

  • Ngay cả khi không tự viết SIMD hoặc định giao cho AI làm, bạn vẫn nên biết tác vụ nào có thể được SIMD tăng tốc trên phần cứng nào. Nhờ đó có thể thiết kế thuật toán và cấu trúc mã sao cho có thể áp dụng SIMD
    Ảnh hưởng của phụ thuộc dữ liệu, chi phí khi tăng độ rộng phần tử vector và cách tránh, cách biến điều kiện và nhánh thành mask, các đặc tính như “không có lệnh chia” sẽ dễ nắm bắt hơn nhiều nếu bạn từng trực tiếp dùng SIMD dù chỉ một chút

    • Chưa nói đủ về việc SIMD nhanh hơn khi nào
      Nó hoạt động tốt khi kiểm tra hoặc chuyển đổi dữ liệu lớn, liên tục trong một lần, nhưng nếu cứ vài byte đầu vào lại phải đưa ra quyết định, nó có thể ngang hoặc chậm hơn cách scalar. SIMD không phải là nút tăng tốc ma thuật

  • Đây là video hữu ích trong đó Casey Muratori giải thích cách đội ngũ phát triển The Witness giải quyết một vấn đề hiệu năng thực tế bằng SIMD: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Bài nói rất hay nhưng video quá dài để giới thiệu cho người khác; sẽ tốt hơn nếu có một phiên bản bài viết tập trung vào phần cốt lõi
      Đây là một ví dụ tốt về tích hợp dọc vì hiệu năng: sau khi hiểu vì sao các abstraction thông thường tồn tại và vì sao chúng cần mang tính tổng quát, nó cho thấy trong một trường hợp sử dụng cụ thể, việc tích hợp dọc từ định nghĩa vấn đề đến SIMD có thể đem lại lợi ích lớn ra sao

  • Trước khi đi vào các tối ưu hóa vi mô như SIMD, cần nghiêm túc xem xét cấu trúc dữ liệu và mẫu truy cập trước
    Trước đây tôi từng áp dụng SIMD cho mã Zig, nhưng mô hình cấu trúc dữ liệu lại đi ngược hoàn toàn với hướng tối ưu hóa; chẳng khác nào lắp lốp đua hiệu năng cao cho một chiếc xe cũ nát có động cơ hỏng. Đó là kiểu tối ưu hóa vội vàng điển hình: không đo hiệu năng, cũng không cân nhắc vị trí cấp phát bộ nhớ
    Giờ đây tôi nhìn dữ liệu như các bảng SQL và thiết kế cấu trúc xoay quanh các khóa chính tiềm năng cùng mẫu truy cập. Trước đây tôi dùng cây trỏ tới các struct khác trên heap, nên phải gánh đủ nhược điểm của danh sách liên kết, phân mảnh từ nhiều vector trên heap, và chi phí tạo/hủy chậm; chỉ riêng Drop cũng đã chiếm một phần đáng kể thời gian chạy
    Vì cây lúc nào cũng có thể được tuyến tính hóa, tôi xem xét các mẫu truy cập/chèn, liệu đó có thực sự là cây hay là một loại đồ thị khác, và nên lưu bằng Vec hay một struct gồm nhiều Vec. Kết quả là mã nhanh hơn và đơn giản hơn; dữ liệu được gom vào các mảng đồng nhất, giúp trình biên dịch dễ tận dụng tối ưu hóa SIMD và cache L1 hơn, và khi cần cũng có thể tự viết mã SIMD không rẽ nhánh
    Tài liệu liên quan: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Muốn làm cho hot loop nhanh hơn bằng SIMD thì bố trí dữ liệu và cấu trúc thân thiện với cache là then chốt
      Ở các đoạn nghẽn cổ chai thực sự, cần tránh cấp phát bộ nhớ, tra cứu bảng hàm ảo và tham chiếu gián tiếp quá mức. Ngay cả vector của C++ cũng không phải lúc nào là lựa chọn tốt nhất nếu nó có thể kích hoạt các lần cấp phát ngoài dự kiến
    • Đây là vấn đề tôi luôn gặp với tư cách kỹ sư hiệu năng. Hiệu năng bắt đầu từ kiến trúc, và với các hot path có bố trí dữ liệu kém thì lượng hiệu năng có thể vắt ra luôn có giới hạn
      Ngược lại, mã theo hướng dữ liệu gần như luôn hỗ trợ threading và SIMD một cách dễ dàng
    • Cơ bản hơn nữa, mẫu truy cập bộ nhớ mới là quan trọng
      Điều thú vị là cuối cùng mã CPU cũng được viết theo phong cách GPU, và một cách làm là dùng struct của các mảng kiểu Parquet thay vì mảng các đối tượng
    • Bảng là cách triển khai đồ thị tổng quát một cách hiệu quả; chừng nào không thể chuyên biệt hóa đồ thị, đó là biểu diễn tốt nhất mà tôi biết