Enhancing the Power of Polyhedral-Based Optimizations with Coordinate-Based Hill Climbing

Gaurav Verma; Michael Canesche; Fernando Magno Quintão Pereira

Source-linked AI summary

Enhancing the Power of Polyhedral-Based Optimizations with Coordinate-Based Hill Climbing

Gaurav Verma, Michael Canesche, Fernando Magno Quintão Pereira

arXiv:2609.03114v1Sep 2, 2026cs.PL

TL;DR

Static polyhedral compilers select promising kernel structures, but full empirical autotuning is costly and static cost models may not identify hardware-optimal numeric parameters. The paper therefore applies coordinate-wise hill climbing to parameters after polyhedral generation, with expanded neighborhoods and shortest-hop refinement. The resulting CPU and GPU tuning improves defaults, reaches performance competitive with AutoTVM, and uses substantially less search time, although recompilation dominates the reported search overhead.

Problem
Empirical autotuning captures hardware effects but requires costly execution of multiple kernel versions, while polyhedral cost models do not directly identify the best hardware-dependent parameter values.
Method
The approach fixes kernel shape with polyhedral analysis and applies coordinate-wise hill climbing to numeric parameters, augmented with expanded neighborhoods and shortest-hop refinement.
Results
1.06–1.28x geometric mean speedups across 11 CPU benchmarks and 5.5–8.5% improvement on an NVIDIA A100 were achieved over default configurations, with CPU performance competitive with AutoTVM.
Takeaways & Limitations
Post-optimization parameter tuning offers a practical middle ground between fixed-cost-model polyhedral compilation and full autotuning.
Takeaways & Limitations
Each hill-climbing step regenerates and recompiles the kernel, producing a reported 40–75x search-time overhead relative to compilation time.

Abstract

from arXiv · show

This paper describes our experience extending the polyhedral compiler Pluto with a lightweight, coordinate-wise hill-climbing tuner that adjusts numeric transformation parameters, such as tile sizes and thread-block dimensions, after Pluto selects the kernel's loop structure. To ensure fast convergence and escape local minima, hill climbing is augmented with two techniques: expanded neighborhood exploration and a shortest-hop refinement phase. On x86 and ARM CPUs, tuned kernels outperform Pluto's default configuration (1.06-1.28x geometric mean speedup across 11 benchmarks) and static optimizers (Clang -O3, Polly, IOOpt), reaching performance competitive with the AutoTVM autotuner at substantially lower search cost. Applying the same technique to GPU thread-block allocation on an NVIDIA A100 yields 5.5-8.5% improvement over default configurations. These results position post-optimization parameter tuning as a practical middle ground between fixed-cost-model polyhedral compilation and full autotuning.

1 INTRODUCTION

The paper combines Pluto’s static polyhedral kernel-shape selection with lightweight hill climbing over numeric parameters, targeting a lower-cost alternative to broad empirical autotuning. Across CPU and GPU settings, this approach improves default configurations and approaches full autotuner performance while retaining substantially lower search cost.

Motivation: Polyhedral analysis represents loop iterations geometrically, enabling dependency-aware transformations such as interchange, tiling, and fusion.This supplies a static way to improve cache utilization and parallelism.
Motivation: Empirical autotuners adapt kernels to hardware by executing multiple versions, but this exploration is costly.They capture architecture-specific effects that static models may not fully account for.
Approach: The proposed hybrid fixes the kernel shape with polyhedral analysis, then hill-climbs numeric parameters including tile sizes, unrolling factors, and thread-block dimensions.It focuses search on parameters after loop ordering and memory-access structure have been selected.
Approach: Focused post-hoc tuning searches a smaller space than approaches covering schedules, fusion choices, and transformation sequences.The paper argues that this narrower space can recover much available performance at a fraction of broader exploration cost.
Approach: Polyhedral analysis provides both Pluto’s default seed and the search space, avoiding manual initialization or expensive pre-tuning.This addresses how gradient-based tuning can start without empirical sampling.
Results: 1.06–1.28x geometric mean speedups across 11 CPU benchmarks were achieved, while tuned kernels matched AutoTVM performance at substantially lower search cost.The results covered x86 and ARM CPUs and exceeded Pluto’s default configuration and static optimizers including clang -O3, Polly, and IOOpt.
Results: 5.5–8.5% improvement over default configurations was obtained for GPU thread-block allocation on an NVIDIA A100.The search times were a fraction of exhaustive exploration, supporting a middle ground between fixed-cost-model compilation and full autotuning.

