Global Address Space Programming in TitaniumTitanium GoalsTitaniumNew Language FeaturesLecture OutlineJava: A Cleaner C++Java ObjectsJava Object ExampleImmutable Classes in TitaniumArrays, Points, DomainsArrays in JavaMultidimensional Arrays in TitaniumNaïve MatMul with Titanium ArraysUnordered iterationBetter MatMul with Titanium ArraysPoint, RectDomain, Arrays in GeneralExample: DomainExample using Domains and foreachSPMD Execution ModelSlide 20SPMD ModelSlide 22Global Address SpaceUse of Global / LocalDistributed Data StructuresConsistency ModelOther Language ExtensionsImplementationApplicationsCurrent Sequential PerformanceParallel performanceHow to use TitaniumRecommended UseCaveatsTitanium StatusTitanium 1CS267 Lecture 8Global Address Space Programming in TitaniumCS267Kathy YelickTitanium 2CS267 Lecture 8Titanium Goals•Performance–close to C/FORTRAN + MPI or better•Safety–as safe as Java, extended to parallel framework•Expressiveness–close to usability of threads–add minimal set of features•Compatibility, interoperability, etc.–no gratuitous departures from Java standardTitanium 3CS267 Lecture 8Titanium•Take the best features of threads and MPI–global address space like threads (ease programming)–SPMD parallelism like MPI (for performance)–local/global distinction, i.e., layout matters (for performance)•Based on Java, a cleaner C++–classes, memory management•Language is extensible through classes–domain-specific language extensions–current support for grid-based computations, including AMR•Optimizing compiler–communication and memory optimizations–synchronization analysis –cache and other uniprocessor optimizationsTitanium 4CS267 Lecture 8New Language Features•Scalable parallelism–SPMD model of execution with global address space•Multidimensional arrays–points and index sets as first-class values to simplify programs–iterators for performance•Checked Synchronization –single-valued variables and globally executed methods•Global Communication Library•Immutable classes–user-definable non-reference types for performance•Operator overloading–by demand from our user community•Semi-automated zone-based memory management–as safe as a garbage-collected language–better parallel performance and scalabilityTitanium 5CS267 Lecture 8Lecture Outline•Linguistic support for uniprocessor performance–Immutable classes–Multidimensional Arrays–foreach•Parallelism Support–SPMD execution–Global and local references–Communication–Barriers and single–Synchronized (not yet implemented)•Example: Sharks and Fish•Java introduction interspersed•Compiler statusTitanium 6CS267 Lecture 8Java: A Cleaner C++•Java is an object-oriented language–classes (no standalone functions) with methods–inheritance between classes; multiple interface inheritance only•Documentation on web at java.sun.com•Syntax similar to C++class Hello { public static void main (String [] argv) { System.out.println(“Hello, world!”); }}•Safe–Strongly typed: checked at compile time, no unsafe casts–Automatic memory management•Titanium is (almost) strict supersetTitanium 7CS267 Lecture 8Java Objects•Primitive scalar types: boolean, double, int, etc.–implementations will store these on the program stack–access is fast -- comparable to other languages•Objects: user-defined and from the standard library–passed by pointer value (object sharing) into functions–has level of indirection (pointer to) implicit–simple model, but inefficient for small objects2.63truer: 7.1i: 4.3Titanium 8CS267 Lecture 8Java Object Exampleclass Complex { private double real; private double imag; public Complex(double r, double i) { real = r; imag = i; } public Complex add(Complex c) { return new Complex(c.real + real, c.imag + imag); public double getReal {return real; } public double getImag {return imag;}}Complex c = new Complex(7.1, 4.3);c = c.add(c);class VisComplex extends Complex { ... }Titanium 9CS267 Lecture 8Immutable Classes in Titanium•For small objects, would sometimes prefer–to avoid level of indirection –pass by value (copying of entire object)–especially when objects are immutable -- fields are unchangable»extends the idea of primitive values (1, 4.2, etc.) to user-defined values•Titanium introduces immutable classes–all fields are final (implicitly)–cannot inherit from (extend) or be inherited by other classes–needs to have 0-argument constructor, e.g., Complex () immutable class Complex { ... } Complex c = new Complex(7.1, 4.3);Titanium 10CS267 Lecture 8Arrays, Points, Domains•Fast, expressive arrays–multidimensional–lower bound, upper bound, stride–concise indexing: A[p] instead of A(i, j, k)•Points–tuple of integers as primitive type•Domains–rectangular sets of points (bounds and stride)–arbitrary sets of points•Multidimensional iteratorsTitanium 11CS267 Lecture 8Arrays in Java•Arrays in Java are objects•Only 1D arrays are directly supported•Array bounds are checked (as in Fortran)•Multidimensional arrays as arrays-of-arrays are slowTitanium 12CS267 Lecture 8Multidimensional Arrays in Titanium•New kind of multidimensional array added–Two arrays may overlap (unlike Java arrays)–Indexed by Points (tuple of ints)–Constructed over a set of Points, called Domains–RectDomains are special case of domains–Points, Domains and RectDomains are built-in immutable classes• Support for adaptive meshes and other mesh/grid operationsRectDomain<2> d = [0:n,0:n];Point<2> p = [1, 2];double [2d] a = new double [d];a[0,0] = a[9,9];Titanium 13CS267 Lecture 8Naïve MatMul with Titanium Arrayspublic static void matMul(double [2d] a, double [2d] b, double [2d] c) { int n = c.domain().max()[1]; // assumes square for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { c[i,j] += a[i,k] * b[k,j]; } } }}Titanium 14CS267 Lecture 8Unordered iteration•As seen in matmul, we need to reorder iterations •Compilers can (in principle) do this for matrix multiply, but hard in general•Titanium adds unordered iteration on rectangular domains foreach (p within r) { … } –p is a Point new point, scoped only within the foreach body–r is a previously-declared RectDomain•Foreach simplifies bounds checking as well –note: current optimizer
View Full Document
Unlocking...