Titanium Performance andPotential: an NPB Experimental
StudyKaushik Datta, Dan Bonachea, andKatherine Yelick
http://titanium.cs.berkeley.edu
LCPC 2005
U.C. Berkeley
October 20, 2005
http://titanium.cs.berkeley.edu

1 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Take-Home Messages• Titanium:• allows for elegant and concise programs• gets comparable performance to Fortran+MPI on threecommon yet diverse scientific kernels (NPB)• is well-suited to real-world applications• is portable (runs everywhere)

http://titanium.cs.berkeley.edu

2 Kaushik Datta, Dan Bonachea, and Katherine Yelick

NAS Parallel Benchmarks• Conjugate Gradient (CG)• Computation: Mostly sparse matrix-vector multiply (SpMV)• Communication: Mostly vector and scalar reductions• 3D Fourier Transform (FT)• Computation: 1D FFTs (using FFTW 2.1.5)• Communication: All-to-all transpose• Multigrid (MG)• Computation: 3D stencil calculations• Communication: Ghost cell updates
http://titanium.cs.berkeley.edu

3 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Titanium Overview• Titanium is a Java dialect for parallel scientificcomputing• No JVM, no JIT, and no dynamic class loading• Titanium is extremely portable• Ti compiler is source-to-source, and first compiles to C forportability• Ti programs run everywhere- uniprocessors, sharedmemory, and distributed memory systems• All communication is one-sided for performance• GASNet communication system (not MPI)
http://titanium.cs.berkeley.edu

4 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Presented Titanium Features• Features in addition to standard Java:• Flexible and efficient multi-dimensional arrays• Built-in support for multi-dimensional domain calculus• Partitioned Global Address Space (PGAS) memory model• Locality and sharing reference qualifiers• Explicitly unordered loop iteration• User-defined immutable classes• Operator-overloading• Efficient cross-language support• Many others not covered…
http://titanium.cs.berkeley.edu

5 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Titanium Arrays• Ti Arrays are created and indexed using points:
double [3d] gridA = new double [[-1,-1,-1]:[256,256,256]];(MG)

Lower Bound

Upper Bound• gridA has a rectangular index set (RectDomain)of all points in box with corners [-1,-1,-1]
and [256,256,256]• Points and RectDomains are first-class types• The power of Titanium arrays lies in:• Generality: indices can start at any point• Views: one array can be a subarray of another
http://titanium.cs.berkeley.edu

6 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Foreach Loops• Foreach loops allow for unordered iterations through a
RectDomain:
public void square(double [3d] gridA, double [3d] gridB) {foreach (p in gridA.domain()) {gridB[p] = gridA[p] * gridA[p];}}• These loops:• allow the compiler to reorder execution to maximize performance• require only one loop even for multidimensional arrays• avoid off-by-one errors common in for loops

http://titanium.cs.berkeley.edu

7 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Point Operations•

Titanium allows for arithmetic operations on Points:
final Point<2> NORTH = [0,1], SOUTH = [0,-1],
EAST = [1,0], WEST = [-1,0];
foreach (p in gridA.domain()) {gridB[p] = S0 * gridA[p] +S1 * ( gridA[p + NORTH] + gridA[p + SOUTH] +gridA[p + EAST] + gridA[p + WEST] );}•This makes the MG stencil code more readable and concise
p+NORTHp+WEST

pp+EAST

p+SOUTHhttp://titanium.cs.berkeley.edu

8 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Titanium Parallelism Model• Ti uses an SPMD model of parallelism• Number of threads is fixed at program startup• Barriers, broadcast, reductions, etc. are supported• Programmability using a Partitioned GlobalAddress Space (i.e., direct reads and writes)• Programs are portable across shared/distributed memory• Compiler/runtime generates communication as needed• User controls data layout locality; key to performance

http://titanium.cs.berkeley.edu

9 Kaushik Datta, Dan Bonachea, and Katherine Yelick

PGAS Memory Model• Global address space is logically partitioned

Global address space•• Independent of underlying hardware (shared/distributed)• Data structures can be spread over partitions of shared space
References (pointers) are either local or global (meaning possiblyremote)
t0

t1

x: 1
y: 2

x: 5
y: 6

l:

l:

l:

g:

g:g:

http://titanium.cs.berkeley.edu

tnx: 7
y: 8

Object heaps
are default shared
Program stacks
are private

10 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Distributed Arrays• Titanium allows construction of distributed arrays in theshared Global Address Space:double [3d] mySlab = new double [startCell:endCell];// “slabs” array is pointer-based directory over all procs
double [1d] single [3d] slabs = new double [0:Ti.numProcs()-1]
single [3d];slabs.exchange(mySlab);

(FT)
slabs

t0local
mySlabhttp://titanium.cs.berkeley.edu

slabs

t1

local
mySlab

slabs

t2

local
mySlab11 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Domain Calculus and Array Copy
• Full power of Titanium arrays combined with PGAS model• Titanium allows set operations on RectDomains:// update overlapping ghost cells of neighboring block
data[neighborPos].copy(myData.shrink(1));(MG)• The copy is only done on intersection of array RectDomains• Titanium also supports nonblocking array copy
non-ghost (“shrunken”)
cells

ghost cells
http://titanium.cs.berkeley.edu

