TL;DR
This paper tackles the challenge of automatically generating highly optimized code for signal processing algorithms like the Fast Fourier Transform (FFT) and Walsh-Hadamard Transform (WHT). By learning to predict the performance of different algorithmic structures and then using reinforcement learning to guide the search for optimal implementations, they can discover faster code than exhaustive search methods, even for large problem sizes.
What Problem Does This Paper Address?
Signal processing algorithms, such as the FFT and WHT, can be implemented using a vast number of mathematically equivalent formulas. However, the actual runtime performance of these formulas on real hardware varies dramatically due to factors like processor architecture, cache behavior, and instruction pipelining. Manually finding the fastest implementation for a given algorithm and hardware is incredibly difficult and time-consuming. Exhaustively searching all possible implementations is computationally infeasible for larger problem sizes. This paper aims to automate the discovery of these fast implementations by learning to predict performance and then intelligently generating promising candidates.
Methods
The core of the paper's approach involves two main components:
- Performance Prediction: They develop models to predict the performance (runtime or cache misses) of different parts of a signal processing implementation.
- For WHT, they observe that performance is dominated by "leaf" nodes in the algorithm's "split tree" representation. They train decision trees to classify leaf performance into a few categories (e.g., near-zero cache misses, near-quarter cache misses).
- For both WHT and FFT, they also train regression trees to predict actual runtimes for leaves and internal nodes.
- Crucially, these predictors are trained on data from one specific transform size but demonstrate good generalization to other sizes.
- Generation of Fast Formulas: They frame the problem as a control learning task, inspired by Markov Decision Processes (MDPs).
- The algorithm recursively grows a "split tree" representing the signal processing algorithm.
- At each node, it uses the learned performance predictors to evaluate potential "actions" (e.g., splitting the node into children or treating it as a leaf).
- A value function is computed to estimate the total performance of a subtree.
- The algorithm then selects splits that minimize this predicted cost, effectively generating formulas that are predicted to be fast.
Datasets
The paper uses data generated from timing various WHT and FFT formulas.
- WHT: Data was collected for WHT formulas of sizes 2¹² to 2²⁰.
- FFT: Data was collected for FFT formulas of sizes 2¹² to 2¹⁸.
- The training data for predictors was often derived from a subset of formulas of a specific size (e.g., WHT(2¹⁶) or FFT(2¹⁶)), and then these predictors were evaluated on a wider range of sizes.
Key Insights and Ideas
- Performance is Hardware-Specific: The "best" implementation is not universal and depends heavily on the target hardware.
- Cache Misses as a Proxy for Speed (on some architectures): For WHT on a Pentium, minimizing L1 data cache misses strongly correlated with finding the fastest formulas, simplifying the prediction task.
- Generalization Across Sizes: Performance predictors trained on one transform size can accurately predict performance for other sizes, a critical insight for generating fast code without timing every possible size.
- Intelligent Search is Key: Given the enormous search space of possible formulas, an intelligent search guided by learned performance models is far more effective than brute-force enumeration.
- FFT Internal Nodes Matter: Unlike WHT, FFT implementations have significant computation in internal nodes, requiring separate predictors for these nodes.
Key Results
- WHT Cache Miss Predictor: Achieved very low leaf prediction error rates (<2%) and accurately identified the fastest formulas.
- WHT Runtime Predictors: Achieved average percentage errors of <20% for leaf runtime prediction and <15% for entire formula runtime prediction on Pentium, and <20% on Sun. Crucially, these predictors effectively ordered formulas by speed.
- FFT Runtime Predictors: Achieved error rates <20% for entire formula runtime prediction, outperforming WHT prediction errors.
- Formula Generation: The method consistently generated the fastest known formulas, often within the first few generated, even for sizes larger than those used for training. For WHT, it generated a significant portion of the top 100 fastest formulas.
- Comparison to Other Methods: The generation method outperformed a basic dynamic programming search for FFTs, finding faster formulas for most sizes.
Limitations and Future Work
- Predictor Accuracy: While good, the predictors are not perfect, leading to some error in runtime predictions. The paper notes that runtime prediction is harder than cache miss prediction due to the continuous nature of runtimes.
- Hardware Dependence: While the method can be applied to different architectures, the performance predictors themselves are trained on specific hardware, meaning new predictors would need to be trained for each new architecture.
- Feature Engineering: The effectiveness of the predictors relies on carefully chosen features to describe the algorithmic structures.
- Future Work: The authors suggest extending the method to other transforms and exploring more sophisticated predictor models. They also note that the generation algorithm can be extended to produce a set of formulas within a certain tolerance of the optimal predicted performance, not just the single best one.
Summary updated