X10: an object-oriented approach to non-uniform cluster computing

ABSTRACT

It is now well established that the device scaling predicted by Moore's Law is no longer a viable option for increasing the clock frequency of future uniprocessor systems at the rate that had been sustained during the last two decades. As a result, future systems are rapidly moving from uniprocessor to multiprocessor configurations, so as to use parallelism instead of frequency scaling as the foundation for increased compute capacity. The dominant emerging multiprocessor structure for the future is a Non-Uniform Cluster Computing (NUCC) system with nodes that are built out of multi-core SMP chips with non-uniform memory hierarchies, and interconnected in horizontally scalable cluster configurations such as blade servers. Unlike previous generations of hardware evolution, this shift will have a major impact on existing software. Current OO language facilities for concurrent and distributed programming are inadequate for addressing the needs of NUCC systems because they do not support the notions of non-uniform data access within a node, or of tight coupling of distributed nodes.We have designed a modern object-oriented programming language, X10, for high performance, high productivity programming of NUCC systems. A member of the partitioned global address space family of languages, X10 highlights the explicit reification of locality in the form of places}; lightweight activities embodied in async, future, foreach, and ateach constructs; a construct for termination detection (finish); the use of lock-free synchronization (atomic blocks); and the manipulation of cluster-wide global data structures. We present an overview of the X10 programming model and language, experience with our reference implementation, and results from some initial productivity comparisons between the X10 and Java™ languages.

REFERENCES

