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. In this work we examine the validity of this assumption by studying the effect of systematically relaxing synchronization for a wide set of parallel programs.
We consider the class of computations for which the quality of result can be quantified, and the quality need only fall within some acceptable range. Several computations from important benchmark suites such as PARSEC, STAMP, and NU-MineBench, belong to this class. We propose a technique which relaxes the programmer-specified synchronization to reduce, and in some cases completely eliminate, the synchronization overhead. In addition, we also develop model computations that map to some of the well-known parallel applications, and analyze the effects of relaxing synchronization. Our results show that relaxing synchronization can achieve significant speedups; for example, up to 15x for the Kmeans benchmark and up to 70x for one of the model computations, with no degradation in the quality of the results. Our study also provides valuable insight into the synchronization resilience of parallel applications, thus paving the way towards the development of more effective synchronization primitives that can be exploited efficiently by compilers and parallel runtime systems.
By: Lakshminarayanan Renganarayana; Vijayalakshmi Srinivasan; Ravi Nair; Daniel Prener; Colin Blundell
Published in: RC25256 in 2011
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .