# Presentation: 439239

## Global Address Space Languages

**U.C. Berkeley**
**Computer Science Division**

**Kathy Yelick**
- _[http://titanium.cs.berkeley.edu/](http://titanium.cs.berkeley.edu/)_
- _[http://upc.nersc.gov](http://upc.nersc.gov/)_

## Titanium Group (Past and Present)

**Susan Graham**
**Katherine Yelick**
**Paul Hilfinger**
**Phillip Colella (LBNL)**
**Alex Aiken**
**Greg Balls**
**Andrew Begel**
**Dan Bonachea**
**Kaushik Datta**
**David Gay**
**Arvind Krishnamurthy**

**Ben Liblit**
**Peter McQuorquodale (LBNL)**
**Sabrina Merchant**
**Carleton Miyamoto**
**Chang Sun Lin**
**Geoff Pike**
**Luigi Semenzato (LBNL)**
**Jimmy Su**
**Tong Wen (LBNL)**
**Siu Man Yau**

- (and many undergrad researchers)

**Notes:**
My background in compiler analysis & optimizations and runtime systems support and networking
We've had cooperation from scientific computing experts at LBL during language design & refinement

## UPC Group

**Kathy Yelick**
**Christian Bell**
**Dan Bonachea**
**Wei Chen**
**Yannick Cote**
**Jason Duell**

**Paul Hargrove, **
**Parry Husbands**
**Costin Iancu**
**Mike Welcome**
**Yannick Cote**

## A Little History

**Most parallel programs are written using explicit parallelism, either:**
- Message passing with a SPMD model
- Usually for scientific applications with C++/Fortran
- Scales easily
- Shared memory with threads C or Java
- Usually for non-scientific applications
- Easier to program, but usually provide less scalable performance
**Global Address Space Languages take the best of both**
- global address space like threads (programming)
- SPMD parallelism like MPI (performance)
- local/global distinction, i.e., layout matters (performance)

## Unified Parallel C (UPC)

**UPC compilers**
- IDA: t3e implementation based on old gcc
- NERSC: Open64 implementation + generic runtime
- GMU (documentation) and UMD (benchmarking)
- Compaq/HP (Alpha cluster)
- MTU (based on Compaq compiler, but C+MPI)
- Cray, Sun, and HP (implementations)
- Intrepid (SGI compiler and t3e compiler)

## Titanium

**Take the best features of threads and MPI**
**Based on Java, a cleaner C++**
- classes, automatic memory management, etc.
- compiled to C and then native binary (no JVM)
**Optimizing compiler**
- static (compile-time) optimizer, not a JIT
- communication and memory optimizations
- synchronization analysis (e.g. static barrier analysis)
- cache and other uniprocessor optimizations

**Notes:**
Java is already being used for scientific computing.
Personal experience with development (research vehicle)
The Titanium project seeks to improve Java, making a better language for scientific computing  on parallel machines.

## Summary of Features Added to Java

**Scalable parallelism: **
- SPMD model of execution with global address space
**Multidimensional arrays with language-level iterators **
**Checked Synchronization **
- Statically prevent barrier deadlocks
**Immutable classes**
- user-definable non-reference types for performance
**Operator overloading**
**Templates**
**Zone-based memory management (regions)**
**Libraries**
- Useful collective communication primitives
- Distributed arrays & scientific kernels
- Fast bulk I/O
**Support a large variety of parallel architectures**
- Shared-memory, distributed-memory and hierarchical architectures

## Lecture Outline

**Language and compiler support for uniprocessor performance**
- Immutable classes
- Operator overloading
- Templates (parameterized types)
- Multidimensional Arrays
- Unordered iteration
**Language support for parallel computation**
**Applications and application-level libraries**
**Summary and future directions**

## Java: A Cleaner C++

**Java is an object-oriented language**
- classes (no standalone functions) with methods
- inheritance between classes
**Documentation on web at java.sun.com**
**Syntax similar to C++**
- public class Hello {
-    public static void main (String [] argv) {
-         System.out.println("Hello, world!");
-    }
- }
**Safe: strongly typed, auto memory management**
**Titanium is (almost) strict superset**

**Notes:**
Java 1.0

## Traditional Java 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 standard library**
- passed by pointer value (object sharing) into functions
- has level of indirection (pointer to) implicit
- simple model, but inefficient for small objects

- 2.6
- 3
- true

- r: 7.1
- i:  4.3

*(bookkeeping info)*

**Notes:**
Review of how boxed Objects work in Java
The only language feature useful for building abstractions - Used ubiquitously throughout Java applications & libraries
Bad for sequential performance – Why?
 memory overhead, gc churn, indirection performance cost, aliasing difficulties, dynamic dispatch

## Java Object Example

***Java Object Example***

**class 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 { ... }**

## Immutable Classes in Titanium

**For small objects, would sometimes prefer**
- to avoid level of indirection
- pass by value (copying of entire object)
- especially when immutable -- fields never modified
- extends the idea of primitive values to user-defined values
**Titanium introduces immutable classes**
- also known as "value classes" in the PL literature
- all fields are final (implicitly)
- cannot inherit from or be inherited by other classes
- needs to have 0-argument constructor
**Note: considering extension to allow mutation**

**Notes:**
No inheritance => no polymorphism => static dispatch
No aliasing problems – more aggressive optimizations

## Example of Immutable Classes

**The immutable complex class nearly the same**
-       **immutable**** class Complex {**
**           ****Complex () {real=0; imag=0; }**
**           ****...**
**        ****}**
**Use of immutable complex values**
**     ****Complex c1 = new Complex(7.1, 4.3);**
**    ****Complex c2 = new Complex(2.5, 9.0);**
**    ****c1 = c1.add(c2);  **
**Similar to structs in C in terms of performance****  **

- Zero-argument constructor required

- new keyword

- Rest unchanged.  No assignment to fields outside of constructors.

## Example of Operator Overloading

**Titanium allows a more intuitive definition of the sum() method using operator overloading **
- Very similar to operator overloading in C++
- (Standard Java lacks operator overloading)
**public Complex operator+(Complex c) { **
**     ****return new Complex(c.real + real, c.imag + imag);  **
**}**
**Use of operator overloading**
**     ****Complex c1 = new Complex(7.1, 4.3);**
**    ****Complex c2 = new Complex(2.5, 9.0);**
**    ****c1 = c1 + c2;****  **

**Same meaning, ****more intuitive syntax**

## Templates

**Many applications use containers:**
- E.g., arrays parameterized by dimensions, element types
- Java supports this kind of parameterization through inheritance
- Only put Object types into containers
- Inefficient when used extensively
**Titanium provides a template mechanism like C++**
- Used to build a distributed array package
- Hides the details of exchange, indirection within the data structure, etc.

## Example of Templates

**template <class Element> class Cons {**
**    ****public final Element head;**
**    ****public final Cons tail;**
**    ****public Cons( Element head, Cons tail ) {...}**
**}**
**template <class Element> class Stack {**
**    ****private template Cons< Element > data;**
**    ****public boolean empty() {...}**
**	****	**** ****public Element pop() {...}**
**    ****public void push( Element arrival ) {...}**
**}**
**template Stack<int> list = new template Stack<int>();**
**list.push( 1 );**
**int x = list.pop();**

**Strongly typed,**
**No dynamic cast**

## Arrays in Java

**Arrays in Java are objects**
**Only 1D arrays are directly supported**
**Array bounds are checked **
- Safe but potentially slow
**Multidimensional arrays                                          as arrays-of-arrays**
- General, but slow

**Subarrays are important in AMR (e.g., interior of a grid)**
- Even C and C++ don’t support these well
- Hand-coding (array libraries) can confuse optimizer

**Notes:**
Multi-D slow because of:
 indexing requires several lookups
 potential row aliasing kills optimizations – hard to analyze effectively

## Multidimensional Arrays in Titanium

**New kind of multidimensional array added**
- Subarrays are supported (unlike Java arrays)
- Indexed by Points (tuple of ints)
- Constructed over a set of Points, called Domains
- RectDomains (rectangular domains) are a special case
- Points, Domains, RectDomains are immutable classes
** ****Support for adaptive meshes and other mesh/grid operations**
- e.g., can refer to the boundary region of an array

**Notes:**
Sophisticated operations for taking subarrays (e.g. just the interior points in a grid)

## Point, RectDomain, Arrays in General

**Points specified by a tuple of ints**
**RectDomains given by 3 points: **
- lower bound, upper bound (and stride)
**Array declared by # dimensions and type**
**Array created by passing RectDomain**

## Simple Array Example

**Matrix sum in Titanium**

**Point<2> lb = [1,1];**
**Point<2> ub = [10,20];**
**RectDomain<2> r = [lb,ub];**
**double [2d] a = new double [r];**
**double [2d] b = new double [1:10,1:20];**
**double [2d] c = new double [lb:ub:****[1,1]****];**
**for (int i = 1; i <= 10; i++)**
**   ****for (int j = 1; j <= 20; j++) **
**     ****c[i,j] = a[i,j] + b[i,j];**

- No array allocation here

- Syntactic sugar

- Optional stride

## Naïve MatMul with Titanium Arrays

**public static void matMul(double [2d] a, **
**    ****double [2d] b, double [2d] c) {**
**  ****int n = c.domain().max()[1]; // 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];**
**         ****}**
**      ****}**
**   ****}**
**}**

