Photo from Manuel Rodríguez (CC BY-SA 2.5 MX)

IMPACT 2025

15th International Workshop on Polyhedral Compilation Techniques

January 22, 2025 | Barcelona, Spain In conjunction with HiPEAC 2025, January 20-22, 2025

Polyhedral compilation techniques have been at the forefront of research and innovation, playing a central role in a wide range of domain-specific languages and optimizing compilers. Thanks to a unified formalism for parallelization and memory optimization, they provide high impact in competitive areas such as machine learning, scientific computing, and media processing. Like a well-aged bottle of wine, these techniques have evolved and branched into new domains over time, with successful applications spanning across various products.

IMPACT is a unique event focusing on polyhedral compilation. The workshop brings together researchers and practitioners for a high-quality one-day event including a keynote, paper presentations, and work-in-progress discussions. The workshop has a well established tradition of high quality, extensive peer reviews, with a PC balancing core polyhedral expertise with applications and broader computing systems research.

Program

Palau de Congressos @ Fira de Barcelona

Room: Extra 2

HiPEAC session site

• Opening
  
• Keynote: Counting-based Loop Optimization
  Philippe Clauss
  [Abstract]
  From the rediscovery and extension of Ehrhart polynomials in the mid-90s, to the use and extension of mathematician Barvinok's results in the early 2000s, we now have efficient software tools for calculating a parameterized expression of the exact number of integer points of a polytope, linearly dependent on integer parameters. We show in this presentation that these expressions, which are called quasi-polynomials, have enabled, and still enable, the development of new techniques for loop nest analysis and transformation. They allow the polyhedral model, originally exclusively based on affine equations, to be extended to polynomials, and even more generally to algebraic expressions. In short, they enable the development of non-linear loop optimization techniques, yielding non-linear memory allocations and loop statement schedules. Among the techniques based on these quasi-polynomials, we'll mention memory consumption analysis, data layout transformation, collapsing of non-rectangular loops, and especially algebraic tiling. For the latter, we'll show its latest extensions to trapezoidal algebraic tiling of parallel stencil computations, which tends to outperform diamond tiling, in applicability, execution time and CPU cores consumption, thanks to quasi perfect load balancing among the parallel threads.
  [Bio]
  Philippe Clauss is a full-time professor at the University of Strasbourg, France, and leads projects for Inria CAMUS and MULTICORE. His research focuses on program compilation and optimization, utilizing both static and dynamic approaches. He develops innovative tools and mathematical methods for precise code analysis and optimization. His primary application domains are high-performance computing and multi-core parallelization.

• Polynomial Loop Recognition in Traces
  Alain Ketterlin
  [Abstract]
  This paper describes a tool named PLR which recognizes polynomial loop nests in traces. After providing background on affine (i.e., polyhedral) loop recognition with NLR, it exposes how a particular representation for integer polynomials leads to a simple and efficient interpolation technique. The new PLR algorithm, a slight modification of the original NLR, leverages this interpolation technique to recognize polynomial loops, i.e., loops where all bounds and values are expressed as multivariate polynomials in the loop counters.
  [Paper] [BibTeX]

              @inproceedings{ketterlin25-plr,
                title     = {Polynomial Loop Recognition in Traces},
                author    = {Ketterlin, Alain},
                booktitle = {15th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2025, in conjunction with HiPEAC 2025)},
                year      = 2025,
                url       = {https://impact-workshop.org/impact2025/#ketterlin25-plr},
              }
            

• Estimating the Upper Bound on Arithmetic Intensity for a Stencil Algorithm
  Sergey Khilkov
  [Abstract]

  For a stencil algorithm, arithmetic intensity is closely related to performance. We want to find an upper bound for arithmetic intensity for a given stencil algorithm with the help of geometric inequalities. This article presents a conjecture that for large problems arithmetic intensity 𝐼 is bound by the cache size 𝐷cache to the power of 1/𝑛, 𝐼 ≤ 𝐶 · sqrt(n, 𝐷cache), where 𝑛 is the number of space dimensions for the algorithm lattice. The coefficient 𝐶 depends only on the algorithm parameters and does not depend on the parameters of a computer system.

  The conjecture works for every implementation of the algorithm as long as the arithmetic operations stay the same. Therefore it helps to understand the limits of the optimization techniques like polyhedral optimization.

  To estimate the bound 𝐶 for a stencil algorithm, we introduce a geometric locality model. The model works in a continuous vector space and is expected to yield asymptotic estimations of the bound 𝐶 for large tile sizes. It also produces other interesting results related to tiling validity. We discuss several ways to generalize the geometric locality model. The space transformation, which makes the stencil convex, is of particular importance, since it may also prove to be useful in the polyhedral model.

  [Paper] [BibTeX]

              @inproceedings{Khilkov25-arithintensity,
                title     = {Estimating the Upper Bound on Arithmetic Intensity for a Stencil Algorithm},
                author    = {Khilkov, Sergey},
                booktitle = {15th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2025, in conjunction with HiPEAC 2025)},
                year      = 2025,
                url       = {https://impact-workshop.org/impact2025/#Khilkov25-arithintensity},
              }
            

