Programming with relaxed synchronization
Authors:
Open Access
- 21 October 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 41-50
Abstract
Synchronization overhead is a major bottleneck in scaling parallel applications to a large number of cores. This continues to be true in spite of various synchronization-reduction techniques that have been proposed. Previously studied synchronization-reduction techniques tacitly assume that all synchronizations specified in a source program are essential to guarantee quality of the results produced by the program. Recently there have been proposals to relax the synchronizations in a parallel program and compute approximate results. A fundamental challenge in using relaxed synchronization is guaranteeing that the relaxed program always produces results with a specified quality. We propose a methodology that addresses this challenge in programming with relaxed synchronization. Using our methodology programmers can systematically relax synchronization while always producing results that are of same quality as the original (un-relaxed) program. We demonstrate significant speedups using our methodology on a variety of benchmarks (e.g., up to 15x on KMeans benchmark, and up to 3x on a already highly tuned kernel from Graph500 benchmark).Keywords
This publication has 14 references indexed in Scilit:
- Patterns and statistical analysis for understanding reduced resource computing2010
- Green2010
- MineBench: A Benchmark Suite for Data Mining Workloads2006
- Iterative Compilation2002
- Transactional memory1993
- Performance issues in non-blocking synchronization on shared-memory multiprocessors1992
- Array privatization for parallel execution of loops1992
- A framework for determining useful parallelism1988
- Asynchronous Iterative Methods for MultiprocessorsJournal of the ACM, 1978
- Concurrent reading and writingCommunications of the ACM, 1977