IMPACT 2019

9th International Workshop on Polyhedral Compilation Techniques

January 23, 2019 | Valencia, Spain In conjunction with HiPEAC 2019, January 21-23, 2019

With multicore processors and deep memory hierarchies remaining the main source of performance, and emerging areas such as energy-aware computation requiring research breakthroughs, 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, selected paper presentations, and posters for work-in-progress discussions.

Program

Opening and Keynote (10:00 - 11:00)


• Welcome
  David Wonnacott (Haverford College) and Oleksandr Zinenko (Google Inc.)
  
• Keynote: With great trends come great (polyhedral) responsibilities
  Benoît Meister (Reservoir Labs)
  [Abstract] [Slides]
  Larger scale computing requires a step up from loop parallelism in exhibiting parallelism in programs. Simultaneously, the prominence of accelerators and the arrival of Near Threshold Voltage make computing more heterogeneous and call for better load balancing technologies. Memories are still mostly far away from processing, and over-provisioning of computations seems to be the magic bullet that enables data access latency to be covered by computations, provided that … there is enough parallelism. Event-Driven Task (EDT) programming paradigms, in which a parallel program is declared in terms of tasks that can schedule each other asynchronously and define inter-task dependencies, seem to be the community’s response to these combined needs. We discuss the challenges and ideas we had in the process of targeting EDTs in a polyhedral mapper.
  Do you know anybody who doesn’t do anything related to Deep Learning (DL), nowadays ? This mega-trend is an incredible opportunity to show the superiority of the polyhedral approach to the world. We take note that DL researchers tend to reinvent the wheel at an age when wheels are automatically built (and there are even free wheel-building machines!), and we open the Pandora’s box of how to make developers use polyhedral model more broadly.


Break (11:00 — 11:30)


Session 1: Theoretical Aspects (11:30 — 13:00)
• Paper: Some Efficient Algorithms for the Tightest U-TVPI Polyhedral Over-Approximation problem.
  Abhishek Patwardhan and Ramakrishna Upadrasta.
  [Abstract] [Paper]
  Many static analysis problems involve solving mathematical data-flow equations over various numerical abstract domains. Convex polyhedra is one such abstract domain that is widely used to precisely capture affine relationships among program variables. However, majority of the analysis problems based on convex polyhedral domains fail to scale for large problem sizes due to the high-complexity/exponential nature of operations defined over them (such as Feasibility, Optimization, Fourier-Motzkin, Vertex enumeration).
  The (Unit-)Two Variable Per Inequality (UTVPI) Polyhedra (also called as Octagons) have been proven to be a very useful abstract domain; due to its improved worst-case polynomial time complexity, as well as ease of implementation. In order to enable usage of Octagon abstract domain, it becomes important to efficiently compute the tightest Octagonal Over-Approximation (OA) from an arbitrary convex-polyhedron.
  In this paper, we present two new algorithms that compute the tightest UTVPI-OA of a given convex polyhedron (provided it exists) by relying on elementary polyhedral operations. Our algorithms improve over the OA algorithm that is implemented in the state-of-art libraries.
  Our first algorithm is based on linear programming (LP) which based on a series of LP calls. Our second algorithm is based on Fourier-Motzkin elimination (projections) combined with a only rotation operations. Both the algorithms fully exploit the Octagonal nature of the OA that they aim to obtain; so, they are highly simple in nature (in theory as well as implementation), simple to reason about correctness and optimality, and also very easy to implement. We implemented our two algorithms in the Integer Set Library (ISL), a open-source polyhedral compilation library.
  We believe that our algorithms will be useful in various static analysis as well as polyhedral compilation applications like polyhedral scheduling, code-generation, cache miss calculation, transitive closure.
• Paper: The Limit of Polynomials
  Tomofumi Yuki
  [Abstract] [Paper] [Slides]
  This paper studies the Handelman's theorem used for polynomial scheduling, which resembles the Farkas' lemma for affine scheduling. Theorems from real algebraic geometry and polynomial optimization show that some polynomials have Handelman representations when they are non-negative on a domain, instead of strictly positive as stated in Handelman's theorem. The global minimizers of a polynomial must be at the boundaries of the domain to have such a representation with finite bounds on the degree of monomials. This creates discrepancies in terms of polynomials included in the exploration space with a fixed bound on the monomial degree. Our findings give an explanation to our failed attempt to apply polynomial scheduling to Index-Set Splitting: we were precisely trying to find polynomials with global minimizers at the interior of a domain.
• Talk: Semantic Array Dataflow Analysis.
  Paul Iannetta, Laure Gonnord, Lionel Morel and Tomofumi Yuki.
  [Abstract] [Slides]
  This paper revisits the polyhedral model's key analysis, dependency analysis. The semantic formulation we propose allows a new definition of the notion of dependency and the computation of the dependency set. As a side effect, we propose a general algorithm to compute an over-approximation of the dependency set of general imperative programs.
  We argue that this new formalization will later allow for a new vision of the polyhedral model in terms of semantics, which will help us fully characterize its expressivity and applicability. We also believe that abstract semantics will be the key for designing an approximate abstract model in order to enhance the applicability of the polyhedral model.


Break (13:00 — 14:00)


