Thiết kế thuật toán SIMD từ đầu

 (mcyoung.xyz)
2 điểm bởi GN⁺ 2023-11-29 | 1 bình luận | Chia sẻ qua WhatsApp

Thiết kế thuật toán SIMD

  • Giải thích về tối ưu hóa SIMD: SIMD là viết tắt của single instruction, multiple data, và cần suy nghĩ như một nhà thiết kế mạch.
  • SIMD thường được nhắc đến trong hiệu năng và HPC (điện toán hiệu năng cao), nhưng không phải là chủ đề quen thuộc với người mới bắt đầu.
  • Trong hầu hết ngôn ngữ lập trình, API lập trình SIMD khá khó sử dụng.
  • Thuật toán SIMD khó hiểu nếu tiếp cận bằng tư duy lập trình thủ tục; lập trình hàm có thể hữu ích.
  • Bài viết nói về vb64, một triển khai codec base64 sử dụng thư viện std::simd của Rust.

Giới hạn vật lý

  • Máy tính tồn tại trong thế giới thực và bị ràng buộc bởi các định luật vật lý.
  • Trong thời kỳ đầu của điện toán, có thể cải thiện hiệu năng bằng cách mua một máy tính mới.
  • Hiệu ứng Dennard scaling đã sụp đổ, khiến transistor nhỏ hơn đồng nghĩa với tiêu thụ nhiều điện năng hơn.
  • Việc tăng số lượng lõi trở thành xu hướng mới. Có thể cải thiện hiệu năng CPU bằng đa luồng, nhưng sẽ phát sinh overhead đồng bộ hóa.

Sự chậm chạp của mã thủ tục

  • Lõi máy tính hiện đại không thực thi mã theo từng dòng.
  • Thông qua song song mức lệnh, nhiều phép toán có thể được thực hiện đồng thời nếu không có phụ thuộc dữ liệu.
  • Mức độ song song tăng lên khi trình biên dịch có thể giải quyết các rủi ro dữ liệu.
  • Nhánh và các thao tác bộ nhớ gây ra stall, làm mã chạy chậm hơn.

SIMD và lane

  • SIMD và vector thường được dùng gần như đồng nghĩa.
  • Lệnh SIMD sử dụng vector, tức mảng số có kích thước cố định, làm đơn vị cơ bản.
  • Mỗi phần tử của vector được gọi là một lane, và vector SIMD thường có kích thước nhỏ.

Các phép toán trên vector thực tế

  • Vector SIMD cung cấp các phép toán phức tạp hơn thanh ghi thông thường.
  • Thanh ghi vector hỗ trợ nhiều phép toán như thao tác bit, số học theo từng lane, so sánh theo từng lane, shuffle, v.v.
  • Shuffle rất quan trọng trong lập trình SIMD để di chuyển dữ liệu vào đúng vị trí.

Hàm nội tại và lựa chọn lệnh

  • Khi viết mã SIMD, các phép toán khả dụng khác nhau tùy theo kiến trúc.
  • Trình biên dịch giải bài toán lựa chọn lệnh, tức quyết định sẽ ánh xạ phép toán người dùng yêu cầu sang lệnh máy nào.
  • Viết mã SIMD portable rất phức tạp, nhưng có thể tạo mã tối ưu cho nhiều bộ xử lý khác nhau thông qua phát hiện tính năng lúc chạy.

Phân tích cú pháp bằng SIMD

  • Có thể dùng SIMD để phân tích cú pháp văn bản, và tốc độ có thể rất cao.
  • Có thể lấy việc triển khai giải mã base64 bằng SIMD làm ví dụ.
  • Loại bỏ mọi nhánh là trọng tâm của quá trình tạo ra phiên bản SIMD.

Ý kiến của GN⁺

Điểm quan trọng nhất của bài viết này là lập trình SIMD, khác với cách lập trình thủ tục truyền thống, có thể cải thiện hiệu năng bằng cách xử lý dữ liệu song song. SIMD rất quan trọng trong lĩnh vực điện toán hiệu năng cao, và việc hiểu cách sử dụng SIMD hiệu quả trong các ngôn ngữ lập trình hiện đại như Rust có thể là một chủ đề rất thú vị với kỹ sư phần mềm. Lý do là thông qua SIMD, có thể học được cách tối ưu hóa các thuật toán phức tạp và vượt qua những giới hạn của phần cứng thực tế.

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-11-29
Ý kiến trên Hacker News
  • Một bài viết rất hay để xem các trường hợp sử dụng SIMD portable. Khi thử tái lập benchmark trên hệ thống Zen 3, tôi cũng xác nhận được cùng mức tăng tốc. Trên M1 mbp, mức cải thiện hiệu năng tăng dần lên tối đa 2 lần với độ dài đầu vào 110 byte. Dù lợi ích ít hơn so với x86_64, có thể xem là đã đạt được mục tiêu. Tuy vậy, điều này cũng cho thấy Rust vẫn có phần khá bất tiện trong các công việc liên quan đến SIMD và con trỏ, cũng như kỹ thuật tối ưu hiệu năng nói chung.
  • Đôi khi thật đáng kinh ngạc khi dù đã cố gắng lập trình tốt nhất có thể bằng C++, phiên bản dùng SIMD vẫn cho hiệu năng nhanh hơn hơn 10 lần. Độ portable của mã sẽ kém đi, nhưng vẫn mong compiler làm tốt hơn ở mảng auto-vectorization. Cũng hy vọng ngôn ngữ có thêm hỗ trợ thông qua annotation để có thể sắp xếp lại thứ tự của một số phép toán cụ thể.
  • Có ý kiến chỉ ra rằng compiler đã không thể tối ưu một triển khai popcount cụ thể thành một lệnh đơn, trong khi với các triển khai khác thì điều đó đôi khi vẫn làm được.
  • _mm256_cvtps_epu32 không phải là lệnh của AVX2 mà là của AVX-512; trong AVX1, số nguyên tồn tại ở dạng có dấu và lệnh tương ứng là _mm256_cvtps_epi32.
  • Tôi rất thích minimap nhỏ ở bên phải.
  • ISPC được đánh giá là tốt hơn việc thêm SIMD vào C++ hay Rust. Ngoài ra, nó còn hỗ trợ dynamic dispatch, vốn là tính năng khá khó để tự triển khai.
  • Có người đặt câu hỏi so với fastbase64 thì thế nào, đồng thời bày tỏ muốn chia sẻ sự lạc quan của tác giả về các thư viện SIMD portable.
  • Một bài viết tuyệt vời, để lại cảm giác rằng bản thân có lẽ sẽ không bao giờ trở nên thông minh đến mức này.
  • Dù ví dụ đầu tiên về triển khai popcnt không được vector hóa bị nhận xét là tạo ra "đoạn mã thành thật mà nói là lố bịch", nhưng nếu biên dịch ở chế độ release cho CPU đích native thì có vẻ hàm đó vẫn được vector hóa khá ổn.
  • Có người đặt câu hỏi đâu là điểm bất thường gây ngạc nhiên nhất khi kiểm tra mã được sinh ra từ Rust Simd.