Pengantar

Memperlakukan kejarangan sebagai properti, bukan detail implementasi (yang membosankan), memungkinkan sparsifier1 compiler membuat kode jarang secara otomatis. Konsep ini dipelopori untuk aljabar linear oleh [Bik96] di MT1 dan diformalisasi ke aljabar tensor oleh [Kjolstad17,Kjolstad20] dalam project Sparse Tensor Algebra Compiler (TACO).

Dialek SparseTensor mendukung semua atribut, jenis, operasi, dan penerusan yang diperlukan untuk menjadikan jenis tensor jarang sebagai warga kelas satu dalam infrastruktur compiler MLIR. Dialek ini membentuk jembatan antara operasi tingkat tinggi pada jenis tensor jarang dan operasi tingkat lebih rendah pada skema penyimpanan jarang yang sebenarnya yang terdiri dari posisi, koordinat, dan nilai. Dukungan tingkat yang lebih rendah dapat terdiri dari kode yang sepenuhnya dihasilkan atau dapat disediakan melalui library dukungan runtime yang kecil dan jarang.

Implementasi MLIR [Biketal22] mengikuti dengan cermat 'sparse iteration theory' yang membentuk dasar TACO. Compiler memiliki aturan penulisan ulang untuk setiap ekspresi tensor dalam dialek Linalg (notasi indeks tensor MLIR): kejarangan setiap tingkat tensor ditunjukkan oleh jenis tingkat (misalnya, padat, terkompresi, singleton) dan spesifikasi urutan pada tingkat (lihat [Chou18] untuk pembahasan mendalam dan kemungkinan ekstensi untuk jenis tingkat ini). Untuk setiap ekspresi tensor dalam input, compiler terlebih dahulu membuat grafik iterasi yang diurutkan secara topologi yang mencerminkan pengurutan koordinat sehubungan dengan level setiap tensor; hal ini memastikan bahwa semua tensor dikunjungi dalam urutan koordinat level alami. Selanjutnya, kisi-kisi iterasi dibuat untuk setiap indeks dalam urutan topologi. Setiap titik kisi-iterasi terdiri dari konjungsi koordinat tensor dan subekspresi tensor yang perlu dievaluasi untuk konjungsi tersebut. Dalam kisi, titik iterasi diurutkan sesuai dengan cara koordinat dihabiskan. Dengan demikian, kisi-kisi iterasi ini mendorong pembuatan kode jarang yang sebenarnya, pemetaan satu-ke-satu yang relatif mudah dari kisi-kisi iterasi ke kombinasi loop for, loop while, dan pernyataan if. Output tensor jarang yang terwujud tidak diinisialisasi ditangani dengan penyisipan langsung, jika semua loop paralel adalah yang terluar, atau penyisipan yang secara tidak langsung melalui perluasan pola akses 1 dimensi (alias ruang kerja), jika memungkinkan [Gustavson72,Bik96,Kjolstad19].

  • [Bik96] Aart J.C. Bik. Dukungan Compiler untuk Komputasi Matriks Sparse. Tesis PhD, Leiden University, Mei 1996.

  • [Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng, dan Fredrik Kjolstad. Dukungan Compiler untuk Komputasi Tensor Sparse di MLIR. ACM Transactions on Architecture and Code Optimization, Juni 2022. Lihat: https://dl.acm.org/doi/10.1145/3544559

  • [Chou18] Stephen Chou, Fredrik Berg Kjolstad, dan Saman Amarasinghe. Abstraksi Format untuk Compiler Aljabar Tensor Sparse. Prosiding ACM on Programming Languages, Oktober 2018.

  • [Chou20] Stephen Chou, Fredrik Berg Kjolstad, dan Saman Amarasinghe. Pembuatan Otomatis Rutin Konversi Format Tensor Sparse yang Efisien. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Juni 2020.

  • [Gustavson72] Fred G. Gustavson. Beberapa teknik dasar untuk menyelesaikan sistem persamaan linear yang jarang. Dalam Sparse Matrices and Their Applications, halaman 41–52. Plenum Press, New York, 1972.

  • [Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato, dan Saman Amarasinghe. Tensor Algebra Compiler. Proceedings of the ACM on Programming Languages, Oktober 2017.

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

  • [Kjolstad20] Fredrik Berg Kjolstad. Kompilasi Aljabar Tensor Sparse. PhD thesis, MIT, Februari 2020.

Ingin berkontribusi? Berikut beberapa masalah pertama yang baik.

  1. Perhatikan bahwa kami sekarang lebih memilih istilah 'sparsifier' daripada terminologi 'sparse compiler' yang juga umum digunakan untuk merujuk pada proses tersebut guna memperjelas bahwa proses sparsifier bukanlah compiler terpisah, tetapi harus menjadi bagian integral dari pipeline compiler apa pun yang dibangun dengan infrastruktur compiler MLIR. ↩