NDLI: Revisiting loop fusion in the polyhedral framework

Please wait, while we are loading the content...

21st century computer architecture

PREDATOR: predictive false sharing detection

X10 and APGAS at Petascale

CUDA-NP: realizing nested thread-level parallelism in GPGPU applications

Eliminating global interpreter locks in ruby through hardware transactional memory

Beyond parallel programming with domain specific languages

Designing and auto-tuning parallel 3-D FFT for computation-communication overlap

Revisiting loop fusion in the polyhedral framework

Towards fair and efficient SMP virtual machine scheduling

Heterogeneous computing: what does it mean for compiler research?

Fast concurrent lock-free binary search trees

Lock contention aware thread migrations

Concurrency testing using schedule bounding: an empirical study

Resilient X10: efficient failure-aware programming

yaSpMV: yet another SpMV framework on GPUs

Leveraging hardware message passing for efficient thread synchronization

A decomposition for in-place matrix transposition

Triolet: a programming system that unifies algorithmic skeleton interfaces for high-performance cluster computing

Efficient deterministic multithreading without global barriers

A general technique for non-blocking trees

Infrastructure-free logging and replay of concurrent execution on multiple cores

Trace driven dynamic deadlock detection and reproduction

Portable, MPI-interoperable coarray fortran

Singe: leveraging warp specialization for high performance on GPUs

Well-structured futures and cache locality

In-place transposition of rectangular matrices on accelerators

A tool to analyze the performance of multithreaded programs on NUMA architectures

Race directed scheduling of concurrent programs

Practical concurrent binary search trees via logical ordering

Parallelization hints via code skeletonization

Efficient search for inputs causing high floating-point errors

Time-warp: lightweight abort minimization in transactional memory

Parallelizing dynamic programming through rank convergence

A practical wait-free simulation for lock-free data structures

Concurrency bug localization using shared memory access pairs

Task mapping stencil computations for non-contiguous allocations

Data structures for task-based priority scheduling

Detecting silent data corruption through data dynamic monitoring for scientific applications

Fine-grain parallel megabase sequence comparison with multiple heterogeneous GPUs

Automatic semantic locking

Optimistic transactional boosting

Provably good scheduling for parallel programs that use data structures through implicit batching

Theoretical analysis of classic algorithms on highly-threaded many-core GPUs

SCCMulti: an improved parallel strongly connected components algorithm

Initial study of multi-endpoint runtime for MPI+OpenMP hybrid programming model on multi-core systems

Extracting logical structure and identifying stragglers in parallel execution traces

Revisiting loop fusion in the polyhedral framework

Content Provider	ACM Digital Library
Author	Yew, Pen-Chung Mehta, Sanyam Lin, Pei-Hung
Abstract	Loop fusion is an important compiler optimization for improving memory hierarchy performance through enabling data reuse. Traditional compilers have approached loop fusion in a manner decoupled from other high-level loop optimizations, missing several interesting solutions. Recently, the polyhedral compiler framework with its ability to compose complex transformations, has proved to be promising in performing loop optimizations for small programs. However, our experiments with large programs using state-of-the-art polyhedral compiler frameworks reveal suboptimal fusion partitions in the transformed code. We trace the reason for this to be lack of an effective cost model to choose a good fusion partitioning among the possible choices, which increase exponentially with the number of program statements. In this paper, we propose a fusion algorithm to choose good fusion partitions with two objective functions - achieving good data reuse and preserving parallelism inherent in the source code. These objectives, although targeted by previous work in traditional compilers, pose new challenges within the polyhedral compiler framework and have thus not been addressed. In our algorithm, we propose several heuristics that work effectively within the polyhedral compiler framework and allow us to achieve the proposed objectives. Experimental results show that our fusion algorithm achieves performance comparable to the existing polyhedral compilers for small kernel programs, and significantly outperforms them for large benchmark programs such as those in the SPEC benchmark suite.
Starting Page	233
Ending Page	246
Page Count	14
File Format	PDF
ISBN	9781450326568
DOI	10.1145/2555243.2555250
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-02-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Coarse-grained parallelism Data reuse Loop fusion Polyhedral framework
Content Type	Text
Resource Type	Article

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

Revisiting loop fusion in the polyhedral framework

Dependence-Based Code Transformation for Coarse-Grained Parallelism

Exploiting Loop-Level Parallelism on Coarse-Grained Reconfigurable Architectures Using Modulo Scheduling

Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model

Exploiting coarse-grained task, data, and pipeline parallelism in stream programs

A Multiprocessor Architecture Combining Fine-Grained and Coarse-Grained Parallelism Strategies (1994)

Memory-Aware Loop Paralleling for Coarse-Grained Reconfigurable Architectures

Exploiting Coarse-Grained Parallelism in B+ Tree Searches on an APU

Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model.

Revisiting loop fusion in the polyhedral framework

Similar Documents

Revisiting loop fusion in the polyhedral framework

Dependence-Based Code Transformation for Coarse-Grained Parallelism

Exploiting Loop-Level Parallelism on Coarse-Grained Reconfigurable Architectures Using Modulo Scheduling

Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model

Exploiting coarse-grained task, data, and pipeline parallelism in stream programs

A Multiprocessor Architecture Combining Fine-Grained and Coarse-Grained Parallelism Strategies (1994)

Memory-Aware Loop Paralleling for Coarse-Grained Reconfigurable Architectures

Exploiting Coarse-Grained Parallelism in B+ Tree Searches on an APU

Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model.

Revisiting loop fusion in the polyhedral framework