Introduction
Writing high-performance software is a moving target. An implementation of the Fast Fourier Transform (FFT) that screams on an Intel Xeon might crawl on an ARM processor due to differences in cache sizes, pipeline depths, and instruction sets. To solve this, developers use automatic performance tuning, where a "planner" searches through thousands of ways to recursively break down a mathematical problem to find the fastest version for a specific machine.
This paper introduces TAG (Threshold Ascend on Graph), a novel search algorithm that uses multi-armed bandit techniques to navigate the massive search spaces of high-performance code optimization. By treating library tuning as an optimization problem over a directed acyclic graph (DAG), TAG finds faster implementations up to 10x quicker than traditional dynamic programming, often discovering code that is 10% more efficient.
The Problem with Dynamic Programming
The standard approach to automatic performance tuning has historically been Dynamic Programming (DP). However, DP suffers from two major flaws in this context:
- It is slow: DP must solve every sub-problem before giving an answer, which can take days for large transforms.
- It is rigid: It assumes the "optimal" solution is always composed of "optimal" sub-solutions. In complex modern memory hierarchies, where cache conflicts and pipeline stalls are prevalent, this assumption frequently breaks down.
The authors sought a search strategy that is "anytime"—meaning it provides a good answer quickly and improves over time—and can handle search spaces too large for exhaustive or DP-based methods.
Methodology: The TAG Algorithm
The authors formalize the tuning process as a search over a Directed Acyclic Graph (DAG) generated by a formal grammar. By representing code generation as a formal grammar, the authors turn a messy engineering problem into a clean graph-theory problem. Each path through the graph represents a different way to implement the algorithm.
To navigate this graph, they propose the TAG algorithm, which is inspired by Upper Confidence Bounds applied to Trees (UCT) but specifically modified for DAGs. Most bandit algorithms (like those used in Google search or medical trials) try to maximize the cumulative or average reward. In code optimization, we don't care about the average; we only care about finding the single fastest "outlier." TAG is specifically tuned for this "Max-Bandit" scenario.
TAG operates in three repeating steps:
- Descend: Starting from the root, the algorithm picks the most promising "branch" using a Max $k$-Armed Bandit strategy. TAG uses the "Threshold Ascend" algorithm to find the branch most likely to contain the single maximum reward (the fastest code).
- Evaluate: When it hits a new area of the graph, it performs a "Monte-Carlo rollout"—randomly completing the implementation to get a performance estimate.
- Backpropagate: The performance result is sent back up the graph to update the "promise" of all parent nodes.
Experimental Setup
The researchers evaluated their approach using Spiral, a program generation system, targeting complex FFT libraries (Adaptive Linear Transform Libraries). Benchmarks were performed on a 64-bit Linux platform with two dual-core 3 GHz Intel Xeon 5160 processors. They compared TAG against standard Dynamic Programming (DP) and pure Monte-Carlo (MC) search.
Key Findings
- Speed of Search: TAG reached the same performance levels as Dynamic Programming an order of magnitude (10x) faster. Because TAG explores the most promising branches first and keeps a "current best" solution, it can be stopped at any moment. This "anytime utility" is a massive quality-of-life improvement for developers who can't wait 48 hours for a library to finish "planning."
- Code Performance: In several cases, TAG found implementations that were 10% faster than those found by DP. This is significant because DP's "optimal sub-problem" assumption often misses global optimizations related to cache conflicts.
- Reliability: TAG showed much lower variance and higher mean performance compared to pure Monte-Carlo search, proving that the bandit-based "guidance" was effectively steering the search toward better code.
Limitations and Future Work
The authors noted a specific quirk of performance tuning: evaluating "bad" nodes is expensive. In many machine learning problems, every evaluation takes the same amount of time. In code tuning, a "bad" implementation might run 10x slower than a "good" one, meaning the search algorithm actually slows down when it explores poor areas of the graph.
Future work includes modifying the algorithm to account for the "cost of evaluation," potentially avoiding branches that are not just low-performing, but also time-consuming to test. Additionally, the authors plan to apply TAG to even more complex libraries beyond linear transforms, such as those involving more intricate data dependencies.
Summary updated