Customized Monte Carlo Tree Search for LLVM/Polly's Composable Loop Optimization Transformations
Event Type
Workshop
Online Only
Accelerator-based Architectures
Applications
Computational Science
Emerging Technologies
Extreme Scale Comptuing
File Systems and I/O
Heterogeneous Systems
Parallel Programming Languages and Models
Performance
Scientific Computing
Software Engineering
W
TimeMonday, 15 November 20213:30pm - 4pm CST
LocationOnline
DescriptionPolly is the LLVM project's polyhedral loop optimizer. Recent user-directed loop transformation pragmas were proposed based on LLVM/Clang and Polly. The search space exposed by the transformation pragmas is a tree, wherein each node represents a specific combination of loop transformations. To find the best combination of these loop transformations, we developed a search algorithm based on Monte Carlo tree search (MCTS). The algorithm consists of two phases: exploring loop transformations at different depths of the tree to identify promising regions and exploiting those regions. A restart mechanism is used to avoid the MCTS trapped in a local solution. The best and worst solutions are transferred from the previous restarts to leverage the search history. We compare our approach with breadth-first, beam, global greedy and random search methods using PolyBench benchmarks and ECP proxy applications. Our MCTS algorithm achieves a speedup of 2.3x over Polly's heuristic optimizations on average.