• 1: Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and friends, Computer, v.19 n.8, p.26-34, Aug. 1986 [doi>10.1109/MC.1986.1663305]
• 2: Eric Allan, David Chase, Victor Luchangco, Jan-Willem Maessen, Sukyoung Ryu, Guy L. Steele Jr., and Sam Tobin-Hochstadt. The Fortress language specification version 0.618. Technical report, Sun Microsystems, April 2005.
• 3: Yariv Aridor , Michael Factor , Avi Teperman, cJVM: A Single System Image of a JVM on a Cluster, Proceedings of the 1999 International Conference on Parallel Processing, p.4, September 21-24, 1999
• 4: Henri E. Bal , M. Frans Kaashoek, Object distribution in Orca using Compile-Time and Run-Time techniques, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.162-177, September 26-October 01, 1993, Washington, D.C., United States
• 5: Ray Barriuso and Allan Knies. SHMEM user's guide. Technical report, Cray Inc. Research, May 1994.
• 6: J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
• 7: Hans-J. Boehm, Threads cannot be implemented as a library, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 8: Luca Cardelli, A language with distributed scope, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.286-297, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199516]
• 9: Calin Cascaval , Evelyn Duesterwald , Peter F. Sweeney , Robert W. Wisniewski, Multiple Page Size Modeling and Optimization, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques (PACT'05), p.339-349, September 17-21, 2005 [doi>10.1109/PACT.2005.32]
• 10: IBM International Technical Support Organization Poughkeepsie Center. Overview of lapi. Technical report sg24-2080-00, chapter 10, IBM, December 1997. www.redbooks.ibm.com/redbooks/pdfs/sg242080.pdf.
• 11: Bradford L. Chamberlain, Sung-Eun Choi, Steven J. Deitz, and Lawrence Snyder. The high-level parallel language ZPL improves productivity and performance. In Proceedings of the IEEE International Workshop on Productivity and Performance in High-End Computing, 2004.
• 12: Elaine Cheong , Judy Liebman , Jie Liu , Feng Zhao, TinyGALS: a programming model for event-driven embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952668]
• 13: Brian Chin , Shane Markstrum , Todd Millstein, Semantic type qualifiers, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 14: CILK-5.3 reference manual. Technical report, Supercomputing Technologies Group, June 2000.
• 15: F. Darema, D.A. George, V.A. Norton, and G.F. Pfister. A Single-Program-Multiple-Data Computational model for EPEX/FORTRAN. Parallel Computing, 7(1):11--24, 1988.
• 16: Kemal Ebcioc glu, Vijay Saraswat, and Vivek Sarkar. X10: Programming for hierarchical parallelism and nonuniform data access (extended abstract). In Language Runtimes '04 Workshop: Impact of Next Generation Processor Architectures On Virtual Machines (colocated with OOPSLA 2004), October 2004. www.aurorasoft.net/workshops/lar04/lar04home.htm.
• 17: Kemal Ebcioc glu, Vijay Saraswat, and Vivek Sarkar. X10: an experimental language for high productivity programming of scalable systems (extended abstract). In Workshop on Productivity and Performance in High-End Computing (P-PHEC), February 2005.
• 18: ECMA. Standard ecma-334: C} language specification. http://www.ecma-international.org/publications/files/ecma-st/Ecma-334.pdf, December 2002.
• 19: Tarek El-Ghazawi, William W. Carlson, and Jesse M. Draper. UPC Language Specification v1.1.1, October 2003.
• 20: High Performance Fortran Forum. High performance fortran language specification version 2.0. Technical report, Rice University Houston, TX, October 1996.
• 21: Ian Foster , Carl Kesselman, The Globus toolkit, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 22: Basilio B. Fraguela , Jia Guo , Ganesh Bikshandi , María J. Garzarán , Gheorghe Almási , José Moreira , David Padua, The Hierarchically Tiled Arrays programming approach, Proceedings of the 7th workshop on Workshop on languages, compilers, and run-time support for scalable systems, p.1-12, October 22-23, 2004, Houston, Texas [doi>10.1145/1066650.1066657]
• 23: Al Geist , Adam Beguelin , Jack Dongarra , Weicheng Jiang , Robert Manchek , Vaidy Sunderam, PVM: Parallel virtual machine: a users' guide and tutorial for networked parallel computing, MIT Press, Cambridge, MA, 1995
• 24: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 25: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 26: Per Brinch Hansen, Structured multiprogramming, Communications of the ACM, v.15 n.7, p.574-578, July 1972 [doi>10.1145/361454.361473]
• 27: Tim Harris , Keir Fraser, Language support for lightweight transactions, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 28: Matthias Hauswirth , Peter F. Sweeney , Amer Diwan , Michael Hind, Vertical profiling: understanding the behavior of object-priented applications, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 29: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 30: 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
• 31: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 32: HPC challenge benchmark. http://icl.cs.utk.edu/hpcc/.
• 33: HPL Workshop on High Productivity Programming Models and Languages, May 2004. http://hplws.jpl.nasa.gov/.
• 34: Cray Inc. The Chapel language specification version 0.4. Technical report, Cray Inc., February 2005.
• 35: The Java Grande Forum benchmark suite. http://www.epcc.ed.ac.uk/javagrande/javag.html.
• 36: The Java RMI Specification. http://java.sun.com/products/jdk/rmi/.
• 37: 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]
• 38: L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, 28(9), 1979.
• 39: Doug Lea , Douglas Lea, Concurrent Programming in Java. Second Edition: Design Principles and Patterns, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 40: Doug Lea. The Concurreny Utilities, 2001. JSR 166, http://www.jcp.org/en/jsr/detail?id=166.
• 41: Maged M. Michael , Michael L. Scott, Simple, fast, and practical non-blocking and blocking concurrent queue algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.267-275, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248106]
• 42: José E. Moreira , Samuel P. Midkiff , Manish Gupta, A comparison of three approaches to language, compiler, and library support for multidimensional arrays in Java, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.116-125, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376831]
• 43: J. E. Moreira , S. P. Midkiff , M. Gupta , P. V. Artigas , M. Snir , R. D. Lawrence, Java programming for high-performance numerical computing, IBM Systems Journal, v.39 n.1, p.21-56, January 2000
• 44: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]
• 45: Nathaniel Nystrom, Michael R. Clarkson, and Andrew C. Myers. Polyglot: An extensible compiler framework for Java. In Proceedings of the Conference on Compiler Construction (CC'03), pages 1380--152, April 2003.
• 46: OpenMP specifications. http://www.openmp.org/specs.
• 47: Vijay Saraswat and Radha Jagadeesan. Concurrent clustered programming. In Proceedings of the International Conference on Concurrency Theory (CONCUR'05), August 2005.
• 48: Vijay Saraswat, Radha Jagadeesan, Armando Solar-Iezama, and Christoph von Praun. Determinate imperative programming: A clocked interpretetation of imperative syntax. Submitted for publication, available at http://www.saraswat.org/cf.html, September 2005.
• 49: V. Sarkar and G. R. Gao. Analyzable atomic sections: Integrating fine-grained synchronization and weak consistency models for scalable parallelism. Technical report, CAPSL Technical Memo 52, February 2004.
• 50: Vivek Sarkar, Clay Williams, and Kemal Ebcioc glu. Application development productivity challenges for high-end computing. In Workshop on Productivity and Performance in High-End Computing (P-PHEC), February 2004. http://www.research.ibm.com/arl/pphec/pphec2004-proceedings.pdf.
• 51: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1999
• 52: L. A. Smith , J. M. Bull , J. Obdrzálek, A parallel java grande benchmark suite, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.8-8, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582042]
• 53: L. A. Smith , J. M. Bull , J. Obdrzálek, A parallel java grande benchmark suite, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.8-8, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582042]
• 54: Standard Performance Evaluation Corporation (SPEC). SPECjbb2000 (java business benchmark). http://www.spec.org/jbb2000.
• 55: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 56: Robert W. Wisniewski, Peter F. Sweeney, Kartik Sudeep, Matthias Hauswirth, Evelyn Duesterwald, Calin Cascaval, and Reza Azimi. Performance and Environment Monitoring for Whole-System Characterization and Optimization. In Conference on Power/Performance interaction with Architecture,Circuits, and Compilers, 2004.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages; Object-oriented languages
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Keywords:
Java, X10, atomic blocks, clocks, data distribution, multithreading, non-uniform cluster computing (NUCC), partitioned global address space (PGAS), places, productivity, scalability