research-article

Modeling optimistic concurrency using quantitative dependence analysis

Authors:

Christoph von Praun,

Rajesh Bordawekar,

Calin CascavalAuthors Info & Claims

PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming

Pages 185 - 196

https://doi.org/10.1145/1345206.1345234

Published: 20 February 2008 Publication History

Abstract

This work presents a quantitative approach to analyze parallelization opportunities in programs with irregular memory access where potential data dependencies mask available parallelism. The model captures data and causal dependencies among critical sections as algorithmic properties and quantifies them as a density computed over the number of executed instructions. The model abstracts from runtime aspects such as scheduling, the number of threads, and concurrency control used in a particular parallelization.

We illustrate the model on several applications requiring ordered and unordered execution of critical sections. We describe a run-time tool that computes the dependence densities from a deterministic single-threaded program execution. This density metric provides insights into the potential for optimistic parallelization, opportunities for algorithmic scheduling, and performance defects due to synchronization bottlenecks.

Based on the results of our analysis, we classify applications into three categories with low, medium, and high dependence densities. Applications with low dependence density are naturally good candidates for optimistic concurrency, applications with medium density may require a scheduler that is aware of the algorithmic dependencies for optimistic concurrency to be effective, and applications with high dependence density may not be suitable for parallelization.

References

[1]

D. Bader and K. Madduri. Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors. In Proc. of HiPC 2005, pages 465--476, December 2005.

Digital Library

[2]

J. Bobba, K. E. Moore, H. Volos, L. Yen, M. D. Hill, M. M. Swift, and D. A. Wood. Performance Pathologies in Hardware Transactional Memory. In Proc. of ISCA'07, pages 81--91, 2007.

Digital Library

[3]

M. K. Chen and K. Olukotun. TEST: A Tracer for Extracting Speculative Thread. In Proc. of CGO'03, pages 301--314, 2003.

Digital Library

[4]

M. K. Chen and K. Olukotun. The Jrpm System for Dynamically Parallelizing Java Programs. In Proc. of ISCA'03, pages 434--445, 2003.

Digital Library

[5]

T. Chen, J. Lin, X. Dai, W.-C. Hsu, and P.-C. Yew. Data Dependence Proceeding for Speculative Optimizations. In Proc. of Compiler Construction'04, pages 57--72, 2004.

[6]

D. Dice and N. Shavit. Understanding Tradeoffs in Software Transactional Memory. In Proc. of CGO'07, 2007.

Digital Library

[7]

L. Hammond, M. Willey, and K. Olukotun. Data Speculation Support for a Chip Multiprocessorx. In Proc. of ASPLOS'98, 1998.

Digital Library

[8]

T. Harris and K. Fraser. Language Support for Lightweight Transactions. In Proc. of OOPSLA'03, pages 14--25, 2006.

Digital Library

[9]

T. Harris and S. Stipic. Abstract Nested Transactions. In Proc. of TRANSACT'07, 2007.

[10]

M. Herlihy and E. Koskinen. Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects. Technical Report CS07-08, Department of Computer Science, Brown University, July 2007.

[11]

M. Herlihy and J. E. B. Moss. Transactional Memory: Architecture Support for Lock-free Data Structures. In Proc. of ISCA'93, pages 289--300, 1993.

Digital Library

[12]

V. Krishnan and J. Torrellas. Hardware and Software Support for Speculative Execution of Sequential Binaries on a ChipMultiprocessor. In Proc. of ICS'98, 1998.

Digital Library

[13]