intersection (copied area)
fills in neighbor’s ghost cells

mydata data[neighborPos]
12 Kaushik Datta, Dan Bonachea, and Katherine Yelick

The Local Keyword and Compiler
Optimizations• Local keyword ensures that compiler staticallyknows that data is local:
double [3d] myData = (double [3d] local) data[myBlockPos];• This allows the compiler to use more efficientnative pointers to reference the array• Avoid runtime check for local/remote• Use more compact pointer representation• Titanium optimizer can often automaticallypropagate locality info using Local QualifierInference (LQI)
http://titanium.cs.berkeley.edu

13 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Is LQI (Local Qualifier Inference) Useful?

GOOD• LQI does a solid
job ofpropagating
locality
information• Speedups:

http://titanium.cs.berkeley.edu• CG- 58%
improvement• MG- 77%
improvement

14 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Immutable Classes• For small objects, would sometimes prefer:• to avoid level of indirection and allocation overhead• to pass by value (copying of entire object)• especially when immutable (fields never modified)• Extends idea of primitives to user-defined data types• Example: Complex number classimmutable class Complex {// Complex class is now unboxed
public double real, imag;…
}(FT)

No assignment to fields
outside of constructors

http://titanium.cs.berkeley.edu

15 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Operator Overloading• For convenience, Titanium allows operator overloading• Overloading in Complex makes the FT benchmark more readable• Similar to operator overloading in C++
immutable class Complex {public double real;public double imag;
public Complex op+(Complex c) {return new Complex(c.real + real, c.imag + imag);}}Complex c1 = new Complex(7.1, 4.3);
Complex c2 = new Complex(5.4, 3.9);
Complex c3 = c1 + c2;(FT)
http://titanium.cs.berkeley.edu“+” is overloaded to add Complex objects
16 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Cross-Language Calls• Titanium supports efficient calls tokernels/libraries in other languages• no data copying required• Example: the FT benchmark calls the FFTWlibrary to perform the local 1D FFTs
• This encourages:• shorter, cleaner, and more modular code
• the use of tested, highly-tuned libraries

http://titanium.cs.berkeley.edu

17 Kaushik Datta, Dan Bonachea, and Katherine Yelick

GOODAre these features expressive?

http://titanium.cs.berkeley.edu• Compared line countsof timed,uncommented portionof each program• MG and FT disparities
mostly due to Ti
domain calculus andarray copy
• CG line counts are
similar since Fortranversion is alreadycompact
18 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Testing Platforms• Opteron/InfiniBand (NERSC / Jacquard):• Processor: Dual 2.2 GHz Opteron (320 nodes, 4 GB/node)• Network: Mellanox Cougar InfiniBand 4x HCA• G5/InfiniBand (Virginia Tech / System X):• Processor: Dual 2.3 GHz G5 (1100 nodes, 4 GB/node)• Network: Mellanox Cougar InfiniBand 4x HCA

http://titanium.cs.berkeley.edu

19 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Problem Classes
CG Class C
CG Class D
FT Class C
MG Class C
MG Class D

Matrix or Grid
Dimensions
150,0002
1,500,0002
5123512310243

Iterations
75100202050All problem sizes shown are relatively large
http://titanium.cs.berkeley.edu

20 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Data Collection and Reporting• Each data point was run three times, and theminimum of the three is reported• For a given number of procs, the Fortran andTitanium codes were run on the same nodes (forfairness)• All the following speedup graphs use the best
time at the lowest number of processors as thebaseline for the speedup

http://titanium.cs.berkeley.edu

21 Kaushik Datta, Dan Bonachea, and Katherine Yelick

GOOD

FT Speedup• All versions of the code
use FFTW 2.1.5 for theserial 1D FFTs
• Nonblocking array copy
allows for comp/commoverlap• Max Mflops/proc:

http://titanium.cs.berkeley.edu

ForTi(bl) Ti(nbl)

G5

238

294

350

Opt.

203

268

318

22 Kaushik Datta, Dan Bonachea, and Katherine Yelick

GOOD
http://titanium.cs.berkeley.edu

MG Speedup

23 Kaushik Datta, Dan Bonachea, and Katherine Yelick

GOOD
http://titanium.cs.berkeley.edu

CG Speedup

24 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Other Applications in Titanium• Larger Applications• Heart and cochlea simulations (E. Givelberg, K. Yelick, A.
Solar-Lezama, J. Su)• AMR Elliptic PDE solver (P. Colella, T. Wen)

• Other Benchmarks and Kernels• Scalable Poisson solver for infinite domains• Unstructured mesh kernel: EM3D
• Dense linear algebra: LU, MatMul• Tree-structured n-body code
• Finite element benchmark
http://titanium.cs.berkeley.edu

25 Kaushik Datta, Dan Bonachea, and Katherine Yelick

Conclusions• Titanium:• Captures many abstractions needed for common scientifickernels• Allows for more productivity due to fewer lines of code
• Performs comparably and sometimes better to Fortranw/MPI• Provides more general distributed data layouts andirregular parallelism patterns for real-world problems (e.g.,heart simulation, AMR)

http://titanium.cs.berkeley.edu

26 Kaushik Datta, Dan Bonachea, and Katherine Yelick