Chapter 18: Scientific Computing

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.

Simulation of Microelectromechanical Systems

SUGAR is a simulation tool for MEMS that inherits its name and philosophy from the IC simulator SPICE. SUGAR is used by researchers at the Berkeley Sensor and Actuator Center, and also at outside sites. Currently, about 500 users have filled out the registration form, and there are many unregistered users as well.

We are working to extend SUGAR in several ways:

• Applying homotopy methods to discover electrostatic pull-in, buckling of mechanical components, and other significant bifurcations
• Building fast reduced-order models that incorporate nonlinear effects
• Studying sensitivity of microsystem performance to deviations from nominal geometry and material properties
• Extending the set of models available to the user
• Building a framework for comparing results from optical measurement tools to simulation results, in order to improve the fidelity of the simulation and to better understand the behavior of different designs

We have also deployed a version of SUGAR as a web service running on the Millennium cluster. Also, the SUGAR software was used in a graduate introduction to MEMS course.

There now exists an open source SUGAR repository under the BSD software license on sourceforge.net at http://sourceforge.net/projects/mems. Other relevant information may be found through this website.

SUGAR is a collaborative effort of many graduate students and professors. Affiliated graduate students include David Bindel, Jason V. Clark, David Garmire, Babak Jamshidi, Rishi Kant, Shyam Lakshmin, Jiawang Nie. Affiliated professors include Alice Agogino, Zhaojun Bai, James Demmel, Sanjay Govindjee, Ming Gu, and Kristofer S. J. Pister.

A Computer Algebra Integration Web Server

This work is part of the continuing activity at Berkeley in computer systems for symbolic mathematics (computer algebra). This research involves the establishment and extension of TILU, our online table-look-up symbolic integration service. This table-look-up service currently includes only about 700 forms, although we have data to extend it to the majority of about 13,000 forms in current tables, including many definite integrals involving special functions.

Why bother with table look-up, when there are alleged to be algorithms for symbolic integration? There are several reasons. The best of the algorithms are for indefinite integration only; even so, they somewhat ignore special functions, and often provide a useless result: that no answer exists in closed form in terms of elementary functions. The algebraic algorithms generally ignore the domain of validity of the answer. The results of some of the more powerful techniques are, in many cases, woefully unsimplified. Our table look-up can do the task in about 6.5 milliseconds CPU time on an HP-9000/715 at http://torte.cs.berkeley.edu:8010/tilu. If we can't find it, you will know soon. By comparison, typical algorithms can be orders of magnitude slower.

TILU serves an average of 125 requests a day, and is now tied to a button on the new release of the "Graphing Calculator" shipped with every Apple Macintosh computer.

In addition to studying extensions of this system to more integrals, we are also considering applications to other domains such as symbolic solution of ordinary differential equations.

Adaptive Approximations and Exact Penalization for the Solution of Generalized Semi-Infinite Min-Max Problems

We develop an implementable algorithm for the solution of a class of generalized semi-infinite min-max problems. To this end, first we use exact penalties to convert a generalized semi-infinite min-max problem into a finite family of semi-infinite min-max-min problems. Second, the inner min-function is smoothed and the semi-infinite max part is approximated, using discretization, to obtain a three-parameter family of finite min-max problems. Under a calmness assumption, we show that when the penalty is sufficiently large the semi-infinite min-max-min problems have the same solutions as the original problem, and that when the smoothing and discretization parameters go to infinity the solutions of the finite min-max problems converge to solutions of the original problem, provided the penalty parameter is sufficiently large.

Our algorithm combines tests for adjusting the penalty, the smoothing, and the discretization parameters and makes use of a min-max algorithm as a subroutine. In effect, the min-max algorithm is applied to a sequence of gradually better-approximating min-max problems, with the penalty parameter eventually ceasing to increase, but the smoothing and discretization parameters driven to infinity. A numerical example demonstrates the viability of the algorithm.

¹Graduate Student (non-EECS)
²Outside Adviser (non-EECS)

Optimization of Cost Functions that Are Defined on the Solution of Differential Algebraic Equations

We are interested in the optimization of a cost function that is evaluated by a thermal building simulation program. Such programs solve a complex system of differential algebraic equations, and can nowadays only be optimized heuristically.

We developed a generalized pattern search method with adaptive precision function evaluations that uses coarse approximations to the cost function in the early iterations, with the approximation precision controlled by a test. Such an approach leads to substantial time savings, and the precision control guarantees that the optimization converges to a stationary point of the infinite precision cost function.

However, implementing the precision control requires knowledge of an error bound function which is hard to obtain for thermal building simulation programs. Therefore, we currently develop simulation models that allow us to obtain such an error bound function, and that reduce computation time for the optimization significantly.

In parallel to the above optimization method, we develop a smoothing method that will allow using existing simulation programs for optimization with guaranteed convergence properties.

¹Graduate Student (non-EECS), LBNL, EETD, Simulation Research Group
²Outside Adviser (non-EECS)
³Outside Adviser (non-EECS), LBNL, EETD, Simulation Research Group