IMPACT 2021

11th International Workshop on Polyhedral Compilation Techniques

January 20, 2021 | Worldwide Event In conjunction with HiPEAC 2021, January 18-20, 2021

With multicore processors, hardware accelerators, and deep memory hierarchies remaining the main sources of performance and energy-efficiency, polyhedral compilation techniques receive more attention than ever from both researchers and practitioners. Thanks to a unified formalism for parallelization and memory optimization, these techniques are now powering domain-specific language compilers yielding best performance in highly competitive areas such as machine learning and numeric simulation. IMPACT is a unique event focusing exclusively on polyhedral compilation that brings together researchers and practitioners for a high-quality one-day event including a keynote and selected paper presentations.

Online Event Logistics

Since this will be the first entirely online IMPACT, we made significant changes to the schedule, compressing it in a single afternoon (CET) workshop. We use the HiPEAC online conference facilities (web, Zoom) for presentationss and discussions.

Update: IMPACT presentations are available online.

Social: IMPACT has a gather.town space! An opportunity to network, discuss in smaller groups, share a whiteboard or have a virtual drink. We have a license for up to 50 concurrent users: in case space fills up please be mindful of other participants and disconnect. You may refer to the HOWTO doc to get started.

Sponsors: We are very grateful to Reservoir Labs for supporting the workshop and sponsoring the HiPEAC conference. Google supported us in providing a gather.town space for all participants.

Program

Slides will be uploaded shortly after the workshop.

Opening (15:00)
• [Slides]


Session 1 (15:00 — 16:30)
• Polygeist: Affine C in MLIR
  William Moses, Lorenzo Chelini, Ruizhe Zhao and Oleksandr Zinenko
  [Abstract]
  We present Polygeist, a new tool that reroutes polyhedral compilation flows to use the representation available in the recent MLIR compilation infrastructure. It consists of two parts: a C and C++ frontend capable of converting a wide vari- ety of existing codes into MLIR suitable for polyhedral trans- formation, and a bi-directional conversion between MLIR’s polyhedral representation and existing polyhedral exchange formats. We demonstrate Polygeist’s flow by converting the entire Polybench/C benchmark suite into MLIR, and by per- forming an IR-to-IR optimization leveraging an existing poly- hedral compiler (Pluto). Our flow produces results within 1.25% of the state-of-the-art Clang compiler, enabling direct comparison of source-to-source and IR-to-binary compilers. We believe Polygeist can improve the interoperation between MLIR and the existing polyhedral tooling, benefiting both the research and the production compiler communities.
  [Paper] [Slides]
• A Templated C++ Interface for isl
  Sven Verdoolaege, Oleksandr Zinenko, Manjunath Kudlur, Ron Estrin, Tianjiao Sun and Harinath Kamepalli
  [Abstract]
  Polyhedral libraries typically support only a very limited collection of types for representing objects, corresponding to broad mathematical classes such as sets, binary relations and functions. Software built on top of these libraries, on the other hand, needs to deal with a plethora of different kinds of objects such as instance sets, access relations and dependence relations. Conceptually, these different kinds of objects can only be combined in very specific ways, but they are all mapped to the same limited collection of types, so that inconsistent combinations can only be detected at run time, if at all. This paper introduces a new templated C++ interface for isl that offers more fine-grained and application- specific types of objects, allowing inconsistencies in use to be detected at compile time, including some that cannot be detected at run time. This makes it easier to understand and correctly write polyhedral code.
  [Paper] [Slides]
• Representing Non-Affine Parallel Algorithms by means of Recursive Polyhedral Equations
  Patrice Quinton and Tomofumi Yuki
  [Abstract]
  Polyhedral equations allow parallel program to be ex- pressed, analyzed, and compiled automatically, but they cannot express divide-and-conquer approaches. This li- mitation is basically due to the affine nature of the de- pendence functions imposed by the model. In this pa- per, we describe how this limitation can be overcome by extending a structured polyhedral equational language to recursive calls of polyhedral programs. Doing so, we preserve the affine property inside a given call, whereas the non-affine part is carried by the recursive expres- sion of subsystem calls. We describe the basic mech- anisms of this extension, show that the fundamental results of polyhedral equations hold, in particular, the schedule of such a system can be found automatically. We illustrate this approach on several well known algo- rithms, including the FFT.
  [Paper] [Slides]


