IMPACT 2018

8th International Workshop on Polyhedral Compilation Techniques

January 23, 2018 | Manchester, United Kingdom In conjunction with HiPEAC 2018, January 22-24, 2018

Polyhedral techniques have gained attention due to the rise of multi-core processors and other architectures that require parallelism and more complex schedules for data locality. At the heart of the polyhedral model is an abstraction of programs that enables powerful analysis and scheduling of applications. Recent developments in the polyhedral model research area includes automatic parallelization targeting various platforms, program verification, and hardware synthesis. IMPACT is a unique workshop aimed to bring together researchers and practitioners interested in polyhedral techniques to exchange ideas.

The workshop will be held in Room #11

Program

Opening (10:00 - 10:15)


• Welcome
  Martin Kong (Brookhaven National Laboratory) and Francois Irigoin (Mines ParisTech)
  
  
Keynote: Can compilers help us achieve high performance, software productivity, and portability? (10:15-11:15am)
• Prof. P. (Saday) Sadayappan (Ohio State University)
  Summary:
  It is generally very challenging to achieve high performance and high user productivity in developing software. Although compiler technology continues to advance, significant manual effort or the use of high performance libraries (which have typically been manually synthesized/tuned) is currently necessary to achieve high performance. Further compounding the software development problem is the multiplicity of architectural targets of interest for high-performance, including short-vector SIMD processors, GPUs, and FPGAs. Thus, it is a grand challenge to achieve all three: productivity, performance, and portability. The diversity of architectural targets and the increasing relative cost of data movement over computation will make this challenge more daunting in the future. Compilers can play a significant role, but many challenges must be addressed. This talk will discuss opportunities and challenges.
  Bio:
  P. (Saday) Sadayappan is a Professor of Computer Science and Engineering at The Ohio State University. His research interests include compiler optimization for heterogeneous systems, domain/pattern-specific compiler optimization, characterization of data movement complexity of algorithms, and data-structure centric performance optimization. He obtained a Bachelors degree from IIT-Madras, and an M.S. and Ph.D. from Stony Brook University. He is a Fellow of the IEEE.
  

Break (11:15 - 11:30)



Session I: Scheduling and Optimization
• Polyhedral Optimization For JavaScript: The Challenges
  Manuel Selva, Julien Pages and Philippe Clauss
  The JavaScript language was originally designed to help writ- ing small scripts adding dynamism in web pages. It is now widely used, both on the server and client sides, also for programs requiring intensive computations. Some examples are video game engines and image processing applications. This work focuses on improving performance for this kind of programs. Because JavaScript is a dynamic language, a JavaScript program cannot be compiled e ciently to native code. For achieving good performance on such dynamic programs, the common implementation strategy is to have several layers handling the JavaScript code, starting from interpretation, up to aggressive just-in-time compilation. Nev- ertheless, all existing implementations execute JavaScript functions using a single thread. In this work we propose to use the polyhedral model in the just-in-time compilation layer to parallelize compute-intensive programs that include loop nests. We highlight what are the scientific challenges, resulting from the dynamism of the language, for integrating automatic polyhedral optimization. We then show how to solve these challenges in the JavaScriptCore implementation of Apple.
  [paper], [slides]


• Extending Pluto-Style Polyhedral Scheduling with Consecutivity
  Sven Verdoolaege and Alexandre Isoard
  The Pluto scheduler is a successful polyhedral scheduler that is used in one form or another in several research and produc- tion compilers. The core scheduler is focused on parallelism and temporal locality and does not directly target spatial locality. Such spatial locality is known to bring performance bene ts and has been considered in various forms outside and inside polyhedral compilation. For example, the Pluto compiler has some support for spatial locality, but it is limited to a post-processing step involving only loop interchange. Consecutivity is a special case of spatial locality that aims for stride-1 accesses, which can be useful for constructing burst accesses and for vectorization. Stride-1 accesses have been targeted by an approach based on one-shot scheduling, but it is fairly approximative and not directly transferable to a Pluto-style scheduler. This paper describes an approach for consecutivity that is integrated in a Pluto-style polyhedral scheduler, as implemented in isl. Both intra-statement and inter-statement consecutivity is considered, taking into account multiple references per statement and the integration into a component based incremental scheduler.
  [paper], [slides]


