Considerare la sparsità come una proprietà anziché come un dettaglio di implementazione (noioso) consente allo sparsificatore del compilatore1 di generare automaticamente codice sparso. Il concetto è stato introdotto per l'algebra lineare da [Bik96] in MT1 e formalizzato per l'algebra tensoriale da [Kjolstad17,Kjolstad20] nel progetto Sparse Tensor Algebra Compiler (TACO).
Il dialetto SparseTensor supporta tutti gli attributi, tipi, operazioni e passaggi necessari per rendere i tipi di tensore sparsi cittadini di prima classe all'interno dell'infrastruttura del compilatore MLIR. Il dialetto costituisce un ponte tra le operazioni di alto livello sui tipi di tensore sparso e le operazioni di basso livello sugli schemi di archiviazione sparsi effettivi costituiti da posizioni, coordinate e valori. Il supporto di livello inferiore può consistere in codice completamente generato o può essere fornito tramite una piccola libreria di supporto runtime sparsa.
L'implementazione di MLIR [Biketal22] segue da vicino la "teoria dell'iterazione sparsa" che costituisce la base di TACO. Il compilatore ha una regola di riscrittura per ogni espressione tensoriale nel dialetto Linalg (notazione dell'indice tensoriale di MLIR): la sparsità di ogni livello di un tensore è indicata dai tipi di livello (ad es. denso, compresso, singleton) e da una specifica dell'ordine sui livelli (vedi [Chou18] per discussioni approfondite e possibili estensioni di questi tipi di livello). Per ogni espressione tensoriale nell'input, il compilatore crea innanzitutto un grafico di iterazione ordinato topologicamente che riflette l'ordinamento delle coordinate rispetto ai livelli di ogni tensore; in questo modo tutti i tensori vengono visitati nell'ordine naturale di livello-coordinate. Successivamente, vengono costruite griglie di iterazione per ogni indice in ordine topologico. Ogni punto del reticolo di iterazione è costituito da una congiunzione di coordinate tensoriali e da un'espressione (secondaria) tensoriale che deve essere valutata per quella congiunzione. All'interno del reticolo, i punti di iterazione sono ordinati in base al modo in cui le coordinate vengono esaurite. Pertanto, questi reticoli di iterazione guidano la generazione effettiva di codice sparso, una mappatura uno a uno relativamente semplice dai reticoli di iterazione alle combinazioni di cicli for, cicli while e istruzioni if. Gli output dei tensori sparsi che materializzano non inizializzati vengono gestiti con inserimenti diretti, se tutti i loop paralleli sono esterni, o con inserimenti che passano indirettamente attraverso un'espansione del pattern di accesso unidimensionale (ovvero spazio di lavoro), ove possibile [Gustavson72,Bik96,Kjolstad19].
[Bik96] Aart J.C. Bik. Supporto del compilatore per i calcoli della matrice sparsa. Tesi di dottorato, Leiden University, maggio 1996.
[Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng e Fredrik Kjolstad. Supporto del compilatore per i calcoli dei tensori sparsi in MLIR. ACM Transactions on Architecture and Code Optimization, giugno 2022. Vedi: https://dl.acm.org/doi/10.1145/3544559
[Chou18] Stephen Chou, Fredrik Berg Kjolstad e Saman Amarasinghe. Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of the ACM on Programming Languages, ottobre 2018.
[Chou20] Stephen Chou, Fredrik Berg Kjolstad e Saman Amarasinghe. Generazione automatica di routine di conversione del formato Efficient Sparse Tensor. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, giugno 2020.
[Gustavson72] Fred G. Gustavson. Alcune tecniche di base per risolvere sistemi di equazioni lineari sparse. In Sparse Matrices and Their Applications, pagine 41-52. Plenum Press, New York, 1972.
[Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato e Saman Amarasinghe. Il compilatore di algebra tensoriale. Proceedings of the ACM on Programming Languages, ottobre 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. Compilazione dell'algebra dei tensori sparsi. Tesi di dottorato, MIT, febbraio 2020.
Vuoi contribuire? Ecco alcuni good first issues.
-
Tieni presente che ora preferiamo il termine "sparsifier" rispetto alla terminologia "sparse compiler" utilizzata anche comunemente per fare riferimento a un passaggio di questo tipo, per chiarire che il passaggio sparsifier non è un compilatore separato, ma dovrebbe essere parte integrante di qualsiasi pipeline di compilazione creata con l'infrastruttura del compilatore MLIR. ↩