Tratar a esparsidade como uma propriedade em vez de um detalhe de implementação (tedioso) permite que o sparsifier do compilador1 gere código esparso automaticamente. O conceito foi pioneiro para álgebra linear por [Bik96] em MT1 e formalizado para álgebra de tensores por [Kjolstad17,Kjolstad20] no projeto Sparse Tensor Algebra Compiler (TACO).
O dialeto SparseTensor oferece suporte a todos os atributos, tipos, operações e transmissões necessários para tornar os tipos de tensores esparsos cidadãos de primeira classe na infraestrutura do compilador MLIR. O dialeto forma uma ponte entre operações de alto nível em tipos de tensores esparsos e operações de nível mais baixo em esquemas de armazenamento esparso reais, que consistem em posições, coordenadas e valores. O suporte de nível mais baixo pode consistir em código totalmente gerado ou ser fornecido por uma pequena biblioteca de suporte de tempo de execução esparsa.
A implementação do MLIR [Biketal22] segue de perto a "teoria da iteração esparsa" que forma a base do TACO. O compilador tem uma regra de reescrita para cada expressão de tensor no dialeto Linalg (notação de índice de tensor do MLIR): a esparsidade de cada nível de um tensor é indicada pelos tipos de nível (por exemplo, denso, compactado, singleton) e uma especificação da ordem nos níveis. Consulte [Chou18] para discussões detalhadas e possíveis extensões desses tipos de nível. Para cada expressão de tensor na entrada, o compilador primeiro cria um gráfico de iteração classificado topologicamente que reflete a ordenação das coordenadas em relação aos níveis de cada tensor. Isso garante que todos os tensores sejam visitados na ordem natural de nível-coordenada. Em seguida, as treliças de iteração são construídas para cada índice em ordem topológica. Cada ponto de rede de iteração consiste em uma conjunção de coordenadas de tensor e uma expressão (sub)de tensor que precisa ser avaliada para essa conjunção. Na rede, os pontos de iteração são ordenados de acordo com a forma como as coordenadas são esgotadas. Assim, essas estruturas de repetição geram código esparso, um mapeamento relativamente simples de um para um de estruturas de repetição para combinações de loops for, while e instruções if. Saídas de tensores esparsos que materializam não inicializados são processadas com inserções diretas, se todos os loops paralelos forem externos, ou inserções que indiretamente passam por uma expansão de padrão de acesso unidimensional (também conhecido como espaço de trabalho), quando possível [Gustavson72,Bik96,Kjolstad19].
[Bik96] Aart J.C. Bik. Suporte do compilador para cálculos de matriz esparsa. Tese de doutorado, Universidade de Leiden, maio de 1996.
[Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng e Fredrik Kjolstad. Suporte do compilador para cálculos de tensores esparsos em MLIR. ACM Transactions on Architecture and Code Optimization, junho de 2022. Consulte: https://dl.acm.org/doi/10.1145/3544559
[Chou18] Stephen Chou, Fredrik Berg Kjolstad e Saman Amarasinghe. Abstração de formato para compiladores de álgebra de tensores esparsos. Proceedings of the ACM on Programming Languages, outubro de 2018.
[Chou20] Stephen Chou, Fredrik Berg Kjolstad e Saman Amarasinghe. Geração automática de rotinas eficientes de conversão de formato de tensor esparso. Anais da 41ª Conferência da ACM SIGPLAN sobre Design e Implementação de Linguagens de Programação, junho de 2020.
[Gustavson72] Fred G. Gustavson. Algumas técnicas básicas para resolver sistemas esparsos de equações lineares. Em Sparse Matrices and Their Applications, páginas 41–52. Plenum Press, Nova York, 1972.
[Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato e Saman Amarasinghe. O compilador de álgebra de tensores. Anais da ACM sobre linguagens de programação, outubro de 2017.
[Kjolstad19] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil e Saman Amarasinghe. Tensor Algebra Compilation with Workspaces, Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization, 2019.
[Kjolstad20] Fredrik Berg Kjolstad. Compilação de álgebra de tensores esparsos. Tese de doutorado, MIT, fevereiro de 2020.
Gostaria de contribuir? Confira algumas boas primeiras questões.
-
Agora preferimos o termo "sparsifier" em vez de "compilador esparso", que também é usado com frequência, para se referir a essa transmissão. Assim, fica claro que a transmissão do sparsifier não é um compilador separado, mas deve ser parte integrante de qualquer pipeline de compilador criado com a infraestrutura do compilador MLIR. ↩