Abstract
OpEvo is a novel evolutionary algorithm designed to automatically tune deep learning tensor operators for peak hardware performance. By introducing a topology-aware mutation strategy based on q-random walks, it navigates complex, discrete search spaces more efficiently than existing methods, finding optimal configurations with fewer trials and reduced wall-clock time.
Introduction
The performance of modern deep neural networks (DNNs) is fundamentally tied to the efficiency of low-level tensor operators, such as matrix multiplications and convolutions, on specific hardware targets. Optimizing these operators requires selecting ideal configurations—parameters governing loop unrolling, tiling strategies, and execution order. This task presents a massive combinatorial optimization problem characterized by a discrete, high-dimensional search space where evaluating a single point is computationally expensive, requiring code compilation and hardware execution.
Existing optimization strategies generally fall into two categories: Sequential Model-Based Optimization (SMBO) and traditional Evolutionary Algorithms (EA). SMBO methods, like AutoTVM, utilize surrogate models to predict performance but often struggle with discrete spaces and introduce significant training overhead. Conversely, traditional EAs handle discrete spaces effectively but are typically sample-efficient, requiring an impractical number of trials to converge.
Methodology: Topology-Aware Evolution
OpEvo addresses these challenges by introducing a lightweight, model-free evolutionary approach that leverages the inherent topological structure of the search space.
Topological Mapping
The core innovation of OpEvo is the definition of "neighborhoods" for various parameter types, transforming the search space into a set of connected graphs.
- Factorization: Tiling configurations are connected if one can be reached by moving a single prime factor between loops.
- Permutation: Loop orders are neighbors if they differ by a single swap.
- Discrete/Categorical: Parameters are mapped to path or complete graphs respectively.
q-random walk Mutation
Rather than employing purely random mutations, OpEvo utilizes a q-random walk on these topological graphs. A parameter $q \in [0, 1]$ controls the walk length: higher values promote exploration through longer walks, while lower values encourage exploitation by keeping mutations near the parent configuration. This strategy exploits the assumption of local smoothness—that similar configurations likely yield similar performance—allowing the algorithm to "walk" toward performance peaks.
Experimental Evaluation
The researchers evaluated OpEvo across standard tensor operators (MatMul, Batch MatMul, and 2D Convolution) sampled from models like BERT and AlexNet. Testing was conducted on both NVIDIA (GTX 1080Ti) and AMD (MI50) hardware. OpEvo was compared against state-of-the-art baselines, including AutoTVM, G-BFS, and N-A2C.
Results and Discussion
OpEvo demonstrated significant improvements in both sample efficiency and raw performance:
- Efficiency: In end-to-end AlexNet benchmarks, OpEvo achieved optimal inference times in approximately 200 trials, halving the 400 trials required by AutoTVM.
- Wall-Clock Time: By eliminating surrogate model training, OpEvo reduced total optimization time by roughly 30% on NVIDIA platforms.
- Performance: The method consistently identified configurations with higher TFLOPS and lower performance variance compared to reinforcement learning and greedy search baselines.
A key insight from the study is the role of graph degree in the search process. In a q-random walk, nodes with higher connectivity are sampled more frequently. These complex neighborhoods often provide richer information about the objective function, accelerating convergence.
Conclusion
OpEvo provides a robust and efficient alternative for tensor operator tuning by formalizing the search space as a structured topology. While its effectiveness depends on the quality of the defined neighborhood structures, it excels in scenarios where human expertise can be encoded into these topologies. Future work may extend this topology-aware evolutionary framework to broader combinatorial optimization challenges beyond the domain of deep learning hardware acceleration.
Summary updated