Photo from Michael Kruse

IMPACT 2024

14th International Workshop on Polyhedral Compilation Techniques

January 17, 2024 | Munich, Germany In conjunction with HiPEAC 2024, January 17-19 2024

Polyhedral compilation techniques receive more attention than ever from both researchers and practitioners. Thanks to a unified formalism for parallelization and memory optimization, polyhedral techniques play a central role in a wide range of domain-specific languages and optimizing compilers, with high impact in competitive areas such as machine learning, scientific computing and media processing.

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

Science Congress Center Munich

Room: Orion 2

HiPEAC session site

• Opening
  [Slides]
• Keynote: Scalable Polyhedral Compilation in Open-Source and AI Compilers.
  Tobias Grosser.
  [Abstract]
  Polyhedral compilation has evolved beyond an academic tool and drives the optimization of AI and computational science software. Its software stack is relatively mature and even integrated with production compilers (e.g., GCC, LLVM, and MLIR). Thanks to its formal foundation, extensions to the polyhedral model are dependable and can solve problems inaccessible to ad-hoc methods. Yet, polyhedral compilation remains foreign to classical compilers. It is often seen as "the other" approach instead of a tool that fits well into the classical compiler stack, its "exponential complexity" fuels scalability concerns, and many developers are afraid of a potentially steep learning curve. Tools such as MLIR promote a high-level compilation approach that claims to make polyhedral compilation unnecessary. Yet, our community solves exceptionally difficult problems, e.g., cache analysis, that are out of reach for others. Based on my experience developing GCC/Graphite, LLVM/Polly, and MLIR/FPL, I make a case that scaling polyhedral compilation to real-world compilers requires both technical innovation and close social connections with the production-compiler community. I will share along which dimensions Graphite and Polly "failed", where both projects succeeded in potentially not widely visible metrics, and where I see potential for polyhedral compilation to scale to the complex social demands of open-source communities and the technical challenges of modern AI compiler stacks. In this talk, I raise the question of where we - as the polyhedral compilation community - should stand and how we can connect even better with the global research community to increase the IMPACT we have on our society.
  [Bio]
  Tobias Grosser is an Associate Professor at the University of Cambridge and an advocate for open-source-first research. Tobias co-founded the Polyhedral loop optimization framework Polly, the FPL Presburger Library for MLIR, the LLHD/CIRCT hardware-design compiler, and is regularly teaching compiler design using the Python-Native xDSL compiler project designed to lower the barrier of entry into the LLVM ecosystem. Tobias worked as a Google PhD Fellow at ENS Paris, an SNSF Ambizione Fellow at ETH Zurich, and a Reader at the University of Edinburgh. He supervises several PhD students who actively contribute the the open-source compiler ecosystem.
  [Slides]

• A Polyhedral Compilation Library with Explicit Disequality Constraints.
  Sven Verdoolaege.
  [Abstract]
  Polyhedral libraries usually have no explicit support for disequality constraints, requiring them to be encoded as a disjunction of inequality constraints instead. Every additional disequality constraint then typically leads to a doubling of the size of the representation. This paper shows how the isl library can be extended to support disequality constraints natively, allowing for a significantly reduced computation time due to the more efficient representation.
  [Paper] [Slides] [BibTeX]

              @inproceedings{verdoolaege24-disequality,
                title     = {A Polyhedral Compilation Library with Explicit Disequality Constraints},
                author    = {Verdoolaege, Sven},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#verdoolaege24-disequality},
              }
            

• Easy Counting and Ranking for Simple Loops.
  Alain Ketterlin.
  [Abstract]
  This paper describes a way to count instructions executed by a loop nest, and assign a sequence number to each one of them. It is restricted to a specific class of affine loop nests, and uses an uncompromising representation of integer polynomials, which is described in detail. The general focus is on mathematical and algorithmic simplicity, searching for easy to implement methods under acceptable restrictions.
  [Paper] [Slides] [BibTeX]

              @inproceedings{ketterlin24-counting,
                title     = {Easy Counting and Ranking for Simple Loops},
                author    = {Ketterlin, Alain},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#ketterlin24-counting},
              }
            

