Abstracts for Katherine A. Yelick

The EECS Research Summary for 2003

Automatic Performance Tuning of Sparse Matrix Kernels

The overall performance in a variety of scientific computing and information retrieval applications is dominated by a few computational kernels. One important class of such operations are sparse matrix kernels--computations with matrices having relatively few non-zero entries. Performance tuning of sparse kernels is a particularly tedious and time-consuming task because performance is a complicated function of the kernel, machine, and non-zero structure of the matrix: for every machine, a user must carefully choose a data structure and implementation (code and transformations) that minimize the matrix storage while achieving the best possible performance.

The goal of this research project is to generate implementations of particular sparse kernels tuned to a given matrix and machine. Our work builds on Sparsity [1], an early successful prototype for sparse matrix-vector multiply (y = A*x, where A is a sparse matrix and x, y, are dense vectors), in the following ways:

• Architecture-specific performance bounds: by careful analysis, we have shown that the code generated by the Sparsity system is often within 20% of the fastest possible. This places a limit on what additional low-level tuning (e.g., instruction scheduling) will do, and helps identify new opportunities for performance improvements [2]. We have applied a similar analysis to sparse triangular solve [3].
• New optimization techniques: we are currently exploring a large space of techniques to exploit a variety of matrix structures (symmetry, diagonals, bands, variable blocks, etc.) and to increase locality (reordering to create dense structure, cache blocking, multiple vectors, etc.). We will develop automatic techniques for deciding when and in what combinations to apply these methods.
• Extensions to higher-level kernels: we are exploring new sparse kernels, such as multiplying by A and A^T simultaneously, A*A^T*x (for interior point methods and the SVD), R*A*R^T (A and R are sparse; used in multigrid methods), and A^k*x, among others.
• Implementation of an automatically tuned sparse matrix library: we will make this work available as an implementation of the new Sparse BLAS standard [4], augmented by a single routine to facilitate automatic tuning.

This research is being conducted by members of the Berkeley Benchmarking and OPtimization (BeBOP) project [5].

[1]

E.-J. Im, "Optimizing the Performance of Sparse Matrix-Vector Multiplication," PhD thesis, UC Berkeley, May 2000.

[2]

R. Vuduc, J. Demmel, K. Yelick, et al., "Performance Optimizations and Bounds for Sparse-Matrix Vector Multiply," Supercomputing, November 2002.

[3]

R. Vuduc, S. Kamil, et al., "Automatic Performance Tuning and Analysis of Sparse Triangular Solve," Int. Conf. Supercomputing, Workshop on Performance Optimization of High-level Languages and Libraries, June 2002.

[4]

BLAS Technical Forum: http://www.netlib.org/ blas/blast-forum.

[5]

The BeBOP Homepage: http://www.cs.berkeley. edu/~richie/bebop.

Titanium: A High-Performance Parallel Java Dialect

Titanium is an explicitly parallel dialect of Java developed at UC Berkeley [1] to support high-performance scientific computing on large-scale multiprocessors, including massively parallel supercomputers and distributed-memory clusters with one or more processors per node. Other language goals include safety, portability, and support for building complex data structures.

The main additions [2] to Java are:

• User-defined immutable classes (often called "lightweight" or "value" classes)
• Flexible and efficient multi-dimensional arrays
• Built-in types for representing multi-dimensional points, rectangles and general domains
• Unordered loop iteration to allow aggressive optimization
• Explicitly parallel SPMD control model
• Zone-based memory management (in addition to standard Java garbage collection)
• Augmented type system for expressing or inferring locality and sharing properties of distributed data structures
• Compile-time prevention of deadlocks on barrier synchronization
• Library of useful parallel primitives (barrier, broadcast, reductions, etc.)
• Operator-overloading
• Templates (parameterized classes)

Titanium provides a global memory space abstraction (similar to other languages such as Split-C and UPC) whereby all data has a user-controllable processor affinity, but parallel processes may directly reference each other's memory to read and write values or arrange for bulk data transfers. A specific portability result is that Titanium programs can run unmodified on uniprocessors, shared memory machines, and distributed memory machines. Performance tuning may be necessary to arrange an application's data structures for distributed memory, but the functional portability allows for development on shared memory machines and uniprocessors.

Titanium is a superset of Java and inherits all the expressiveness, usability, and safety properties of that language. Titanium augments Java's safety features by providing checked synchronization that prevents certain classes of synchronization bugs. To support complex data structures, Titanium uses the object-oriented class mechanism of Java along with the global address space to allow for large shared structures. Titanium's multidimensional array facility adds support for high-performance hierarchical and adaptive grid-based computations.

Our compiler research focuses on the design of program analysis techniques and optimizing transformations for Titanium programs, and on developing a compiler and run-time system that exploit these techniques. Because Titanium is an explicitly parallel language, new analyses are needed even for standard code motion transformations. The compiler analyzes both synchronization constructs and shared variable accesses. Transformations include cache optimizations, overlapping communication, identifying references to objects on the local processor, and replacing runtime memory management overhead with static checking. Our current implementation translates Titanium programs entirely into C, where they are compiled to native binaries by a C compiler and then linked to the Titanium runtime libraries (there is no JVM).

The current implementation runs on a wide range of platforms, including uniprocessors, shared memory multiprocessors, distributed-memory clusters of uniprocessors or SMPs (CLUMPS), and a number of specific supercomputer architectures (Cray T3E, IBM SP, Origin 2000). The distributed memory back-ends can use a wide variety of high-performance network interconnects, including Active Messages, MPI, IBM LAPI, shmem, and UDP.

Titanium is especially well adapted for writing grid-based scientific parallel applications, and several such major applications have been written and continue to be further developed ([3,4], and many others).

[1]

Titanium Project home page: http://titanium.cs.berkeley.edu.

[2]

P. Hilfinger et al., Titanium Language Reference Manual, UC Berkeley Computer Science Division, Report No. UCB/CSD 01/1163, November 2001.

[3]

G. Balls and P. Colella, A Finite Difference Domain Decomposition Method Using Local Corrections for the Solution of Poisson's Equation, Lawrence Berkeley National Laboratory Report No. LBNL-45035, 2001.

[4]

G. Pike, L. Semenzato, P. Colella, and P. Hilfinger, "Parallel 3D Adaptive Mesh Refinement in Titanium," Proc. SIAM Conf. Parallel Processing for Scientific Computing, San Antonio, TX, March 1999.

GASNet--A High-Performance Portable Communication System for Global Address Space Languages

GASNet [1] is a network-independent and language-independent high-performance communication interface intended for use in implementing the runtime system for global address space languages, such as Unified Parallel C (UPC) [2] or Titanium [3]. GASNet stands for "Global-Address Space Networking."

Goals of this research include: