Automatic nonblocking communication for partitioned global address space programs

ABSTRACT

Overlapping communication with computation is an important optimization on current cluster architectures; its importance is likely to increase as the doubling of processing power far outpaces any improvements in communication latency. PGAS languages offer unique opportunities for communication overlap, because their one-sided communication model enables low overhead data transfer. Recent results have shown the value of hiding latency by manually applying language-level nonblocking data transfer routines, but this process can be both tedious and error-prone. In this paper, we present a runtime framework that automatically schedules the data transfers to achieve overlap. The optimization framework is entirely transparent to the user, and aggressively reorders and aggregates both remote puts and gets. We preserve correctness via runtime conflict checks and temporary buffers, using several techniques to lower the overhead. Experimental results on application benchmarks suggest that our framework can be very effective at hiding communication latency on clusters, improving performance over the blocking code by an average of 16% for some of the NAS Parallel Benchmarks, 48% for GUPS, and over 25% for a multi-block fluid dynamics solver. While the system is not yet as effective as aggressive manual optimization, it increases programmers' productivity by freeing them from the details of communication management.

REFERENCES

• 1: D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Browning, R. L. Carter, D. Dagum, R. A. Fatoohi, P. O. Frederickson, T. A. Lasinski, R. S. Schreiber, H. D. Simon, V. Venkatakrishnan, and S. K. Weeratunga. The NAS Parallel Benchmarks. The International Journal of Supercomputer Applications, 5(3):63--73, Fall 1991.
• 2: Christian Bell , Dan Bonachea , Yannick Cote , Jason Duell , Paul Hargrove , Parry Husbands , Costin Iancu , Michael Welcome , Katherine Yelick, An Evaluation of Current High-Performance Networks, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.28.1, April 22-26, 2003
• 3: C. Bell, D. Bonachea, R. Nishtala, and K. Yelick. Optimizing Bandwidth Limited Problems Using One-sided Communication and Overlap. In 20th International Parallel and Distributed Processing Symposium (IPDPS), 2006.
• 4: K. Berlin, J. Huan, M. Jacob, et al. Evaluating the Impact of Programming Language Features on the Performance of Parallel Applications on Cluster Architectures. In 16th International Workshop on Languages and Compilers for Parallel Processing (LCPC), October 2003.
• 5: Dan Bonachea, GASNet Specification, v1.1, University of California at Berkeley, Berkeley, CA, 2002
• 6: D. Bonachea. Proposal for Extending the UPC Memory Copy Library Functions and Supporting Extensions to GASNet. Technical Report LBNL-56495, Lawrence Berkeley National Lab, October 2004.
• 7: John B. Carter , John K. Bennett , Willy Zwaenepoel, Implementation and performance of Munin, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.152-164, October 13-16, 1991, Pacific Grove, California, United States
• 8: Soumen Chakrabarti , Manish Gupta , Jong-Deok Choi, Global communication analysis and optimization, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.68-78, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 9: CHARM++ project web page. Available at http://charm.cs.uiuc.edu.
• 10: Parry Husbands , Costin Iancu , Katherine Yelick, A performance analysis of the Berkeley UPC compiler, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782825]
• 11: Wei-Yu Chen , Costin Iancu , Katherine Yelick, Communication Optimizations for Fine-Grained UPC Applications, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.267-278, September 17-21, 2005 [doi>10.1109/PACT.2005.13]
• 12: Sung-Eun Choi , Lawrence Snyder, Quantifying the Effects of Communication Optimizations, Proceedings of the international Conference on Parallel Processing, p.218-222, August 11-15, 1997
• 13: Yuri Dotsenko , Cristian Coarfa , John Mellor-Crummey, A Multi-Platform Co-Array Fortran Compiler, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.29-40, September 29-October 03, 2004 [doi>10.1109/PACT.2004.3]
• 14: Cristian Coarfa , Yuri Dotsenko , John Mellor-Crummey , François Cantonnet , Tarek El-Ghazawi , Ashrujit Mohanti , Yiyi Yao , Daniel Chavarría-Miranda, An evaluation of global address space languages: co-array fortran and unified parallel C, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065950]
• 15: Compaq UPC version 2.0 for Tru64 UNIX. http://h30097.www3.hp.com/upc/.
• 16: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 17: K. Datta, D. Bonachea, and K. Yelick. Titanium Performance and Potential: an NPB Experimental Study. In 18th International Workshop on Languages and Compilers for Parallel Processing (LCPC), 2005.
• 18: Tarek El-Ghazawi , Francois Cantonnet, UPC performance and potential: a NPB experimental study, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-26, November 16, 2002, Baltimore, Maryland
• 19: A. Faraj and X. Yuan. Communication characteristics in the NAS parallel benchmarks. In 14th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2002), November 2002.
• 20: Manish Gupta , Edith Schonberg , Harini Srinivasan, A Unified Framework for Optimizing Communication in Data-Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.7, p.689-704, July 1996 [doi>10.1109/71.508249]
• 21: Costin Iancu , Parry Husbands , Paul Hargrove, HUNTing the Overlap, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.279-290, September 17-21, 2005 [doi>10.1109/PACT.2005.25]
• 22: L. Iftode and J. P. Singh. Shared Virtual Memory: Progress and Challenges. Proc. of the IEEE, Special Issue on Distributed Shared Memory, 87(3):498--507, 1999.
• 23: Jacob Sorensen and Scott Baden. A Data Driven Model for Tolerating Communication Delays. In Proceedings of the 12th SIAM Conference on Parallel Processing for Scientific Computing, 2006.
• 24: Amir Kamil , Jimmy Su , Katherine Yelick, Making Sequential Consistency Practical in Titanium, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.15, November 12-18, 2005 [doi>10.1109/SC.2005.43]
• 25: Mahmut Kandemir , Alok Choudhary , Prithviraj Banerjee , J. Ramanujam , Nagaraj Shenoy, Minimizing Data and Synchronization Costs in One-Way Communication, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1232-1251, December 2000 [doi>10.1109/71.895791]
• 26: Pete Keleher , Alan L. Cox , Sandhya Dwarkadas , Willy Zwaenepoel, TreadMarks: distributed shared memory on standard workstations and operating systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.10-10, January 17-21, 1994, San Francisco, California
• 27: Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.74-88, March 1992 [doi>10.1145/130616.130623]
• 28: R. Numrich and J. Reid. Co-Array Fortran for Parallel Programming. Technical Report RAL-TR-1998-060, Rutherford Appleton Laboratory, 1998.
• 29: Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002 [doi>10.1145/509705.509708]
• 30: POSIX standard. http://www.opengroup.org/onlinepubs/009695399/.
• 31: J. Savant and S. Seidel. MuPC: A Run Time System for Unified Parallel C. Technical Report CS-TR-02-03, Department of Computer Science, Michigan Techincal University, September 2002.
• 32: Daniel J. Scales , Kourosh Gharachorloo , Chandramohan A. Thekkath, Shasta: a low overhead, software-only approach for supporting fine-grain shared memory, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.174-185, October 01-04, 1996, Cambridge, Massachusetts, United States
• 33: J. Su and K. Yelick. Array Prefetching for Irregular Array Accesses in Titanium. In Sixth Annual Workshop on Java for Parallel and Distributed Computing, 2004.
• 34: UPC language specifications, v1.2. Technical Report LBNL-59208, Berkeley National Lab, 2005.
• 35: K. Yelick, L. Semenzato, G. Pike, C. Miyamoto, B. Liblit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, P. Colella, and A. Aiken. Titanium: A high-performance Java dialect. Concurrency: Practice and Experience, 10:825--836, 1998.
• 36: Zhang Zhang , Steven Seidel, Benchmark Measurements of Current UPC Platforms, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 15, p.276.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.123]
• 37: Yingchun Zhu , Laurie J. Hendren, Communication optimizations for parallel C programs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.199-211, June 17-19, 1998, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Design, Experimentation, Performance

Keywords:
PGAS, UPC, nonblocking