Reducing Data Movement Energy via Commutative Data Reordering


Data movement is a significant consumer of energy in modern computer systems.To reduce these costs, recent work has proposed architecting interconnects with asymmetric data transmission costs, and developing encoding techniques to exploit this asymmetry. Although promising, these encoding techniques do not take full advantage of application level characteristics. As an example of a missed optimization opportunity, consider the case of computing a dot product as part of a neural network inference task. The order in which the weights are fetched from memory does not affect correctness, and can be optimized to minimize data movement energy—an optimization that is not possible on today’s systems.

This paper examines commutative data reordering (CDR), a new technique that leverages the commutative property in linear algebra to strategically select the lowest energy order in which data can be transmitted. When applied to sparse matrix vector multiplication, CDR reduces data movement energy by 21% over existing encoding techniques, for a total reduction of 1.89x over a baseline interconnect. These energy savings are achieved with zero metadata or bandwidth overhead to support the reordering.

In Government Microcircuit Applications And Critical Technology Conference (GOMACTech) 2019