  Convolution is the most time-consuming part in the computation of
convolutional neural networks (CNNs), which have achieved great successes in
numerous applications. Due to the complex data dependency and the increase in
the amount of model samples, the convolution suffers from high overhead on data
movement (i.e., memory access). This work provides comprehensive analysis and
methodologies to minimize the communication for the convolution in CNNs. With
an in-depth analysis of the recent I/O complexity theory under the red-blue
game model, we develop a general I/O lower bound theory for a composite
algorithm which consists of several different sub-computations. Based on the
proposed theory, we establish the data movement lower bound results of two
representative convolution algorithms in CNNs, namely the direct convolution
and Winograd algorithm. Next, derived from I/O lower bound results, we design
the near I/O-optimal dataflow strategies for the two main convolution
algorithms by fully exploiting the data reuse. Furthermore, in order to push
the envelope of performance of the near I/O-optimal dataflow strategies
further, an aggressive design of auto-tuning based on I/O lower bounds, is
proposed to search an optimal parameter configuration for the direct
convolution and Winograd algorithm on GPU, such as the number of threads and
the size of shared memory used in each thread block. Finally, experiment
evaluation results on the direct convolution and Winograd algorithm show that
our dataflow strategies with the auto-tuning approach can achieve about 3.32x
performance speedup on average over cuDNN. In addition, compared with TVM,
which represents the state-of-the-art technique for auto-tuning, not only our
auto-tuning method based on I/O lower bounds can find the optimal parameter
configuration faster, but also our solution has higher performance than the
optimal solution provided by TVM.
