Trellis: A Domain-Specific Language for Hidden Markov Models with Sparse Transitions
summary
Trellis is a DSL that specifies sparse HMMs and compiles to CUDA with a Python wrapper, using a predecessor analyzer and two predecessor strategies: a compile-time brute force (one-time quadratic work, high memory-bandwidth at runtime) and a runtime predecessor approach that generates compact GPU loops. Compilation (including CUDA build) is under 7s for benchmarks, handles models with ~200k states, outperforms prior high-level HMM tools on GPUs, and for evaluated sparse models matches a hand-written CUDA kernel's runtime.
AI-written summary · about
chapters (10)
- 0:00Trellis introduction
- 1:26Talk overview
- 2:52Hidden Markov Models
- 6:28HMM example
- 11:46Trellis language design
- 14:31Compiler architecture
- 17:00Predecessor computation
- 20:12Compilation times
- 21:38CUDA comparison
- 23:22Summary
related talks
01h 00mThe Shape of Things to Come
28mFunctional Sparse Tensor Compilation
28mHelion: A High-level DSL for Kernel Authoring
19mOptimizations and abstractions for sparse machine learning
39mDynamics Programming for Machine Learning- Hidden Markov Models
19mGeneralSparse: Bridging the Gap in SpMM for Pruned Large Language Model Inference..
32mCompilation of Dynamic Sparse Tensor Algebra
19mCompiler Support for Sparse Tensor Convolutions