Scalable Polyhedral Compilation, Syntax vs. Semantics: 1–0 in the First Round
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.
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.
Research Areas
