Evaluating support for global address space languages on the Cray X1

ABSTRACT

The Cray X1 was recently introduced as the first in a new line of parallel systems to combine high-bandwidth vector processing with an MPP system architecture. Alongside capabilities such as automatic fine-grained data parallelism through the use of vector instructions, the X1 offers hardware support for a transparent global-address space (GAS), which makes it an interesting target for GAS languages. In this paper, we describe our experience with developing a portable, open-source and high performance compiler for Unified Parallel C (UPC), a SPMD global-address space language extension of ISO C. As part of our implementation effort, we evaluate the X1's hardware support for GAS languages and provide empirical performance characterizations in the context of leveraging features such as vectorization and global pointers for the Berkeley UPC compiler. We discuss several difficulties encountered in the Cray C compiler which are likely to present challenges for many users, especially implementors of libraries and source-to-source translators. Finally, we analyze the performance of our compiler on some benchmark programs and show that, while there are some limitations of the current compilation approach, the Berkeley UPC compiler uses the X1 network more effectively than MPI or SHMEM, and generates serial code whose vectorizability is comparable to the original C code.

REFERENCES

• 1: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model for parallel computation, Journal of Parallel and Distributed Computing, v.44 n.1, p.71-79, July 10, 1997 [doi>10.1006/jpdc.1997.1346 ]
• 2: The Berkeley UPC Compiler, 2002. http://upc.lbl.gov.
• 3: 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.
• 4: Dan Bonachea, GASNet Specification, v1.1, University of California at Berkeley, Berkeley, CA, 2002
• 5: Programming Languages -- C, 1999. The ISO C Standard, ISO/IEC 9899:1999.
• 6: 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
• 7: 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]
• 8: C. Coarfa, Y. Dotsenko, J. Eckhardt, and J. Mellor-Crummey. Co-array Fortran performance and potential: An NPB experimental study. In 16th International Workshop on Languages and Compilers for Parallel Processing (LCPC), October 2003.
• 9: Cray C/C++ reference manual. http://www.cray.com/craydoc/manuals/004-2179-003/html-004-2179-003/.
• 10: Cray X1 system overview. http://www.cray.com/craydoc/20/manuals/S-2346-23/html-S-2346-23/S-2346-23-toc.html.
• 11: 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]
• 12: T. H. Dunigan, Jr. , M. R. Fahey , J. B. White III , P. H. Worley, Early Evaluation of the Cray X1, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.18, November 15-21, 2003
• 13: Earth Simulator. http://www.es.jamstec.go.jp/.
• 14: 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
• 15: T. El-Ghazawi, W. Carlson, and J. Draper. UPC specification, 2003. http://upc.gwu.edu/documentation.html.
• 16: Paul N. Hilfinger , Dan Bonachea , David Gay , Susan Graham , Ben Liblit , Geoff Pike , Katherine Yelick, Titanium Language Reference Manual, University of California at Berkeley, Berkeley, CA, 2001
• 17: Arvind Krishnamurthy , Katherine Yelick, Analyses and optimizations for shared address space programs, Journal of Parallel and Distributed Computing, v.38 n.2, p.130-144, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0136 ]
• 18: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 19: Managing Concurrent Access for Shared Memory Active Messages, Proceedings of the 12th. International Parallel Processing Symposium on International Parallel Processing Symposium, p.272, March 30-April 03, 1998
• 20: F. McMahon. The Livermore Fortran Kernels: A computer test of the numerical performance range. Technical report, Lawrence Livermore National Laboratory, December 1986.
• 21: The Message Passing Interface (MPI) standard. http://www.mpi-forum.org/.
• 22: R. Numwich and J. Reid. Co-Array Fortran for parallel programming. Technical Report RAL-TR-1998-060, Rutherford Appleton Lab, 1998.
• 23: Leonid Oliker , Andrew Canning , Jonathan Carter , John Shalf , David Skinner , Ethier Ethier , Rupak Biswas , Jahed Djomehri , Rob Van der Wijngaart, Evaluation of Cache-based Superscalar and Cacheless Vector Architectures for Scientific Computations, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.38, November 15-21, 2003
• 24: Optimizing applications on the Cray X1 system. http://www.cray.com/craydoc/20/manuals/S-2315-51/html-S-2315-51/S-2315-51-toc.html.
• 25: Steven L. Scott, Synchronization and communication in the T3E multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.26-36, October 01-04, 1996, Cambridge, Massachusetts, United States
• 26: Man page collections: Shared memory access (SHMEM). http://www.cray.com/craydoc/20/manuals/S-2383-22/S-2383-22-manual.pdf.
• 27: A. Wakatani. Effectiveness of Message Strip-Mining for Regular and Irregular Communication. In PDCS, Oct 94.
• 28: K. Yelick, D. Bonachea, and C. Wallace. A proposal for a UPC memory consistency model. Technical Report LBNL-54983, Lawrence Berkeley National Lab, May 2004.
• 29: K. Yelick et al. Titanium: a high performance java dialect. In proceedings of ACM 1998 Workshop on Java for High-Performance Network Computing, February 1998.
• 30: Yingchun Zhu , Laurie J. Hendren, Communication optimizations for parallel C programs, Journal of Parallel and Distributed Computing, v.58 n.2, p.301-332, Aug. 1999 [doi>10.1006/jpdc.1999.1554 ]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Experimentation, Languages

Keywords:
UPC, X1, global address space