• Optimization Through Recomputation in the Polyhedral Model
  Mike Jongen, Luc Waeijen, Roel Jordans, Lech Jozwiak, Henk Corporall
  Many modern (mobile) systems involve memory intensive computations. External memory accesses are costly when it comes to the execution time and energy consumption of a program. To overcome this, we usually apply tiling to improve data locality and data reuse in internal memories. In the research reported in this paper we add the possibility to recompute data rather than storing temporary results, and demonstrate that this can have a positive e ect on the overall application performance.
  To achieve this we represented recomputation in the Polyhedral model by extending Polly. We experimentally veri ed the e ectiveness of recomputation on a pair of Convolutional Neural Network layers, when applying loop tiling, loop fusion, and recompute.
  [paper], [slides]



Lunch (13:00 - 14:00)



Session II: Polyhedral Runtime Techniques
• Load Balancing with Polygonal Partitions
  Aniket Shivam, Priyanka Ravi, Alexander Veidenbaum, Alexandru Nicolau and Rosario Cammarota
  In this work we propose a new dynamic scheduling technique for DOALL loops with non-uniform reuse patterns. Dynamic scheduling of a DOALL loop with non-uniform reuse patterns partitions the loop into chunks of iterations that exhibit poor locality at runtime - dynamic scheduling algorithms do not factor in locality. This results in suboptimal completion time even if the load imbalance is bounded by the chosen scheduling algorithm, e.g., guided self-scheduling. Partitioning a DOALL loop for maximizing locality produces chunks of sizes that depend on the reuse patterns in the loop and do not account for load imbalance at runtime. Hence, even though locality in each chunk is maximized, the performance achieved during parallel execution is suboptimal. The proposed technique starts with partitioning a DOALL loop with a polyhedral framework to create partitions that maximize locality, and then re-tiles these partitions to achieve load balance at runtime. The proposed re-tiling and scheduling technique shows a performance speedup up to 2x against PLuTo.
  [paper], [slides]


• Abstractions for Specifying Sparse Matrix Data Transformations
  Payal Nandy, Eddie Davis, Mahdi Soltan Mohammadi, Wei He, Mary Hall, Michelle Strout and Catherine Olschanowsky
  The inspector/executor paradigm permits using runtime information in concert with compiler optimization. An inspector collects information that is only available at runtime; this information is used by an optimized executor that was created at compile time. Inspectors are widely used in optimizing irregular computations, where information about data dependences, loop bounds, data structures, and memory access patterns are collected at runtime and used to guide code transformation, parallelization, and data layout. Most research that uses inspectors relies on instantiating inspector templates, invoking inspector library code, or manually writing inspectors. In this paper, we build on existing abstractions and develop new abstractions with the goal of a framework for specifying inspectors that combine loop and data transformations for sparse matrix computations. As a starting point, we rely on existing abstractions in the Sparse Polyhedral Framework (SPF), which is an extension of the polyhedral framework for transformation and code generation. SPF extends the polyhedral framework to represent runtime information with uninterpreted functions and represent inspector computations that explicitly realize such functions at runtime. An Inspector Dependence Graph (IDG) describes a set of interrelated computations that comprise the inspector. We extend the existing IDG, which was previously used for data and iteration space reordering, to also encompass data transformations such as conversions between sparse matrix formats. We show how inspectors from prior work on sparse matrix transformations can be expressed using these abstractions, and discuss possible extensions to support inspector composition and incorporate other optimizations. This paper represents a step towards the goal of creating composable inspectors in keeping with the composability of affine transformations on the executors.
  [paper], [slides]


