NDLI: A Transformation Framework for Optimizing Task-Parallel Programs

Content Provider	ACM Digital Library
Author	Shirako, Jun Nandivada, V. Krishna Zhao, Jisheng Sarkar, Vivek
Copyright Year	2013
Abstract	Task parallelism has increasingly become a trend with programming models such as OpenMP 3.0, Cilk, Java Concurrency, X10, Chapel and Habanero-Java (HJ) to address the requirements of multicore programmers. While task parallelism increases productivity by allowing the programmer to express multiple levels of parallelism, it can also lead to performance degradation due to increased overheads. In this article, we introduce a transformation framework for optimizing task-parallel programs with a focus on task creation and task termination operations. These operations can appear explicitly in constructs such as async, finish in X10 and HJ, task, taskwait in OpenMP 3.0, and spawn, sync in Cilk, or implicitly in composite code statements such as foreach and ateach loops in X10, forall and foreach loops in HJ, and parallel loop in OpenMP. Our framework includes a definition of data dependence in task-parallel programs, a happens-before analysis algorithm, and a range of program transformations for optimizing task parallelism. Broadly, our transformations cover three different but interrelated optimizations: (1) $\textit{finish-elimination},$ (2) $\textit{forall-coarsening},$ and (3) $\textit{loop-chunking}.$ Finish-elimination removes redundant task termination operations, forall-coarsening replaces expensive task creation and termination operations with more efficient synchronization operations, and loop-chunking extracts useful parallelism from ideal parallelism. All three optimizations are specified in an iterative transformation framework that applies a sequence of relevant transformations until a fixed point is reached. Further, we discuss the impact of exception semantics on the specified transformations, and extend them to handle task-parallel programs with precise exception semantics. Experimental results were obtained for a collection of task-parallel benchmarks on three multicore platforms: a dual-socket 128-thread (16-core) Niagara T2 system, a quad-socket 16-core Intel Xeon SMP, and a quad-socket 32-core Power7 SMP. We have observed that the proposed optimizations interact with each other in a synergistic way, and result in an overall geometric average performance improvement between 6.28× and 10.30×, measured across all three platforms for the benchmarks studied.
Starting Page	1
Ending Page	48
Page Count	48
File Format	PDF
ISSN	01640925
e-ISSN	15584593
DOI	10.1145/2450136.2450138
Volume Number	35
Issue Number	1
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	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

Optimizing parallel programs with explicit synchronization

Contech: Efficiently Generating Dynamic Task Graphs for Arbitrary Parallel Programs

Compiling task and data parallel programs for iWarp

An unfold/fold transformation framework for definite logic programs

Optimizing SQL queries for parallel execution

A distributed parallel programming framework

Estimating and optimizing performance for parallel programs

Using hammock graphs to structure programs

A cost-driven compilation framework for speculative parallelization of sequential programs

A Transformation Framework for Optimizing Task-Parallel Programs

Similar Documents

Optimizing parallel programs with explicit synchronization

Contech: Efficiently Generating Dynamic Task Graphs for Arbitrary Parallel Programs

Compiling task and data parallel programs for iWarp

An unfold/fold transformation framework for definite logic programs

Optimizing SQL queries for parallel execution

A distributed parallel programming framework

Estimating and optimizing performance for parallel programs

Using hammock graphs to structure programs

A cost-driven compilation framework for speculative parallelization of sequential programs

A Transformation Framework for Optimizing Task-Parallel Programs