Break (16:30 — 17:00)


Session 2 (17:00 — 18:30)
• Simplifying Dependent Reductions
  Sanjay Rajopadhye
  [Abstract]
  Reductions combine multiple input values with an associative operator to produce (a single or multiple) result(s). When the same input value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduc- tion simplification. Gautam and Rajopadhye [6] showed how reductions in the polyhedral model could be simplified au- tomatically and optimally. In this paper, we tackle the case when (some) input values depend on (some) outputs. This couples simplification with the classic scheduling problem. We show how to extend the Gautam-Rajopadhye algorithm to optimally simplify such dependent reductions.
  [Paper] [Slides]
• Static Versioning in the Polyhedral Model
  Adithya Dattatri and Benoit Meister
  [Abstract]
  We present an approach to enhancing the optimization process in a polyhedral compiler by introducing compile-time versioning, i.e., the production of several versions of optimized code under varying assumptions on its run-time parameters. We illustrate this process by enabling versioning in the polyhedral processor placement pass. We propose an efficient code generation method and validate that versioning can be useful in a polyhedral compiler by performing benchmarking on a small set of deep learning layers defined for dynamically-sized tensors.
  [Paper] [Slides]
• Hardware Abstractions for targeting EDDO Architectures with the Polyhedral Model
  Angshuman Parashar, Prasanth Chatarasi and Po-An Tsai
  [Abstract]
  Unlike cache-based load-store architectures, Explicit De- coupled Data Orchestration (EDDO) architectures are pro- grammed using decoupled but synchronized programs run- ning at various units on the hardware, moving data between storage units and/or performing computations. As such, they present a unique programming challenge. In this paper, we propose a set of hardware abstractions to represent EDDO architectures, enabling them to be targeted with the polyhedral model for statically analyzable work- loads. The abstractions are rich enough to support EDDO ar- chitectures with arbitrarily deep storage hierarchies, hierar- chical parallelism and support for temporal and spatial reuse exploitation via multicast, peer-to-peer communications, and spatial reduction. We also frame the abstractions within the context of an in-progress project called PolyEDDO, which is a mapping analysis and code-generation framework for EDDO architectures.
  [Paper] [Slides] [Recording]

Important Dates

Call For Paper Information

We welcome both theoretical and experimental papers on all aspects of polyhedral compilation and optimization. We also welcome submissions describing preliminary results, crazy new ideas, position papers, experience reports, and available tools, with an aim to stimulate discussions, collaborations, and advances in the field. The following illustrate 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.

Submissions

Submissions should not exceed 10 pages (recommended 8 pages), excluding references, formatted as per ACM SIGPLAN proceedings format. Please use version 1.54 or above of the following templates to prepare your manuscript: ACM Proceedings Template. Make sure to use the sigplan subformat. Visit the SIGPLAN Author Resources page 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=impact2021. Deadline extended until Sunday December 13 AoE. Submission deadline has passed.

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 2021 or any other overlapping SIGPLAN event.

Organizers

Program Committee

• Riyadh Baghdadi, MIT, USA
• Muthu M. Baskaran, Reservoir Labs, USA
• Sam Bayliss, Xilinx, USA
• Philippe Clauss, University of Strasbourg, France
• Paul Feautrier, ENS Lyon, France
• Guillaume Iooss, INRIA, France
• Louis Noel Pouchet, Colorado State University, USA
• Eun Jung Park, LANL, USA
• Mahesh Ravishankar, Google, USA
• Michelle Strout, The University of Arizona, USA
• Adilla Susungi, Huawei, France
• Ramakrishna Upadrasta, IITH, India
• Tomofumi Yuki, INRIA, France
• Jie Zhao, State Key Laboratory of Mathematical Engineering and Advanced Computing, China

Contact us

Please send any questions to impact-chairs@lists.gforge.inria.fr.