NDLI: Enabling speculative parallelization via merge semantics in stms.

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

Enabling speculative parallelization via merge semantics in stms.

Content Provider	CiteSeerX
Author	Ravichandran, Kaushik Pande, Santosh
Abstract	STM (Software Transactional Memory) systems can be used to speculatively parallelize irregular applications such as those based on graphs and trees. While the transactional paradigm is suitable for such speculative parallelization, STMs do not deal with the semantics of speculation. In this paper we introduce merge semantics for speculations. STMs optimistically execute code and monitor the execution for memory access conflicts. On detecting a conflict between a pair of transactions the STM performs a rollback on one of them, discarding all the work that has been done until that point. This wastage leads to performance and scalability issues when there are many transactional conflicts. The key insight of this paper is that it is sometimes possible to salvage partially completed work and merge it with the other transaction. In this paper we motivate the need for the merge construct and develop the ideas behind it. We propose a simple API which can be used to define the merge operation. We discuss applications which would benefit from this construct. We implement the supporting framework and demonstrate its benefits on a Connected Components benchmark and a Minimum Spanning Tree benchmark. We report performance improvements of more than 75 % when compared to a traditional STM parallelization of the Minimum Spanning Tree benchmark. Our framework also demonstrates excellent scalability when there are a large number of conflicts, a scenario where traditional STM systems do not scale well. 1.
File Format	PDF
Access Restriction	Open
Subject Keyword	Speculative Parallelization Merge Semantics Minimum Spanning Tree Benchmark Merge Operation Excellent Scalability Supporting Framework Simple Api Software Transactional Memory Scalability Issue Irregular Application Merge Construct Many Transactional Conflict Memory Access Conflict Large Number Traditional Stm Parallelization Performance Improvement Key Insight Transactional Paradigm Connected Component Benchmark Traditional Stm System
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