NDLI: Eliminating synchronization bottlenecks using adaptive replication

Content Provider	ACM Digital Library
Author	Rinard, Martin C. Diniz, Pedro C.
Copyright Year	2003
Abstract	This article presents a new technique, adaptive replication, for automatically eliminating synchronization bottlenecks in multithreaded programs that perform atomic operations on objects. Synchronization bottlenecks occur when multiple threads attempt to concurrently update the same object. It is often possible to eliminate synchronization bottlenecks by replicating objects. Each thread can then update its own local replica without synchronization and without interacting with other threads. When the computation needs to access the original object, it combines the replicas to produce the correct values in the original object. One potential problem is that eagerly replicating all objects may lead to performance degradation and excessive memory consumption.Adaptive replication eliminates unnecessary replication by dynamically detecting contention at each object to find and replicate only those objects that would otherwise cause synchronization bottlenecks. We have implemented adaptive replication in the context of a parallelizing compiler for a subset of C++. Given an unannotated sequential program written in C++, the compiler automatically extracts the concurrency, determines when it is legal to apply adaptive replication, and generates parallel code that uses adaptive replication to efficiently eliminate synchronization bottlenecks.In addition to automatic parallelization and adaptive replication, our compiler also implements a lock coarsening transformation that increases the granularity at which the computation locks objects. The advantage is a reduction in the frequency with which the computation acquires and releases locks; the potential disadvantage is the introduction of new synchronization bottlenecks caused by increases in the sizes of the critical sections. Because the adaptive replication transformation takes place at lock acquisition sites, there is a synergistic interaction between lock coarsening and adaptive replication. Lock coarsening drives down the overhead of using adaptive replication, and adaptive replication eliminates synchronization bottlenecks associated with the overaggressive use of lock coarsening.Our experimental results show that, for our set of benchmark programs, the combination of lock coarsening and adaptive replication can eliminate synchronization bottlenecks and significantly reduce the synchronization and replication overhead as compared to versions that use none or only one of the transformations.
Starting Page	316
Ending Page	359
Page Count	44
File Format	PDF
ISSN	01640925
e-ISSN	15584593
DOI	10.1145/641909.641911
Volume Number	25
Issue Number	3
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Atomic operations Commutativity analysis Parallel computing Parallelizing compilers Replication Synchronization
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

Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives

Commutativity analysis: a new analysis technique for parallelizing compilers

Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback

Eliminating Synchronization Bottlenecks in Object-Based Programs Using Adaptive Replication (1999)

Eliminating synchronization bottlenecks in object-based programs using adaptive replication

Commutativity analysis:a new analysis framework for parallelizing compilers

Eliminating synchronization bottlenecks using adaptive replication (2003).

Eliminating Synchronization Bottlenecks in Object-Based Programs Using Adaptive Replication (1999)

Eliminating Synchronization Bottlenecks in Object-Based Programs Using Adaptive Replication (1999)

Eliminating synchronization bottlenecks using adaptive replication

Similar Documents

Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives

Commutativity analysis: a new analysis technique for parallelizing compilers

Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback

Eliminating Synchronization Bottlenecks in Object-Based Programs Using Adaptive Replication (1999)

Eliminating synchronization bottlenecks in object-based programs using adaptive replication

Commutativity analysis:a new analysis framework for parallelizing compilers

Eliminating synchronization bottlenecks using adaptive replication (2003).

Eliminating Synchronization Bottlenecks in Object-Based Programs Using Adaptive Replication (1999)

Eliminating Synchronization Bottlenecks in Object-Based Programs Using Adaptive Replication (1999)

Eliminating synchronization bottlenecks using adaptive replication