Programming with relaxed synchronization

Citations Over TimeTop 10% of 2012 papers

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).

Related Papers

• → Comparison of bottleneck detection methods for AGV systems(2004)56 cited
• → Identification and characteristics analysis of bottlenecks on urban expressways based on floating car data(2018)12 cited
• → Simulation test bed for manufacturing analysis: comparison of bottleneck detection methods for AGV systems(2003)11 cited
• → Empirical Complex Pattern Formation Caused by Peculiarities of Freeway Infrastructure(2004)4 cited
• → Direction of the Bottleneck in Dependence on Inventory Levels(2016)3 cited