2 OPTIMAL CONFIGURATIONS OF POLYHEDRAL OPTIMIZATIONS

The section introduces the polyhedral representation of loop iteration spaces and shows how dependence-safe transformations produce tiled matrix multiplication. It then motivates tuning tile sizes because compiler defaults can be substantially improved, while noting that convexity is an assumption rather than a guarantee.

Polyhedral Transformations: Polyhedral compilation analyzes loop interactions, rewrites loops with transformations such as tiling or interchange, and generates transformed code.The model represents bounds and dependencies with inequalities over iteration spaces.
Polyhedral Transformations: Matrix multiplication is represented as a three-dimensional iteration space with axes i, j, and k, bounded by loop limits.Each point corresponds to a valid combination of loop indices and an operation.
Polyhedral Transformations: Strip mining and loop interchange form tiles that improve cache locality by traversing blocks instead of the entire iteration space.The tiled implementation is reported to run in about 0.1 seconds versus more than 2 seconds for the naïve version on 1024 × 1024 matrices.
Parameter Tuning: Tile sizes I, J, and K are configurable parameters, and Pluto’s default I = J = K = 32 values are not necessarily optimal.This motivates post-generation parameter tuning.
Parameter Tuning: An exhaustive grid search selected J = 256 and I = 64, achieving a running time of 0.12 seconds for 1024×1024 matrices with K = 32.The search varied I and J over {4, 8, 16, 32, 64, 128, 256} on an AMD Ryzen 2.6GHz.
Parameter Tuning: The Droplet Hypothesis expects the region from the search-space origin to the global optimum to be convex, but many analyzed benchmarks are non-convex.Convexity guarantees convergence to an optimal configuration when present, but it is not necessary for the proposed adjustment policy to work.

3 COORDINATE-WISE HILL CLIMBING OVER POLYHEDRA

The paper represents loop transformations as structured polyhedral spaces, then searches their numeric parameter configurations with coordinate-wise hill climbing. Polyhedral analysis supplies a promising optimization space, while hardware-dependent parameter selection is left to empirical search.

Search procedure: Coordinate-wise hill climbing repeatedly evaluates nearby kernels and moves to a better-performing candidate differing in one optimization parameter.The neighborhood combines single-parameter changes across all coordinates, rather than exhausting one coordinate before considering others.
Kernel optimization space: A kernel optimization space is an ordered sequence of transformations applied to a polyhedral kernel, with each point corresponding to a choice of numeric optimization parameters.The example combines interchange, tiling, parallelization, unrolling, and vectorization, with finite parameter sets for the parameterized transformations.
Polyhedral representation: The polyhedral model represents loop iterations as integer points in polyhedra and applies transformations by multiplying points by transformation matrices.Loop interchange is illustrated by swapping the j and k coordinates through a permutation matrix.
Bootstrapping: Out-of-the-box polyhedral analyses can find a good kernel optimization space, but the best point within that space depends on hardware details.The paper therefore uses hill climbing to select numeric parameters after the transformation space has been identified.
Search variants: Expanded neighborhoods examine higher-degree candidates, while shortest-hop search can consider valid parameter values beyond the predefined list.Expanded search increases computational cost; shortest-hop refinement addresses the omission of additive parameter choices from immediate and expanded neighborhoods.

4 EVALUATION

The evaluation measures PlutoCD across CPU and GPU settings, comparing kernel quality, search overhead, initialization, neighborhood strategies, and generalization. Results show consistent CPU gains over Pluto, faster search than AutoTVM, and near-exhaustive GPU performance with hill climbing.

