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