**Notes:**
For illustration purposes – will show a better version shortly

## Array Performance Issues

**Array representation is fast, but access methods can be slow, e.g., bounds checking, strides**
**Compiler optimizes these **
- common subexpression elimination
- eliminate (or hoist) bounds checking
- sophisticated strength reduction: e.g., naïve code has 1 divide per dimension for each array access
**Currently +/- 20% of C/Fortran for large loops**
**Future: small loop and cache optimizations**

**Notes:**
Geoff working on memory tiliing optimizations

## Unordered iteration

**All of these optimizations require loop analysis **
**Compilers can do this for simple operations, e.g., matrix multiply, but hard in general**
**Titanium adds unordered iteration on rectangular domains -- gives user more control**
**     ****foreach (p within r) { ... }****  **
- p is a new Point within the foreach body
- r is a previously-declared RectDomain (often the domain of some Titanium array)

**Notes:**
Not a data parallel contruct

## Laplacian Example

**Simple example of using arrays and foreach**
** **
** ****Domain<2> interior = A.domain().shrink(1);**
** ****Point<2> dx = [1,0];**
** ****Point<2> dy = [0,1];**
** ****foreach (p in interior) {**
**   ****L[p] = 4*a[p] - a[p+dx] - a[p-dx] **
**                 ****- a[p+dy] - a[p-dy];**
** ****}**