• Automatic Specialization of Polyhedral Programs on Sparse Structures
  Alec Sadler and Christophe Alias
  [Abstract]
  Most High-Performance Computing applications manipulate sparse data, which results in highly irregular code whose compile-time optimization is quite challenging. One way is to start from the original dense specification, which is usually much more regular and ready to be optimized thanks to state-of-the-art program optimization algorithms. This paper presents an algorithm to specialize a dense polyhedral program on sparse inputs. Our approach is able to propagate the input sparse structure across the computation and to keep only the necessary computations computing non-zero values. It is meant to be coupled with other code transformation strategies to generate efficient parallel code. The key ingredient of our algorithm is the transitive closure of affine relations, for which efficient and accurate heuristics exist. Experimental evaluation assesses the scalability and the accuracy of our approach.
  [Paper] [BibTeX]

              @inproceedings{sadler25-sparsestructopt,
                title     = {Automatic Specialization of Polyhedral Programs on Sparse Structures},
                author    = {Sadler, Alec and Alias, Christophe},
                booktitle = {15th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2025, in conjunction with HiPEAC 2025)},
                year      = 2025,
                url       = {https://impact-workshop.org/impact2025/#sadler25-sparsestructopt},
              }
            

• Dead Iteration Elimination
  Cedric Bastoul, Maxime Schmitt, Benoît Meister and Chandan Reddy
  [Abstract]

  Dead code elimination (DCE) is a compiler technique that aims at increasing the program performance and reducing the executable size by removing program parts which do not contribute to the program output. Usual DCE implementations identify instructions not producing live-out data and remove them entirely. However, it may happen that only some dynamic executions of the instruction are dead. This situation notably arises when an instruction is enclosed inside a loop and some iterations of that loop do not contribute to the program output.

  In this paper we present dead iteration elimination (DIE), a technique to identify and to remove those iterations. DIE relies on polyhedral analysis to compute the required data space and the iterations which contributed them. It enables the safe removal of parts of the iteration space, possibly up to complete statement removal, in a complementary way to DCE. It also makes it possible to consider required output specification which opens new applications such as automatic specialization, sparsification or subsampling.

  [Paper] [BibTeX]

              @inproceedings{bastoul25-die,
                title     = {Dead Iteration Elimination},
                author    = {Bastoul, Cedric and Schmitt, Maxime and Meister, Benoît and Reddy, Chandan},
                booktitle = {15th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2025, in conjunction with HiPEAC 2025)},
                year      = 2025,
                url       = {https://impact-workshop.org/impact2025/#bastoul25-die},
              }
            

Ask questions and interact with the polyhedral community.

Call For Papers

We welcome both theoretical and experimental papers and presentations on all aspects of polyhedral compilation. We also welcome submissions describing preliminary results, crazy new ideas, position papers, experience reports, education material, and available tools, with an aim to stimulate discussions, collaborations, and advances in the field. The following illustrates potential IMPACT papers:

• Thorough theoretical discussion of a preliminary idea with an attempt to place it in context but no experimental results.
• Experimental results comparing two or more existing ideas, followed by a detailed analysis.
• Presentation of an existing idea in a different way, including illustrations of how the idea applies to new use cases, code, architectures, etc. Attribution should as clear as possible.

Topics of interest include, but are not limited to:

• program optimization (automatic parallelization, tiling, etc.);
• code generation;
• data/communication management on GPUs, accelerators and distributed systems;
• hardware/high-level synthesis for affine programs;
• static analysis;
• program verification;
• model checking;
• theoretical foundations of the polyhedral model;
• extensions of the polyhedral model;
• scalability and robustness of polyhedral compilation techniques.

Important Dates

Submission

Paper Submissions

Paper submissions should not exceed 10 pages (recommended 8 pages), excluding references, formatted as per ACM SIGPLAN proceedings format. Short paper submissions, even with only 2 pages, are welcome as well.

Please use version 1.54 or above of the following templates to prepare your manuscript: https://www.acm.org/publications/proceedings-template

Make sure to use the "sigplan" subformat.

Visit http://sigplan.org/Resources/Author/ for further information on SIGPLAN manuscript formatting.

NOTE: older versions of the article template use smaller fonts for submission, please double-check that you are using the recent style file (in particular, various LaTeX distributions ship older versions of the acmart style file, please download the most recent one from ACM).

Submissions should use PDF format and be printable on US Letter or A4 paper.

Please submit your manuscripts through EasyChair: https://easychair.org/conferences/?conf=impact2025

Proceedings

Proceedings will be posted online. If the final version of an accepted paper does not sufficiently address the comments of the reviewers, then it may be accompanied by a note from the program committee. Publication at IMPACT will not prevent later publication in conferences or journals of the presented work. However, simultaneous submission to IMPACT and other workshop, conference, or journal is often prohibited by the policy of other venues. For instance, a manuscript overlapping significantly with IMPACT submission cannot be submitted to PLDI 2025 or any other overlapping SIGPLAN event.

Presentations

The presentation should take no longer than 25 minutes to present. Please make sure that at least one of the authors can attend the workshop if your work is accepted. Registration are processed through the HiPEAC website.

Workshop Chair

Program Committee

Contact Us

For any inquiries or questions you may have regarding the IMPACT 2025 workshop, please feel free to reach out to us at impact25.barcelona@gmail.com.