Thu 16 Jun 2022 15:30 - 15:50 at Macaw - Storage Chair(s): Albert Cohen

This paper shows how to generate code that efficiently converts sparse tensors between disparate storage formats (data layouts) like CSR, DIA, ELL, and many others. We decompose sparse tensor conversion into three logical phases: coordinate remapping, analysis, and assembly. We then develop a language that precisely describes how different formats group together and order a tensor’s nonzeros in memory. This enables a compiler to emit code that performs complex reorderings (remappings) of nonzeros when converting between formats. We additionally develop a query language that can extract complex statistics about sparse tensors, and we show how to emit efficient analysis code that computes such queries. Finally, we define an abstract interface that captures how data structures for storing a tensor can be efficiently assembled given specific statistics about the tensor. Disparate formats can implement this common interface, thus letting a compiler emit optimized sparse tensor conversion code for arbitrary combinations of a wide range of formats without hard-coding for any specific one.

Our evaluation shows that our technique generates sparse tensor conversion routines with performance between 0.99 and 2.2$\times$ that of hand-optimized implementations. By emitting code that avoids materializing temporaries, our technique also outperforms a widely used sparse linear algebra library, SPARSKIT, by 3.2$\times$ and 4.0$\times$ respectively for conversions from the CSC and COO formats to DIA.

Thu 16 Jun

Displayed time zone: Pacific Time (US & Canada) change

15:30 - 16:50
StorageSIGPLAN Track at Macaw
Chair(s): Albert Cohen Google
15:30
20m
Talk
(PLDI 2020) Automatic Generation of Efficient Sparse Tensor Format Conversion Routines
SIGPLAN Track
Stephen Chou Massachusetts Institute of Technology, Fredrik Kjolstad Stanford University, Saman Amarasinghe MIT CSAIL
15:50
20m
Talk
(PLDI 2020) NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey
SIGPLAN Track
Naama Ben-David Carnegie Mellon University, USA, Guy E. Blelloch Carnegie Mellon University, Michal Friedman Technion, Israel, Erez Petrank Technion, Israel, Yuanhao Wei Carnegie Mellon University, USA
16:10
20m
Talk
(PLDI 2021) Mirror: Making Lock-Free Data Structures Persistent
SIGPLAN Track
Michal Friedman Technion, Israel, Erez Petrank Technion, Israel, Pedro Ramalhete Cisco Systems
16:30
20m
Talk
(POPL 2021) Provably Space Efficient Parallel Functional Programming
SIGPLAN Track
Jatin Arora Carnegie Mellon University, Sam Westrick Carnegie Mellon University, Umut A. Acar Carnegie Mellon University