  An important linear algebra routine, GEneral Matrix Multiplication (GEMM), is
a fundamental operator in deep learning. Compilers need to translate these
routines into low-level code optimized for specific hardware. Compiler-level
optimization of GEMM has significant performance impact on training and
executing deep learning models. However, most deep learning frameworks rely on
hardware-specific operator libraries in which GEMM optimization has been mostly
achieved by manual tuning, which restricts the performance on different target
hardware. In this paper, we propose two novel algorithms for GEMM optimization
based on the TVM framework, a lightweight Greedy Best First Search (G-BFS)
method based on heuristic search, and a Neighborhood Actor Advantage Critic
(N-A2C) method based on reinforcement learning. Experimental results show
significant performance improvement of the proposed methods, in both the
optimality of the solution and the cost of search in terms of time and fraction
of the search space explored. Specifically, the proposed methods achieve 24%
and 40% savings in GEMM computation time over state-of-the-art XGBoost and RNN
methods, respectively, while exploring only 0.1% of the search space. The
proposed approaches have potential to be applied to other operator-level
optimizations.