• Polyhedral Modeling of Immutable Sparse Matrices
  Gabriel Rodriguez and Louis-Noel Pouchet
  Sparse matrices conveniently store only non-zero values of the matrix. This representation may greatly optimize storage and computation size, but typically prevents polyhedral analysis of the application due to the presence of indirection arrays. While speciic strategies have been proposed to address this limitation, such as the Sparse Polyhedral Framework and Inspector/Executor approaches, we aim instead in this paper to partition the irregular computation into a union of regular (polyhedral) pieces which can then be optimized by of-the-shelf polyhedral compilers. This paper proposes to automatically analyze sparse matrix codes with irregular accesses and build a sequence of static control parts which reproduce the sparse matrix computation but using only aine loops and indices. Speciically, we focus on immutable sparse matrices, and develop a custom polyhedral trace compression technique to uncover regular pieces on the input sparse matrix. We illustrate how to build a łsparse" matrix-vector multiplication operation as a union of dense polyhedral subcomputations, and show experimental results for the Harwell-Boeing collection.
  [paper], [slides]



Break (15:30 - 16:00)



Session III: Core Techniques
• On Polynomial Code Generation
  Paul Feautrier, Alain Darte and Albert Cohen
  Parallel programs need optimizing compilers capable of analyzing, transforming and generating code with complex concurrent and parallel constructs. While polyhedral methods are popular means to reason about loop nests and data parallelism, the concurrency arising from task parallel and streaming languages leads to more complex control ow and dependence patterns. One important family of transformations consists in converting one expression of parallelism into another, closer to the machine. For example, one may need to convert massive amounts of task-level concurrency in OpenStream to data parallel execution or to “compile” this parallelism into coarser grain tasks. In the same spirit, an optimizing compiler for parallel programs may aim at reducing the dynamic range of runtime behavior by restricting the schedules to a constrained set of parallel executions, thereby controling memory usage in streams, improving temporal locality, avoiding false sharing, bounding latency, etc. We argue that polynomial scheduling methods are well suited to express such transformations, and investigate the downstream schedule-guided generation of syntactic code for a target parallel language using clocks. With this motivation in mind, let us review the main challenges and state of the art in polynomial methods to reason about the transformation of task-parallel programs.
  [paper], [slides]


• Basic Algorithms for Periodic-Linear Inequalities and Integer Polyhedra
  Alain Ketterlin
  This paper explores an alternative definition of linear inequalities over integer variables, focusing on expressive power and precision. The core technique is to use periodic numbers (also called Ehrhart numbers) to account for the seemingly irregular behavior of affine combinations of integer variables. The new representation is used to tighten inequalities, and from there derive a correct and complete decision procedure similar to Fourier-Motzkin elimination. A decomposition algorithm is also described: its result is a disjoint union of elementary polyhedra. Members of the union have a single contiguous range on each dimension, and are guaranteed to be non-empty. The data-structure used to represent the decomposition is similar to an abstract syntax tree. Several properties of this representation are briefly examined.
  [paper], [slides]



Important Dates

Abstract deadline:	October 27, 2017 (AoE)
Paper deadline:	November 3, 2017 (AoE)
Paper deadline:	November 10, 2017 (AoE)
Notification of decision:	December 4, 2017
Final version due:	December 16, 2017
Workshop:	January 23, 2018

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:

• 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.
• Presentation of an existing idea in a different way including illustrations of how the idea applies in current codes. Attribution should be done as well 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
• static analysis
• program verification
• model checking
• theoretical foundations of the polyhedral model
• extensions of the polyhedral model
• scalability and robustness of polyhedral compilation techniques
• autotuning
• application case studies
• tool demonstration

Submissions

Submissions should not exceed 10 pages (recommended 8 pages), excluding references, formatted as per the new ACM proceedings style. When preparing your manuscript, please use the sigplan subformat and a font size of 10pt or higher. Latex and Word sources can be found in ACM. For more information please refer to PLDI18-Formatting Requirements and SIGPLAN's Author Resources.




Submissions should be in PDF format and printable on US letter or A4 sized paper.




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 paper with significant overlap with IMPACT submission cannot be sent to PLDI 2018 or any other overlapping SIGPLAN event.




This year we will be using EasyChair to handle IMPACT's submissions of abstracts and papers. To do so, please use the following link: EasyChair/Impact

Contact us

Please send any questions or comments to Francois Irigoin and Martin Kong:

impact-chairs@lists.gforge.inria.fr.