Supporting Sparse Computations

Speaker: Saman Amarasinghe

Brief History of Computing

  1. Pioneering Era: any useful program stretched the machine resources and had to be engineered to fit the machine
  1. The Gilded Era of Computing: Moore's law doubles performance every 18 months, software engineering ruled; increasing levels of abstraction
  1. The Trustfund Era: a lot of bloat/low hanging fruit left over from previous era, many things to exploit easily
  1. The Resurgent Era: ML created a surge of demand for compute, need innovation in compilers and architecture

Where is Sparsity in ML?

  • Many existing problems are sparse
    • Gives great chart about how sparse many problems actually are
  • Next-gen problems can be sparce
    • GNNs
  • Many sparse datasets
In sparse case as we might have a zero somewhere downstream which makes part of computation irellevant, we need to consider whole chain for optimisation

World is Built for Density

Peak performance on sparse problems is about 10% GPU and CPU usage - spends all its time going to mem
Dense problems have many great abstractions: BLAS, TF, etc.


The Sparse Tensor Algebra Compiler
Goes from all kinds of sparse algebraic expressions to C, CUDA, domain-specific architectures.
Challenges for sparsity:
  • Irregular data scructures, addressed by:
    • hierarchical storage abstractions (compressed storage formats)
    • if we reduce to dense version we need some efficient system for using coords for sparse matrix (CSR format)
  • Sparse iteration space with limited O(1) access, addressed by:
    • Sparse Iteration Graphs
    • Compressed storage formats mean no O(1) access
    • Generate graphs indicating ?
  • Avoid wasted work and iterations, addressed by:
    • Coiteration Code Generation???
  • Oprimise Parallelism and Locality, addressed by:
    • Scheduling language
Performance equivalent to best domain-specific equivalents


DSL for Graph Analytics, high performance
Decouples algorithm from optimisation