Session 2: Practical Aspects (14:00 — 15:30)
• Paper: The Polyhedral Model Beyond Loops - Recursion Optimization and Parallelization Through Polyhedral Modeling
  Salwa Kobeissi and Philippe Clauss.
  [Abstract] [Paper] [Slides]
  There may be a huge gap between the statements outlined by programmers in a program source code and instructions that are actually performed by a given processor architecture when running the executable code. This gap is due to the way the input code has been interpreted, translated and transformed by the compiler and the final processor hardware. Thus, there is an opportunity for efficient optimization strategies, that are dedicated to specific control structures and memory access patterns, to apply as soon as the actual runtime behavior has been discovered, even if they could not have been applied on the original source code.
  In this paper, we develop this idea by identifying code extracts that behave as polyhedral-compliant loops at runtime, while not having been outlined at all as loops in the original source code. In particular, we are interested in recursive functions whose runtime behavior can be modeled as polyhedral loops. Therefore, the scope of this study exclusively includes recursive functions whose control flow and memory accesses exhibit an affine behavior, which means that there exists a semantically equivalent affine loop nest, candidate for polyhedral optimizations. Accordingly, our approach is based on analyzing early executions of a recursive program using a Nested Loop Recognition (NLR) algorithm, performing the affine loop modeling of the original program runtime behavior, which is then used to generate an equivalent iterative program, finally optimized using the polyhedral compiler Polly. We present some preliminary results showing that this approach brings recursion optimization techniques into a higher level in addition to widening the scope of the polyhedral model to include originally non-loop programs.
• Talk: Abstracting Iteration- and Data-Space Transformations with High-Level Language Features
  David Wonnacott, Mary Glaser, Divesh Otwani and Sehyeok Park.
  [Abstract] [Slides]
  Automatic polyhedral optimizers may fail to identify an op- timal transformation for a number of reasons. For example, they may be unable to analyze non-affine terms, their sched- uling technique may include assumptions or algorithmic steps that exclude the optimal schedule(s), or they may not be able to identify optimizations that require data-space, as well as iteration-space, transformation. When performance is critical and automatic tools fail, programmers may resort to hand-tuning their codes, hoping to buy performance at the price of hours of work, loss of code readability and porta- bility, and the potential introduction of bugs.
  In general, we aim to solve these problems with (1) clever polyhedral or non-polyhedral optimizations of both iteration and storage spaces, and, (2) abstractions that use high-level languages features to maintain the clarity of the algorithms in optimized code.
  Prior work has abstracted PluTo’s “diamond tiling” op- timization via Chapel’s iterators (without sacrificing per- formance results). We have used Chapel’s iterators, along with Chapel’s records, to abstract optimizations -that are not found by PluTo- of Nussinov’s algorithm (in prior work) and the Deriche image processing algorithm, and we have confirmed that storage-space transformation can produce greater speedup than Pluto for the syr2k linear algebra kernel (all from the Polybench benchmark suite).
• Paper: Beyond Polyhedral Analysis of OpenStream Programs
  Nuno Miguel Nobre, Andi Drebes, Graham Riley and Antoniu Pop.
  [Abstract] [Paper] [Slides]
  Polyhedral techniques are, when applicable, an effective instrument for automatic parallelization and data locality optimization of sequential programs. This paper motivates their adoption in OpenStream, a task-parallel streaming language following the dataflow model of execution. We show that (1) it is possible to exploit the parallelism that naturally arises from dataflow task graphs with loop tiling transformations provided by the polyhedral model and (2) that a combination of dataflow task-parallelism and polyhedral optimizations performs significantly better than polyhedral parallelization techniques applied to sequential programs and dataflow task-parallelism without polyhedral optimization techniques. Our technique obtains parallel speedups superior to 1.2x when compared to state-of-the-art polyhedral-tiled OpenMP, and 1.6x when compared to manually tiled OpenStream implementations, for a simple Gauss-Seidel kernel.
  However, stream indexing is often polynomial in the general case, severely limiting the set of OpenStream programs amenable to polyhedral tools and hindering the automation of our technique. We further investigate how the approach of Feautrier may offer a path not only to automatically convert fine-grained task-level concurrency to coarser-grained tasks, but also for scheduling under resource constraints.


Break (15:30 — 16:00)


Session 3: Data Layout Transformations (16:00 — 16:30)
• Paper: Integrating Data Layout Transformations with the Polyhedral Model
  Jun Shirako and Vivek Sarkar.
  [Abstract] [Paper] [Slides]
  In the polyhedral model, classical loop transformations and statement reordering transformations have been unified and formalized as affine scheduling problems that can be applied to optimization goals such as locality and parallelism. More recently, data layout transformations have shown significant benefits in improving performance by contributing to improved efficiencies in spatial locality, multi-core parallelism and vector parallelism. However, integration of data layout transformations in the polyhedral model has received relatively little attention thus far.
  In this paper, we report on our work-in-progress on integrating data layout transformations in the polyhedral model, with a focus on affine representations of data layout transformations. We also demonstrate the potential benefit of performing loop and data layout transformations as an integrated optimization problem, compared to standard decoupled approaches which pick a specific phase order (e.g., data layout transformations before loop transformations) and can thereby miss opportunities to co-optimize both data layout transformations and loop transformations.


Panel Discussion and Closing (16:30 — 17:15)
• Panel: The Polyhedral Model in the Age of Implementation
  Panelists: Cédric Bastoul, Albert Cohen, Benoît Meister, Sven Verdoolaege.

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=impact2019. 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 2019 or any other overlapping SIGPLAN event.

Organizers

Program Committee

Contact us

Please send any questions to Oleksandr Zinenko and David Wonnacott to impact-chairs@lists.gforge.inria.fr.