Write a Blog >>
PLDI 2020
Mon 15 - Fri 19 June 2020
Thu 18 Jun 2020 13:00 - 13:20 at PLDI Research Papers live stream - Code Generation Chair(s): Fan Long

This paper shows how to generate code that efficiently converts sparse tensors between disparate storage formats (data layouts) such as 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 lets a compiler emit code that performs complex remappings of nonzeros when converting between formats. We also develop a query language that can extract 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 many formats without hard-coding for any specific combination.

Our evaluation shows that the technique generates sparse tensor conversion routines with performance between 1.00 and 2.01× that of hand-optimized versions in SPARSKIT and Intel MKL, two popular sparse linear algebra libraries. And by emitting code that avoids materializing temporaries, which both libraries need for many combinations of source and target formats, our technique outperforms those libraries by 1.78 to 4.01× for CSC/COO to DIA/ELL conversion.

Thu 18 Jun
Times are displayed in time zone: Pacific Time (US & Canada) change

13:00 - 14:00: Code GenerationPLDI Research Papers at PLDI Research Papers live stream
Chair(s): Fan LongUniversity of Toronto

YouTube lightning session video

13:00 - 13:20
Automatic Generation of Efficient Sparse Tensor Format Conversion Routines
PLDI Research Papers
Stephen ChouMassachusetts Institute of Technology, USA, Fredrik KjolstadStanford University, Saman AmarasingheMassachusetts Institute of Technology, USA
13:20 - 13:40
OOElala: Order-of-Evaluation Based Alias Analysis for Compiler Optimization
PLDI Research Papers
Ankush PhuliaIIT Delhi, India, Vaibhav BhageeIIT Delhi, India, Sorav BansalIIT Delhi, India
13:40 - 14:00
Effective Function Merging in the SSA Form
PLDI Research Papers
Rodrigo C. O. RochaUniversity of Edinburgh, UK, Pavlos PetoumenosUniversity of Manchester, UK, Zheng WangUniversity of Leeds, UK, Murray ColeUniversity of Edinburgh, UK, Hugh LeatherUniversity of Edinburgh, UK