PolyGym: Polyhedral Optimizations as an Environment for Reinforcement Learning

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

Abstract

The polyhedral model allows a structured way of defining semantics-preserving transformations to improve the performance of a large class of loops. Finding profitable points in this space is a hard problem which is usually approached by heuristics that generalize from domain-expert knowledge. Existing search space formulations in state-of-the-art heuristics depend on the shape of particular loops, making it hard to leverage generic and more powerful optimization techniques from the machine learning domain. In this paper, we propose a shape-agnostic formulation for the space of legal transformations in the polyhedral model as a Markov Decision Process (MDP). Instead of using transformations, the formulation is based on an abstract space of possible schedules. In this formulation, states model partial schedules, which are constructed by actions that are reusable across different loops. With a simple heuristic to traverse the space, we demonstrate that our formulation is powerful enough to match and outperform state-of-the-art heuristics. On the Polybench benchmark suite, we found the search space to contain transformations that lead to a speedup of 3.39× over LLVM O3, which is 1.34× better than the best transformations found in the search space of isl, and 1.83× better than the speedup achieved by the default heuristics of isl. Our generic MDP formulation enables future work to use reinforcement learning to learn optimization heuristics over a wide range of loops. This also contributes to the emerging field of machine learning in compilers, as it exposes a novel problem formulation that can push the limits of existing methods.

Details

OriginalspracheEnglisch
TitelParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
Herausgeber (Verlag)IEEE Xplore
Seiten17-29
Seitenumfang13
ISBN (elektronisch)978-1-6654-4278-7
ISBN (Print)978-1-6654-4279-4
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusJa

Publikationsreihe

ReiheInternational Conference on Parallel Architecture and Compilation Techniques (PACT)
ISSN1089-795X

Konferenz

Titel30th International Conference on Parallel Architectures and Compilation Techniques, PACT 2021
Dauer26 - 29 September 2021
StadtVirtual, Onliine
LandUSA/Vereinigte Staaten

Externe IDs

ORCID /0000-0002-5007-445X/work/141545624
Mendeley b8ba63b1-2dc9-3cf5-b73f-970ba41b286b

Schlagworte

Forschungsprofillinien der TU Dresden

Schlagwörter

  • Loop scheduling, Machine learning, PolyGym, Polyhedral optimization, Reinforcement learning

Bibliotheksschlagworte