Modeling optimistic concurrency using quantitative dependence analysis
Authors:
Open Access
- 20 February 2008
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 185-196
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.Keywords
This publication has 20 references indexed in Scilit:
- Performance pathologies in hardware transactional memory2007
- An effective hybrid transactional memory system with strong isolation guarantees2007
- Implicit parallelism with ordered transactions2007
- McRT-STM2006
- POSH2006
- Pin2005
- Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors2005
- Language support for lightweight transactions2003
- Hardware and software support for speculative execution of sequential binaries on a chip-multiprocessor1998
- Run-time parallelization and scheduling of loopsIEEE Transactions on Computers, 1991