NDLI: The Batched DOACROSS loop parallelization algorithm

Content Provider	IEEE Xplore Digital Library
Author	Lucas, D.C.S. Araujo, G.
Copyright Year	2015
Description	Author affiliation: Inst. of Comput., Univ. of Campinas, Campinas, Brazil (Lucas, D.C.S.; Araujo, G.)
Abstract	Parallelizing loops containing loop-carried dependencies has been considered a very difficult task, mainly due to the overhead imposed by communicating dependencies between iterations. Despite the huge effort to devise effective parallelization techniques for such loops, the problem is still far from solved. For many loops, old (DOACROSS), and new (DSWP) techniques have not been able to offer a solution to this problem. This paper does a qualitative and quantitative analysis of synchronization costs of these two loop parallelization algorithms, on two modern computer architectures (ARM A9 MPCore and Intel Ivy Bridge). Our results show that at least 30% of the execution time of the programs we parallelized are spent on synchronization/data communication. We also show that, besides the problem being hard, these architectures are on opposite endpoints along the axis of commonly accepted requisites for efficient loop parallelization. As a consequence, both techniques struggle to effectively speed up several programs. Moreover, this paper presents a novel algorithm, called Batched DOACROSS (BDX), that capitalizes on the advantages of DSWP and DOACROSS, while minimizing their deficiencies. BDX does not require new hardware mechanisms (as DSWP does) and makes use of thread local buffers to reduce DOACROSS synchronization overheads.
Starting Page	476
Ending Page	483
File Size	829165
Page Count	8
File Format	PDF
ISBN	9781467378123
e-ISBN	9781467378130
DOI	10.1109/HPCSim.2015.7237079
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-07-20
Publisher Place	Netherlands
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Fine-grain Parallelism Multicore Processors Instruction sets Computer architecture Parallel processing Loop Parallelization Algorithm Synchronization
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

Scalable Graph Exploration on Multicore Processors

Characterizing Fine-Grain Parallelism on Modern Multicore Platform

Increasing Parallelism on multicore processors using Induced Parallelism

Data Access Partitioning for Fine-grain Parallelism on Multicore Architectures

Parallelism detection for multicore processors

Vlock: Lock virtualization mechanism for exploiting fine-grained parallelism in graph traversal algorithms

An Automatic Parallel-Stage Decoupled Software Pipelining Parallelization Algorithm Based on OpenMP

Toward Harnessing DOACROSS Parallelism for Multi-GPGPUs

Parallelization strategies to speed-up computations for terrain analysis on multi-core processors

The Batched DOACROSS loop parallelization algorithm

Similar Documents

Scalable Graph Exploration on Multicore Processors

Characterizing Fine-Grain Parallelism on Modern Multicore Platform

Increasing Parallelism on multicore processors using Induced Parallelism

Data Access Partitioning for Fine-grain Parallelism on Multicore Architectures

Parallelism detection for multicore processors

Vlock: Lock virtualization mechanism for exploiting fine-grained parallelism in graph traversal algorithms

An Automatic Parallel-Stage Decoupled Software Pipelining Parallelization Algorithm Based on OpenMP

Toward Harnessing DOACROSS Parallelism for Multi-GPGPUs

Parallelization strategies to speed-up computations for terrain analysis on multi-core processors

The Batched DOACROSS loop parallelization algorithm