This paper proposes a theoretical bandwidth model for entropy-coded SpMV, establishing relationships between matrix entropy, compression ratio, decoding overhead, and effective memory bandwidth. It predicts optimal compression strategies and identifies performance regimes where entropy-coded approaches outperform conventional methods.
Key findings
Proposes a theoretical bandwidth model for entropy-coded SpMV.
Establishes quantitative relationships between matrix entropy, compression ratio, decoding overhead, and effective memory bandwidth.
Derives bounds on achievable speedup as a function of matrix entropy and decoder throughput.
Predicts up to 2× effective bandwidth improvement for matrices with entropy below 4 bits per nonzero.
Limitations & open questions
Theoretical model may not account for all practical implementation details.
Validation framework is proposed but not yet implemented, leaving room for empirical results to vary.