1 Introduction2 Serial Extensions to Java2.1 Titanium Arrays2.2 Domain Calculus2.3 Foreach Loops3 Models of Parallelism3.1 Creating Parallelism3.2 Models of Sharing and Communication4 Parallel Extensions to Java4.1 SPMD Parallelism in Titanium4.2 Distributed Arrays4.3 The Local Keyword and Locality Qualification4.4 Non-blocking Array Copy4.5 Regions5 Other Changes to Java5.1 Immutables and Operator Overloading5.2 Cross-Language Calls5.3 Templates5.4 Other Significant Deviations from Java6 Application Experience6.1 Adaptive Mesh Refinement Framework6.2 Immersed Boundary Method6.3 Expressiveness6.4 Performance7 Compilation and Runtime Technology7.1 Source-to-source Compilation7.2 Program Analysis of Parallel Code7.3 Memory Management7.4 GASNet and One-Sided Communication8 ConclusionsParallel Languages and Compilers: Perspective from the Titanium Experience∗Katherine Yelick1,2, Paul Hilfinger1, Susan Graham1, Dan Bonachea1,Jimmy Su1, Amir Kamil1, Kaushik Datta1, Phillip Colella2, and Tong Wen2{yelick, hilfingr, graham, bonachea, jimmysu, kamil, kdatta}@cs.berkeley.edu{pcolella, twen}@lbl.govComputer Science Division, University of California at Berkeley1Lawrence Berkeley National Laboratory2June 7, 2006AbstractWe describe the rationale behind the design of key features of Titanium—an explicitly parallel dialect of JavaTMforhigh-performance scientific programming—and our experiences in building applications with the language. Specifically, weaddress Titanium’s Partitioned Global Address Space model, SPMD parallelism support, multi-dimensional arrays and array-index calculus, memory management, immutable classes (class-like types that are value types rather than reference types),operator overloading, and generic programming. We provide an overview of the Titanium compiler implementation, coveringvarious parallel analyses and optimizations, Titanium runtime technology and the GASNet network communication layer. Wesummarize results and lessons learned from implementing the NAS parallel benchmarks, elliptic and hyperbolic solvers usingAdaptive Mesh Refinement, and several applications of the Immersed Boundary method.1 IntroductionTitanium is an explicitly parallel dialect of JavaTMdesigned for high-performance scientific programming [67]. The Titaniumproject started in 1995, at a time when custom supercomputers were losing market share to PC clusters. The motivation was tocreate a language design and implementation enabling portable programming for a wide range of parallel platforms that strikesan appropriate balance between expressiveness, user-provided information about concurrency and memory locality, and compilerand runtime support for parallelism. Our goal was to design a language that could be used for high performance on some ofthe most challenging applications, such as those with adaptivity in time and space, unpredictable dependencies, and sparse,hierarchical, or pointer-based data structures.The strategy we used was to build on the experience of several global address space languages, including Split-C [20],CC++ [37], and AC [17], but to design a higher-level language offering object-orientation with strong typing and safe memorymanagement in the context of applications requiring high-performance and scalable parallelism. Although Titanium initiallyused C++ as a base language, there were several reasons why there was an early decision to design Titanium as a dialect ofJava instead. Relative to C++, Java is a semantically simpler and cleaner language, making it easier to extend. Also, Java isa type-safe language, which protects programmers from the obscure errors that can result from violations of unchecked runtimeconstraints. Type-safety enables users to write more robust programs and the compiler to perform better optimizations. Javahas also become a popular teaching language, providing a growing community of users for whom the basics of Titanium shouldbe easy to master.The standard Java language alone is insufficient for large-scale scientific programming. Its multi-dimensional array supportmakes heavy use of pointers, and is fundamentally asymmetric in its treatment of the dimensions. Its memory model is completelyflat, making no provision for distributed or otherwise hierarchical memories. Its multi-processing support does not distinguish“logical threads,” used as program-structuring devices and intended to operate sequentially, from “process-like threads,” intendedto represent opportunities for concurrency. This conflation impacts static program analysis required by some optimizations.It is possible to approach these deficiencies either through language extensions or library extensions. The former choice allowsmore concise and user-friendly syntax, and makes more information explicitly available to the compiler. The latter choice wouldperforce be more portable. However, it was clear that in either case, we would have to modify or build a compiler to get the∗This work was supported in part by the Department of Energy under DE-FC03-01ER25509, by the California State MICRO Program, by theNational Science Foundation under ACI-9619020 and EIA-9802069, by the Defense Advanced Research Projects Agency under F30602-95-C-0136, andby Sun Microsystems. Machine access was provided by NERSC/DOE, SDSC/NSF, PSC/NSF, LLNL/DOE, U.C. Berkeley, Virginia Tech, and RiceUniversity. The information presented here does not necessarily reflect the position or the policy of the Government and no official endorsement shouldbe inferred.1necessary performance, and that while the library-only approach would be portable in a purely functional sense, it would makeportability of application performance more problematic. For these reasons, we chose to introduce a new dialect. We argue thatparallel languages like Titanium provide greater expressive power than conventional approaches, enabling much more conciseand expressive code and minimizing time to solution without sacrificing parallel performance.In the remainder of the paper, we present highlights of the design of the Titanium language, our experiences using it forscientific applications, and compilation and runtime innovations that support efficient execution on sequential and parallelplatforms.2 Serial Extensions to JavaWe added several features to Java to better support scientific computation and high single-processor performance. In this sectionwe illustrate these features, drawing on examples taken from our implementations of