Experimental setup: PlutoCD evaluates 11 Pluto kernels using GCC, Clang, Polly, TVM, and IOOpt across x86 and ARM-based A64FX systems.The x86 system is an Intel Xeon Max CPU 9468, while the ARM system is Fujitsu A64FX-FX700.
CPU performance: 1.28x, 1.06x, 1.21x, and 1.12x geometric-mean speedups are reported for GCC/x86, Clang/x86, GCC/A64FX, and Clang/A64FX over Pluto, respectively.Across 44 architecture and code-generator experiments, PlutoCD settled on Pluto’s default parameters in only five cases.
Search overhead: 40-75x search-induced slowdowns are measured relative to Pluto, while kernel execution improves by 1.23x, 1.06x, 1.19x, and 1.04x for x86/GCC, x86/Clang, ARM/GCC, and ARM/Clang.The reported PlutoCD times include hill climbing, kernel sampling, and generated-kernel execution.
Comparison with autotuning: 24.44x faster search than AutoTVM is reported for generating all eleven executables, with PlutoCD limited to 100 iterations versus AutoTVM’s 1,000 samples.The comparison uses different input infrastructures: TensorIR for AutoTVM and C++ programs for PlutoCD.
Search initialization: Pluto’s tile-size-32 seed consistently reduces convergence time compared with starting from tile size one, while usually producing similar kernel quality.The origin is faster only for conv2d in the reported kernel-execution comparisons.
Neighborhood exploration: Degree-1 neighborhoods are typically more efficient because higher-degree neighborhoods add search-time overhead without significant kernel-quality improvements.The degree-1 configuration is PlutoCD’s default.
Shortest-hop refinement: Shortest-hop refinement improves kernel running times by about 3% but increases search time by about 30x, improving only gemm, gemm_layernorm, and self_attention.The comparison is against PlutoCD’s default immediate-neighborhood method.
GPU generalization: On an NVIDIA A100, geometric-average improvement reaches 5.48%, 7.67%, and 8.53% for degree-one hill climbing, degree-two hill climbing, and exhaustive search.Hill climbing is close to exhaustive search, while degree two improves over degree one in four benchmarks.

5 RELATED WORK

The paper situates its approach between model-driven polyhedral compilation and feedback-driven autotuning, combining polyhedral search-space reduction with lightweight empirical tuning. It contrasts this narrower search with broader optimization frameworks, analytical models, and recompilation-free code generation, while identifying future opportunities for composition.

Polyhedral and autotuning paradigms: Auto-tuning uses runtime feedback to adapt code to hardware, whereas polyhedral compilation relies on theoretical cost models without runtime feedback.Auto-tuners test multiple code versions but incur substantial computational cost.
Hybrid search: The paper combines polyhedral analysis for kernel-shape selection with hill climbing over numeric parameters, narrowing the search space after scheduling decisions are fixed.This differs from broader approaches that jointly explore scheduling, fusion/fission, tiling, and transformation sequences.
Alternative tuning strategies: Analytical tile-size models avoid runtime sampling, while the paper’s hill climbing approximates hardware characteristics through empirical sampling; the authors describe these approaches as complementary.They suggest analytical models could replace Pluto’s fixed default as the search seed, but leave that composition for future work.
Alternative tuning strategies: Parametric code generation can avoid regenerating and recompiling each candidate, addressing the reported 40–75x search-time overhead of the current implementation.The paper identifies recompilation-free generation as a future way to reduce overhead without changing the hill-climbing search.
Hybrid search: Hill climbing is positioned as a lightweight alternative to broader empirical searches, using Pluto’s analysis to provide both a search space and a competitive starting point without manual seeding.The paper distinguishes this use from prior hill-climbing applications seeded by humans or other autotuners.

6 CONCLUSION

The paper concludes that hill climbing can make static polyhedral optimizers more competitive with modern autotuners by tuning their optimization parameters. An artifact is provided to reproduce the experiments in Section 4.

Conclusion: Hill climbing makes polyhedral-based compilers more competitive with autotuners by fine-tuning parameters selected by static optimization.The conclusion attributes the method’s strength to combining simple hill climbing with static optimizers such as Pluto.
Conclusion: A reproducibility artifact containing the tools for the Section 4 experiments is available online.The artifact is hosted at the Kelpie GitHub repository.