DMC4ML: Data Movement Complexity for Machine Learning
This work addresses the critical bottleneck of memory access in ML algorithms, offering a foundational tool for optimizing performance across various applications, though it is incremental in its analytical approach.
The paper tackles the problem of analyzing memory access costs in machine learning algorithms by introducing a novel complexity measure called Data Movement Complexity (DMC), which asymptotically identifies primary sources of memory cost and provides symbolic results for parameter selection in transformers, spatial convolution, and FFT.
The greatest demand for today's computing is machine learning. This paper analyzes three machine learning algorithms: transformers, spatial convolution, and FFT. The analysis is novel in three aspects. First, it measures the cost of memory access on an abstract memory hierarchy, instead of traditional time or space complexity. Second, the analysis is asymptotic and identifies the primary sources of the memory cost. Finally, the result is symbolic, which can be used to select algorithmic parameters such as the group size in grouped query attention for any dimension size and number of heads and the batch size for batched convolution for any image size and kernel size.