Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies

Girbal, Sylvain; Vasilache, Nicolas; Bastoul, C├ędric; Cohen, Albert; Parello, David; Sigler, Marc; Temam, Olivier
June 2006
International Journal of Parallel Programming;Jun2006, Vol. 34 Issue 3, p261
Academic Journal
Modern compilers are responsible for translating the idealistic operational semantics of the source program into a form that makes efficient use of a highly complex heterogeneous machine. Since optimization problems are associated with huge and unstructured search spaces, this combinational task is poorly achieved in general, resulting in weak scalability and disappointing sustained performance. We address this challenge by working on the program representation itself, using a semi-automatic optimization approach to demonstrate that current compilers offen suffer from unnecessary constraints and intricacies that can be avoided in a semantically richer transformation framework. Technically, the purpose of this paper is threefold: (1) to show that syntactic code representations close to the operational semantics lead to rigid phase ordering and cumbersome expression of architecture-aware loop transformations, (2) to illustrate how complex transformation sequences may be needed to achieve significant performance benefits, (3) to facilitate the automatic search for program transformation sequences, improving on classical polyhedral representations to better support operation research strategies in a simpler, structured search space. The proposed framework relies on a unified polyhedral representation of loops and statements, using normalization rules to allow flexible and expressive transformation sequencing. Thisrepresentation allows to extend the scalability of polyhedral dependence analysis, and to delay the (automatic) legality checks until the end of a transformation sequence. Our work leverages on algorithmic advances in polyhedral code generation and has been implemented in a modern research compiler.


Related Articles

  • Minimal Unroll Factor for Code Generation of Software Pipelining. Bachir, Mounira; Touati, Sid-Ahmed-Ali; Brault, Frederic; Gregg, David; Cohen, Albert // International Journal of Parallel Programming;Feb2013, Vol. 41 Issue 1, p1 

    We address the problem of generating compact code from software pipelined loops. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates lifetime intervals spanning multiple loop iterations. These intervals require periodic register allocation (also...

  • Model, Design, and Evaluation of a Compiler for a Parallel Processing Environment. Baer, Jean-Loijp; Ellis, Carla S. // IEEE Transactions on Software Engineering;Nov77, Vol. 3 Issue 6, p394 

    The problem of designing compilers for a multiprocessing environment is approached. We show that by modeling an existing sequential compiler, we gain an understanding of the modifications necessary to transform the sequential structure into a pipeline of processes. The pipelined compiler is then...

  • Loop Tiling.  // Network Dictionary;2007, p293 

    A definition of the term "Loop Tiling" is presented. Also called loop blocking, it refers to a loop optimization used by compilers to make the execution of certain types of loops more efficient. It partitions a loop's iteration space into smaller chunks or blocks to ensure that data used in a...

  • Keep up with multiple cores. Weltzin, Casey; Bell, Ian // Electronics Weekly;5/27/2009, Issue 2385, p12 

    The article focuses on harnessing developments in the parallel processing. Most commercial compilers do not automatically optimize code for parallel execution, so embedded designers use parallel programming which add overhead and are difficult to debug. The most apparent solution to the...

  • Parallel Compiler.  // Network Dictionary;2007, p365 

    A definition of the term "parallel compiler" in the context of computer software is presented. This refers to a type of computer compiling technique that speeds up the process of compilation on multi-processor machines. Super-computers and other large scale multi-processor machines make use of...

  • Automatic Parallelization of Recursive Procedures. Gupta, Manish; Mukhopadhyay, Sayak; Sinha, Navin // International Journal of Parallel Programming;Dec2000, Vol. 28 Issue 6, p537 

    Parallelizing compilers have traditionally focussed mainly on parallelizing loops. This paper presents a new framework for automatically parallelizing recursive procedures that typically appear in divide-and-conquer algorithms. We present compile-time analysis, using powerful, symbolic array...

  • OPTIMAL ASSIGNMENT OF COMPONENTS TO PARALLEL-SERIES AND SERIES-PARALLEL SYSTEMS. Prasad, V. Rajendra; Nair, K. P. K.; Aneja, Y. P. // Operations Research;May/Jun91, Vol. 39 Issue 3, p407 

    This paper deals with the problem of assigning components to parallel-series (PS) and series-parallel (SP) systems so as to maximize the system's reliability We assume that any component can be assigned to any position of the system and the reliability of component j is r[sub I] p[sub j] if it...

  • A New Approach to Parallelization of Serial Nested Loops Using Genetic Algorithms. Parsa, Saeed; Lotfi, Shahriar // Journal of Supercomputing;Apr2006, Vol. 36 Issue 1, p83 

    Loop parallelization is an important issue in the acceleration of the execution of scientific programs. To exploit parallelism in loops a system of equations representing the dependencies between the loop iterations and a system of non-equations indicating the loop boundary conditions has to be...

  • Parallel loop generation and scheduling. Lotfi, Shahriar; Parsa, Saeed // Journal of Supercomputing;Dec2009, Vol. 50 Issue 3, p289 

    Loop tiling is an efficient loop transformation, mainly applied to detect coarse-grained parallelism in loops. It is a difficult task to apply n-dimensional non-rectangular tiles to generate parallel loops. This paper offers an efficient scheme to apply non-rectangular n-dimensional tiles in...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics