Using early phase termination to eliminate load imbalances at barrier synchronization points

ABSTRACT

We present a new technique, early phase termination, for eliminating idle processors in parallel computations that use barrier synchronization. This technique simply terminates each parallel phaseas soon as there are too few remaining tasks to keep all of the processors busy.

Although this technique completely eliminates the idling that would other wise occur at barrier synchronization points, it may also change the computation and therefore the result that the computation produces. We address this issue by providing probabilistic distortion models that characterize how the use of early phase termination distorts the result that the computation produces. Our experimental results show that for our set of benchmark applications, 1) early phase termination can improve the performance of the parallel computation, 2) the distortion is small (or can be made to be small with the use of an appropriate compensation technique) and 3) the distortion models provide accurate and tight distortion bounds. These bounds can enable users to evaluate the effect of early phase termination and confidently accept results from parallel computations that use this technique if they find the distortion bounds to be acceptable.

Finally, we identify a general computational pattern that works well with early phase termination and explain why computations that exhibit this pattern can tolerate the early termination of parallel tasks without producing unacceptable results.

REFERENCES

• 1: C. Ananian and M. Rinard. Efficient object-based software transactions. In Proceedings of the Workshop on Synchronization and Concurrency in Object-Oriented Languages, San Diego, CA, Oct. 2005.
• 2: C. Scott Ananian , Martin Rinard, Architectural and compiler support for strongly atomic transactional memory, Massachusetts Institute of Technology, Cambridge, MA, 2007
• 3: J. Barnes and P. Hut. A hierarchical O(NlogN) force calculation algorithm. Nature, 324(4):446--449, Dec. 1986.
• 4: W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992 [doi>10.1109/71.180621 ]
• 5: R. Browning, T. Li, B. Chui, J. Ye, R. Pease, Z. Czyzewski, and D. Joy. Empirical forms for the electron/atom elastic scattering cross sections from 0.1-30keV. J. Appl. Phys., 76(4):2016--2022, Aug. 1994.
• 6: R. Browning, T. Li, B. Chui, J. Ye, R. Pease, Z. Czyzewski, and D. Joy. Low-energy electron/atom elastic scattering cross sections for 0.1-30keV. Scanning, 17(4):250--253, July/August 1995.
• 7: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 8: Rudolf Jakob Freund , Ramon C. Littell, SAS System for Regression, John Wiley & Sons, Inc., New York, NY, 2000
• 9: A. Frommer and D. Szyld. On asynchronous iterations.
• 10: J. M. Goodman, Chemical Applications of Molecular Modeling, Royal Society of Chemistry, The, 2007
• 11: Rajiv Gupta, The fuzzy barrier: a mechanism for high speed synchronization of processors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.54-63, April 03-06, 1989, Boston, Massachusetts, United States
• 12: J. Harris, S. Lazaratos, and R. Michelena. Tomographic string inversion. In Proceedings of the 60th Annual International Meeting, Society of Exploration and Geophysics, Extended Abstracts, pages 82--85, 1990.
• 13: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 14: T. Kay and J. Kajiya. Ray tracing complex scenes. Computer Graphics (Proceedings of SIGGRAPH'86), 20(4):269--78, Aug. 1986.
• 15: C. Moler. Numerical Computing with Matlab. Society for Industrial and Applied Mathematics, 2004.
• 16: J. Nieh and M. Levoy. Volume rendering on scalable shared-memory MIMD architectures. Technical Report CSL-TR-92-537, Computer Systems Laboratory, Stanford Univ., Stanford, Calif., Aug. 1992.
• 17: Martin C. Rinard, The design, implementation and evaluation of Jade: a portable, implicitly parallel programming language, Stanford University, Stanford, CA, 1994
• 18: Martin C. Rinard, Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.337-371, Nov. 1999 [doi>10.1145/329466.329486]
• 19: Martin Rinard , Cristian Cadar , Huu Hai Nguyen, Exploring the acceptability envelope, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA [doi>10.1145/1094855.1094866]
• 20: Martin Rinard, Probabilistic accuracy bounds for fault-tolerant computations that discard tasks, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183447]
• 21: Daniel J. Scales , Monica S. Lam, Transparent fault tolerance for parallel applications on networks of workstations, Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, p.27-27, January 22-26, 1996, San Diego, CA

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages, Performance, Reliability

Keywords:
barrier synchronization, early phase termination, parallel computing, probabilistic cistortion models