Accelerating graph substitutions in DNN optimization by heuristic algorithms

Abstract Graph substitution is a key optimization technique used in deep learning frameworks. Traditional search-based methods are one way to address the problem of graph substitution. However, with the ongoing expansion of deep neural networks (DNNs), the exploration of their vast equivalent graph search space becomes increasingly time-consuming. In this paper, we propose two heuristic methods to accelerate the search process in graph substitution, offering a relatively novel direction compared to existing methods. The first method employs a Memory-Augmented heuristic to optimize computation graphs. To further enhance the efficiency of computation graph optimization, the second method uses the simulated annealing method. This method adds computation graphs with degraded performance into the candidate set with a certain probability. The experimental results show that without significant compromise of inference performance, these two methods can find graph substitutions delivering similar DNN computing performance compared to existing searching methods, while the overall searching time can be reduced from hours to seconds. The source code is available at https://github.com/hudevictor/MAS-SAS .