Giới thiệu

Việc coi độ thưa thớt là một thuộc tính thay vì một chi tiết triển khai (tẻ nhạt) cho phép trình làm thưa thớt 1 của trình biên dịch tự động tạo mã thưa thớt. Khái niệm này được [Bik96] tiên phong cho đại số tuyến tính trong MT1 và được [Kjolstad17,Kjolstad20] chính thức hoá thành đại số tensor trong dự án Trình biên dịch đại số tensor thưa thớt (TACO).

Phương ngữ SparseTensor hỗ trợ tất cả các thuộc tính, loại, thao tác và lượt truyền cần thiết để tạo các loại tensor thưa thớt là các thành phần hạng nhất trong cơ sở hạ tầng trình biên dịch MLIR. Ngôn ngữ này tạo thành cầu nối giữa các thao tác cấp cao trên các loại tensor thưa và các thao tác cấp thấp hơn trên các lược đồ lưu trữ thưa thực tế bao gồm vị trí, toạ độ và giá trị. Hỗ trợ ở cấp thấp hơn có thể bao gồm mã được tạo đầy đủ hoặc có thể được cung cấp thông qua một thư viện hỗ trợ thời gian chạy thưa thớt nhỏ.

Việc triển khai MLIR [Biketal22] tuân theo chặt chẽ "lý thuyết lặp lại thưa thớt" tạo thành nền tảng của TACO. Trình biên dịch có một quy tắc viết lại cho từng biểu thức tensor trong phương ngữ Linalg (ký hiệu chỉ mục tensor của MLIR): độ thưa thớt của mỗi cấp của tensor được biểu thị bằng các loại cấp (ví dụ: dày đặc, nén, đơn lẻ) và một quy cách về thứ tự trên các cấp (xem [Chou18] để biết các cuộc thảo luận chuyên sâu và các tiện ích có thể có cho các loại cấp này). Đối với mỗi biểu thức tenxơ trong đầu vào, trình biên dịch trước tiên sẽ tạo một biểu đồ lặp được sắp xếp theo cấu trúc liên kết, phản ánh thứ tự của các toạ độ theo cấp độ của từng tenxơ; điều này đảm bảo rằng tất cả các tenxơ đều được truy cập theo thứ tự tự nhiên của toạ độ cấp. Tiếp theo, các lưới lặp được tạo cho mọi chỉ mục theo thứ tự liên kết. Mỗi điểm lặp lại-lưới bao gồm một liên từ của các toạ độ tensor và một biểu thức (phụ) tensor cần được đánh giá cho liên từ đó. Trong mạng tinh thể, các điểm lặp được sắp xếp theo cách các toạ độ được sử dụng hết. Do đó, các lưới lặp này thúc đẩy quá trình tạo mã thưa thực tế, một quá trình ánh xạ tương đối đơn giản từ lưới lặp đến các tổ hợp vòng lặp for, vòng lặp while và câu lệnh if. Đầu ra của tensor thưa thớt hiện thực hoá chưa được khởi tạo được xử lý bằng cách chèn trực tiếp (nếu tất cả các vòng lặp song song đều nằm ngoài cùng) hoặc chèn gián tiếp thông qua việc mở rộng mẫu truy cập 1 chiều (còn gọi là không gian làm việc), nếu có thể [Gustavson72,Bik96,Kjolstad19].

  • [Bik96] Aart J.C. Bik. Hỗ trợ trình biên dịch cho các phép tính ma trận thưa. Luận án tiến sĩ, Đại học Leiden, tháng 5 năm 1996.

  • [Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng và Fredrik Kjolstad. Hỗ trợ trình biên dịch cho các phép tính toán tensor thưa trong MLIR. ACM Transactions on Architecture and Code Optimization, tháng 6 năm 2022. Xem tại: https://dl.acm.org/doi/10.1145/3544559

  • [Chou18] Stephen Chou, Fredrik Berg Kjolstad và Saman Amarasinghe. Trừu tượng hoá định dạng cho trình biên dịch đại số tensor thưa. Proceedings of the ACM on Programming Languages (Kỷ yếu của ACM về Ngôn ngữ lập trình), tháng 10 năm 2018.

  • [Chou20] Stephen Chou, Fredrik Berg Kjolstad và Saman Amarasinghe. Tự động tạo các quy trình chuyển đổi định dạng Tensor thưa thớt hiệu quả. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June, 2020.

  • [Gustavson72] Fred G. Gustavson. Một số kỹ thuật cơ bản để giải hệ phương trình tuyến tính thưa. Trong Sparse Matrices and Their Applications (Ma trận thưa và các ứng dụng của ma trận thưa), trang 41–52. Plenum Press, New York, 1972.

  • [Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato và Saman Amarasinghe. Trình biên dịch đại số Tensor. Proceedings of the ACM on Programming Languages, tháng 10 năm 2017.

  • [Kjolstad19] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil và Saman Amarasinghe. Tensor Algebra Compilation with Workspaces, Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization, 2019.

  • [Kjolstad20] Fredrik Berg Kjolstad. Biên dịch đại số tensor thưa thớt. Luận án tiến sĩ, MIT, tháng 2 năm 2020.

Bạn có muốn đóng góp không? Sau đây là một số vấn đề phù hợp cho người mới bắt đầu.

  1. Xin lưu ý rằng hiện tại, chúng tôi ưu tiên dùng thuật ngữ "trình làm thưa" thay vì thuật ngữ "trình biên dịch thưa" cũng thường được dùng để chỉ một lượt như vậy nhằm làm rõ rằng lượt trình làm thưa không phải là một trình biên dịch riêng biệt, mà phải là một phần không thể thiếu của bất kỳ quy trình biên dịch nào được tạo bằng cơ sở hạ tầng trình biên dịch MLIR. ↩