Speaker: Saman Amarasinghe

### Brief History of Computing

- Pioneering Era: any useful program stretched the machine resources and had to be engineered to fit the machine

- The Gilded Era of Computing: Moore's law doubles performance every 18 months, software engineering ruled; increasing levels of abstraction

- The Trustfund Era: a lot of bloat/low hanging fruit left over from previous era, many things to exploit easily

- 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.

### Taco

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

### GraphIt

DSL for Graph Analytics, high performance

Decouples algorithm from optimisation