Google Research

Scalable Polyhedral Compilation, Syntax vs. Semantics: 1–0 in the First Round

IMPACT 2020 workshop (associated with HIPEAC 2020)

Abstract

The development of lightweight polyhedral compilation algorithms opens polyhedral loop transformation, parallelization and code generation to a larger class or programs. The Pluto scheduling algorithm plays a major role in state-of-the-art polyhedral compilers, aiming for the simultaneous enhancement of locality and the exploitation of coarse-grain parallelism through loop tiling. Reducing the run time of affine scheduling algorithms like Pluto has a significant impact on the overall compilation time of polyhedral compilers. Several approaches have been proposed to reduce the run time of affine scheduling while preserving most of the optimization opportunities. Yet these works have taken separate rather than consolidated attempts at the problem. In an attempt to better characterize the potential and limitations of such approaches, we introduce and evaluate a family of techniques called offline statement clustering. Program statements are clustered into macro-statements and the dependence graph is projected onto these macrostatements before affine scheduling. Offline statement clustering integrates transparently into the flow of a state-of-the-art polyhedral compiler and can reduce the scheduling time by a factor of 6 (median) without inducing a significant loss in optimization opportunities. We also study the theoretical and experimental properties of statement clustering, shedding new light on the leading syntax-driven heuristic. Our work-in-progress study confirms the surprising finding that the simpler, apparently more fragile and syntax-dependent methods tend to perform well on a wide range of benchmarks.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work