• Reuse Analysis via Affine Factorization.
  Ryan Job and Sanjay Rajopadhye.
  [Abstract]
  Affine maps are a crucial structure within the polyhedral model of computation, essential for expressing programs in the model. Detecting values which are reused by a collection of affine maps within the same program expression can enable a number of optimization techniques: reducing the amount of storage needed, the time required for computing values, and even value based common sub-expression elimination, as well as more sophisticated optimizations like reduction simplification that reduce the asymptotic complexity. We present an algorithm to factorize a dependence map so that the maximum potential reuse is exposed.
  [Paper] [Slides] [BibTeX]

              @inproceedings{job24-factorization,
                title     = {Reuse Analysis via Affine Factorization},
                author    = {Job, Ryan and Rajopadhye, Sanjay},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#job24-factorization},
              }
            

• ParameTrick: Coefficient Generalization for Faster Polyhedral Scheduling.
  Gianpietro Consolaro, Harenome Razanajato, Nelson Lossing, Denis Barthou, Zhen Zhang, Corinne Ancourt, and Cédric Bastoul.
  [Abstract]
  Polyhedral Schedulers have been widely used for loop optimization in general-purpose compilers and, more recently, deep-learning compilers. State-of-the-art scheduling algorithms define a vast space of loop transformations and find an optimal solution according to pre-designed cost functions. However, this Integer Linear Programming (ILP) approach can sometimes have complexity issues. The resolution time of ILP grows rapidly as the size of the problem increases. The complexity of the kernel to optimize, in terms of the number of statements, loops, and dependencies, has a significant impact on solving time. Additionally, the performance of ILP solvers can be severely impacted by big coefficients in the ILP, which mostly come from the loop bounds in the original kernel. To tackle this issue, this paper introduces a technique called "ParameTrick". This technique is used during the scheduling pipeline to replace some large coefficients with parameters, which are new variables in the ILP model. The approach is analyzed to determine its impact on the solving time, as well as the transformations that are lost and how to limit the number of unfeasible transformations. Results show that ParameTrick leads to faster solving times while the space of dropped desirable solutions is limited.
  [Paper] [Slides] [BibTeX]

              @inproceedings{consolaro24-parametrick,
                title     = {ParameTrick: Coefficient Generalization for Faster
                              Polyhedral Scheduling},
                author    = {Consolaro, Gianpietro and Razanajato, Harenome
                              and Lossing, Nelson and Barthou, Denis and 
                              Zhang, Zhen and Ancourt, Corinne and Bastoul, C\'{e}dric},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#consolaro24-parametrick},
              }
            

• Polyhedra at Work: Automatic Generation of VHDL Code for the Sherman-Morrison Formula.
  Patrice Quinton, Jérémy Poupart, Michel Lemaire, Daniel Massicotte, and Sanjay Rajopadhye.
  [Abstract]
  Simulation of electrical circuits in real-time requires very short latency implementations that can be achieved only on special-purpose hardware accelerators. The heart of such algorithms is a matrix-vector multiplication between the inverse of the admittance matrix of the circuit and of its current state vector, yielding the next state vector. The main difficulty is to obtain the inverse of the admittance matrix in real-time, as this matrix depends on the state–open or closed–of the switches of the circuit. We consider here the problem of obtaining a new inverse matrix, using the Sherman-Morrison update algorithm, and we explain how various VHDL implementations of this algorithm can be obtained from a high-level, polyhedral equational, description of the circuit.
  [Paper] [Slides] [BibTeX]

              @inproceedings{quinton24-vhdl,
                title     = {Polyhedra at Work: Automatic Generation of VHDL Code
                              for the Sherman-Morrison Formula},
                author    = {Quinton, Patrice and Poupart, J\'{e}r\'{e}my and Lemaire, Michel
                              and Massicotte, Daniel and Rajopadhye, Sanjay},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#quinton24-vhdl},
              }
            

• Employing Polyhedral Methods to Optimize Stencils on FPGAs with Stencil-specific Caches, Data Reuse, and Wide Data Bursts.
  Florian Mayer, Julian Brandner, and Michael Philippsen.
  [Abstract]
  It is well known that to accelerate stencil codes on CPUs or GPUs and to exploit hardware caches and their lines optimizers must find spatial and temporal locality of array accesses to harvest data-reuse opportunities. On FPGAs there is the burden that there are no built-in caches (or only pre-built hardware descriptions for cache blocks that are inefficient for stencil codes). But this paper demonstrates that this lack is also a chance as polyhedral methods can be used to generate stencil-specific cache-structures of the right sizes on the FPGA and to fill and flush them efficiently with wide bursts during stencil execution. The paper shows how to derive the appropriate directives and code restructurings from stencil codes so that the FPGA compiler generates fast stencil hardware. Switching on our optimization improves the runtime of a set of 10 stencils by between 43× and 156×.
  [Paper] [Slides] [BibTeX]

              @inproceedings{mayer24-fpgas,
                title     = {Employing Polyhedral Methods to Optimize Stencils on FPGAs
                              with Stencil-specific Caches, Data Reuse, and Wide Data Bursts},
                author    = {Mayer, Florian and Brandner, Julian and Philippsen, Michael},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#mayer24-fpgas},
              }
            

• An Irredundant Decomposition of Data Flow with Affine Dependences. [25min + 5 min Q&A]
  Corentin Ferry, Steven Derrien, and Sanjay Rajopadhye.
  [Abstract]
  Optimization pipelines targeting polyhedral programs try to maximize the compute throughput. Traditional approaches favor reuse and temporal locality; while the communicated volume can be low, failure to optimize spatial locality may cause a low I/O performance. Memory allocation schemes using data partitioning such as data tiling can improve the spatial locality, but they are domain-specific and rarely applied by compilers when an existing allocation is supplied. In this paper, we propose to derive a partitioned memory allocation for tiled polyhedral programs using their data flow information. We extend the existing MARS partitioning [7] to handle affine dependences, and determine which dependences can lead to a regular, simple control flow for communications. While this paper consists in a theoretical study, previous work on data partitioning in inter-node scenarios has shown performance improvements due to better bandwidth utilization.
  [Paper] [Slides] [BibTeX]

              @inproceedings{ferry24-decomposition,
                title     = {An Irredundant Decomposition of Data Flow with Affine Dependences},
                author    = {Ferry, Corentin and Derrien, Steven and Rajopadhye, Sanjay},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#ferry24-decomposition},
              }
            

• Recover Polyhedral Transformations From Polyhedral Scheduler. [15min + 5 min Q&A]
  Nelson Lossing, Walid Astaoui, Gianpietro Consolaro, Harenome Razanajato, Zhen Zhang, and Denis Barthou.
  [Abstract]
  While Polyhedral optimization offers good performance results, it is often at the price of understandability. The Chlore project — using Clay transformations — is a first attempt at describing Polyhedral optimizations as sequences of highlevel transformations. However, Chlore's output may often be overly complex or contain redundant transformation passes. In this paper,we extend on Chlore's ideas.We present techniques to reduce the number of generated transformation primitives and to optimize the recovery algorithm, showing some important speedups compared to the original Chlore algorithm.
  [Paper] [Slides] [BibTeX]

              @inproceedings{lossing24-recover,
                title     = {Recover Polyhedral Transformations From Polyhedral Scheduler},
                author    = {Lossing, Nelson and Astaoui, Walid and Consolaro, Gianpietro
                              and Razanajato, Harenome and Zhang, Zhen and Barthou, Denis},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#lossing24-recover},
              }
            

• Algebraic Tiling facing Loop Skewing. [15min + 5 min Q&A]
  Clément Rossetti, Alexis Hamon, and Philippe Clauss.
  [Abstract]
  Last year at Impact 2023, we presented an ongoing work of a new tiling technique called algebraic tiling. With algebraic tiling, tiles are defined by their volume (the number of iterations) instead of the size of their edges. This way tile of quasi-equal volumes are generated at runtime, whatever are the original loop bounds. This has many advantages, particularly it addresses load-balancing when parallelizing loops. However, algebraic tiling poses particular challenges when the tiled loops require a final skewing transformations of the tiles in order to exhibit parallel loops. In this paper, we focus on this challenge and propose a solution that makes algebraic tiling applicable in this context too.
  [Paper] [Slides] [BibTeX]

              @inproceedings{rossetti24-algebraic,
                title     = {Algebraic Tiling facing Loop Skewing},
                author    = {Rossetti, Cl\'{e}ment and Hamon, Alexis and Clauss Philippe},
                booktitle = {14th International Workshop on Polyhedral Compilation Techniques
                             (IMPACT 2024, in conjunction with HiPEAC 2024)},
                year      = 2024,
                url       = {https://impact-workshop.org/impact2024/#rossetti24-algebraic},
              }
            

• [Slides]

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=impact2024

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 2024 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.

Workshop Chair

Program Committee

Contact Us

Please send any questions related to the IMPACT 2024 workshop to impact2024.munich@gmail.com