## Better MatMul with Titanium Arrays

**public static void matMul(double [2d] a, **
**       ****double [2d] b, double [2d] c) {**
**  ****foreach (ij within c.domain()) {**
**    ****double [1d] aRowi = a.slice(1, ij[1]);**
**    ****double [1d] bColj = b.slice(2, ij[2]);**
**    ****foreach (k within aRowi.domain()) {**
**      ****c[ij] += aRowi[k] * bColj[k];**
**    ****}**
**  ****}**
**}**
**Current performance: comparable to 3 nested loops in C**

## SciMark Benchmark

**Numerical benchmark for Java, C/C++**
** ****Five kernels:**
- FFT (complex, 1D)
- Successive Over-Relaxation (SOR)
- Monte Carlo integration (MC)
- Sparse matrix multiply
- dense LU factorization
**Results are reported in Mflops**
**Download and run on your machine from:**
- _[http://math.](http://math.nist.gov/scimark2)__[nist](http://math.nist.gov/scimark2)__[.](http://math.nist.gov/scimark2)__[gov](http://math.nist.gov/scimark2)__[/scimark2](http://math.nist.gov/scimark2)_
- C and Java sources also provided

**Notes:**
100% Pure Java  / ANSI C
SOR- nearest neighbor relaxation on a mesh (2-D) w/ red-black ordering

## Java Compiled by Titanium Compiler

- Note the Ti/Java numbers use (slow) Java arrays, not Titanium arrays
- Ti -nobc is with bounds-checking disabled

## Lecture Outline

**Language and compiler support for uniprocessor performance**
**Language support for parallel computation**
- SPMD execution
- Barriers and single
- Explicit Communication
- Implicit Communication (global and local references)
- More on Single
- Synchronized methods and blocks (as in Java)
**Applications and application-level libraries**
**Summary and future directions**

## SPMD Execution Model

**Java programs can be run as Titanium, but the result will be that all processors do all the work**
**E.g., parallel hello world**
**      ****class HelloWorld {**
**          ****public static void main (String [] argv) {**
**            ****System.out.println("Hello from proc " + **
**                               ****Ti.thisProc()****);**
**            ****}**
**         ****}**
**Any non-trivial program will have communication and synchronization**

**Notes:**
Define SPMD CONTROL model

## SPMD Execution Model

**A common style is compute/communicate**
**E.g., in each timestep within particle simulation with gravitation attraction**
**      ****read all particles and compute forces on mine**
**      ****Ti.barrier();**
**      ****write to my particles using new forces**
**      ****Ti.barrier();**
**  **
**This is neither message passing nor data-parallel**

## SPMD Model

**All processor start together and execute same code, but not in lock-step**
**Basic control done using**
- Ti.numProcs() total number of processors
- Ti.thisProc() number of executing processor
**Sometimes they take different branches**
**        ****if (Ti.thisProc() == 0) { /*.. do setup ..*/ }**
**    ****System.out.println("Hello from " + Ti.thisProc());**
**    ****double [1d] a = new double [Ti.numProcs()];**

## Barriers and Single

**Common source of bugs is barriers or other global operations inside branches or loops**
-  **barrier, broadcast, reduction, exchange**
**A “single” method is one called by all procs**
-  **public single static void allStep(...)**
**A “single” variable has same value on all procs**
-  **int single timestep = 0;**
**Single annotation on methods (also called “sglobal”) is optional, but useful to understanding compiler messages.**

**Notes:**
Single methods - Called by all procs "at the same time"
Single variables – same value on all procs, changes in value happen everywhere "at the same time" 
"at the same time" basically means in a total ordering relative to other global operations

Given a few small annotations reflecting program structure, compiler enforces these constraints

## Explicit Communication: Broadcast

**Broadcast is a one-to-all communication**
**               ****broadcast <value> from <processor>**
**For example: **
**        ****int count = 0;**
**        ****int allCount = 0;**
**        ****if (Ti.thisProc() == 0) count = computeCount();**
**        ****allCount = broadcast count from 0;**
**The processor number in the broadcast must be single (trivially satisfied for constants like 0)**
**The allCount variable could be declared single.**

## Example of Data Input

**Same example, but reading from keyboard**
**Shows use of Java exceptions**
**   ****int myCount = 0;**
**   ****int single allCount = 0;**
**   ****if (Ti.thisProc() == 0) **
**     ****try {**
**        ****DataInputStream kb = new DataInputStream(System.in);**
**        ****myCount = Integer.valueOf(kb.readLine()).intValue();**
**     ****} catch (Exception e) {**
**       ****System.err.println("Illegal Input");**
**	****  ****}**
**   ****allCount = broadcast myCount from 0;**

## Explicit Communication: Exchange

**To create shared data structures**
- each processor builds its own piece
- pieces are exchanged (for objects, just exchange pointers)
**Exchange primitive in Titanium**
**    ****int [1d] single allData;**
**    ****allData = new int [0:Ti.numProcs()-1];**
**    ****allData.exchange(Ti.thisProc()*2);**
**E.g., on 4 procs, each will have copy of allData:**

## Exchange on Objects

**More interesting example:**
**  ****class Boxed {**
**     ****public Boxed (int j) {**
**       ****val = j;**
**     ****}**
**     ****public int val;**
**  ****}**
**Object [1d] single allData;**
**allData = new Object [0:Ti.numProcs()-1];**
**allData.exchange(new Boxed(Ti.thisProc());**

## Distributed Data Structures

**Building distributed arrays: **
**    ****Particle [1d] single [1d] allParticle = **
**                       ****new Particle [0:Ti.numProcs-1][1d];**
**    ****Particle [1d] myParticle = **
**                       ****new Particle [0:myParticleCount-1];**
**    ****allParticle.exchange(myParticle);**
**Now each processor has array of pointers, one to each processor’s chunk of particles**

- P0

- P1

- P2

## More on Single

**Global synchronization needs to be controlled**
- if (this processor owns some data) {
-     compute on it
-     barrier
- }
**Hence the use of “single” variables in Titanium**
**If a conditional or loop block contains a barrier, all processors must execute it**
- conditions in such loops, if statements, etc. must contain only single variables

## Single Variable Example

**Barriers and single in N-body Simulation**
**    ****class ParticleSim {**
**       ****public static void main (String [] argv) {**
**       ****int ****single**** allTimestep = 0;**
**       ****int ****single**** ****allEndTime = 100;**
**       ****for (; allTimestep < allEndTime; allTimestep++){**
**          ****// ...read all particles and compute forces on mine...**
**          ****Ti.barrier();**
**          ****// ...write to my particles using new forces...**
**          ****Ti.barrier();**
**        ****}**
**      ****}**
**    ****}     **
**Single methods inferred; see David Gay’s work **

## Use of Global / Local

**As seen, references (pointers) may be remote**
- easy to port shared-memory programs
**Global pointers are more expensive than local**
- True even when data is on the same processor
- Use local declarations in critical sections
**Costs of global:**
- space (processor number + memory address)
- dereference time (check to see if local)
**May declare references as local**

**Notes:**
Good for debugging & testing

## Global Address Space

**Processes allocate locally**
**References can be passed to other processes**

**Class C { int val;.. }**
**C gv;****	****      // global pointer**
**C local lv; // local pointer **
**if (Ti.thisProc() == 0) {**
**	****lv = new C();****	**
**}**
**gv = broadcast lv from 0;    **
**gv.val = ..; // full**
**.. = gv.val; // functionality**

- Process 0

- Other processes

**LOCAL HEAP**

**LOCAL HEAP**

**Notes:**
Each row is a memory snapshot

## Shared/Private vs Global/Local

**Titanium’s global address space is based on pointers rather than shared variables**
**There is no distinction between a private and shared heap for storing objects**
**All objects may be referenced by global pointers or by local ones**
**There is no direct support for distributed arrays**
- Irregular problems do not map easily to distributed arrays, since each processor will own a set of objects (sub-grids)
- For regular problems, Titanium uses pointer dereference instead of index calculation
- Important to have local “views” of data structures

## Local Pointer Analysis

**Compiler can infer many uses of local**
- See Liblit’s work on Local Qualification Inference
**Data structures must be well partitioned**

## Region-Based Memory Management

**PrivateRegion r = new PrivateRegion();**
**for (int j = 0; j < 10; j++) {**
**   ****int[] x = new ( r ) int[j + 1];**
**   ****work(j, x);**
**}**
**try { r.delete(); }**
**catch (RegionInUse oops) {**
**    ****System.out.println(“failed to delete”);**
**  ****}**
**}**

**Notes:**
No gc overhead – explicitly free objects
Free all objects in a single operation
David Gay's work has made this a safe operation

## Lecture Outline

**Language and compiler support for uniprocessor performance**
**Language support for parallel computation**
**Applications and application-level libraries**
- AMR overview
- AMR and uniform grid algorithms in Titanium
- Several smaller benchmarks
- MatMul, LU, FFT, Join, Sort, EM3d
- Library interfaces
- PETSc, Metis,
**Summary and future directions**

## Block-Structured AMR

**Algorithms for many rectangular, grid-based computations are**
- communication intensive
- memory intensive
**AMR makes these harder**
- more small messages
- more complex data structures
- most of the programming effort                                          is debugging the boundary cases
- locality and load balance trade-off is hard

**Notes:**
Define AMR

## Algorithms for AMR

**Existing algorithms in Titanium**
- 3D AMR Poisson solver (multi-grid)
- 3D AMR Gas dynamics
- Domain-decomposition MLC Poisson
- Immersed boundary method (3D, non-adaptive)
- Peskin and MacQueen’s method for heart model, etc.
**All joint with Colella’s group at LBNL**
**Project Ideas (contact Prof. Yelick): **
- 3-D MLC Poisson solver
- Evaluation of and proposal for general domains
- See Titanium website for a broad list of project ideas

**Notes:**
Define AMR – one driving application for Titanium
MultiGrid – coarsen grid (for performance), solve coarse (often replicated), solve more refined meshes in parallel
Projects must include careful performance analysis, but need not be scientific programs

## 3D AMR Poisson

**Poisson Solver [Semenzato, Pike, Colella]**
- finite domain
- variable                                                                                        coefficients
- multigrid                                                                                        across levels
**Performance of Titanium implementation**
- Sequential multigrid performance +/- 20% of Fortran
- On fixed, well-balanced problem of 8 patches, each 723
- parallel speedups of 5.5 on 8 processors

**Notes:**
Mesh refinement levels – finer meshes for more interesting areas
Solve multigrid across each level

## 3D AMR Gas Dynamics

**Hyperbolic Solver [McCorquodale and Colella]**
- Implementation of Berger-Colella algorithm
- Mesh generation algorithm included
**2D Example (3D supported) **
- Mach-10 shock on solid surface                                                            at oblique angle
**Future: Self-gravitating gas dynamics package**

**Notes:**
Bottom of picture is the wall
Shockwave entering at 45 deg like / and reflecting back from wall
Color is areal density

## MLC for Finite-Differences

**Poisson solver with infinite domains [Colella, Balls]**
- Uses a Method of Local Corrections (MLC)
- Currently non-adaptive, 2D and only constant coefficients
**Uses 2-level, domain decomposition approach**
- Fine-grid solutions are computed in parallel (no communication)
- Information transferred to a coarse-grid and solved serially (replicated)
- Fine-grid solutions is computed using boundary conditions from the coarse grid (accuracy still very good – 2nd order)
**Future work & project idea**
- extend to 3D and Adaptive mesh

## Error on High-Wavenumber Problem

**Charge is**
- 1 charge of concentric waves
- 2 star-shaped charges.
**Largest error is where the charge is changing rapidly. Note:**
- discretization error
- faint decomposition error
**Run on 16 procs **

**Notes:**
This was solved on sixteen processors.
Zero is around light orange.
The charge distribution for this problem is a combination of several high-wavenumber charges: one large radially symmetric charge of concentric waves and two star-shaped charges.
The error is largest where the charge is changing rapidly, as we would expect.  It is possible to detect faint lines where the pieces are joined together, but the important point is that those errors induced by the domain decomposition are very small compared to the other errors.

## Scalable Poisson Solver (MLC)

**Communication performance is good (< 5%)**
**Scaled speedup experiments are nearly ideal (flat)**
**           ****IBM SP at SDSC                      Cray T3E at NERSC**

**Notes:**
Explain scaled speedup – scale problem size with num procs
Problem (work) itself doesn't always scale exactly linearly

## Titanium in non-grid applications
M.O.O.S.E.
Bio information-processing 
Select optimal nucleotide sequences from the genome of an organism for use in manufacturing DNA microarrays
Parallel properties differ from AMR
High degree of parallelism
Low communication requirements
Unpredictable workload – 
	uses dynamic load balancing
I/O intensive
CS267 Final Project: F2000!

**M.O.O.S.E.**
**Bio information-processing **
- Select optimal nucleotide sequences from the genome of an organism for use in manufacturing DNA microarrays
- Parallel properties differ from AMR
- High degree of parallelism
- Low communication requirements
- Unpredictable workload –
- 	uses dynamic load balancing
- I/O intensive
**CS267 Final Project: F2000!**

***OligoNucleotide Selection Engine***

## Human Heart Simulation

- Immersed Boundary Method  [Peskin/MacQueen, Yau]
- Fibers (e.g., heart muscles) modeled by list of fiber points
- Fluid space modeled by a regular lattice
- Irregular fiber lists need to interact with regular fluid lattice
- Trade-off between load balancing of fibers and minimizing communication
- memory and communication intensive
- Uses several parallel numerical kernels
- Navier-Stokes solver
- 3-D FFT solver
- Soon to be enhanced using an adaptive multigrid solver (possibly written in KeLP)

***Human Heart Simulation***

**Notes:**
Current model can be used to design heart valves
Ultimately: real-time clinical work

## Load Balance vs. Locality

***Load Balance vs. Locality***

**Tried various assignments of fiber points**

**Optimizing for load balance generally better**
- Application (fiber structure) dependent
- Somewhat constrained by spectral solver
- Multigrid should give more options

## Load Balancing vs. Locality

## Heart Simulation

- Source: www.psc.org

## An Irregular Problem: EM3D

**Maxwells Equations on an Unstructured 3D Mesh: Explicit Method**

**Irregular Bipartite Graph of varying degree**
**(about 20) with weighted edges**

**Basic operation is to subtract weighted sum of**
**neighboring values**
**  ****for all E nodes**
**  ****for all H nodes**

- H

- E

- B

- D

**w1**

**w2**

**v1**

**v2**

## EM3D: Unstructured Mesh Kernel

**Relaxation on a 3D unstructured mesh**
- Propagation of electromagnetic waves through objects in 3-D
- Overlapping grids representing electric & magnetic fields with weighed edges between nodes
**Speedup on Ultrasparc SMP**
**Simple kernel: mesh not partitioned**

## Calling Other Languages

**We have built interfaces to **
- PETSc : scientific library for finite element applications
- Metis: graph partitioning library
- KeLP: starting work on this
**Two issues with cross-language calls**
- accessing Titanium data structures (arrays) from C
- possible because Titanium arrays have same format on inside
- having a common message layer
- Titanium is built on lightweight communication
**PETSc was 267 Final Project (with benchmark)!**

## Lecture Outline

**Language and compiler support for uniprocessor performance**
**Language support for parallel computation**
**Applications and application-level libraries**
**Summary**
- Performance tuning notes
- Implementation
- Project ideas

## Titanium Summary

**Performance**
- close to C/FORTRAN + MPI on limited class of problems
**Portability**
- develop on uniprocessor, then SMP, then MPP/Cluster
**Safety**
- as safe as Java, extended to parallel framework
**Expressiveness**
- easier than MPI, harder than threads
**Compatibility, interoperability, etc.**
- no gratuitous departures from Java standard
- Important caveat: based on Java 1.0

## Performance Tuning Notes

**Arrays**
- Multi-dimensional Ti arrays are stored contiguously (+)
- Rich set of operations (transpose, slice, stride) (-)
- Only “foreach” loops are optimized, not “for” loops
- Turn off bounds checking (-nobcheck) when tuning
**Communication**
- Beware of repeated remote reads: no caching
- Array copy or immutable copy is “shallow”

## Implementation

**Strategy**
- Titanium into C
- Solaris or Posix threads for SMPs
- Lightweight communication for MPPs/Clusters
- Active messages, LAPI, shmem, MPI, UDP, others...
**Status: Titanium runs on **
- Solaris or Linux SMPs, clusters, CLUMPS
- Berkeley NOW & Berkeley Millennium clusters
- Cray T3E (NERSC and NPACI)
- IBM SP2/SP Power3
- SGI Origin 2000

## Using Titanium

**On machines in the CS Division**
**/project/cs/titanium/srs/titanium/*/bin/tcbuild file.ti**
- Solaris 2.6 and Linux supported; need to mount this filesystem
**On NERSC SP (seaborg) **
**For documentation, source code, see the home page**
- http://www.cs.berkeley.edu/projects/titanium
- Web page includes a list of research project ideas!!
**Documentation includes**
- Language reference, terse but complete
- Tutorial, incomplete
**For problems or questions:**
**titanium-group@cs.berkeley.edu**

## CS267 Project Ideas

**Titanium **
- Small application in Titanium with performance analysis
- FEM method, FMM method done last year
- Possibilities: Sparse Cholesky factorization, NAS PB, AMR, N-Body extension, Data mining
- Extension of the immersed boundary method code
- “Plates” as part of cochlea model done last year
- Platelet coagulation, small animal swimming, others?
**UPC**
- Benchmarking/applications
- NERSC compiler is very new, so smaller problems should be used
- Contact _[upc@lbl.gov](mailto:upc@lbl.gov)_ if you’re interested
**Sparsity**