DMC4ML: Data Movement Complexity for Machine Learning
Chen Ding Christopher Kanan Dylan McKellips Toranosuke Ozawa Arian Shahmirza Wesley Smith
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.