M. Kulkarni, L. P. Chew, and K. Pingali. Using Transactions in Delaunay Mesh Generation. In Workshop on Transactional Memory Workloads (WTW'06), 2006.

[14]

M. Kulkarni and K. Pingali. Scheduling Issues in Optimistic Parallelization. In Proc. of IPDPS'07, pages 1--7, 2007.

[15]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic Parallelism Requires Abstractions. In Proc. of PLDI'07, pages 211--222, 2007.

Digital Library

[16]

M. S. Lam and R. P. Wilson. Limits of control flow on parallelism. In Proc. of ISCA '92, pages 46--57, 1992.

Digital Library

[17]

W. Liu, J. Tuck, L. Ceze, W. Ahn, K. Strauss, J. Renau, and J. Torrellas. POSH: a TLS compiler that exploits program structure. In Proc. of PPoPP '06, pages 158--167, 2006.

Digital Library

[18]

C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation. In Proc. of PLDI'05, 2005.

Digital Library

[19]

P. Marcuello and A. Gonzalez. A Quantitative Assessment of TLS Techniques . In Proc. of IPDPS'00, 2000.

[20]

C. C. Minh, M. Trautmann, J. Chung, A. McDonald, N. Bronson, J. Casper, C. Kozyrakis, and K. Olukotun. An Effective Hybrid Transactional Memory System with Strong Isolation Guarantees. In Proc. of ISCA'07, pages 69--80, 2007.

Digital Library

[21]

E. J. B. Moss and T. Hosking. Nested Transactional Memory: Model and Preliminary Architecture Sketches. In In Proceedings, Workshop on Synchronization and Concurrency in Object-Oriented Languages, Oct 2005.

[22]

MySQL - The World's Most Popular Open Source Database. http://www.mysql.com.

[23]

R. Narayanan, B. Ozisikyilmaz, J. Zamberno, G. Memik, and A. Choudhary. MineBench: A Benchmark Suite for Data Mining Workloads. In Proc. of IISWC'06, pages 182--188, 2006.

[24]

N. Neelakantam, R. Rajwar, S. Srinivas, U. Srinivasan, and C. Zilles. Hardware Atomicity for Reliable Software Speculation. In Proc. of ISCA'07, pages 174--185, 2007.

Digital Library

[25]

J. Oplinger, D. Heine, and M. Lam. In Search of Speculative Thread Level Parallelism. In Proc. of PACT'99, pages 303--313, 1999.

Digital Library

[26]

B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. C. Minh, and B. Hertzberg. McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime. In Proc. of PPoPP'06, pages 187--197, March 2006.

Digital Library

[27]

J. Saltz, R. Mirchandaney, and K. Crowley. Run-Time Parallelization and Scheduling of Loops. IEEE Transacations on Computers, 40(5), 1991.

Digital Library

[28]

N. Shavit and D. Touitou. Software Transactional Memory. In Proc. of PODC'95, pages 204--213, 1995.

Digital Library

[29]

J. G. Steffan and T. C. Mowry. The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization. In Proc. of HPCA'98, 1998.

Digital Library

[30]

The UMT Benchmark Code. http://www.llnl.gov/asci/purple/benchmarks/limited/umt.

[31]

T. Vijaykumar and G. S. Sohi. Task Selection for a Multiscalar Processor. In Proc. of MICRO'98, 1998.

Digital Library

[32]

C. von Praun, L. Ceze, and C. Cascaval. Implicit Parallelism with Ordered Transactions. In Proc. of PPoPP'07, pages 79--89, 2007.

Digital Library

[33]

A. Zhai, C. B. Colohan, J. G. Steffan, and T. C. Mowry. Compiler Optimization of Memory-Resident Value Communication Between Speculative Threads. In Proc. of CGO'04, pages 39--52, 2004.

Digital Library

Cited By

Deiana ESuchy BWilkins MHomerding BMcMichen TDunajewski KDinda PHardavellas NCampanoni SDubach CBruening DHardekopf B(2023)Program State Element CharacterizationProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580011(199-211)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580011
Blom SDarabi SHuisman MSafari M(2021)Correct program parallelisationsInternational Journal on Software Tools for Technology Transfer10.1007/s10009-020-00601-zOnline publication date: 14-Feb-2021
https://doi.org/10.1007/s10009-020-00601-z
Zhu HPhanishayee APekhimenko GGavrilovska AZadok E(2020)DaydreamProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489169(337-352)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489169
Show More Cited By

Index Terms

Modeling optimistic concurrency using quantitative dependence analysis

Recommendations

Effective Transactional Memory Execution Management for Improved Concurrency

This article describes a transactional memory execution model intended to exploit maximum parallelism from sequential and multithreaded programs. A program code section is partitioned into chunks that will be mapped onto threads and executed ...
TxLinux: using and managing hardware transactional memory in an operating system
SOSP '07

TxLinux is a variant of Linux that is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first to manage HTM in the scheduler. This paper describes and measures TxLinux and discusses two ...
TxLinux: using and managing hardware transactional memory in an operating system
SOSP '07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles

TxLinux is a variant of Linux that is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first to manage HTM in the scheduler. This paper describes and measures TxLinux and discusses two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming

February 2008

308 pages

ISBN:9781595937957

DOI:10.1145/1345206

General Chair:
Siddhartha Chatterjee
IBM Research USA
,
Program Chair:
Michael L. Scott
University of Rochester USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 February 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PPoPP08

Sponsor:

PPoPP08: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 20 - 23, 2008

UT, Salt Lake City, USA

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
723
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)6

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deiana ESuchy BWilkins MHomerding BMcMichen TDunajewski KDinda PHardavellas NCampanoni SDubach CBruening DHardekopf B(2023)Program State Element CharacterizationProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580011(199-211)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580011
Blom SDarabi SHuisman MSafari M(2021)Correct program parallelisationsInternational Journal on Software Tools for Technology Transfer10.1007/s10009-020-00601-zOnline publication date: 14-Feb-2021
https://doi.org/10.1007/s10009-020-00601-z
Zhu HPhanishayee APekhimenko GGavrilovska AZadok E(2020)DaydreamProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489169(337-352)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489169
Saad MPalmieri RRavindran B(2019)LernaACM Transactions on Storage10.1145/331036815:1(1-24)Online publication date: 22-Mar-2019
https://dl.acm.org/doi/10.1145/3310368
Saad MKishi MJing SHans SPalmieri RHollingsworth JKeidar I(2019)Processing transactions in a predefined orderProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295730(120-132)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295730
Bubel RHähnle RHeydari Tabar A(2019)A Program Logic for Dependence AnalysisIntegrated Formal Methods10.1007/978-3-030-34968-4_5(83-100)Online publication date: 22-Nov-2019
https://doi.org/10.1007/978-3-030-34968-4_5
Saad MPalmieri RRavindran BBreitgand DYadgar GPorter DEyal I(2018)LernaProceedings of the 11th ACM International Systems and Storage Conference10.1145/3211890.3211897(37-48)Online publication date: 4-Jun-2018
https://dl.acm.org/doi/10.1145/3211890.3211897
Curtsinger CBerger E(2018)CozCommunications of the ACM10.1145/320591161:6(91-99)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3205911
Li YZhao YSun LShen M(2017)A hybrid sample generation approach in speculative multithreadingThe Journal of Supercomputing10.1007/s11227-017-2118-3Online publication date: 7-Aug-2017
https://doi.org/10.1007/s11227-017-2118-3
Liu HLam KLin HWang CMa J(2016)Lightweight Dependency Checking for Parallelizing Loops with Non-Deterministic Dependency on GPU2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS.2016.0119(884-893)Online publication date: Dec-2016
https://doi.org/10.1109/ICPADS.2016.0119
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents