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

Content Provider	Springer Nature Link
Author	Girbal, Sylvain Vasilache, Nicolas Bastoul, Cédric Cohen, Albert Parello, David Sigler, Marc Temam, Olivier
Copyright Year	2006
Abstract	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.
Starting Page	261
Ending Page	317
Page Count	57
File Format	PDF
ISSN	08857458
Journal	International Journal of Parallel Programming
Volume Number	34
Issue Number	3
e-ISSN	15737640
Language	English
Publisher	Kluwer Academic Publishers-Plenum Publishers
Publisher Date	2006-07-21
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Compiler optimization semi-automatic program transformation polyhedral model automatic parallelization Theory of Computation Software Engineering/Programming and Operating Systems Processor Architectures
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons

Dynamic resolution: A runtime technique for the parallelization of modifications to directed acyclic graphs

Predictive Modeling in a Polyhedral Optimization Space

Extensible Recognition of Algorithmic Patterns in DSP Programs for Automatic Parallelization

The Cetus Source-to-Source Compiler Infrastructure: Overview and Evaluation

Towards Systematic Parallelization of Graph Transformations Over Pregel

New Data Structures to Handle Speculative Parallelization at Runtime

Nested Parallelization with OpenMP

Automatic Parallelization of Recursive Procedures

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

Similar Documents

Dynamic and Speculative Polyhedral Parallelization Using Compiler-Generated Skeletons

Dynamic resolution: A runtime technique for the parallelization of modifications to directed acyclic graphs

Predictive Modeling in a Polyhedral Optimization Space

Extensible Recognition of Algorithmic Patterns in DSP Programs for Automatic Parallelization

The Cetus Source-to-Source Compiler Infrastructure: Overview and Evaluation

Towards Systematic Parallelization of Graph Transformations Over Pregel

New Data Structures to Handle Speculative Parallelization at Runtime

Nested Parallelization with OpenMP

Automatic Parallelization of Recursive Procedures

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