Irregular computations involving sparse matrices, tensors and graphs (referred to as sparse computations) are found in a variety of important applications such as molecular dynamics, particle simulation, and deep learning.  A common aspect of sparse computations is that not all points representing a 3-dimensional space have associated data -- as a result, the data are compressed to only describe nonzero values, and the data's organization, density, and nonzero patterns are only known when the data becomes available during program execution.  Moreover, data must be decompressed during computation, which leads to unpredictable memory access patterns.  These aspects of sparse computations lead to very low arithmetic intensity, where performance is dominated by moving the sparse data through the memory system.

The CHiLL-I/E project developed compiler optimization techniques to optimize sparse computations for modern parallel platforms including CPUs and GPUs.  Recognizing that the memory access patterns are not fully available until runtime, CHiLL-I/E employs an inspector-executor approach, where the compiler generates inspector code at compile time that collects runtime information used in the optimized executor code that performs the computation.  This work combines the existing CHiLL autotuning compiler and the IEGenLib for generating inspector-executor code. The resulting system employs sparse polyhedral compilation technology and a configurable schedule of polyhedral transformations to compose inspector-executor code generation with other code transformations, thus increasing parallelism and improving memory access patterns for sparse computations. 

The CHiLL-I/E project focused on several critical issues associated with optimizing sparse computations using an inspector-executor approach:

• Automated dependence testing for sparse computations and wavefront parallelism:  We developed techniques for testing data dependences in the presence of indirect memory accesses through index arrays, which map from sparse data layouts to associated dense locations.  The compiler derives a set of constraints, and a SAT solver determines whether the constraints are unsatisfiable, indicated there are no data dependences.  Data dependences associated with remaining satisfiable constraints are evaluated at runtime using an inspector.  This approach has been used to optimize common sparse linear algebra computations via wavefront parallelism, including privatizing index arrays to reduce dependences.
• Optimizing inspectors: Inspectors may be generated to support multiple optimization goals, each potentially requiring a sweep over sparse data.  We have developed a dataflowrepresentation of inspector computations, and graph-based abstractions for fusing computations and reducing unnecessary intermediate storage.
• Generalizing sparse data layout conversion: Since the most performant sparse data format depends on architectural features, sparsity patterns and density, it is frequently necessary to transform a computation to work with different sparse data layouts. We have prototyped a general approach to layout conversion that is capable of transforming existing sparse tensor computations from the layout of their current specification to any new layout that can be expressed in a sparse polyhedral framework.
• Co-optimizing data layout and tensor computation: We have developed a code generator in CHiLL-I/E that employs sparse polyhedral technology and code synthesis to generate code for co-iteration across multiple sparse tensors, limited to multiplication and addition operations between tensors. Our approach composes the iteration space of the computation with an iteration space over the data layout for one of the sparse tensors. It then performs a lookup in the other sparse tensor to see if that element appears in both tensors. Our approach combines polyhedral scanning over the composed iteration space with code synthesis using an SMT solver to implement the find operation. 

Last Modified: 01/24/2022
Modified by: Mary Hall