---
description: Saman Amarasinghe (MIT)
---

# Support sparse computations in ML

### History of Computing&#x20;

* The Gilded Era of Computing&#x20;
  * Driven by Moore's Law&#x20;
  * Performance was free&#x20;
  * Software Engineering Ruled&#x20;
    * High level languages, abstraction, layering
    * Innovations, complex software systems, coupled with excess bloat&#x20;
* The Trustfund Era of Computing&#x20;
  * Moore's law is dead&#x20;
  * How bad is the bloat?&#x20;
* The Resurgent Era of Computing&#x20;
  * Why is sparsity in machine learning&#x20;
    * Existing ML problems are sparse&#x20;
      * Replacing dense solvers with sparse can have a huge benefit&#x20;
    * Next-generation ML problems can be sparse&#x20;
      * GNNs&#x20;
    * Training ML models&#x20;
      * RW&#x20;

### Today

* The world is built for dense&#x20;

#### Hardware utilization&#x20;

Dense&#x20;

* Peak Performance (GEMM)
  * 70-80% of CPU&#x20;
  * 80-90% GPU
* Optimization
  * Prefetching, Branch, Predictions, TLB, cache&#x20;

Sparse

* Peak performance&#x20;
  * <10%&#x20;

#### Programming System

Dense&#x20;

* Abstractions that work across different algorithms (dense linear algebra, image processing, deep learning, ...)
  * BLAS, Halide, TensorFlow&#x20;
  * Optimizing Compilers&#x20;

Sparse&#x20;

* What abstractions?&#x20;

### Tensor&#x20;

* Too many tensor kernels for a fixed-function library&#x20;
* Many non-binary expressions must be computed in a single kernel&#x20;
  * Sampled Dense-Dense Matrix Multiplication (SDDMM)&#x20;

### The Tensor Algebra Compiler (Taco)&#x20;

* Challenges&#x20;
  * Irregular data structures&#x20;
    * Hierarchical Storage Abstractions&#x20;
  * Sparse iteration space with limited O(1) access&#x20;
    * sparse Iteration graph
    * Code generation from iteration graph&#x20;
  * Avoid wasted work and iterations&#x20;
    * Coiteration code generation&#x20;
  * Optimize Parallelism and Locality&#x20;
    * Scheduling language&#x20;
