NDLI: Chunking parallel loops in the presence of synchronization

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

A european perspective on supercomputing

The roadrunner project and the importance of energy efficiency on the road to exascale computing

Computing outside the box

Implementation of a wide-angle lens distortion correction algorithm on the cell broadband engine

Zero-content augmented caches

OhHelp: a scalable domain-decomposing dynamic load balancing for particle-in-cell simulations

Fast memory snapshot for concurrent programmingwithout synchronization

Parametric multi-level tiling of imperfectly nested loops

Efficient high performance collective communication for the cell blade

Fast and scalable list ranking on the GPU

Creating artificial global history to improve branch prediction accuracy

A graph based approach for MPI deadlock detection

FTL design exploration in reconfigurable high-performance SSD for server applications

Single-particle 3d reconstruction from cryo-electron microscopy images on GPU

Combining thread level speculation helper threads and runahead execution

EpiFast: a fast algorithm for large scale realistic epidemic simulations on distributed memory systems

Adagio: making DVS practical for complex HPC applications

MPI collective communications on the blue gene/p supercomputer: algorithms and optimizations

High-performance regular expression scanning on the Cell/B.E. processor

Dynamic cache clustering for chip multiprocessors

Pattern-based sparse matrix representation for memory-efficient SMVM kernels

QuakeTM: parallelizing a complex sequential application using transactional memory

Dynamic parallelization of single-threaded binary programs using speculative slicing

Practice of parallelizing network applications on multi-core architectures

Tuned and wildly asynchronous stencil kernels for hybrid CPU/GPU systems

Exploring pattern-aware routing in generalized fat tree networks

Maximizing MPI point-to-point communication performance on RDMA-enabled clusters with customized protocols

/scratch as a cache: rethinking HPC center scratch storage

How GPUs can outperform ASICs for fast LDPC decoding

Limited early value communication to improve performance of transactional memory

Using many-core hardware to correlate radio astronomy signals

A comprehensive power-performance model for NoCs with multi-flit channel buffers

TransMetric: architecture independent workload characterization for transactional memory benchmarks

Computer generation of fast fourier transforms for the cell broadband engine

Less reused filter: improving l2 cache performance via filtering less reused lines

Dynamic topology aware load balancing algorithms for molecular dynamics applications

Refereeing conflicts in hardware transactional memory

Synchronization optimizations for efficient execution on multi-cores

Towards 100 gbit/s ethernet: multicore-based parallel communication protocol design

Performance modeling and automatic ghost zone optimization for iterative stencil loops on GPUs

Understanding the interconnection network of SpiNNaker

MPI-aware compiler optimizations for improving communication-computation overlap

P-Code: a new RAID-6 code with optimal properties

A translation system for enabling data mining applications on GPUs

A parallel levenberg-marquardt algorithm

Rate-based QoS techniques for cache/memory in CMP platforms

Cancellation of loads that return zero using zero-value caches

DBDB: optimizing DMATransfer for the cell be architecture

Divide-and-conquer: a bubble replacement for low level caches

Chunking parallel loops in the presence of synchronization

Virtualization polling engine (VPE): using dedicated CPU cores to accelerate I/O virtualization

Evaluating high performance communication: a power perspective

R-ADMAD: high reliability provision for large-scale de-duplication archival storage systems

Auto-vectorization through code generation for stream processing applications

Subdomain communication to increase scalability in large-scale scientific applications

Access map pattern matching for data cache prefetch

Prediction-based power estimation and scheduling for CMPs

Design of a novel SIMD architecture by fusing operations and registers

Thrifty interconnection network for HPC systems

Performance modeling for DFT algorithms in FFTW

PARSEC: hardware profiling of emerging workloads for CMP design

Approximate kernel matrix computation on GPUs forlarge scale learning applications

Dynamic task set partitioning based on balancing memory requirements to reduce power consumption

High-performance CUDA kernel execution on FPGAs

Load balancing using work-stealing for pipeline parallelism in emerging applications

Prefetch optimizations on large-scale applications via parameter value prediction

Designing multi-socket systems using silicon photonics

An infrastructure for scalable and portable parallel programs for computational chemistry

Chunking parallel loops in the presence of synchronization

Content Provider	ACM Digital Library
Author	Nandivada, V. Krishna Zhao, Jisheng M. Sarkar, Vivek N. Shirako, Jun
Abstract	Modern languages for shared-memory parallelism are moving from a bulk-synchronous Single Program Multiple Data (SPMD) execution model to lightweight Task Parallel execution models for improved productivity. This shift is intended to encourage programmers to express the ideal parallelism in an application at a fine granularity that is natural for the underlying domain, while delegating to the compiler and runtime system the job of extracting coarser-grained useful parallelism for a given target system. A simple and important example of this separation of concerns between ideal and useful parallelism can be found in chunking of parallel loops, where the programmer expresses ideal parallelism by declaring all iterations of a loop to be parallel and the implementation exploits useful parallelism by executing iterations of the loop in sequential chunks. Though chunking of parallel loops has been used as a standard transformation for several years, it poses some interesting challenges when the parallel loop may directly or indirectly (via procedure calls) perform synchronization operations such as barrier, signal or wait statements. In such cases, a straightforward transformation that attempts to execute a chunk of loops in sequence in a single thread may violate the semantics of the original parallel program. In this paper, we address the problem of chunking parallel loops that may contain synchronization operations. We present a transformation framework that uses a combination of transformations from past work (e.g., loop strip-mining, interchange, distribution, unswitching) to obtain an equivalent set of parallel loops that chunk together statements from multiple iterations while preserving the semantics of the original parallel program. These transformations result in reduced synchronization and scheduling overheads, thereby improving performance and scalability. Our experimental results for 11 benchmark programs on an UltraSPARC II multicore processor showed a geometric mean speedup of 0.52x for the unchunked case and 9.59x for automatic chunking using the techniques described in this paper. This wide gap underscores the importance of using these techniques in future compiler and runtime systems for programming models with lightweight parallelism.
Starting Page	181
Ending Page	192
Page Count	12
File Format	PDF
ISBN	9781605584980
DOI	10.1145/1542275.1542304
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-06-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Exceptions Loop chunking Phasers
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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