> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/conference/index/mlsys-21/support-sparse-computations-in-ml.md). # Support sparse computations in ML ### History of Computing * The Gilded Era of Computing * Driven by Moore's Law * Performance was free * Software Engineering Ruled * High level languages, abstraction, layering * Innovations, complex software systems, coupled with excess bloat * The Trustfund Era of Computing * Moore's law is dead * How bad is the bloat? * The Resurgent Era of Computing * Why is sparsity in machine learning * Existing ML problems are sparse * Replacing dense solvers with sparse can have a huge benefit * Next-generation ML problems can be sparse * GNNs * Training ML models * RW ### Today * The world is built for dense #### Hardware utilization Dense * Peak Performance (GEMM) * 70-80% of CPU * 80-90% GPU * Optimization * Prefetching, Branch, Predictions, TLB, cache Sparse * Peak performance * <10% #### Programming System Dense * Abstractions that work across different algorithms (dense linear algebra, image processing, deep learning, ...) * BLAS, Halide, TensorFlow * Optimizing Compilers Sparse * What abstractions? ### Tensor * Too many tensor kernels for a fixed-function library * Many non-binary expressions must be computed in a single kernel * Sampled Dense-Dense Matrix Multiplication (SDDMM) ### The Tensor Algebra Compiler (Taco) * Challenges * Irregular data structures * Hierarchical Storage Abstractions * Sparse iteration space with limited O(1) access * sparse Iteration graph * Code generation from iteration graph * Avoid wasted work and iterations * Coiteration code generation * Optimize Parallelism and Locality * Scheduling language