Giriş

Seyrekliği (sıkıcı) bir uygulama ayrıntısı yerine bir özellik olarak ele almak, derleyicinin seyrekleştiricisinin1 seyrek kodu otomatik olarak oluşturmasına olanak tanır. Bu kavram, lineer cebir için [Bik96] tarafından MT1'de öncülük edilmiş ve Sparse Tensor Algebra Compiler (TACO) projesinde [Kjolstad17,Kjolstad20] tarafından tensör cebiri için resmileştirilmiştir.

SparseTensor lehçesi, seyrek tensör türlerini MLIR derleyici altyapısında birinci sınıf vatandaşlar yapmak için gereken tüm özellikleri, türleri, işlemleri ve geçişleri destekler. Bu dil, seyrek tensör türleri üzerindeki üst düzey işlemler ile konumlar, koordinatlar ve değerlerden oluşan gerçek seyrek depolama şemaları üzerindeki alt düzey işlemler arasında bir köprü oluşturur. Daha düşük düzeydeki destek, tamamen oluşturulmuş koddan oluşabilir veya küçük bir seyrek çalışma zamanı destek kitaplığı aracılığıyla sağlanabilir.

MLIR uygulaması [Biketal22], TACO'nun temelini oluşturan "seyrek yineleme teorisini" yakından takip eder. Derleyicide, Linalg lehçesindeki (MLIR'nin tensör dizin gösterimi) her tensör ifadesi için bir yeniden yazma kuralı vardır: Tensörün her düzeyinin seyrekliği, düzey türleriyle (ör. yoğun, sıkıştırılmış, tekil) ve düzeylerdeki sıranın belirtilmesiyle gösterilir (bu düzey türleriyle ilgili ayrıntılı tartışmalar ve olası uzantılar için [Chou18] adlı makaleye bakın). Girişteki her tensör ifadesi için derleyici önce koordinatların her tensörün seviyelerine göre sıralanmasını yansıtan, topolojik olarak sıralanmış bir yineleme grafiği oluşturur. Bu, tüm tensörlerin doğal seviye-koordinat sırasına göre ziyaret edilmesini sağlar. Ardından, yineleme kafesleri topolojik sıraya göre her dizin için oluşturulur. Her yineleme-kafes noktası, tensör koordinatlarının birleşimi ve bu birleşim için değerlendirilmesi gereken bir tensör (alt) ifadesinden oluşur. Kafes içinde, yineleme noktaları koordinatların tükenme şekline göre sıralanır. Bu nedenle, bu yineleme kafesleri gerçek seyrek kod oluşturmayı sağlar. Bu, yineleme kafeslerinden for döngüleri, while döngüleri ve if ifadeleri kombinasyonlarına yönelik nispeten basit bir bire bir eşlemedir. Başlatılmamış öğeleri somutlaştıran seyrek tensör çıkışları, tüm paralel döngüler en dıştaysa doğrudan eklemelerle, mümkün olduğunda ise 1 boyutlu erişim kalıbı genişletme (diğer adıyla çalışma alanı) üzerinden dolaylı olarak geçen eklemelerle işlenir [Gustavson72,Bik96,Kjolstad19].

  • [Bik96] Aart J.C. Bik. Seyrek matris hesaplamaları için derleyici desteği. Doktora tezi, Leiden Üniversitesi, Mayıs 1996.

  • [Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng ve Fredrik Kjolstad. MLIR'de seyrek tensör hesaplamaları için derleyici desteği. ACM Transactions on Architecture and Code Optimization, Haziran 2022. https://dl.acm.org/doi/10.1145/3544559 adresine bakın.

  • [Chou18] Stephen Chou, Fredrik Berg Kjolstad ve Saman Amarasinghe. Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of the ACM on Programming Languages, Ekim 2018.

  • [Chou20] Stephen Chou, Fredrik Berg Kjolstad ve Saman Amarasinghe. Verimli Seyrek Tensor Biçimi Dönüştürme Rutinlerinin Otomatik Olarak Oluşturulması. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Haziran 2020.

  • [Gustavson72] Fred G. Gustavson. Seyrek doğrusal denklem sistemlerini çözmeye yönelik bazı temel teknikler. In Sparse Matrices and Their Applications, sayfalar 41–52. Plenum Press, New York, 1972.

  • [Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato ve Saman Amarasinghe. Tensor Cebir Derleyicisi. Proceedings of the ACM on Programming Languages, Ekim 2017.

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

  • [Kjolstad20] Fredrik Berg Kjolstad. Seyrek Tensor Cebir Derlemesi. Doktora tezi, MIT, Şubat 2020.

Katkıda bulunmak ister misiniz? İşte bazı iyi ilk sorunlar.

  1. Bu tür bir geçişi ifade etmek için artık "sparsifier" terimini, yaygın olarak kullanılan "sparse compiler" terimine tercih ettiğimizi lütfen unutmayın. Bunun nedeni, sparsifier geçişinin ayrı bir derleyici olmadığını, MLIR derleyici altyapısıyla oluşturulan herhangi bir derleyici hattının ayrılmaz bir parçası olması gerektiğini netleştirmektir. ↩